Bantu temanmu belajar dengan menambahkan soal di Kujawab. Klik disini..

Olimpiade Sains Nasional (OSN) 2014 - Komputer , Nomor 7

7

0.5s, 64MB

Perang dunia ketiga sudah pecah! Kedamaian di Negara Bebek pun terancam. Pak Dengklek yang sangat cinta Negara Bebek pun membuat sebuah senjata canggih yang menggunakan teknologi laser dan diyakini mampu menghancurkan musuh sekuat apapun.

Senjata canggih Pak Dengklek memiliki sebuah layar dan 3 tombol:

Layar: Untuk menampilkan kekuatan laser saat ini (harus selalu berupa bilangan asli).
Tombol "Tembak": Untuk menembakkan laser ke musuh.
Tombol "Kali 2": Membuat laser menjadi 2 kali lebih kuat dari sebelumnya.
Tombol "Bagi 2": Membuat kekuatan laser menjadi setengah dari sebelumnya. Jika kekuatan laser sebelum dilakukan operasi ini berupa bilangan ganjil, maka tidak terjadi apa-apa.
Nilai awal kekuatan laser hanya dapat diatur sekali sebelum pasukan musuh datang, karena untuk mengganti kekuatan laser membutuhkan waktu yang sangat lama (kecuali menggunakan tombol "Kali 2" dan tombol "Bagi 2"). Perhatikan bahwa nilai awal kekuatan laser ini harus lebih dari 0.

Senjata laser buatan Pak Dengklek ini tentunya menggunakan daya yang sangat besar. Pak Dengklek berkata bahwa untuk setiap satuan kekuatan laser yang ditembakkan menggunakan 1 unit energi. Tentunya kekuatan setiap pasukan musuh berbeda-beda, sehingga kekuatan laser yang diperlukan untuk menghancurkan mereka pun bisa jadi berbeda-beda. Untungnya, BINB (Badan Intelijen Negara Bebek) sudah mengetahui kekuatan musuh yang akan menyerang Negara Bebek dan sudah menghitung kekuatan laser yang diperlukan untuk menghancurkan masing-masing musuh.

Diberikan kekuatan laser minimum yang dibutuhkan untuk menghancurkan pasukan-pasukan negara musuh, berapa minimal unit energi yang harus terbuang untuk menghancurkan seluruh pasukan musuh? Anda harus menentukan nilai awal kekuatan laser, yang boleh ditentukan secara bebas.

Unit energi yang terbuang untuk menghancurkan satu pasukan musuh didefinisikan sebagai selisih dari unit energi minimal untuk menghancurkan pasukan tersebut dan unit energi yang digunakan Negara Bebek untuk menghancurkan pasukan tersebut. Sedangkan unit energi yang terbuang untuk menghancurkan seluruh musuh adalah jumlah dari unit energi yang terbuang untuk setiap pasukan musuh.

Format Masukan

Pada awalnya, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, atau berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua pada berkas masukan berisi sebuah bilangan bulat N yang menyatakan banyaknya pasukan musuh yang akan menyerang Negara Bebek.

Baris ketiga berisi N buah bilangan bulat non-negatif Xi yang menyatakan kekuatan laser minimum untuk menghancurkan pasukan ke-i.

Format Keluaran

Sebuah baris berisi sebuah bilangan bulat yang menyatakan unit energi yang terbuang minimal yang diperlukan untuk menghancurkan semua pasukan musuh.

Contoh Masukan 1

0..3456
2
7 31
Contoh Keluaran 1

2
 

Contoh Masukan 2

0..3456
3
4 8 2
Contoh Keluaran 2

0

Subsoal

Subsoal 1 (11 poin)

  • N = 10
  • Xi = i
  • Kasus uji dapat diunduh di sini.

Subsoal 2 (7 poin)

  • N = 12
  • 0 ? Xi ? 10
  • Kasus uji dapat diunduh di sini.

Subsoal 3 (23 poin)

  • 1 ? N ? 100
  • 0 ? Xi ? 100

Subsoal 4 (12 poin)

  • 1 ? N ? 3.000
  • 0 ? Xi ? 3.000

Subsoal 5 (31 poin)

  • 1 ? N ? 100.000
  • 0 ? Xi ? 100.000

Subsoal 6 (16 poin)

  • 1 ? N ? 1.000.000
  • 0 ? Xi ? 1.000.000