Uzbekistan Open Championship Selection Contest, Sunday, April 6, 2020 Page of 11

 

Problem G. Game 

Input file:   

standard input 

 

Output file:  

standard output 

 

Time limit:   

2 seconds

 

Memory limit: 

512 mebibytes

 

Yura  va  Roma  stol  oʻyinlarni  yaxshi  koʻrishadi.  Yaqinda  HAL  kompaniyasi  “Atomlar”  nomli 

yangi stol oʻyinini ishlab chiqdi. Oʻyinda maʼlum atomlar soni (10

100

 atrofida) berilgan. Oʻyin 

boshida tomonlarida 1 dan 2 * 10

9

 gacha barcha naturlar sonlarni oʻz ichiga olgan koʻpburchakni 

oʻrtaga tashlash kerak. Koʻpburchakda N soni tushgandan soʻng oʻyin maydonini initsializatsiya 

qilish kerak: atomlar N toʻplamini yaratish kerak, i-toʻplamda i-atomlar teng boʻlishi kerak. 

Oʻyin vaqtida Yura va Roma navbat bilan yurishadi. Bir yurishda boʻsh boʻlmagan har qanday 

toʻplamdan atomlarning har qanday sonini olish va ularni ularni oʻyindan chiqarib tashlash 

mumkin. Kim navbatdagi yurishni amalga oshira olmasa magʻlubiyatga uchraydi. 

Yura  “Atomlar”  oʻyini  boʻyicha  qiziqarli  faktlarni  oʻylab  topishni  yaxshi  koʻradi.  Bugun  u 

“Qancha turli birinchi yurishlarni amalga oshirish mumkin?” degan savolga qiziqmoqda. Ushbu 

savolga  Roma  juda  tez  javob  bera  oldi.  Ammo  shu  zahotiyoq  boshqa  savol  paydo  boʻldi: 

“Raqibning optimal oʻyinida baribir yutish mumkin boʻlish uchun qancha birinchi yurishlar qilish 

kerak?”. 

Ikkinchi savol bolalardan qiyinchilik tugʻdirdi, ular oʻyinni tashlab, qayta yozishga kirishdi.