A. Berbagi Candil

Deskripsi

Pak Dengklek memiliki N ekor bebek. Pagi hari ini, Pak Dengklek telah membeli M butir candil untuk dibagikan ke bebek-bebeknya. Perhatikan bahwa nilai M ini bisa saja 0 yang artinya Pak Dengklek sebenarnya tidak membeli candil.

Pak Dengklek ingin membagikan candil-candil tersebut sebanyak mungkin kepada bebek-bebeknya selama setiap bebeknya mendapatkan banyak butir candil yang sama rata. Setelah membagikan candil-candil tersebut, sisa candil akan dimakan oleh Pak Dengklek.

Tugas Anda adalah menentukan banyaknya candil yang akhirnya dimakan oleh Pak Dengklek.

Soal A1

Jika Pak Dengklek membeli 100 butir candil untuk dibagikan ke 7 ekor bebeknya, berapakah banyaknya candil yang akhirnya dimakan oleh Pak Dengklek?

Tuliskan jawaban dalam bentuk ANGKA.

Soal A2

Asumsikan Pak Dengklek memiliki 10 ekor bebek. Dari 5 skenario berikut, manakah yang menyebabkan Pak Dengklek akhirnya memakan butir candil paling banyak?

• a. Pak Dengklek membeli 8 butir candil
• b. Pak Dengklek membeli 12 butir candil
• c. Pak Dengklek membeli 27 butir candil
• d. Pak Dengklek membeli 64 butir candil
• e. Pak Dengklek membeli 101 butir candil

Soal A3

BENAR atau SALAH: Banyak candil yang akhirnya dimakan oleh Pak Dengklek selalu lebih kecil dari N.

Tuliskan jawaban dalam bentuk BENAR/SALAH dengan huruf kapital.

Soal Pemrograman

Tulislah sebuah program dengan bahasa C/C++ sesuai deskripsi cerita dengan format dan batasan sebagai berikut. Perhatikan bahwa untuk setiap kasus uji berlaku batas waktu selama 2 detik dan batas memori sebanyak 256 MB.

Masukan

Masukan diberikan dalam format berikut:

N M

Keluaran

Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya candil yang akhirnya dimakan oleh Pak Dengklek.

Contoh Masukan dan Keluaran

8 21

5

1 999

0

15 0

0

Penjelasan Contoh

Pada contoh pertama, Pak Dengklek paling banyak dapat membagikan 16 butir candil kepada 8 bebeknya sehingga setiap bebek akan mendapatkan 2 butir candil. Sisa candil yang akhirnya dimakan oleh Pak Dengklek adalah 5.

Pada contoh kedua, karena Pak Dengklek hanya memiliki 1 ekor bebek, maka ia dapat memberikan seluruh candilnya kepada bebek tersebut.

Pada contoh ketiga, Pak Dengklek tidak membeli candil sehingga ia maupun bebek-bebeknya tidak makan candil.

Subsoal 1 (Mudah)

Hanya berisi satu buah kasus uji, yakni:

123 4567890

Subsoal 2 (Sulit)

• 1 ≤ N ≤ 10¹²
• 0 ≤ M ≤ 10¹²

Peringatan

Untuk dapat menjawab pertanyaan ini dengan benar, Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!

B. Menghitung Subsekuens OSN

Deskripsi

Diberikan sebuah string S dengan panjang N yang hanya terdiri dari huruf-huruf 'O', 'S', dan 'N'; Anda diminta untuk menghitung berapa banyak kemunculan subsekuens "OSN" dari string tersebut.

Secara persisnya, Anda diminta untuk menghitung banyaknya cara memilih huruf 'O', 'S', dan 'N' dari string yang diberikan sehingga huruf 'O' yang dipilih berada sebelum huruf 'S' yang dipilih, dan huruf 'S' yang dipilih berada sebelum huruf 'N' yang dipilih.

Soal B1

Manakah dari 5 pilihan string berikut yang memiliki kemunculan subsekuens "OSN" paling banyak?

• a. "OSNOSN"
• b. "OSSNNN"
• c. "OSSSSSN"
• d. "ONNNSOOON"
• e. "NONONONONON"

Soal B2

Dari seluruh kemungkinan string dengan panjang 9, tuliskan string yang memiliki kemunculan subsekuens "OSN" paling banyak! Jika terdapat lebih dari satu kemungkinan jawaban, pilih yang paling kecil secara leksikografis.

Tuliskan jawaban dalam bentuk STRING dengan huruf kapital.

Soal B3

Pada string "SONOSONOSONOSONOSONOSONOSONO" (yakni penggabungan 7 kali string "SONO"), berapa kalikah subsekuens "OSN" muncul?

Tuliskan jawaban dalam bentuk ANGKA.

Soal Pemrograman

Tulislah sebuah program dengan bahasa C/C++ sesuai deskripsi cerita dengan format dan batasan sebagai berikut. Perhatikan bahwa untuk setiap kasus uji berlaku batas waktu selama 2 detik dan batas memori sebanyak 256 MB.

Masukan

Masukan diberikan dalam format berikut:

N
S

Keluaran

Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya kemunculan subsekuens "OSN" dari string S.

Contoh Masukan dan Keluaran

8
SONOSONO

2

Penjelasan Contoh

Ada 2 kemunculan subsekuens "OSN" pada string "SONOSONO", yakni dengan memilih huruf ke-2, 5, dan 7; serta dengan memilih huruf ke-4, 5, dan 7.

Batasan

Untuk seluruh kasus uji, berlaku:

• |S| = N
• S hanya terdiri dari huruf-huruf 'O', 'S', dan 'N'.

Subsoal 1 (Mudah)

• 1 ≤ N ≤ 200

Subsoal 2 (Sulit)

• 1 ≤ N ≤ 200.000

Peringatan

Untuk dapat menjawab pertanyaan ini dengan benar, Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!