IT challenge

[p3tru]

Enunt:

Primesti un credit C la un magazin si vrei sa cumperi 2 obiecte. Mai intai te plimbi prin magazin si creezi o lista L cu toate obiectele disponibile. Din aceasta lista vrei sa cumperi 2 obiecte a caror valoare adunata este egala cu creditul primit. Solutie pe care o dai contine 2 numere intregi, indicand pozitia obiectelor in lista ta. (primul numar mic mai intai)

Date Intrare:

Prima linie de intrare da numarul de teste, N. N teste urmeaza. Pentru fiecare test va fi:

O linie continand valoarea C, creditul pe care-l ai in magazinul respectiv.

O linie continand valoarea i, numarul de obiecte din magazin.

O linie continand o lista cu i numere intregi, separate prin spatiu. Fiecare numar intreg P indica pretul unui obiect din magazin.

Fiecare test are exact o solutie.

Date iesire:

Pentru fiecare test, afiseaza o linie continand: "Cazul #x: " urmat de indicii celor 2 obiecte a caror pret insumat este egal cu creditul initial. Indicele mai mic trebuie afisat primul. (x ia valori intre 1 si N)

Limite:

5 <= C <= 1000

1 <= P <= 1000

Dataset mic (pentru A-small.in):

N = 10

3 <= i <= 100

Dataset mare (petru A-large.in):

N = 50

3 <= i <= 2000

Exemplu:

Intrare:

3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3

Iesire:

Case #1: 2 3
Case #2: 1 4
Case #3: 4 5

* Multumesc celor care doresc sa participe la acest concurs.

* Codul sursa trebuie sa aiba comentarii explicative

* Puteti sa o rezolvati in ce cod doriti...(post source)

FIsier: 2shared - download A.zip

Edited April 9, 2011 by p3tru

[cifratorul]

asta e challenge sau tema ta pentur acasa?

[wildchild]

ce conteaza?e un challenge,fie el tema,fie orice.cine vrea il face cine nu nu.

[p3tru]

asta e challenge sau tema ta pentur acasa?

La vazut pe alt site pe care cotrobai si mi s-a parut interesant sa-l postez si aici...

Si nu e tema pentru acasa, din pacate nu's la profil de genu care sa-mi dea teme tip mai sus (si nici nu-mi doresc)

ps; update fisier.

Edited April 9, 2011 by p3tru

[Patrunjel]

Sortezi elementele din L dupa pret.Cauti numai in portiunea in care ai elemente cu pret mai mic decat creditul (fiindca in rest n-are rost, plm).

Dupa aia bagi cu un backtracking daca nu te intereseaza timpu, daca nu o cautare binara, sau ceva mai calumea (da e destul de greu sa coci ceva pentru cautarea binara.

Tot pentru optimizare, sa tii cont ca daca ai ales deja un element cu pret >=decat jumatate din credit, nu mai are rost sa cauti decat in prima jumatate (adica iti actualizezilimita in care cauti, o faci credit-pretul_elementului_ales).Se aplica si pentru produsele la care ai pret <=decat juma de credit

Cea mai simpla metoda e : Sortezi, iei fiecare element in parte si ii faci o cautare binara (d & i) sa vezi cu cine se combina. Se poate si mai repede, da te complici aiurea.

*Poti sa te gandesti si cum adaptezi greedy aici, imi suna si a problema de greedy, numai ca trebuie sa te cacai oleaca.

*Ba nu, e fix problema de greedy ) (da se poate face si cum am zis mai sus, bagi si tu ce ti-e mai usor)

Scurt pe doi : Qsort -> cauti in elementele mai mici decat creditu (fiecare pe rand)-> daca elementu costa mai putin decat c/2 incepi de la coada (nu de la coada listei, de la coada elementelor care costa mai putin decat creditu), si cobori cu verificatu elementelor, pana la cel care costa credit-pretul_actual (ala, primu element pe care il iei direct).Daca e mai mare, incepi de la inceput si faci invers (cat cauti poti sa aplici cautare binara, da n-are rost...te cacai mult, creste posibilitatea sa ai baguri, si iti si lungesti sursa de-ampulea pentru 0.cateva secunde )

Complexitate vine nlogn la qsort, da la asta nustiu cum se calculeaza, ca difera mult in functie de intrare la cautarea aia...Oricum, e decenta

Edited April 9, 2011 by Patrunjel