# PBinfo #552 – Excursie – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

5
6 7
8 4
2 6
1 4
2 1
Ieșire

3
Explicație
Gigel poate pleca din oraşul 3 sau din oraşul 4.

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/552)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/552/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-552/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)