Fişierul intrare/ieşire:miting.in, miting.outSursăOJI 2016, clasa a 10-a
AutorConstantin GalatanAdăugată devladrochianVlad Rochian vladrochian
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Miting

În Oraşul Liniştit un număr de K tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceştia este mare, ei se vor deplasa spre punctul de întâlnire cu maşinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulţimea A ... Z. Nu există două pancarte cu litere identice. Cele K litere formează un cuvânt, să-l notăm cuv, cunoscut.

Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu N x M zone pătratice, dintre care unele sunt interzise. Se ştie că o maşină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină şi nu consumă combustibil dacă staţionează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două maşini se întâlnesc într-o zonă şi toate literele aflate în cele două maşini reprezintă o secvenţă din cuvântul cuv, atunci ei vor continua drumul cu o singură maşină, luând desigur toate pancartele cu ei. În caz contrar, maşinile îşi continuă drumul separat.

De exemplu, dacă cuvantul cuv este JOS, atunci maşina care transportă litera J poate prelua tânărul care aduce pancarta cu litera O, sau invers: maşina având litera O poate prelua tânărul care aduce litera J. Apoi se poate continua drumul spre maşina care transportă litera S. În altă variantă se pot reuni mai întâi literele S şi O într-o singură maşină, dacă maşinile care le transportau se întâlnesc în aceeaşi zonă. Totuşi, între maşina care transportă doar litera J şi cea care transportă doar litera S nu se poate realiza un transfer, adică o reunire a literelor.

Cerinţe

Cunoscând dimensiunile cartierului N şi M, cuvântul cuv, configuraţia cartierului şi poziţiile iniţiale ale tinerilor, se cere:

  1. Aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate poziţiile iniţiale ale tinerilor.
  2. Numărul minim de unităţi de combustibil consumate de către toate maşinile, ştiind că în final toţi tinerii se vor reuni într-o singură maşină.

Date de intrare

Fişierul de intrare miting.in conţine:

  • Pe prima linie, un număr natural p, care poate avea doar valoarea 1 sau 2.
  • Pe a doua linie două numere naturale N şi M, separate printr-un spaţiu.
  • Pe a treia linie, cuvântul cuv.
  • Pe următoarele N linii, câte M caractere pe linie reprezentând zonele cartierului. O zonă este interzisă dacă îi corespunde caracterul #, este liberă dacă îi corespunde caracterul _ (underline) şi este punctul de plecare al unei maşini dacă îi corespunde una dintre literele cuvântului cuv.

Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai cerinţa 1. În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural A, reprezentând aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate poziţiile iniţiale ale tinerilor.

Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural C, reprezentând numărul minim de unităţi de combustibil consumate de către toate maşinile până la reunirea tinerilor, deci şi a literelor, într-o singură maşină. În cazul în care nu există soluţie, adică nu toţi tinerii se pot reuni într-o singură maşină, se va scrie -1.

Restricţii

  • 2 ≤ N, M ≤ 60
  • 2 ≤ K ≤ 10
  • Fie z numărul zonelor interzise. Atunci 0 ≤ z ≤ (N * M) / 3.
  • În fiecare unitate de timp, o maşină poate să rămână pe loc în aşteptarea alteia sau poate să treacă într-o zonă vecină, indiferent dacă zona respectivă este sau nu ocupată de altă maşină.
  • Lungimea laturii unei zone se consideră egală cu 1.
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.
  • Pentru 30% dintre testele cerinţei 2 se garantează K ≤ 3.

Exemplu

miting.inmiting.out
1
4 5
JOS
#_O_#
_#__S
_#J_#
___#_
9
2
5 7
BUN
_#_#_#_
__N#__#
_#__B__
U__#_#_
_#_#_#_
6
2
6 7
ROST
O#_#_#_
___#__#
_#_R___
____#__
__#_S_#
_#_T_#_
9

Explicaţie

Pentru al doilea exemplu, o variantă de consum minim este: U se deplasează cu două poziţii la dreapta. Apoi B se deplasează cu două poziţii la stânga. U se deplasează din nou cu o singură poziţie în sus. În final, N coboară o poziţie.
Remarcaţi că B s-a reunit cu U, apoi BU cu N.

Pentru al treilea exemplu, variantă de consum minim este: O se deplasează cu o poziţie în jos, apoi cu două poziţii spre dreapta, coboară o poziţie şi în final se deplasează o poziţie spre dreapta, unde se reuneşte cu R. Apoi S se deplasează cu o poziţie la stânga. T urcă o poziţie şi se reuneşte cu S. În final, maşina în care se găsesc S şi T urcă două poziţii şi se întâlneşte cu maşina în care se găsesc R şi O. În această zonă, la linia 3 şi coloana 4, toate literele se reunesc într-o singură maşină.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?