Cerința
Într-o zi, câțiva copii plictisiți de “Popa Prostul”, au inventat jocul “Popa Prostul 2”. Acest joc se joacă cu mai multe cartonașe identice. La început, fiecare jucător primește un număr de cartonașe. Primul jucător pune pe masă un număr de cartonașe egal cu cel mai mare divizor al numărului de cartonașe pe care îl avea în mână. Următorul pune un număr maxim de cartonașe, divizor al numărului de cartonașe pe care le are în mână, dar și divizor al numărului de cartonașe pus de jucătorul dinainte. Jocul continuă până când unul dintre copii pune jos un singur cartonaș. Jucătorul care va fi nevoit să pună un singur cartonaș va fi pierzătorul.
Dându-se numărul n
de copii și numărul de cartonașe pe care îl primește fiecare, să se determine numărul de ordine al copilului care va pierde jocul.
Date de intrare
Pe prima linie a fișierului de intrare cartonase1.in
se va găsi numărul n
de copii. Pe a doua linie vor fi n
numere: x1,x2…xn reprezentând numărul de cartonașe pe care îl primește fiecare jucător.
Date de ieșire
Pe prima linie a fișierului cartonase1.out
se va scrie numărul de ordine al pierzătorului sau valoarea -1
dacă nu există pierzător.
Restricții și precizări
2 ≤ n ≤ 100.000
1 ≤ x
i
≤ 100.000.000
- Primul jucător va avea numărul de ordine
1
.
Exemplu
cartonase1.in
8 30 15 6 18 303 45 44 25
cartonase1.out
7
Explicație
Primul jucător va pune 30 de cartonaşe
.
Al doilea jucător va pune 15 cartonaşe
.
Al treilea jucător va pune 3 cartonaşe
.
Jucătorii 4, 5 şi 6
vor pune 3 cartonaşe fiecare
.
Jucătorul cu numărul 7
va fi obligat să pună 1 cartonaş
şi va pierde jocul.
#include <bits/stdc++.h> using namespace std; ifstream cin("cartonase1.in"); ofstream cout("cartonase1.out"); int cmmdc(int a , int b) { while(b) { int r = a % b; a = b; b = r; } return a; } int main() { int n; cin >> n; int x , y; cin >> x; bool ok = true; for(int i = 2 ; i <= n && ok; ++i) { cin >> y; x = cmmdc(x , y); if(x == 1) cout << i , ok = false; } if(ok) cout << -1; return 0; }