Тавил:
Online-Judge системд оролтын өгөгдлүүд тэст бүр дээр ижилхэн 1 байхад, гаралтын өгөгдлүүдийг тэст бүр дээр ялгаатай буюу 1-ээс N (тэстүүдийн тоо, N < 9) хүртэлх тоонууд байхаар хэвлэ.
Бодолтын санаа:
Шууд тэст дуудах болгонд random-ээр 1-ээс N хүртэлх тоог үүсгээд хэвлэнэ гэвэл 1/2^N хэмжээний магадлалтай болно. Энэ бол боломжгүй шахуу зүйл юм. Иймээс өөр арга олох хэрэгтэй.
Тэст дуудагдах болгонд буюу програм ажиллах болгон өөрчлөгддөг хэдэн зүйл бий. Тэдгээрийн нэг нь цаг хугацаа буюу unixtime. Үүнийг ашиглан бодож болно.
Online-Judge системд i-р тэстийг давсан тохиолдолд i+1 дэхь тэстийг програмд уншуулдаг. Мөн i-р тэстийг шалгаад дууссан бол бараг л шууд i+1 дэхь тэстийг уншуулж эхэлдэг. За энэ хооронд үүсэх хугацааны алдагдлыг хамгийн ихээр бодоход 0.5 секунд гэж үзье. (coder.mn дээр 0.2 секунд байл уу даа?)
1-р тэстийг unixtime-н секундээр T1=X*10+1 дэхь секундэд ажиллуулна гэж үзье. Тэгвэл програм маань гаралтын утгыг (T1 % 10) гэж хэвлэчихээд хугацааг T2=X*10+2 секунд болтол өөр дээрээ delay ажиллуулна. T2=X*10+2 секунд өнгөрөнгүүт програм зогсож, online judge маань дараагийн тэстийг програм руу оруулна. Энэ удаад T2 хугацаа маань хамгийн ихээр бодоход (T2 + 0.5) болж өөрчлөгдөнө. Програм энэ удаад (T2 % 10) гэсэн утгыг хэвлэчихээд дахиад хугацааг T3=X*10+3 секунд болтол delay ажиллуулна. Гэхмэтчилэн хэвлэсээр байгаад бүх тэстийг дуусгана.
Энэ маягаар бодоход шууд нэг удаа бодлогыг илгээгээд ажиллуулах магадлал бага юм. Таны илгээсэн соорс online-judge системд хөрвүүлэгдээд яг ажиллах үед, системийн цаг хугацаа unixtime-н секундээр 10-д хуваахад 1 үлдэгдэл өгж болж байвал бүрэн зөв ажиллаж чадна гэсэн үг.
Тэгэхээр онолын хувьд бол 10 удаа бодолтоо илгээхэд нэг удаад нь бүрэн дүүрэн бодолт хийх магадлалтай ба, хэрвээ та овсгоотой бол шууд нэгхэн илгээгээд удаа unixtime-аар яг 10*X+1 дэхь секундэд програмаа бүрэн зөв ажиллуулах боломжтой юм :)
