Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

JOCUL DIVIZORILOR

calculatoare



+ Font mai mare | - Font mai mic



JOCUL DIVIZORILOR

Ancuta si George s-au jucat cu numerele naturale astfel: Anca trebuia sa se gandeasca la un numar n iar baiatul sa il ghiceasca intreband daca numarul fetei se divide cu diverse numere alese de el. Jocul lua sfarsit cand numarul pentru care punea intrebarea daca este divizor era chiar numarul la care s-a gandit initial Ancuta.



George, istet din fire, si-a dat seama ca poate gasi mai usor raspunsul folosind urmatoarea strategie: alege pe rand numere prime si intreaba daca sunt divizori ai lui n. Daca un numar prim k este divizor al lui n, verifica in ordine valorile kk, kkk etc. pana cand gaseste prima putere a lui k ce nu este divizor a lui n. In acest mod gaseste un factor cu care se divide numarul ales de Ancuta. Daca mai are factori anteriori gasiti astfel, ii inmulteste si o intreaba pe Ancuta. Daca fata nu ii confirma ca jocul s-a terminat, atunci alege urmatorul numar prim si continua procedeul.

El si-a format si un sistem de notare pe un caiet astfel: daca numarul ales de el este divizor al celui cautat va nota 1 iar daca nu e divizor va nota 0.

De exemplu, pentru numarul n=360 sirul rezultat este (1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1) adica: 2 divide 360, 4 divide 360, 8 divide 360, dar 16 nu mai divide 360; primul factor este 8, iar cum nu exista inca determinati alti factori, trece la urmatorul numar prim care este 3; 3 divide 360, 9 divide 360, dar 27 nu divide 360; a determinat urmatorul factor ca fiind 9 si deoarece are un factor anterior 8, alege in continuare pe 72=89 care divide pe 360, dar nu este numarul cautat; continua cu urmatorul numar prim, 5; 5 divide pe 360, 25 nu-l divide pe 360, deci urmatorul factor este 5; urmatorul numar de care intreaba este produsul factorilor determinati pana acum 360=895, care divide pe 360 si jocul se opreste pentru ca Ancuta ii confirma ca a ghicit numarul.

Dupa o vreme, uitandu-se peste notitele sale, George a observat o serie de proprietati la sirul construit de el. De exemplu, ca sunt mai multe numere naturale ce pot avea aceeasi lungime a sirului cu acelasi numar de cifre 1 in el. Curios din fire, a incercat sa gaseasca cel mai mare numar si cel mai mic numar natural pentru care sirurile de 1 si 0 notate pe caiet au un numar de elemente dat precum si un numar de elemente cu valoarea 1 dorit.

Ajutati-l pe George sa gaseasca raspunsurile pe care le cauta.

Date de intrare

Fisierul de intrare JOC.IN contine o singura linie care memoreaza un numar intreg n.

Date de iesire

Fisierul de iesire JOC.OUT contine pe prima linie sirul de elemente de 1 si 0 corespunzatoare numarului n, obtinut prin strategia de joc prezentata mai sus.

Pe a doua linie se afla cel mai mic numar natural al carui sir are tot atatea elemente cate are sirul de pe prima linie si tot atatea elemente de valoare 1 cate are sirul de pe prima linie.

Pe a treia linie se afla cel mai mare numar natural cu proprietatile descrise mai sus.

Restrictii si precizari

1 ≤ n ≤ 25000



se acorda punctaje partiale astfel: prima linie din fisierul de iesire corecta primeste 40%, a doua linie 30% si a treia linie 30%

Exemple

JOC.IN

JOC.OUT

Explicatie

2 nu divide 35, 3 nu divide 35, 5 divide 35, 25 nu divide 35, 7 divide 35, 49 nu divide 35, 57=35 divide 35, am gasit

pentru 14 se obtine sirul 1 0 0 0 1 0 1

pentru 1331 se obtine sirul 0 0 0 0 1 1 1

JOC.IN

JOC.OUT

Explicatie

2 nu divide 81, 3 divide 81, 9 divide 81, 27 divide 81, 81 divide 81, am gasit numarul, ne oprim

81 este singurul numar natural care are in sir 4 cifre de 1 si o cifra de 0.

Timp maxim de executie/test : 1 secunda





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1608
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved