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: \( {x}_{1},{x}_{2}…{x}_{n} \) 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

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.

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 Cartonase1:

#include<bits/stdc++.h>
using namespace std;

ifstream in("cartonase1.in");
ofstream out("cartonase1.out");

/*
int cmmdc(int a,int b)
{
    if(!a || !b)
        return max(a,b);
    int r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
*/

int main()
{
    int a,b,n;
    in>>n>>a>>b;
    if(a==1)
    {
        out<<1;
        return 0;
    }
    int g=__gcd(a,b);
    if(g==1)
    {
        out<<2;
        return 0;
    }
    for(int i=3;i<=n;i++)
    {
        a=b;
        in>>b;
        g=__gcd(g,b);
        if(g==1)
        {
            out<<i;
            return 0;
        }
    }
    out<<-1;
    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 #2881 Cartonase1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2881 Cartonase1 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 #2881 Cartonase1