#2559
train
O companie feroviară a lansat recent un nou prototip de tren, format dintr-un singur vagon cu N
scaune. Scaunele sunt numerotate la 1
la N
(numerotarea începe de la partea din față a trenului) și sunt aranjate într-o linie, unul în spatele altuia. Următoarele reguli urmează să fie respectate de fiecare pasager:
1. Pasagerii vor urca în tren doar pe ușa din spate, care este situată după toate scaunele. Odată urcați, pasagerii au dreptul să se deplaseze doar spre partea din față și pot părăsi trenul doar prin ușa din față (care este situată în fața tuturor scaunelor).
2. Fiecare pasager va ocupa locul situat imediat după ultimul scaun ocupat. Dacă trenul este absolut liber, pasagerul va ocupa scaunul din față (marcat ca locul 1
).
3. Nici un pasager nu are dreptul să-și părăsească locul până la debarcare.
4. La fiecare stație, pasagerii care au ajuns la destinație părăsesc trenul. Dacă există pasageri pe scaune în fața celui care a ajuns la destinație, ei de asemenea vor părăsi trenul, chiar dacă încă nu au ajuns la destinația lor.
5. Odată ce a ieșit din tren, pasagerul nu mai are dreptul să urce înapoi.
Ruta trenului are M
stații, numerotate de la 1
la M
. Trenul se oprește în fiecare stație, începând cu stația 1
și terminând cu stația M
. La toate cele M
stații de tren se află în total N
pasageri, numerotați de la 1
la N
. Pentru fiecare pasager se cunoaște din timp prețul tichetului, stația de îmbarcare și stația de debarcare. Compania feroviară dorește să aibă doar clienți fericiți, care ajung la destinația lor. Pentru a avea doar clienți fericiți, compania a permis conductorului să selecteze pasagerii care se pot îmbarca, precum și ordinea în care li se permite îmbarcarea. Astfel, conductorul poate să decidă să nu permită unor pasageri să urce în tren. Determinați profitul maximal care poate fi obținut de companie având doar clienți fericiți, precum și o ordine de îmbarcare validă, care permite obținerea acestui profit.
Balcaniada de Informatică 2018, ziua 2
Problema | train | Operații I/O |
train.in /train.out
|
---|---|---|---|
Limita timp | 0.4 secunde | Limita memorie |
Total: 128 MB
/
Stivă 32 MB
|
Id soluție | #11389261 | Utilizator | |
Fișier | train.cpp | Dimensiune | 1.77 KB |
Data încărcării | 27 Octombrie 2018, 11:24 | Scor / rezultat | 100 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 | OK | 5 | 5 | ||
5 | 0 secunde | OK | 5 | 5 | ||
6 | 0 secunde | OK | 5 | 5 | ||
7 | 0 secunde | OK | 5 | 5 | ||
8 | 0.024 secunde | OK | 5 | 5 | ||
9 | 0.072 secunde | OK | 5 | 5 | ||
10 | 0.044 secunde | OK | 5 | 5 | ||
11 | 0.024 secunde | OK | 5 | 5 | ||
12 | 0.044 secunde | OK | 5 | 5 | ||
13 | 0.072 secunde | OK | 5 | 5 | ||
14 | 0.072 secunde | OK | 5 | 5 | ||
15 | 0.084 secunde | OK | 5 | 5 | ||
16 | 0.092 secunde | OK | 5 | 5 | ||
17 | 0.08 secunde | OK | 5 | 5 | ||
18 | 0.1 secunde | OK | 5 | 5 | ||
19 | 0.092 secunde | OK | 5 | 5 | ||
Punctaj total | 100 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema train 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ă.