08. Apa itu berpikir komputasional — Pembahasan PR

Soal 1 sampai 3 dikerjakan di kertas. Berkas .cpp untuk soal 4 dan tantangan ada di exercises/08/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Untuk soal kertas, tulis dulu jawabanmu, baru bandingkan — membaca jawaban orang lain terasa jelas padahal belum tentu bisa diulang sendiri. Bagian Uji berisi masukan dan keluaran yang sudah diperiksa untuk soal berkode.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/08/homework/solutions/04-penumpang.cpp
./jawab

Soal 1 — Abstraksi

Soal. Tulis ulang tiga soal cerita dalam satu kalimat "diberikan ... cetak ...".

Cara berpikir. Buang nama tokoh, benda, dan satuan. Sisakan: apa yang diberikan (bentuk datanya) dan apa yang diminta (bentuk jawabannya).

Jawaban.

a. Diberikan n bilangan, cetak jumlah seluruhnya dikurangi nilai terbesarnya.

b. Diberikan n pasang bilangan naik[i] dan turun[i], cetak nilai terbesar yang pernah dicapai oleh jumlah berjalan (naik − turun) setelah setiap pasangan diproses.

c. Diberikan n, cetak banyaknya bilangan 1 sampai n yang jumlah pembaginya ganjil.

Bentuk (c) sengaja masih setengah jalan: "sakelar ditekan sekali untuk setiap pembagi" adalah hasil abstraksi pertama. Abstraksi kedua — bahwa jumlah pembagi ganjil hanya terjadi pada bilangan kuadrat — dikerjakan di tantangan.

Kesalahan umum.

• Menyimpan ceritanya ("ayam", "halte") di dalam kalimat baru. Kalau kata benda masih ada, abstraksinya belum selesai.
• Menjawab dengan kode. Pada tahap ini jawabannya masih berupa kalimat.

Soal 2 — Dekomposisi

Soal. Pecah soal bus menjadi langkah-langkah.

Cara berpikir. Setiap langkah harus cukup kecil untuk ditulis dalam beberapa baris kode, dan cukup jelas untuk diuji sendiri.

Jawaban.

1. Baca n.
2. Siapkan dua penampung: di_dalam (penumpang sekarang) dan terbanyak (rekor tertinggi), keduanya bernilai 0.
3. Ulangi n kali: baca sepasang naik dan turun.
4. Di setiap halte: kurangi di_dalam dengan turun, lalu tambah dengan naik — urutannya sesuai soal.
5. Bandingkan di_dalam dengan terbanyak; kalau lebih besar, perbarui rekornya.
6. Setelah semua halte, cetak terbanyak.

Perhatikan langkah 4 dan 5 adalah dua pola yang sudah dikenal: akumulasi dan juara bertahan.

Kesalahan umum.

• Menyimpan seluruh data ke array lebih dulu. Boleh, tetapi tidak perlu: jawabannya bisa dihitung sambil membaca.
• Memeriksa rekor sebelum memperbarui di_dalam, sehingga halte terakhir tidak pernah terhitung.

Soal 3 — Pengenalan pola

Jawaban.

a. "berapa banyak ... habis dibagi 7" → perulangan + penghitung, dengan syarat % 7 == 0.

b. "dua bilangan yang hasil kalinya terbesar" → perulangan bersarang untuk semua pasangan. Kalau n besar, sort dulu lalu bandingkan hasil kali dua terbesar dengan hasil kali dua terkecil (dua bilangan negatif besar bisa menang).

c. "berapa banyak angka 7 pada digit 1 sampai n" → perulangan 1..n yang di dalamnya memproses digit dengan % 10 dan / 10.

d. "lomba terbanyak tanpa jadwal bertabrakan" → sort + greedy. Ini soal penjadwalan kegiatan yang dibahas di Bab 12.

Kesalahan umum.

• Pada (b), langsung menjawab "ambil dua bilangan terbesar". Untuk data yang boleh negatif, jawaban itu salah.

Soal 4 — Penumpang bus

Soal. Cetak jumlah penumpang terbanyak yang pernah ada di dalam bus.

Cara berpikir. Ikuti hasil dekomposisi soal 2. Tidak ada array yang dibutuhkan: dua variabel sudah cukup, karena rekor bisa diperbarui sambil membaca.

Pembahasan.

int di_dalam = 0, terbanyak = 0;

for (int i = 0; i < n; i++) {
    int naik, turun;
    cin >> naik >> turun;

    di_dalam -= turun;
    di_dalam += naik;
    if (di_dalam > terbanyak) terbanyak = di_dalam;
}

cout << terbanyak << "\n";

Periksa dengan contoh: 5 0 → 5, 3 2 → 6, 1 4 → 3. Rekornya 6.

Uji.

Setiap baris masukan berisi naik lalu turun untuk satu halte. Baris ketiga adalah pemeriksaan terpenting: jumlah terbanyak (6) terjadi di tengah perjalanan, bukan di halte terakhir. Program yang hanya mencetak isi bus di akhir akan menjawab 0.

Kesalahan umum.

• Menaikkan dulu baru menurunkan, sehingga rekornya terlalu besar.
• Mencetak di_dalam di akhir, bukan terbanyak.

Tantangan — Lampu

Soal. Cacah lampu yang menyala, lalu cari polanya.

Cara berpikir. Versi langsungnya sederhana: untuk setiap i, balik keadaan semua kelipatannya. Jumlah pekerjaannya n/1 + n/2 + n/3 + ... ≈ n ln n, jadi untuk n = 1.000.000 masih selesai cepat.

Pembahasan.

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        nyala[j] = !nyala[j];

int banyak = 0;
for (int i = 1; i <= n; i++) if (nyala[i]) banyak++;
cout << banyak << "\n";

Hasilnya:

Polanya: jawabannya bagian bulat dari √n.

Kenapa begitu. Lampu bernomor x ditekan sekali untuk setiap pembagi x. Pembagi selalu berpasangan: kalau a membagi x, maka x / a juga. Jadi jumlah pembaginya genap — kecuali ketika a = x / a, yaitu ketika x bilangan kuadrat. Hanya lampu bernomor kuadrat yang ditekan sebanyak bilangan ganjil dan berakhir menyala. Banyaknya bilangan kuadrat dari 1 sampai n adalah ⌊√n⌋.

Setelah pola itu ditemukan, seluruh program menjadi satu baris:

cout << (int)sqrt((double)n) << "\n";

Inilah bentuk paling murni dari bab ini: pengamatan pola menggantikan perhitungan. Di OSN, selisih antara jawaban n log n dan jawaban O(1) sering berupa satu kalimat pengamatan seperti ini.

Uji.

Kolom terakhir itulah polanya. Sesudah pola ditemukan, seluruh program bisa diganti satu baris — dan bedanya besar: cara langsung memerlukan sekitar n log n penekanan sakelar, sedangkan menghitung akar memerlukan satu operasi.

Kesalahan umum.

• Memakai sqrt tanpa berhati-hati pada bilangan besar. Untuk n sangat besar, (int)sqrt(...) bisa meleset satu; periksa dengan while ((long long)(akar + 1) * (akar + 1) <= n) akar++;.
• Menyimpulkan pola hanya dari satu nilai n. Tiga titik data minimal, dan polanya tetap harus dibuktikan dengan alasan.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/08/osn/solutions/.

Soal 1 — Panen Mangga

Abstraksinya. Diberikan N bilangan dan sebuah ambang K, jalankan penampung berjalan yang bertambah setiap langkah dan dikosongkan setiap kali mencapai K; cetak berapa kali dikosongkan dan berapa sisanya.

Kebun, pasar, dan rasa malas Pak Dengklek tidak ikut masuk ke kode.

Cara berpikir. Yang perlu diingat hanya isi gudang saat ini dan pencacah penjualan. Seluruh Aᵢ tidak perlu disimpan: masing-masing dipakai sekali lalu tidak diperlukan lagi. Kesadaran ini mengubah soal dari "array 200.000 elemen" menjadi "dua variabel".

Periksa tipenya: tepat sebelum dikosongkan, isi gudang paling besar K − 1 + Aᵢ, yang bisa mendekati 2 × 10⁹ — melewati int.

Pembahasan.

long long simpanan = 0;
int penjualan = 0;

for (int i = 0; i < n; i++) {
    long long a;
    cin >> a;
    simpanan += a;
    if (simpanan >= k) {
        penjualan++;
        simpanan = 0;
    }
}

cout << penjualan << " " << simpanan << "\n";

Uji.

Kasus kedua penting: jawabannya bukan 0 0. Sisa yang tidak pernah terjual tetap harus dicetak.

Kesalahan umum.

• Memakai > alih-alih >=. Kalimat soal berbunyi "mencapai K buah atau lebih".
• Lupa mengosongkan gudang setelah penjualan.
• Memakai int untuk simpanan.

Soal 2 — Rekor Baru

Abstraksinya. Diberikan barisan N bilangan, cetak berapa banyak bilangan yang lebih kecil daripada semua bilangan sebelumnya.

Cara berpikir. Membandingkan setiap pelari dengan semua pelari sebelumnya memerlukan N² = 4 × 10¹⁰ perbandingan. Tetapi "lebih cepat daripada semua pelari sebelumnya" sama artinya dengan "lebih cepat daripada yang tercepat sejauh ini" — dan yang tercepat itu cukup disimpan dalam satu variabel. Soalnya selesai dalam satu kali baca.

Pelari pertama ditangani sebagai kasus khusus, karena belum ada pembanding.

Kata lebih cepat harus dibaca teliti: waktu yang sama dengan rekor tidak dihitung, jadi pembandingnya <, bukan <=.

Pembahasan.

long long terbaik = 0;
int rekor = 0;

for (int i = 0; i < n; i++) {
    long long t;
    cin >> t;
    if (i == 0 || t < terbaik) {
        rekor++;
        terbaik = t;
    }
}

cout << rekor << "\n";

Uji.

Kesalahan umum.

• Memakai <=, sehingga waktu yang sama ikut dihitung dan kasus ketiga menjawab 4.
• Mengisi terbaik dengan 0 lalu langsung membandingkan, sehingga pelari pertama tidak pernah dihitung.
• Menyimpan seluruh waktu ke array lalu membandingkan berpasangan.

Soal 3 — Permen Berputar

Abstraksinya. Diberikan N dan M, cetak ((M − 1) mod N) + 1 dan ⌊(M − 1) / N⌋ + 1.

Cara berpikir. Simulasi adalah jawaban yang benar dan sekaligus tidak mungkin: M bisa 10¹⁸, sedangkan sedetik hanya cukup untuk sekitar 10⁸ langkah. Batasan sebesar itu selalu berarti jawabannya berupa rumus.

Polanya terlihat dengan menomori permennya. Permen ke-1 untuk anak 1, permen ke-2 untuk anak 2, permen ke-N untuk anak N, permen ke-(N + 1) kembali ke anak 1. Jadi permen ke-m jatuh ke anak dengan nomor "sisa m dibagi N" — dengan satu penyesuaian: sisa 0 berarti anak ke-N, bukan anak ke-0.

Penyesuaian itu ditulis rapi sebagai (m - 1) % n + 1: menggeser penomoran ke 0 sampai N − 1 lebih dulu, menghitung sisanya, lalu mengembalikan ke 1 sampai N.

Anak nomor 1 menerima permen ke-1, ke-(N + 1), ke-(2N + 1), dan seterusnya. Banyaknya adalah ⌊(M − 1) / N⌋ + 1 — pergeseran yang sama.

Pembahasan.

long long n, m;
cin >> n >> m;

long long terakhir = (m - 1) % n + 1;
long long bagianPertama = (m - 1) / n + 1;

cout << terakhir << " " << bagianPertama << "\n";

Uji.

Baris ketiga adalah kasus tepi N = 1: semua permen jatuh ke anak yang sama. Baris keempat memastikan pembagian besar tetap benar.

Kesalahan umum.

• Menulis m % n tanpa penyesuaian, sehingga kelipatan N menjawab 0 — nomor anak yang tidak ada.
• Menghitung bagian anak pertama sebagai m / n, yang salah setiap kali ada sisa.
• Menulis simulasi for (long long i = 0; i < m; i++). Benar secara logika, tetapi tidak akan pernah selesai.

Kalau masih tersendat

• Soal cerita terasa rumit → Bab 08, bagian Abstraksi dan tabel cerita → inti.
• Tahu jawabannya tetapi tidak tahu mulai dari mana → Bab 08, bagian Dekomposisi.
• Tidak yakin rencanamu cukup cepat → Bab 08, contoh lengkap dari soal ke rencana, lalu Bab 10.

Kebiasaan yang perlu dibangun mulai sekarang: sebelum menulis kode, jawab dulu kelima pertanyaan pada Daftar periksa sebelum menulis kode di Bab 08.