Multisum

multisum

== include(page="template/taskheader" task_id="multisum") ==

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).
 
h2. 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.

Poveste şi cerinţă...

h2. 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.

Fişierul de intrare $multisum.in$ ...

h2. 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.

În fişierul de ieşire $multisum.out$ ...

h2. Restricţii şi precizări

h2. Restricţii

* $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$

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. multisum.in |_. multisum.out |_. Explicaţie |
| 1 1
50 60
| 5
| Există un singur set de date. Se rezolvă cerinţa 1.
Descompunerile maximale ale numerelor din interval au unele 4
termeni, altele 5 termeni. Deci cel mai mare număr de termeni este 5
(şi acesta se obţine pentru numerele 55, 57, 58 şi 59).
|
|1 2
50 60
| 4
|Există un singur set de date. Se rezolvă cerinţa 2.
Numerele care se pot descompune într-un număr maxim de termeni
sunt 55, 57, 58 şi 59. Deci sunt 4 numere care admit o descompunere
maximală.
|
|1 3
50 60
|55
|Există un singur set de date. Se rezolvă cerinţa 3.
Cele 4 numere care admit descompuneri maximale sunt:
55=1+2+4+16+32, 55=1+2+4+12+36, 55=1+2+4+8+40
57=1+2+6+12+36, 58=1+3+6+12+36, 59=1+2+8+16+32
Cea mai mică sumă din punct de vedere lexicografic este
1+2+4+8+40 şi ea corespunde numărului 55.
|
|3 3
50 50
10 13
16 17
|50
11
17
|Sunt 3 seturi de date. Se rezolvă cerinţa 3:
Intervalul [50, 50] conţine doar numărul 50 care admite o singură
descompunere maximală (cu 4 termeni) şi aceasta este minimă din
punct de vedere lexicografic.
Dintre numerele din intervalul [10,13], numerele 10, 11 şi 13 admit o
descompunere cu un număr maxim de termeni (3 termeni), dar o
descompunere maximală a lui 11 (1+2+8) este minimă din punct de
vedere lexicografic.
În intervalul [16,17] numerele admit câte două descompuneri
maximale : 16=1+3+12, 16=1+5+10, 17=1+2+14, 17=1+4+12, iar
descompunerea minimă din punct de vedere lexicografic este 1+2+14
şi corespunde valorii 17.
|

table(example). |_. multisum.in |_. multisum.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="multisum") ==