Question

Problema #552 Excursie PbInfo


Î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.

Answer 1

#include <iostream>

using namespace std;

struct Oras {

   int a,b;

};

Oras orase[1001];

int findFirst(int n){

   for(int inceput = 0; inceput < n; inceput++){

       if(orase[inceput].a > orase[inceput].b)

           continue;

       int energie = orase[inceput].b - orase[inceput].a;

       for(int i = inceput+1; i < n && energie >= 0; i++){

           energie += orase[i].b - orase[i].a;

       }

       for(int i = 0; i < inceput && energie >= 0; i++){

           energie += orase[i].b - orase[i].a;

       }

       if(energie >= 0)

           return inceput+1;

   }

   return -1;

}

int main(){

   int n;

   cin >> n;

   for(int i = 0; i < n; i++)

       cin >> orase[i].a >> orase[i].b;

   cout << findFirst(n);

}