Fişierul intrare/ieşire:siruri3.in, siruri3.outSursăONI 2018, clasa a 10-a, ziua 1
AutorAdrian BudauAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Siruri3

Fie M un tablou bidimensional (matrice), format din N linii şi N coloane, având elemente din mulţimea {0, 1}. Liniile şi coloanele acestui tablou sunt numerotate de 1 la N. Un drum de lungime K în acest tablou este un şir de perechi (xi, yi), cu i de la 1 la K, cu următoarele proprietăţi:

  • xi şi yi sunt valori numere naturale din intervalul [1, N], pentru i de la 1 la K
  • (|xi - xi+1|=1 şi yi=yi+1) sau (|yi - yi+1|=1 şi xi=xi+1), pentru i de la 1 la K-1

Altfel spus, un drum este o succesiune de poziţii în tablou astfel încât două poziţii consecutive sunt alăturate fie sus-jos, fie stânga-dreapta. Numim valoare a unui drum şirul de valori M[xi][yi], cu i de la 1 la K. Prin anagramă a unui şir de valori vom înţelege orice rearanjare a elementelor acestuia. De exemplu, dacă şirul iniţial conţine elementele (1, 0, 0, 1), atunci şirurile (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0), (0, 1, 1, 0) sunt anagrame ale acestuia.

Cerinta

Cunoscând dimensiunea N a tabloului, elementele tabloului M şi un şir S, compus din K elemente din mulţimea {0, 1}, determinaţi un drum în tabloul M, având ca valoare o anagramă a lui S, dacă acest drum există.

Date de intrare

Datele de intrare se citesc din fişierul siruri3.in, care are următoarea structură:

  • pe prima linie se află două numere naturale N şi K, separate printr-un singur spaţiu, reprezentând dimensiunea tabloului, respectiv lungimea şirului S
  • pe fiecare din următoarele N linii se află câte N valori din mulţimea {0, 1}, separate prin câte un spaţiu, reprezentând valorile tabloului M
  • pe linia N+2 se află K numere, din mulţimea {0, 1}, separate prin câte un spaţiu, reprezentând valorile şirului S.

Date de ieşire

Datele de ieşire se vor scrie în fişierul siruri3.out, astfel:

  • dacă nu există niciun drum care satisface cerinţa problemei, atunci se va scrie valoarea -1
  • dacă există un astfel de drum, atunci se vor scrie, pe linii separate, K perechi de valori xi yi, din mulţimea {1,2, ...,N}, separate printr-un singur spaţiu, reprezentând drumul determinat.

Restricţii

  • 1 ≤ N ≤ 100
  • 1 ≤ K ≤ 105
  • Elementele tabloului M şi ale şirului S sunt elemente din mulţimea {0, 1}.
  • Pentru teste în valoare de 20 de puncte, şirul S se găseşte pe o linie sau pe o coloană a matricei, aşa cum este dat în fişierul de intrare sau în ordine inversă.
  • Soluţia nu este unică, se acceptă orice soluţie.

Exemplu

siruri3.insiruri3.outExplicatie
3 10
0 0 0
0 1 1
1 0 1
1 1 1 0 1 1 1 0 1 1
2 2
2 3
2 2
2 1
2 2
2 3
2 2
2 3
3 3
3 2
Valoarea obţinută pentru drumul din fişierul de ieşire este
1 1 1 0 1 1 1 1 1 0 şi reprezintă o anagramă a şirului dat.
4 3
1 0 0 0
0 0 1 0
1 0 0 0
1 0 0 0
1 1 0
4 1
3 1
2 1
Şirul S se găseşte pe coloana 1 a matricei.
2 4
0 0
0 0
1 0 1 0
-1
În tablou nu există valoarea 1, deci nu se poate obţine un drum a cărui valoare să conţină 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?