Fișierul intrare/ieșire	multisum.in, multisum.out	Sursă	ONI 2017, Clasa a 10-a
Autor	Rodica Pintea	Adăugată de	Tinca Matei • TincaMatei
Timp de execuție pe test	0.2 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Multisum (Clasa a 10-a)

Orice număr natural mai mare decât 2 poate fi scris ca sumă de numere naturale nenule aflate în ordine strict crescătoare, astfel încât orice termen al sumei, cu excepția primului termen, este un multiplu al termenului precedent din sumă. De exemplu, 27=3+6+18, unde 6 este multiplul lui 3, iar 18 este multiplul lui 6. Cum se dorește o descompunere formată dintr-un număr cât mai mare de termeni, vom obține și descompuneri cu 4 termeni: 27=1+2+8+16, 27=1+2+4+20, 27=1+2+6+18. Dintre cele trei descompuneri cu 4 termeni, descompunerea 27=1+2+4+20 este minimă din punct de vedere lexicografic (1 și 2 sunt la fel în cele 3 descompuneri, dar 4<6 și 4<8). Numărul 30 poate fi descompus 30=2+4+8+16. El are o descompunere tot de lungime 4, dar este mai mare din punct de vedere lexicografic decât oricare dintre descompunerile cu 4 termeni ale lui 27 (2 > 1).

Cerințe

Pentru mai multe seturi de date formate din câte două numere naturale A și B, A ≤ B, se cere să se determine, pentru fiecare set una dintre următoarele cerințe:
1) numărul maxim de termeni în care pot fi descompuse numerele din intervalul [A,B] după regula descrisă în enunț;
2) numărul de numere din intervalul [A,B] care pot fi descompuse cu un număr maxim de termeni;
3) numărul din intervalul [A,B] care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Date de intrare

Din fișierul multisum.in se citesc, de pe prima linie, două numere N și C, despărțite printr-un spațiu, reprezentând numărul de seturi de date și tipul cerinței: C=1 pentru cerința 1, C=2 pentru cerința 2 și C=3 pentru cerința 3. De pe următoarele N linii ale fișierului se citește câte o pereche de numere A și B, separate printr-un spațiu.

Date de ieșire

În fișierul multisum.out se va scrie câte o linie pentru fiecare pereche A B din fișierul de intrare, linie care va conține numărul cerut, conform cerinței: dacă C=1, numărul va reprezenta numărul maxim de termeni dintr-o descompunere, dacă C=2, numărul va reprezenta numărul de valori din intervalul respectiv care pot fi descompuse cu un număr maxim de termeni, iar dacă C=3, numărul va reprezenta acea valoare din intervalul respectiv care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Restricții și precizări

• 0 < N ≤ 1000
• 2 < A ≤ B ≤ 100 000
• Suma lungimilor intervalelor din toate seturile unui test nu va depăși 100 000.
• Pentru rezolvarea corectă a cerinței 1, se acordă 20% din punctaj, pentru cerința 2 se acordă 40% din punctaj, iar pentru cerința 3 se acordă 40% din punctaj.
• Pentru teste în valoare de 30 de puncte, N ≤ 50, B ≤ 1000 și suma lungimilor intervalelor din teste nu va depăși 10 000

Exemplu