0.4s, 256MB
Pak Dengklek memiliki sebuah kebun yang panjangnya tak hingga. Kebun Pak Dengklek dapat direpresentasikan dalam garis sumbu x pada koordinat Kartesian. Pak Dengklek memiliki N ekor bebek pada kebun tersebut. Bebek ke-i terletak pada koordinat xi pada sumbu x, dengan xi adalah bilangan bulat. Dijamin tidak ada dua bebek pada posisi yang sama.
Sepasang bebek dapat berkomunikasi jika dan hanya jika tidak ada bebek lain yang berada di antara dua bebek tersebut. Karena N bebek semuanya berada pada satu garis, tentu saja ada N - 1 pasang bebek yang dapat berkomunikasi. Jarak dari sebuah komunikasi adalah jarak dua bebek yang sedang melakukan komunikasi tersebut.
Sebagai contoh, jika pada awalnya ada 4 bebek yang berada pada posisi {1, 2, 5, 6}, maka jarak komunikasi bebek 1 dan 2 adalah 1, jarak komunikasi bebek 2 dan 3 adalah 3, dan jarak komunikasi bebek 3 dan 4 adalah 1.
Pada suatu saat mungkin saja terdapat jarak komunikasi yang berbeda-beda. Pak Dengklek merasa komunikasi bebek berjalan tidak lancar jika terdapat lebih dari satu nilai jarak komunikasi. Untuk itu, Pak Dengklek mungkin harus mengganti konfigurasi kebunnya. Bebek-bebek Pak Dengklek sudah terlalu nyaman dengan posisinya, sehingga mereka tidak mau dipindah posisinya. Sehingga, yang bisa dilakukan oleh Pak Dengklek adalah menambahkan bebek baru ke kebun atau mengambil bebek lama keluar dari kebun.
Pak Dengklek akan mengambil X bebek dan meletakkan Y bebek, sehingga pada akhirnya terdapat (N - X + Y) bebek, dan posisi bebek-bebek tersebut harus berbeda-beda dan bebek ke-i terletak pada xi’ dimana xi’ adalah bilangan bulat, dan semua jarak komunikasi untuk (N - X + Y - 1) pasangan bebek bernilai sama. Tentukan nilai X + Y minimal yang dapat dilakukan oleh Pak Dengklek.
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 berisi sebuah bilangan bulat N yang menunjukkan banyaknya bebek mula-mula.
Baris ketiga berisi N bilangan bulat yang dipisahkan spasi. Bilangan ke-i menunjukkan nilai dari xi.
Format Keluaran
Sebuah bilangan bulat yang menunjukkan nilai X + Y minimal agar konfigurasi kebun Pak Dengklek memenuhi ketentuan di atas.
Contoh Masukan
0..3456
5
2 4 6 10 18
Contoh Keluaran
2
Subsoal
Pada semua subsoal, berlaku:
- -2.500 ? xi ? 2.500
Subsoal 1 (6 poin)
- N = 6
- Kasus uji dapat diunduh di sini.
Subsoal 2 (14 poin)
- N = 9
- Kasus uji dapat diunduh di sini.
Subsoal 3 (19 poin)
- 1 ? N ? 15
Subsoal 4 (21 poin)
- 1 ? N ? 50
Subsoal 5 (13 poin)
- 1 ? N ? 300
Subsoal 6 (27 poin)
- 1 ? N ? 2.000
