#1621
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*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ă cuvântul 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.
Cunoscând dimensiunile cartierului n
și m
, cuvântul cuv
, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:
OJI 2016, Clasa a X-a
Problema | Miting | Operații I/O |
![]() miting.in /miting.out
|
---|---|---|---|
Limita timp | 1 secunde | Limita memorie |
Total: 16 MB
/
Stivă 8 MB
|
Id soluție | #51745330 | Utilizator | |
Fișier | miting.cpp | Dimensiune | 3.08 KB |
Data încărcării | 12 August 2024, 23:20 | Scor / rezultat | 100 puncte |
miting.cpp: In function 'int main()': miting.cpp:51:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int k = 1; k <= cuv.length(); ++k) ^ miting.cpp:53:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int l = k; l <= cuv.length(); ++l) ^ miting.cpp:64:32: warning: array subscript has type 'char' [-Wchar-subscripts] fr[matrix[i][j]].x = i; ^ miting.cpp:65:32: warning: array subscript has type 'char' [-Wchar-subscripts] fr[matrix[i][j]].y = j; ^ miting.cpp:74:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i <= cuv.length(); ++i) ^ miting.cpp:76:34: warning: array subscript has type 'char' [-Wchar-subscripts] coada.push({fr[cuv[i - 1]].x, fr[cuv[i - 1]].y}); ^ miting.cpp:76:52: warning: array subscript has type 'char' [-Wchar-subscripts] coada.push({fr[cuv[i - 1]].x, fr[cuv[i - 1]].y}); ^ miting.cpp:80:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int le = 2; le <= cuv.length(); ++le) ^ miting.cpp:82:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i + le - 1 <= cuv.length(); ++i) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | OK. | 5 | 5 | ||
1 | 0 secunde | OK. | 5 | 5 | ||
2 | 0 secunde | OK. | 5 | 5 | ||
3 | 0 secunde | OK. | 5 | 5 | ||
4 | 0 secunde | OK. | 5 | 5 | ||
5 | 0 secunde | OK. | 5 | 5 | ||
6 | 0 secunde | OK. | 5 | 5 | ||
7 | 0 secunde | OK. | 5 | 5 | ||
8 | 0 secunde | OK. | 5 | 5 | ||
9 | 0.008 secunde | OK. | 5 | 5 | ||
10 | 0 secunde | OK. | 5 | 5 | ||
11 | 0.004 secunde | OK. | 5 | 5 | ||
12 | 0 secunde | OK. | 5 | 5 | ||
13 | 0 secunde | OK. | 5 | 5 | ||
14 | 0 secunde | OK. | 5 | 5 | ||
15 | 0.02 secunde | OK. | 5 | 5 | ||
16 | 0.016 secunde | OK. | 5 | 5 | ||
17 | 0.028 secunde | OK. | 5 | 5 | ||
18 | 0.028 secunde | OK. | 5 | 5 | ||
19 | 0.016 secunde | OK. | 5 | 5 | ||
Punctaj total | 100 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Miting face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.