Matematicianul maghiar Paul Erdos (1913–1996) a demonstrat ca din orice multime de p*q+1 numere naturale, putem selecta p+1 numere care se divid succesiv (x1|x2|...|xp|xp+1) sau putem selecta q+1 numere, astfel incat oricare doua dintre numere nu se divid ele.
Cerinta
Date fiind p*q+1 numere naturale distincte, sa se determine o submultime de p+1 numere care se divid succesiv sau o submultime de q+1 numere care nu se divid intre ele.
Date de intrare
Fisierul de intrare erdos.in contine pe prima linie numerele naturale p si q separate printr-un singur spatiu. Pe cea de a doua linie se afla p*q+1 numere naturale distincte separate prin cate un spatiu. Numerele sunt date in ordine crescatoare.
Date de iesire
Fisierul de iesire erdos.out va contine pe prima linie numarul natural p sau numarul natural q. Daca pe prima linie este scris numarul natural p, atunci pe cea de a doua linie sunt scrise p+1 numere naturale dintre cele citite, care au proprietatea ca primul numar il divide pe al doilea, al doilea il divide pe al treilea, s.a.m.d. Daca pe prima linie este scris numarul natural q, atunci pe cea de a doua linie vor fi scrise q+1 numere naturale cu proprietatea ca oricare doua numere dintre cele q+1 afisate nu se divid intre ele. Numerele afisate pe aceeasi linie vor fi separate prin spatiu si vor fi in ordine crescatoare.
Restrictii si precizari
| erdos.in | erdos.out | Explicatie |
|
3 4 |
4 9 12 15 33 35 |
Oricare doua numere din multimea {9 12 15 33 35} nu se divid intre ele. |
| erdos.in | erdos.out | Explicatie |
|
3 4 |
3 3 12 24 72 |
3|12|24|72 |
Timp maxim de executie/test: 0.1 secunde
prof. Emanuela
Cerchez
Liceul de Informatica
"Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com