268 ABC

[ditzone]

Aici puteţi discuta despre problema ABC.

[•Viksen]

Gresesc eu undeva la problema asta de iau 0. Primesc WA pe unele teste, dar unele fac shi TLE. Nu pricep cum iau TLE pe o rezolvara O(n*log(n))... Pot posta ideea mea de rezolvare ca sa imi spuneti macar daca merita sa mai incerc sau nu?

[•wefgef]

poate ca iti intra undeva prin ciclu infinit, de aia iei TLE.

oricum, spune ideea sa vedem 

[•pheon23]

am si io o nelamurire cu privire la solutia oficiala 

cum adica:

Cod:

 ' Bineinteles, nu este nevoie sa aplicam fiecare operatie in parte, ele vor fi aplicate toate in acelasi timp.'

10nx anticipat   

[andreit1]

Pornesti de la cel mai mare spre cel mai mic( in cazul in care suma totala e mai mica decat C) si in loc sa adaogi 1 de mai multe ori, adaogi deodata delta( sau cat a mai ramas). Astfel ai o singura operatie de adougare pt fiecare numar din sir, deci O(N) pentru delta fixat.

[•Viksen]

pey...eu am ordonat crescator, am luat-o de la cel mai mare la cel mai mic. Daca mai trebuia sa adun d ca sa obtin suma ceruta shi eram pe elementul a(i) atunci elementului a(i) ii minimul dintre d div i si b-a(i); apoi din d scadeam cat am pus lui a(i) shi treceam la a(i+1);
dupa aceea le ordonam la loc cum erau la inceput

[•sakka]

            Nici mie numi iese nicicum cu formula d:=a+min(d[i-1]-a,s div (n-i+1)),1<=i<=n.

[•skyel]

mie orice as face imi da WA si am O(N), plus k p final imi da si TLE, dak ar putea sa imi dea cineva niste teste verificate cu o sursa de 100 i'd be extremely grateful

[•Protoman]

salut! am facut o sursa ce ia la rand toate numerele din sir si aduna delta sau delta +1 daca rezultatul < B daca nu il face B si scad din diferentza sumelor pe delta ... am facut multe multe multe teste...si toate miau dat ... dar cand o trimit iau 0 puncte ... pana acum luam si tle dar am reusit sa scap de el .... acu iau numai WA.....puteti pune niste teste sa vad unde gresesc....sau sa imi dati un hint la ce ar fi gresit in algoritmul meu?

am gresit asta prima data.... nu am vzt ca trebuie distincte .... dar am vzt dar tot 0 luam .... am fkt nijte modificari si am luat 40 momentan . p.s.:ms de teste nu mi-a mers ultimu.... mi-a dat un 0 pacolo 

[•fireatmyself]

in:

Cod:

22 32 393
19 28 5 26 23 12 14 21 20 22 30 31 4 9 11 15 17 29 16 25 24 13

20 31 303
1 8 5 6 23 12 14 21 20 22 2 3 4 9 11 15 17 29 16 25

12 37 169
1 17 2 4 13 15 7 8 10 9 12 11 

9 17 55
1 2 4 3 15 7 8 10 9

out:

Cod:

18 27 4 25 22 11 13 20 19 21 29 31 3 8 10 14 16 28 15 24 23 12 

3 10 7 8 25 14 16 23 22 24 4 5 6 11 13 17 19 31 18 27 

6 22 7 9 18 20 12 13 15 14 17 16 

1 2 4 3 15 6 7 9 8

Sper sa te ajute. Vezi sa nu gresesti atunci cand afisezi. (nu afisezi sirul D in oridinea sortarii lui A, ci in ordinea data de sirul initial, din input)

Later edit: cu placere

[•mlazari]

Cred că ar trebui să se menţioneze că elementele şirurilor A şi D sunt nenule.

[•valentin50517]

Indicati va rog ca elementele trebuie sa fie strict mai mari ca 0, fiindca eu luam 40 puncte si nu intelegeam de ce