1765 - Cutie

Cerința

După ce au vizitat toate obiectivele turistice din municipiul Iaşi, Ioana şi Maria au inventat un joc.

Ele au la dispoziţie un număr de n cutii aranjate în linie dreaptă, numerotate în ordine de la 1 la n, şi un număr de m bile ce pot fi aşezate în unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel că bilele dispar dacă sunt puse în acele cutii.

O mutare constă în alegerea unei bile şi poziţionarea ei în una din cutiile învecinate (precedenta sau următoarea ). Bilele pot fi mutate după următoarea regulă: când o bilă a fost mutată pentru prima dată într-o anumită direcţie, atunci bila îşi păstrează direcţia de deplasare la următoarele mutări (de exemplu, dacă o bilă a fost mutată pentru prima dată spre stânga atunci orice mutări ulterioare ale acestei bile se pot face doar spre stânga).

Jocul se termină atunci când nici un jucător nu mai poate face nici o mutare. Pierde primul jucător care nu mai poate face nici o mutare. Fetele joacă un număr de T astfel de jocuri. Ştiind că Ioana este prima care face o mutare, iar apoi fetele mută alternativ, se cere să se stabilească pentru fiecare din cele T jocuri dacă ea are sau nu o strategie sigură de câştig.

Date de intrare

Fişierul cutiein.txt conţine pe prima linie un număr natural T, care reprezintă numărul de jocuri pe care le joacă cele două fete.

Pe următoarele linii fişierul conţine, în ordine, descrierea celor T jocuri. Fiecare joc este descris prin câte 3 linii:

• prima linie va conţine, în ordine, trei numere naturale n, k, m separate prin câte un singur spaţiu (n reprezintă numărul de cutii, k reprezintă numărul de cutii deteriorate şi m reprezintă numărul de bile)
• a doua linie va conţine k numere naturale, separate prin câte un singur spaţiu, reprezentând numerele de ordine ale cutiilor deteriorate
• a treia linie va conţine m numere naturale reprezentând numerele de ordine ale cutiilor care conţin bile la începutul jocului.

Date de ieșire

Fişierul cutieout.txt va conţine pe prima linie un şir de T valori de 0 şi 1 neseparate prin spaţii, având următoarea semnificaţie: valoarea de pe poziţia i din şir (i={1,2,…,T}) este 1 daca jocul i este câştigat de Ioana sau 0 dacă jocul i este pierdut de Ioana.

Restricții și precizări

• 1 ⩽ T ⩽ 10
• 1 ⩽ n ,m ⩽ 10000
• 0 ⩽ k ⩽ 10000
• se consideră că din prima nu poate fi mutată o bilă spre stânga, iar din ultima nu se poate muta o bila spre dreapta;
• iniţial nici o bilă nu se află în prima , în ultima sau într-o deteriorată;
• în fişierul de intrare poziţiile bilelor şi cele ale cutiilor deteriorate sunt sortate crescător;

Exemplu 1

cutiein.txt

2

10 1 1

6

3

10 1 2

5

4 4

cutieout.txt

10

Datele de intrare corespund restricțiilor impuse

Exemplu 2

cutiein.txt

0

0 0 -1

cutieout.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 1765 - Cutie

def verifica_joc(joc):

   n, k, m = joc[0]
   cutii_deteriorate = joc[1]
   bile_initiale = joc[2]

   # Verificăm dacă datele de intrare respectă restricțiile
   if not (1 <= n <= 10000 and 0 <= k <= 10000 and 1 <= m <= 10000):
       return False

   # Verificăm dacă nu există bile în prima, ultima sau în cutiile deteriorate
   if 1 in bile_initiale or n in bile_initiale or any(c in cutii_deteriorate for c in bile_initiale):
       return False

   # Verificăm dacă datele sunt sortate crescător
   if any(bile_initiale[i] >= bile_initiale[i + 1] for i in range(m - 1)):
       return False
   if any(cutii_deteriorate[i] >= cutii_deteriorate[i + 1] for i in range(k - 1)):
       return False

   # Determinăm dacă Ioana are o strategie sigură de câștig
   return (n - k) % 2 == 1

def main():

   with open("cutiein.txt", "r") as fin:
       T = int(fin.readline().strip())
       jocuri = []
       for _ in range(T):
           n, k, m = map(int, fin.readline().strip().split())
           cutii_deteriorate = list(map(int, fin.readline().strip().split()))
           bile_initiale = list(map(int, fin.readline().strip().split()))
           jocuri.append(((n, k, m), cutii_deteriorate, bile_initiale))

   rezultate = [1 if verifica_joc(joc) else 0 for joc in jocuri]

   with open("cutieout.txt", "w") as fout:
       fout.write("".join(map(str, rezultate)))

if __name__ == "__main__":

   main()

</syntaxhighlight>