Fişierul intrare/ieşire:aiacujoc.in, aiacujoc.outSursăGrigore Moisil 2017, 11-12
AutorMircea Popoveniuc, Razvan SalajanAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aiacujoc

În drumul lor către oraşul Zalău, Bulănel şi Bulăniţa au hotărât să joace un joc pentru a alunga plictiseala.

Cei doi au la dispoziţie un grid cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). Bulănel începe jocul prin plasarea unui pătrat pe o celulă a gridului. Scopul jocului este acoperirea gridului înaintea celuilalt jucător. La fiecare pas, un jucător alege o direcţie (nord, est, sud, vest) si extinde figura rectangulară în direcţia respectivă cu maxim K linii (dacă direcţia aleasă a fost nord sau sud) sau maxim K coloane (dacă direcţia aleasă a fost est sau vest). La nici un moment al jocului, nu se poate extinde figura în afara gridului. Jucătorul care nu mai poate extinde figura în nicio direcţie este declarat pierzător. După ce Bulănel plasează pătratul iniţial, Bulăniţa e cea care face prima extindere.

De exemplu, dacă ar juca pe un grid de N = 3 linii şi M = 5 coloane şi ar alege K = 3, jocul s-ar putea desfăşura în felul următor:

Pasul 1: Bulănel plasează pătratul pe linia 2, coloana 5Pasul 2: Bulăniţa extinde figura cu 2 coloane în vest.Pasul 3: Bulănel extinde figura cu 1 linie în nord.
Pasul 4: Bulăniţa extinde figura cu 1 linie în sud.Pasul 5: Bulănel extinde figura cu 1 coloană în vest.Pasul 6: Bulăniţa extinde figura cu 1 coloană în vest.

Bulănel pierde jocul acesta din cauză că nu mai poate extinde figura în nici o direcţie. Totuşi, Bulănel ar fi putut câştiga jocul dacă ar fi făcut o serie diferită de mişcări (de exemplu, dacă ar fi extins figura cu 2 coloane în vest în loc de 1, în pasul 5) sau dacă ar fi plasat pătratul iniţial pe o altă poziţie.

Cerinţă

Cei doi hotărăsc să joace mai multe jocuri. Ajutaţi-l pe Bulănel să afle, pentru fiecare joc, numărul de poziţii în care poate plasa pătratul iniţial astfel încât să aibă strategie de câştig, adică să poată câştiga indiferent de mutările Bulăniţei.

Date de intrare

Fişierul de intrare aiacujoc.in conţine pe prima linie numărul natural T, reprezentând numărul de jocuri pe care Bulănel şi Bulăniţa o să-l joace. Pe fiecare din următoarele T linii, se află câte trei numerele naturale care definesc un joc: numărul natural N, reprezentând numărul de linii ale gridului, urmat de numărul natural M, reprezentând numărul de coloane ale gridului, urmat de numărul natural K, reprezentând numărul maxim de linii sau de coloane cu care un jucător poate extinde figura la un anumit pas.

Date de ieşire

Fişierul de ieşire aiacujoc.out va conţine T linii. Pe fiecare linie i, se va afla câte un număr natural care reprezintă numărul de poziţii de pe grid unde Bulănel poate plasa pătratul iniţial, care îi asigură lui Bulănel strategie câştigătoare pentru al i-lea joc.

Restricţii

  • Pentru toate testele, 1 ≤ T ≤ 10.
  • Pentru teste în valoare de 5 puncte, N = 1, 1 ≤ M ≤ 20, K ≥ max(N, M).
  • Pentru alte teste în valoare de 5 puncte, 1 ≤ N, M ≤ 20, K ≥ max(N, M), N şi M au parităţi diferite.
  • Pentru alte teste în valoare de 10 puncte, 1 ≤ N, M ≤ 20, K ≥ max(N, M).
  • Pentru alte teste în valoare de 30 de puncte, 1 ≤ N, M ≤ 1 000, K ≥ max(N, M).
  • Pentru alte teste în valoare de 10 de puncte, 1 ≤ N, M ≤ 1 000 000, K ≥ max(N, M).
  • Pentru alte teste în valoare de 20 de puncte, 1 ≤ N, M, K ≤ 1 000 000.
  • Pentru alte teste în valoare de 10 de puncte, 1 ≤ N, M ≤ 1 000 000 000, 1 ≤ K ≤ 1 000 000.
  • Ambii jucători joacă optim ceea ce înseamnă că nu fac greşeli, anticipează mişcările adversarului, iar dacă există o strategie de mişcări care să-i conducă spre câştig atunci o vor folosi.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.

Exemplu

aiacujoc.inaiacujoc.out
2
3 5 5
88 200 200
5
320
2
3 5 3
88 200 56
7
680

Explicaţie

Primul exemplu

Pentru primul joc, gridul are dimensiunile N=3, M=5. Un jucător poate extinde figura cu maxim K=5 linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt (1;2), (1;4), (2;3), (3;2), (3;4).
Pentru al doilea joc, gridul are dimensiunile N=88, M=200. Un jucător poate extinde figura cu maxim 200 de linii sau coloane. Sunt 320 de poziţii care conduc la câştig.

Al doilea exemplu

Pentru primul joc, gridul are dimensiunile N=3, M=5. Un jucător poate extinde figura cu maxim K=3 linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt (1;2), (1;4), (2;1), (2;3), (2;5), (3;2), (3;4).
Pentru al doilea joc, gridul are dimensiunile N=88, M=200. Un jucător poate extinde figura cu maxim 56 de linii sau coloane. Sunt 680 de poziţii care conduc la câştig.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?