.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » erdos

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
erdos


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

  • 1 <= p, q <= 50
  • p<>q
  • Numerele naturale date au valori < 263

Exemple

erdos.in erdos.out Explicatie

3 4
3 5 9 12 14 15 24 33 35 41 51 54 61

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 5 9 12 14 15 24 33 72 41 51 54 61

3
3 12 24 72
3|12|24|72

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, sah, formule, perm, cifra, repeat, ture, xor, policefm, unu, criptare, ed, bilete, vector, scor, ratb, infinit, race, dragon, kreg, placi, hanoig, red, 2sec, flood, sume3, balls, festival, croco, johnie, matrice3, pavaj, sume, arthur, kimberley, kafka, vocale, pento, prop, ro, sol, bacan, poligon, reduceri, druid, novel, gramezi, nrbinar, laser, spair, caravane, cuburi, grup, invest, cd, friends2, mese, toys
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre Principiul cutiei Dirichlet: noroc, zid, m01, tabara, ferma, radio1, cifru4, copii, moretime
Software recomandat
surse trimise | ajutor