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

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

2

1s, 32MB

Pak Dengklek mengunjungi kawasan wisata Candi Borobudur. Kawasan ini menarik karena banyak terdapat stupa yang indah. Sang penjaga berkata bahwa ada keajaiban di balik bilangan bulat yang terjadi pada kawasan tersebut. Untuk setiap bilangan bulat positif X, terdapat tepat 0 atau X buah stupa setinggi X meter.

Pak Dengklek, yang tidak sempat berkeliling ke seluruh kawasan, hanya sempat melihat N stupa. Tinggi dari stupa ke-i yang dilihatnya adalah Ai meter. Pak Dengklek pun penasaran mengenai banyaknya stupa di kawasan tersebut.

Tentukan banyaknya stupa minimum di kawasan wisata tersebut!

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, dan 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 berisi sebuah bilangan bulat N. Baris berikutnya berisi N buah bilangan bulat A1, A2, ..., AN.

Format Keluaran

Sebuah baris berisi banyaknya stupa minimum. Apabila masukan tidak sesuai dengan perkataan sang penjaga (mungkin saja Pak Dengklek salah lihat!), keluarkan sebuah baris berisi -1.

Contoh Masukan 1

0..34567
5
2 1 4 2 3
Contoh Keluaran 1

10


Contoh Masukan 2

0..34567
4
2 9 2 2
Contoh Keluaran 2

-1

 

Subsoal

Subsoal 1 (7 poin)

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

Subsoal 2 (11 poin)

  • N = 8
  • 1 ? Ai ? 10
  • Kasus uji dapat diunduh di sini.

Subsoal 3 (7 poin)

  • N = 1
  • 1 ? A1 ? 1.000

Subsoal 4 (11 poin)

  • 1 ? N ? 1.000
  • 1 ? A1 = A= ... = A? 1.000

Subsoal 5 (17 poin)

  • 1 ? N ? 1.000
  • 1 ? Ai ? 1.000

Subsoal 6 (20 poin)

  • 1 ? N ? 100.000
  • 1 ? Ai ? 100.000

Subsoal 7 (27 poin)

  • 1 ? N ? 100.000
  • 1 ? Ai ? 1.000.000.000