Mini-proyek Bagian 2: Flowchart Soal OSN

Proyek ini memakai seluruh Bagian 2: abstraksi, flowchart, pseudocode, penelusuran, dan perhitungan jumlah langkah. Kodenya pendek — yang dinilai adalah rencana yang dibuat sebelum kode ditulis.

Soalnya

Gedung dan matahari terbit. Di sepanjang jalan berdiri n gedung berjajar dari barat ke timur. Gedung ke-i tingginya t[i]. Matahari terbit di timur. Sebuah gedung bisa melihat matahari terbit kalau tidak ada gedung di sebelah timurnya yang tingginya lebih dari atau sama dengan tingginya.

Masukan. Baris pertama berisi n. Baris kedua berisi n bilangan bulat t[1..n], dari gedung paling barat ke paling timur.

Keluaran. Satu baris berisi banyaknya gedung yang bisa melihat matahari terbit.

Batasan. 1 ≤ n ≤ 1.000.000, dan 1 ≤ t[i] ≤ 10⁹.

Contoh masukan:

6
3 7 8 3 6 1

Contoh keluaran:

3

Yang bisa melihat: gedung ke-3 (tinggi 8), ke-5 (tinggi 6), dan ke-6 (tinggi 1). Gedung ke-1 dan ke-2 terhalang gedung setinggi 8; gedung ke-4 terhalang gedung setinggi 6.

Yang harus dikerjakan

Empat hal, berurutan. Jangan melompat ke nomor 4.

  1. Abstraksi. Tulis ulang soal dalam satu kalimat "diberikan ... cetak ...", tanpa gedung dan tanpa matahari.
  2. Flowchart. Gambar di kertas algoritmamu. Harus ada satu oval mulai, satu oval selesai, minimal satu belah ketupat, dan satu panah balik.
  3. Pseudocode. Tulis algoritma yang sama dalam bentuk tulisan, memakai kata kunci Bab 09. Lalu telusuri dengan tangan memakai contoh di atas dan buat tabel penelusurannya.
  4. Kode. Baru sesudah itu, tulis programnya di starter.cpp.

Sebelum menulis kode, jawab dulu di komentar bagian atas berkas:

  • Berapa jumlah langkah algoritmamu dalam notasi O?
  • Untuk n = 1.000.000, apakah itu masuk dalam satu detik?

Petunjuk

  • Pikirkan dari arah timur. Gedung paling timur selalu bisa melihat.
  • Telusuri dari belakang sambil menyimpan satu nilai saja: tinggi tertinggi yang pernah dilihat sejauh ini.
  • Penyelesaian yang memeriksa, untuk setiap gedung, semua gedung di sebelah timurnya adalah O(n²) — 10¹² langkah untuk batasan soal ini. Tabel di Bab 10 mengatakan itu tidak akan selesai.
  • n bisa sampai sejuta: pakai array global, dan "\n" bukan endl.

Kasus tepi yang wajib diuji

Masukan Jawaban yang benar
1 / 5 1
4 / 5 5 5 5 1
4 / 1 2 3 4 1
4 / 4 3 2 1 4

Baris terakhir menjelaskan kenapa soal memakai kata "lebih dari atau sama dengan": gedung yang tingginya sama tetap menghalangi.

File

Compile dan jalankan:

g++ -std=c++17 -O2 -o gedung projects/02-flowchart/starter.cpp
./gedung < projects/02-flowchart/contoh-masukan.txt

Sudah selesai?

Kalau keempat kasus tepi di tabel benar, flowchart dan pseudocode-mu sudah digambar, dan kamu bisa menjelaskan kenapa algoritmamu O(n) — proyek ini selesai.

Lanjut ke Bab 11 — Brute force, tempat rencana mulai berubah menjadi strategi penyelesaian yang punya nama.