Rezumat problemă

scara1

#2675

Domnul G are de urcat o scară cu n trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x. Dacă bea toată apa dintr-o astfel de sticlă, forța și mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conținută de aceste sticle poate să difere de la o treaptă la alta.
Pe j trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y decilitri de băutură energizantă. Dacă bea q (q ≤ y) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q decilitri consumaţi, G trebuie să plătească q lei grei.
Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.
Determinaţi p, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p paşi.

OJI 2005, clasele XI-XII

Fișiere Pracsiu Dan (dnprx) Stelian Ciurea concurs

Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	scara1	Operații I/O	scara.in/scara.out
Limita timp	0.1 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#57080524	Utilizator	Vasilache Andrei (dUnTe)
Fișier	scara1.cpp	Dimensiune	3.12 KB
Data încărcării	15 Martie 2025, 00:03	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

scara1.cpp: In function 'int main()':
scara1.cpp:41:14: error: expected unqualified-id before '[' token
         auto [current_steps, current_cost, pos, buff] = heap.top();

              ^
scara1.cpp:44:13: error: 'current_steps' was not declared in this scope
         if (current_steps > steps[pos][buff] || 

             ^
scara1.cpp:44:35: error: 'pos' was not declared in this scope
         if (current_steps > steps[pos][buff] || 

                                   ^
scara1.cpp:44:40: error: 'buff' was not declared in this scope
         if (current_steps > steps[pos][buff] || 

                                        ^
scara1.cpp:45:51: error: 'current_cost' was not declared in this scope
             (current_steps == steps[pos][buff] && current_cost > costs[pos][buff])) 

                                                   ^
scara1.cpp:47:13: error: 'current_steps' was not declared in this scope
         if (current_steps > min_steps) continue;

             ^
scara1.cpp:49:30: error: 'buff' was not declared in this scope
         for (int m = 1; m <= buff; ++m) {

                              ^
scara1.cpp:50:27: error: 'pos' was not declared in this scope
             int new_pos = pos + m;

                           ^
scara1.cpp:53:35: error: 'current_steps' was not declared in this scope
                 int total_steps = current_steps + 1;

                                   ^
scara1.cpp:54:34: error: 'current_cost' was not declared in this scope
                 int total_cost = current_cost;

                                  ^
scara1.cpp:84:34: error: 'current_steps' was not declared in this scope
                 int next_steps = current_steps + 1;

                                  ^
scara1.cpp:85:33: error: 'current_cost' was not declared in this scope
                 int next_cost = current_cost + added_cost;

                                 ^

Cum funcționează evaluarea?