#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 | #49791375 | Utilizator | |
Fișier | miting.cpp | Dimensiune | 4.46 KB |
Data încărcării | 14 Martie 2024, 21:59 | Scor / rezultat | 20 puncte |
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 | Raspuns gresit. | 5 | 0 | ||
5 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
6 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
7 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
8 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
9 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
10 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
11 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
12 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
13 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
14 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
15 | 0.016 secunde | Raspuns gresit. | 5 | 0 | ||
16 | 0.012 secunde | Raspuns gresit. | 5 | 0 | ||
17 | 0.012 secunde | Raspuns gresit. | 5 | 0 | ||
18 | 0.012 secunde | Raspuns gresit. | 5 | 0 | ||
19 | 0.016 secunde | Raspuns gresit. | 5 | 0 | ||
Punctaj total | 20 |
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ă.