Cerința

În ţara lui Gigel se află n oraşe, numerotate de la 1 la n, cu proprietatea că din oraşul i exista drum numai spre oraşul i+1, iar din oraşul n există drum spre oraşul 1. Gigel doreşte să viziteze toate cel n oraşe în ordine, pornind dintr-un oraş oarecare şi întorcându-se la final în acesta.

Lucrurile nu sunt atât de simple, deoarece pentru a se deplasa dintr-un oraş i în oraşul următor Gigel are nevoie de o cantitate cunoscută de energie, A[i]. De asemenea, în fiecare oraş Gigel acumulează o cantitate cunoscută de energie B[i], pe care o poate folosi pentru a se deplasa mai departe. Iniţial, Gigel nu are deloc energie.

Determinaţi, dacă există, un oraş din care Gigel poate începe vizitarea celor n oraşe, astfel încât la final Gigel să se întoarcă în oraşul din care a plecat.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale A[i] B[i].

Date de ieșire

Programul va afișa pe ecran numărul P, reprezentând numărul de ordine al oraşului din care poate porni Gigel, respectiv -1 dacă drumul nu poate fi parcurs, indiferent din care oraş ar pleca.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ A[i] ≤ 1000
0 ≤ B[i] ≤ 1000
Dacă Gigel poate pleca din mai multe oraşe, se va afişa oraşul cu numărul de ordine mai mic
Dacă energia necesară pentru deplasarea dintr-un oraş în următorul este egală cu energia pe care o are Gigel la plecarea din oraş, deplasarea se poate face.

Exemplu

Intrare

Ieșire

Explicație

Gigel poate pleca din oraşul 3 sau din oraşul 4.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Excursie:

#include <iostream>
using namespace std;

int A[2005], B[2005], n;

// A[i] - necesar
// B[i] - existent

int main(){
    cin  >> n;  
    for(int i = 1 ; i <= n ; ++i)
        cin >> A[i] >> B[i];
    for(int i = 1 ; i <= n ; ++i)
        A[n+i] = A[i], B[n+i] = B[i];
    
    int p = -1;
    for(int i = 1; i <= n && p == -1 ; i ++)
    {
        int s = 0;
        bool OK = true;
        for(int j = 0; j < n && OK ; ++j)
        {
            s += B[i+j];
            s -= A[i+j];
            if(s < 0)
                OK = false;
        }
        if(OK)
            p = i;
    }
    cout << p ;
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #552 Excursie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #552 Excursie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #552 Excursie