| Fișierul intrare/ieșire | fotbal2.in, fotbal2.out | Sursă | IQ Academy |
|---|---|---|---|
| Autor | Mihai Tuțu | Adăugată de |
Mihai Tutu
•
mihai.tutu
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 6144 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Fotbal 2 (clasa a 6-a)
Notă: aceasta este problema Leo cu limita de timp micșorată de la 1.5s la 04s.
Un nou sezon, o nouă aventură pentru nea Gigi, patronul echipei FCSpreB. După ce anul trecut a încurcat lucrurile și nu a reușit să imprime numele jucătorilor pe tricourile echipei sale, acum îi este greu să urmărească meciul și să înțeleagă care jucător este care.
Afacerist dibaci, cu multă înțelegere asupra manipulării numerelor, acesta a găsit o soluție: folosirea numerele excesive. Nea Gigi știe că un număr excesiv x este acela care are suma divizorilor (strict mai mici decât x) mai mare decât numărul însuși, x. De exemplu, 12 este un număr excesiv deoarece divizorii lui sunt 1, 2, 3, 4 și 6, iar suma lor este 16. Următoarele numere excesive sunt 18 și 20.
Așa cum îl știm pe patron, nu vrea să își bată capul cu lucruri mărunte. Așa că te-a rugat să îl ajuți, pe tine, fanul numărul unu al clubului FCSpreB.
Cerință
Federația Română de Fotbal permite ca numerele de pe tricouri să fie cuprinse între 3 și 1000000, astfel că va trebui să te încadrezi în acest interval. Tu va trebui să găsești:
- Cel mai mare număr x ≤ n cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1. Acesta va fi numărul purtat de portarul titular.
- Câte numere de la 1 la n sunt excesive și pot fi imprimate pe tricouri.
- Câte numere de la 1 la n au proprietatea că, reprezentate în baza doi, au același număr de cifre 1 ca reprezentarea în baza doi a sumei tuturor divizorilor lor (toți divizorii, nu doar cei proprii). Acestea vor fi numerele imprimate pe tricourile jucătorilor primei echipe FCSpreB.
Date de intrare
Fișierul de intrare fotbal2.in conține pe prima linie numărul cerinței, 1, 2, sau 3. Pe a doua linie va conține numărul n.
Date de ieșire
Pe prima linie a fișierului de ieșire fotbal2.out veți afișa astfel:
- Dacă cerința este 1, cel mai mare număr x ≤ n cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1. Numărul x va fi afișat în baza 10.
- Dacă cerința este 2, numărul de numere excesive între 1 și n, inclusiv 1 și n.
- Dacă cerința este 3, numărul de numere x între 1 și n, inclusiv 1 și n, ale căror sume ale tuturor divizorilor lor au același număr de cifre 1 în reprezentarea lor în baza doi ca și reprezentarea în baza doi a numerelor x.
Restricții
- 3 ≤ n ≤ 1000000
- suma tuturor divizorilor oricărui număr x nu va depăși 5 milioane
- Pentru rezolvarea primei cerințe se acordă 20% din punctaj, pentru a doua cerință 30% din punctaj și pentru a treia cerință 50% din punctaj.
Exemple
| fotbal2.in | fotbal2.out | Explicație |
|---|---|---|
| 1 16 |
16 |
Cel mai mare număr mai mic sau egal cu 16 care are o singură cifră 1 în reprezentarea în baza doi este chiar 16. |
| 2 16 |
1 |
Avem un singur număr excesiv, acela fiind 12, a cărui sumă a divizorilor stricți este 1+2+3+4+6=16. |
| 3 16 |
5 |
Avem 5 numere ale căror reprezentări în baza doi au același număr de cifre 1 ca și suma divizorilor lor: 1(10) = 1(2), suma divizorilor este 1(10) = 1(2) 5(10) = 101(2), suma divizorilor este 1+5=6(10) = 110(2) 6(10) = 110(2), suma divizorilor este 1+2+3+6=12(10) = 1100(2) 10(10) = 1010(2), suma divizorilor este 1+2+5+10=18(10) = 10010(2) 13(10) = 1101(2), suma divizorilor este 1+13=14(10) = 1110(2) |
| 1 20 |
16 |
Cel mai mare număr mai mic sau egal cu 20 care are o singură cifră 1 în reprezentarea în baza doi este 16. |
| 2 20 |
3 |
Avem 3 numere excesive, 12, 18 și 20. |
| 3 20 |
6 |
Avem 6 numere ale căror reprezentări în baza doi au același număr de cifre 1 ca și suma divizorilor lor, 1, 5, 6, 10, 13, 17. |
