Pembahasan Solusi — CP LA01 Session 1

Berikut penjelasan pendekatan penyelesaian untuk kelima soal.

---

A. Watermelon (4A)

Ide: Pete dan Billy butuh membagi w kilo menjadi dua bagian yang sama-sama genap dan sama-sama positif. Kuncinya: kalau w sendiri genap dan lebih besar dari 2, kita selalu bisa membaginya jadi 2 dan (w-2). Dua-duanya pasti genap karena genap dikurangi genap tetap genap.

Kalau w ganjil, tidak mungkin dua bilangan genap dijumlahkan menghasilkan bilangan ganjil (genap + genap = genap selalu), jadi otomatis NO.

Kalau w = 2, satu-satunya bilangan genap yang jika dibagi 2, keduanya ganjil, yaitu 1 dan 1, jadi tetap NO. Ini kasus khusus yang gampang terlewat kalau cuma cek w % 2 == 0 saja.

Kondisi akhir: w > 2 && w % 2 == 0

Kompleksitas: O(1). Tidak ada loop sama sekali, murni pengecekan matematis.

Source code:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int w;
    cin>>w;

    if(w>2 && w%2==0)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}

---

B. Team (231A)

Ide: Soal ini murni complete search / brute force sederhana. Untuk setiap soal kontes, kita sudah tahu persis siapa yang yakin bisa mengerjakannya (ditandai 0/1 untuk Petya, Vasya, Tonya). Tidak ada yang perlu "dicari" atau dioptimasi, cukup baca ketiga angka, jumlahkan, dan cek apakah totalnya ≥ 2.

Karena n ≤ 1000, pendekatan paling langsung (loop sekali, O(n)) sudah lebih dari cukup, tidak perlu struktur data atau algoritma tambahan apapun.

Langkah:

1. Baca 3 angka per baris.
2. Jumlahkan ketiganya.
3. Kalau jumlahnya ≥ 2, tambah counter.
4. Cetak counter di akhir.

Kompleksitas: O(n)

Source code:

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int count = 0;
	for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;

		int total = a+b+c;
		if(total>=2){
			count++;
		}
	}

	cout << count << endl;
	return 0;
}

---

C. Next Round (158A)

Ide: Soal ini tentang sorting concept, tapi karena input sudah dijamin terurut menurun (non-increasing), kita tidak perlu sorting manual lagi. Yang perlu dipahami adalah cara memanfaatkan keterurutan itu.

Nilai (threshold) adalah skor peserta di posisi ke-k, yaitu a[k-1] (ingat: index array dimulai dari 0, jadi posisi ke-k ada di index k-1).

Peserta lolos ke ronde berikutnya kalau skornya lebih besar atau sama dengan threshold, DAN skornya harus tetap positif (skor 0 tidak boleh lolos meskipun kebetulan threshold-nya juga 0 — ini yang diuji lewat contoh kedua di soal, di mana semua skor 0).

Langkah:

1. Cari threshold = a[k-1].
2. Loop seluruh array, hitung berapa banyak elemen yang >= threshold sekaligus > 0.

Kompleksitas: O(n). n maksimal cuma 50, jadi soal ini sebenarnya sangat longgar dari sisi performa; fokus utamanya di ketelitian logika (kondisi "positif" yang mudah terlewat).

Source code:

#include<bits/stdc++.h>
using namespace std;

int a[55];

int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);

	int threshold = a[k-1];

	int ans=0;
	for(int i=0;i<n;i++){
		if(a[i]>=threshold && a[i]>0){
			ans++;
		}
	}

	printf("%d\n",ans);
	return 0;
}

---

D. Wrong Subtraction (977A)

Ide: Soal ini adalah simulasi langsung dari algoritma yang dideskripsikan di soal:

• Kalau digit terakhir bukan 0 → kurangi 1.
• Kalau digit terakhir 0 → hapus digit terakhir (bagi 10).

Karena k dijamin kecil (maksimal 50), simulasi langsung ini aman dari sisi waktu, tidak perlu dicari rumus tertutup atau shortcut apapun.

Poin teknis penting: n bisa sampai 10⁹, masih muat di int sebenarnya, tapi pakai long long untuk n lebih aman kalau nanti variasi soalnya constraint-nya dinaikkan.

Langkah:

1. Loop sebanyak k kali.
2. Cek digit terakhir pakai n % 10.
3. Terapkan aturan yang sesuai.

Kompleksitas: O(k)

Source code:

#include <iostream>
using namespace std;

int main(){
    long long n;
    int k;
    cin >> n >> k;

    for(int i=0;i<k;i++){
        if(n%10==0){
            n = n/10;
        } else {
            n = n-1;
        }
    }

    cout << n << endl;
    return 0;
}

---

E. Taxi (158B)

Ide: Ini soal greedy yang paling menantang di antara kelimanya. Kuncinya adalah mengelompokkan grup-grup schoolchildren (ukuran 1-4 orang) ke dalam taksi berkapasitas 4, seminimal mungkin jumlah taksinya.

Strategi greedy yang optimal:

1. Grup ukuran 4 | pasti butuh satu taksi sendiri (sudah penuh persis). Tidak ada pertimbangan lain.
2. Grup ukuran 3 | setiap grup 3 orang pasti butuh satu taksi, dan sisa 1 kursi di taksi itu paling optimal diisi oleh satu grup ukuran 1 (kalau ada), karena grup ukuran 2 tidak akan muat di sisa 1 kursi.
3. Grup ukuran 2 | pasangkan dua grup ukuran 2 dalam satu taksi (2+2=4, pas). Kalau jumlah grup ukuran 2 ganjil, satu grup sisa butuh taksi sendiri, dan sisa 2 kursi di taksi itu bisa diisi maksimal 2 grup ukuran 1.
4. Sisa grup ukuran 1 yang belum terpasangkan di atas, digabungkan 4 per taksi (dibulatkan ke atas).

Kenapa strategi ini greedy yang valid? Karena setiap keputusan (pasangkan 3 dengan 1, pasangkan 2 dengan 2) selalu menghasilkan pemakaian kursi taksi paling efisien pada saat itu, dan tidak ada cara mengubah keputusan itu nanti yang menghasilkan hasil lebih baik — ini persis konsep greedy choice property yang sudah dibahas di materi paradigma penyelesaian masalah.

Langkah:

1. Hitung cnt[1..4] — jumlah grup di tiap ukuran.
2. taxis = cnt[4] + cnt[3]
3. Sisa grup ukuran 1 setelah dipasangkan ke grup ukuran 3: rem1 = max(0, cnt[1] - cnt[3])
4. taxis += cnt[2] / 2; kalau ganjil, taxis++ dan kurangi rem1 sampai 2 (kalau ada).
5. taxis += ceil(rem1 / 4), dihitung tanpa fungsi ceil() lewat trik (rem1+3)/4.

Kompleksitas: O(n) untuk membaca input, sisanya O(1) — perhitungan greedy-nya sendiri konstan.

Source code:

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;

	int cnt[5]={0,0,0,0,0};
	for(int i=0;i<n;i++){
		int s;
		cin>>s;
		cnt[s]++;
	}

	int taxis = cnt[4] + cnt[3];

	int rem1 = cnt[1] - cnt[3];
	if(rem1<0) rem1=0;

	taxis += cnt[2]/2;
	if(cnt[2]%2==1){
		taxis++;
		rem1 -= 2;
		if(rem1<0) rem1=0;
	}

	taxis += (rem1+3)/4;

	cout<<taxis<<endl;
	return 0;
}