Question

INFO
Cu ocazia Olimpiadei Naţionale de Informatică, toate drumurile care duceau la Roma, duc acum la Braşov. Drumarii, sub atenta îndrumare a lui Dorel, s-au întrecut pe sine şi s-au hotărât să monteze borne “kilometrice” din 100 în 100 metri. Peste noapte însă, din motive paranormale, unele borne au dispărut. Cunoscând numerele de pe bornele rămase pe fiecare drum spre Braşov, să se determine, pentru fiecare drum, un set de borne dintre cele care lipsesc astfel încât suma numerelor de pe borne să fie divizibilă cu 2017. Rezolvă problema şi vei ajunge cu bine la Braşov!
Date de intrare

Fișierul de intrare roadtooni.inconține pe prima linie numărul n, iar pe următoarele n linii primul număr de pe linie reprezintă numărul de borne rămase pe drumul respectiv, iar următoarele numere reprezintă numerele de pe bornele rămase.

Date de ieșire

Fișierul de ieșire roadtooni.out va conține pe linia i numărul de borne din set, urmat de setul de numere de pe bornele lipsă ale drumului i, care au suma divizibilă cu 2017, pentru orice ide la 1 la n.

Restricții și precizări

1 ≤ n ≤ 20

numerele de pe bornele montate sunt naturale nenule şi mai mici decât 2017

pe fiecare drum au rămas cel mult 500 de borne, inclusiv cea cu numărul maxim de pe drumul respectiv

borna cu număr maxim de pe fiecare drum este cel puţin 1600

punctajul unui test se distribuie uniform pentru fiecare drum din testul respectiv

Ma ajutati si pe mine?

Answer 1

Sa pornim cu cel mai simplu caz posibil: suma termenilor din set este de fix 2017, iar suma este formata doar din 2 termeni. Sa ne uitam in conditiile date de problema daca asa ceva e posibil.
Spune ca borna ramasa de valoare maxima are minimum valoarea 1600. Acesta este si cazul cel mai defavorabil, deoarece daca borna maxima ar avea o valoare mai mare de 1600, ai putea sa folosesti drept al doilea termen o borna lipsa din intervalul 1-417. Asa, trebuie sa iei borne lipsa de la 418 in sus
Apoi, pot sa fie maximum 500 de borne ramase. Cel mai defavorabil caz ar fi daca am avea 500 de borne ramase. Dar chiar daca ar fi toate si ar fi masate fie in intervalul 1101-1600 fie in intervalul 418-918 tot ar ramane suficiente borne lipsa pentru a forma suma de 2017 din doar 2 elemente(cele din intervalul 918-2100). Deci pentru o singura solutie este suficient sa avem 2 termeni pentru fiecare drum. 
Algoritmul necesar este cel de jos
#include <iostream>
#include <fstream>

using namespace std;

//initializam vectorul cu 0
int borne[2017];
int main(){
int n,nr_borne_ramase,borne_ramase[500],borna_max,i,ind_set,ind_borna,cauta_set;
ifstream fit("roadtooni.in");
ofstream fot("roadtooni.out");
fit>>n;
for(ind_set=0;ind_set<n;ind_set++){
fit>>nr_borne_ramase;
//borna maxima determinata in borna_max
borna_max=0;
for(i=0;i<nr_borne_ramase;i++){
fit>>borne_ramase[i];
//marcam in borne borna care a ramas cu 1
borne[borne_ramase[i]]=1;
if(borna_max<borne_ramase[i]){
borna_max=borne_ramase[i];
}
}
//stim de la inceput ca va fi un set din 2 borne
fot<<2<<" ";
//cat timp cauta_set este activ, adica 1
cauta_set=1;
//indicele de borna este cu 1 mai mic decat borna maxima ramasa
ind_borna=borna_max-1;
while(cauta_set==1){
//daca indicele bornei actuale si a celei pereche din suma
//sunt ambele 0, inseamna ca nu se regaseste printre cele ramase,
//deci am gasit o solutie

if(borne[ind_borna]==0&&borne[2017-ind_borna]==0){
cauta_set=0;
fot<<ind_borna<<" "<<2017-ind_borna<<endl;
}
//daca nu am gasit solutie, trecem la urmatoarea borna inferioara
ind_borna--;
}
//dupa ce am terminat verificarea pentru drumul i, reseteaza vectorul borne cu valori 0
//pentru a putea fi folosit la urmatorul drum
for(i=0;i<nr_borne_ramase;i++){
borne[borne_ramase[i]]=0;
}
}
return 0;
}