Chip şi Dale s-au plictisit de jocurile de până acum şi au hotărât că este timpul să îmbine culesul alunelor cu un joc care să le stimuleze inteligenţa. Chip propune: “eu pun alunele culese de mine într-un şir de C scorburi, iar tu pui alunele culese de tine într-un alt şir, de D scorburi”.
Dale a ascultat, a fost de acord şi a propus ca jocul să continue astfel: „dacă la împărţirea numărului de alune din prima scorbură a şirului meu la numărul de alune din fiecare scorbură a şirului tău se obţine acelaşi rest, atunci consider că scorbura mea este umplută corect şi scriu pe hârtie cifra 1, altfel o consider umplută incorect şi scriu cifra 0. Verific apoi, aplicând aceeaşi regulă, dacă a doua scorbură din şirul meu este umplută corect, adică dacă la împărţirea numărului de alune din aceasta la numărul de alune din fiecare scorbură din şirul tău, se obţine acelaşi rest. Notez pe hârtie, în continuare, rezultatul verificării (0 sau 1). Încheiem jocul atunci când terminăm de verificat, după această regulă, toate cele D scorburi ale mele.”

Cerința

Scrieţi un program care citeşte din fişierul alune.in numerele naturale nenule C şi D şi numărul de alune din fiecare scorbură din şirul lui Chip, respectiv al lui Dale. Programul determină şirul de cifre notat de Dale pe hârtie.

Date de intrare

Fişierul alune.in conţine pe prima linie cele două numere naturale, C şi D, pe a doua linie C numere naturale, reprezentând numărul de alune din fiecare scorbură a lui Chip, iar pe a treia linie D numere naturale, reprezentând numărul de alune din fiecare scorbură a lui Dale. Toate numerele situate pe aceeaşi linie a fișierului sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul alune.out conţine o singură linie pe care se află şirul determinat. Cifrele din acest şir nu sunt separate prin spaţii.

Restricții și precizări

1 ≤ C, D ≤ 100 000
Numerele de alune din scorburile lui Chip, scrise pe a doua linie a fişierului de intrare, sunt numere naturale din intervalul [1, 2 000 000 000];
Numerele de alune din scorburile lui Dale, scrise pe a treia linie a fişierului de intrare, sunt numere naturale din intervalul [0, 2 000 000 000].

Exemplu

alune.in

3 2
3 4 5
8 2

alune.out

Explicație

Prima scorbură a lui Dale este umplută incorect, deoarece resturile împărţirii lui 8 la numerele 3, 4 şi 5 sunt diferite, deci rezultatul verificării este 0.
A doua scorbură a lui Dale este umplută corect deoarece resturile împărţirii lui 2 la 3, 4 şi 5 sunt egale, iar rezultatul verificării este 1.

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

//Solutia oficiala, Marius Nicoli   100p N log(VMAX) + Q
#include <stdio.h>
#define DIM 100010

#define MAX 2000000000

long long mc;
int m, X, Q, N, i, ok, q, depaseste;

int cmmdc(int a, int b) {
    int r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int minim (int a, int b) {
    return a < b ? a : b;
}

int main() {
    FILE *f = fopen("alune.in","r");
    FILE *g = fopen("alune.out","w");
    
    fscanf(f,"%d %d",&N, &Q);
    
    fscanf(f,"%d",&X);
    mc = m = X;
    depaseste = 0;
    for (i = 2; i<=N; i++) {
        fscanf(f,"%d",&X);
        m = minim(m, X);
        if (depaseste)
            continue;       
        mc = mc / cmmdc(mc, X) * X;
        if (mc > MAX) {
            depaseste = 1;
        }
    }
    
    for (;Q;--Q) {
        ok = 1;
        fscanf(f,"%d",&q);
        if (depaseste) {
            if (q >= m) {
                ok = 0;
            }
        } else {
            if (q % mc >= m) {
                ok = 0;
            }
        }
        fprintf(g,"%d",ok);
    }
    fprintf(g,"\n");
    fclose(g);
    fclose(f);
    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 #1759 Alune

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