English

Indonesian

Pada suatu hari di kutub utara, ada suatu pabrik besar yang memproduksi mainan-mainan yang keren. Santa Claus, pemilik dari pabrik tersebut ingin mengirimkan mainan-mainan ini sebagai hadiah kepada banyak anak-anak yang menginginkan hadiah di hari natal menggunakan rusa terbang, karena setiap tahunnya jumlah mainan yang diproduksi meningkat dan rusa tgerbangnya semakin tua, ia ingin barang bawaannya seringan mungkin.

Berungtung pada natal kali ini (Desember 2014) ia berhasil menciptakan teknologi yang dapat menyimpan mainan dengan jumlah tanpa batas, ia menamakan ciptaannya itu "Kotak Ajaib", jadi setiap mainan dalam kotak ajaib tidak akan memiliki berat, sungguh hebat! Ia menciptakan kotak ajaib pada tanggal 23 Desember 2014, ada sisa 2 hari lagi menjelang natal, jadi ia ingin mempercepat proses pemasukan barangnya.

Ada banyak mainan yang harus dimasukkan dalam waktu singkat dan kotak ajaib tidak dapat menghisap banyak mainan dalam waktu singkat, jadi ia memutuskan untuk memasukkan mainan ke dalam beberapa kotak ajaib secara bersamaan. Misalkan jika mainan diberi nomor dari 1 hingga n, maka salah satu kemungkinannya adalah kotak ajaib pertama diisi mainan ke_2 hingga mainan ke_5, ... , kotak ajaib terakhir diisi mainan ke_n-7 hingga mainan ke_n-1. Perhatikan bahwa ada kemungkinan kotak ajaibnya Santa tidak dapat menghisap semua mainan di pabriknya dengan tepat waktu meskipun ia menggunakan beberapa kotak ajaib secara bersamaan, jadi beberapa mainan mungkin tertinggal di pabrik untuk natal berikutnya.

Karena kotak ajaib masih dalam "versi percobaan", kemampuan kotak ajaibnya belum sempurna dan masih terdapat beberapa kekurangan dalam fungsinya, salah satu kekurangan yang paling parah adalah kotaknya hanya bisa menghisap mainan yang berurutan saja, misalnya jika mainan nomor 3 dan nomor 5 dimasukkan kedalam kotak ajaib yang sama, mainan nomor 4 mau tidak mau pasti juga akan terhisap ke dalam kotak itu. Karena masalahnya menjadi terlalu rumit, maka Santa ingin beristirahat dan meninggalkan pabriknya sejenak untuk memberi makan dan memberitahu rusa terbangnya kabar gembira bahwa ia berhasil menciptakan kotak ajaib sahingga rusa terbangnya tidak perlu mengangkut beban yang berat lagi seperti tahun lalu. Ia juga merencanakan bagaimana urutan pemasukkan mainan ke dalam kotak ajaib. Karena Santa ingin segalanya sempurna, maka ia ingin agar setiap kotak ajaib jika digunakan berisi setidaknya d mainan.

Sekarang ia penasaran ada berapa banyak cara ia dapat memasukkan mainan ke dalam kotak ajaibnya jika jumlah kotak ajaib sama dengan jumlah mainan di pabriknya. Tidak selalu semua kotak ajaibnya digunakan, ia hanya ingin menggunakan setidaknya satu kotak ajaib. Dapatkah anda membatunya menghitung berapa banyak cara ia dapat melakukannya?

Format Masukan

Pada baris pernama, terdapat satu bilangan bulat c yang melambangkan jenis berkas masukan. Untuk lebih jelasnya tentang jenis berkas, lihat bagian "Batasan".

Setiap baris berikutnya hingga EOF (end of line = akhir dari berkas masukan), terdapat 3 bilangan butat d, n, dan m

• d = Jumlah minimal mainan yang ingin dimasukkan Santa ke dalam setiap kotak ajaib.
• n = Jumlah mainan yang tersedia di pabriknya Santa.
• m = Modulo, kerena banyaknya cara bisa sangat-sangat besar, Santa pasti mengerti, ia hanya ingin banyaknya cara dimodulo m.

Format Keluaran

Untuk setiap jawaban yang didapatkan, keluarkan dua bilangan bulat d dan banyaknya cara dimodulo m dalam satu baris dipisahkan oleh satu spasi.

Batasan

2014 kasus uji.

1 ≤ c ≤ 3

1 ≤ d ≤ 2014 (d akan selalu unik di setiap berkas masukan, tidak ada dua kasus uji dengan d yang sama)

1 ≤ m ≤ 109

Jenis1: 0 ≤ n < 2×d; Nilai = 1 usntuk setiap jawaban yang benar.

Jenis2: 0 ≤ n ≤ maks(d2,2×d); Nilai = 10 untuk setiap jawaban yang benar.

Jenis3: 0 ≤ n < 264; Nilai = 100 untuk setiap jawaban yang benar.

Penilaian

Nilai akhir anda adalah jumlah nilai dari berkas jenis1 sampai jenis3.

Jika anda mencetak semua jawaban benar pada berkas masukan jenis 3,

anda akan mendapatkan nilai tambahan sebesar:

jika x=(25.0-[waktu eksekusi pada berkas 3])*8056.0

maka nilai bonusnya adalah bilangan bulat terbesar yang ≤ x

Contoh 1

Masukan:

1

1 1 1000

2 3 1000

3 5 1000

4 7 1000

Keluaran:

1 1

2 3

3 6

4 10

Nilai:

Karena ini adalah berkas masukan jenis 1, jadi setiap jawaban benar bernilai 1 poin

Untuk contoh ini nilai=4*1=4.

Contoh 2

Masukan:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Keluaran:

1 4

4 16

2 7

Nilai:

Perhatikan bahwa anda dapat mencetak jawaban dengan urutan bebas,

Karena ada 3 jawaban benar dan ini adalah masukan jenis 2 (setiap kasus uji bernilai 10 poin),

untuk contoh ini nilai=3*10=30.

Contoh 3

Masukan:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Keluaran:

1 4

3 10

4 16

2 7

Nilai:

Untuk contoh ini anda akan mendapatkan WA="Wrong Answer".

Ini terjadi karena untuk d=3 dan n=6 dan m=1000 jawaban yang bernar adalah 11,

tetapi yang dicetak adalah 10.

Lebih baik tidak mencetak "3 10" seperti di contoh 2 daripada mencetaknya tetapi salah.

Untuk kasus ini nilai = Tidak ada.

Contoh 4

Masukan:

3

1 11 1000

2 11 1000

Keluaran:

Nilai:

Karena tidak mencetak apa-apa maka nilai=0.

Hati-hati, anda akan mendapatkan WA jika jumlah nilai dari masukan jenis 1 sampai jenis 3=0.

Contoh 5

Masukan:

3

1 12345678987654321 1000

2 11 1000

Keluaran:

2 23

Nilai:

Karena ini adalah berkas masukan jenis 3, jadi setiap jawaban benar bernilai 100 poin

Untuk contoh ini nilai=1*100=100.

Contoh 6

Masukan:

3

1 3 5

2 4 6

Keluaran:

1 2

2 1

1 2

Nilai:

Semua jawabannya benar, tetapi karena d harus unik,

maka untuk contoh ini anda akan mendapatkan WA.

Nilai untuk kasus ini = Tidak ada

Contoh 7

Masukan:

3

1 3 1000000000

2 4 1000000000

Keluaran:

1 12

2 7

Nilai:

200

Penjelasan untuk "Contoh 7"

Ini semua 12 cara untuk memasukkan 3 mainan ke dalam satu atau lebih kotak ajaib dan setiap kotak ajaib setidaknya berisi 1 mainan.

Ini semua 7 cara untuk memasukkan 4 mainan ke dalam satu atau lebih kotak ajaib dan setiap kotak ajaib setidaknya berisi 2 mainan.

Informasi Tambahan

Semua masukan (n and m) dibangkitkan dengan distribusi acak merata dalam interval batasan.

Nilai saya saat publikasi dari soal ini adalah 66554, apakah anda bisa mengalahkan nilai ini(?)

Kabar baru: [2014-12-24 13:42:56] Selamat kepada Min_25, orang pertama yang menyalip nilai saya di soal ini.

Jika ada pengguna yang mendapatkan nilai sempurna (223554) saya tidak akan meningkatkan batasan atau mengubah berkas masukan, saya akan mengganti sistem penilaian (memperhitungkan waktu eksekusi program ke dalam penilaian), namun... apakah itu akan terjadi?

Kabar baru: Itu terjadi! [2015-01-02 22:38:52] Selamat kepada Min_25!

---

Lihat juga: Soal-soal pemrograman lainnya yang ditambahkan oleh Tjandra Satria Gunawan

---

hide comments

< Previous 1 2 Next >
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:42:05 Wow! Thats great news. Scoring system has been updated. If you get perfect score on test type3 you'll get bonus score: floor{(25.0-[your time on test 3])*8056.0}. If you wonder why 8056, the constant 8056 came from (2014=year this problem published) × (100=score each case on input type3) / (25=time limit). No bonus score if you get perfect score on test type1 and type2. New scoring system is designed so I just need to rejudge last submission. All old issue (minor bug) has been fixed. I'll update problem description shortly.
	Min_25: 2015-01-02 23:40:47 @Francky Thank you ! It was quite hard !
	Francky: 2015-01-02 23:15:04 Big congrats to Min_25 !!!!!!!
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @Flago: Yes, I agree, by looking your code, I see how hard your work to beat Mitch for now :p btw, Min_25's points is about 80% of perfect score. There's high probability that someday it become perfect so I should start thinking about new scoring formula. @Anubhav Balodhi: Thank you ^^ Btw, I notice two minor bug in my master_judge 1) If you get "TLE" with zero sum of points, it will be judged as "Wrong Answer". 2) If your code judged as "Time Limit Exceeded" the judge not print details on each test data because there are some typo/unwanted '\n' in my master_judge code. Of course it just "minor" bug and not fatal. I'll fix this when I change scoring system (If Min_25 or someone has perfect score).
	Flago: 2015-01-02 23:15:04 Trying to get some points to beat Mitch is depressive when you see Min_25 having 100*more points ! (Min_25 too strong ! Should get malus !! :D)
	Anubhav Balodhi : 2015-01-26 19:59:28 I must say, very nice problem and good explanation ^_^
	Flago: 2015-01-02 23:15:04 Good one, no quite sure tho where i'm missing something... Type 2, d is 2 10³ as max, so n is 4 10⁶... I should be able to n² without having problems with php max int... edit : nvm m=10⁹ and n=10⁶ overflows... those 10¹⁸ are so bad for php users... Last edit: 2014-12-31 15:54:24
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @californiagurl: I'll explain the image, the blue color on specific cell means the toy is absorbed to magical box, and white color means it left in the factory, if all the color is blue then all toys is absorbed into magical box, |12|3| (all blue) and |1|23| (all blue) in the image is different, |12|3| means toy 1 and toy 2 are absorbed into same magical box while toy 3 is absorbed into other magical box, and |1|23| means toy 2 and 3 is absorbed into same magical box while toy 1 is absorbed into other magical box. If you read problem description carefully, I think it will become clear (I've wrote problem description to be as clear as possible).
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @Min_25: Congratulations! Your code is very amazing, you even optimize your code in low level :-O and also many attack on math side and computation side, many thumbs up for you ;-)
	californiagurl: 2015-01-02 23:15:04 i dont understand the explanation for example 7.