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 trei 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 patru termeni ale lui 27 (2 > 1).
Cerința
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 de intrare 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 de ieșire 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 ≤ 10002 < 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ța2se acordă40%din punctaj, iar pentru cerința3se acordă40%din punctaj. - Pentru teste în valoare de
30de puncte,N ≤ 50,B ≤ 1000și suma lungimilor intervalelor din teste nu va depăși10 000.
Exemplul 1:
multisum.in
1 1 50 60
multisum.out
5
Explicație
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).
Exemplul 2:
multisum.in
1 2 50 60
multisum.out
4
Explicație
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ă.
Exemplul 3:
multisum.in
1 3 50 60
multisum.out
55
Explicație
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.
Exemplul 4:
multisum.in
3 3 50 50 10 13 16 17
multisum.out
50 11 17
Explicație
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema multisum:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
int main() {
ifstream cin("multisum.in");
ofstream cout("multisum.out");
int N, TYPE; cin >> N >> TYPE;
vector< pair<int, int> > V(N);
int maxB = 3;
for (int i = 0; i < N; ++i) {
cin >> V[i].first >> V[i].second;
maxB = max(maxB, V[i].second);
}
vector<int> from(maxB + 1, 0), max_chain(maxB + 1, 0);
vector<int> first(maxB + 1, 0);
max_chain[1] = 1;
from[1] = 1;
first[1] = 1;
int best = 0;
for (int i = 1; i <= maxB; ++i) {
if (max_chain[i] == 0)
continue;
for (int j = i * 2; j < maxB; j += i) {
if (max_chain[i] + 1 >= max_chain[j + 1]) {
max_chain[j + 1] = max_chain[i] + 1;
from[j + 1] = j / i;
first[j + 1] = 1;
}
}
}
for (int i = maxB; i > 0; --i) {
best = max(best, max_chain[i]);
for (int j = i * 2; j <= maxB; j += i) {
if (max_chain[i] > max_chain[j]) {
max_chain[j] = max_chain[i];
from[j] = j / i;
first[j] = j / i;
}
}
}
vector<int> index(maxB + 1, -1);
index[1] = 0;
index[2] = 1;
for (int i = 2; i <= best; ++i) {
vector<int> aux;
for (int j = 1; j <= maxB; ++j)
if (max_chain[j] == i)
aux.push_back(j);
sort(aux.begin(), aux.end(), [&](int pos1, int pos2) {
if (first[pos1] != first[pos2])
return first[pos1] < first[pos2];
if (from[pos1] != from[pos2])
return from[pos1] < from[pos2];
return index[pos1 / from[pos1]] < index[pos2 / from[pos2]];
});
for (int i = 0; i < int(aux.size()); ++i)
index[aux[i]] = i;
}
for (auto &q : V) {
int a, b; tie(a, b) = q;
int best = 0;
int count = 0;
int lexicographic_minimum = a;
for (int i = a; i <= b; ++i) {
if (max_chain[i] > best) {
best = max_chain[i];
count = 1;
lexicographic_minimum = i;
} else if (max_chain[i] == best) {
++count;
if (index[i] < index[lexicographic_minimum])
lexicographic_minimum = i;
}
}
if (TYPE == 1)
cout << best << "\n";
else if (TYPE == 2)
cout << count << "\n";
else
cout << lexicographic_minimum << "\n";
}
} Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2196 multisum
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2196 multisum de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!