Fişierul intrare/ieşire:fotbal2.in, fotbal2.outSursăIQ Academy
AutorMihai TutuAdăugată demihai.tutuMihai Tutu mihai.tutu
Timp execuţie pe test0.4 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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:

  1. 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.
  2. Câte numere de la 1 la n sunt excesive şi pot fi imprimate pe tricouri.
  3. 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 xn 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.infotbal2.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici