infoarena

Aici puteţi discuta despre problema Sume (http://infoarena.ro/problema/sume).

Asta cu ce se face? 8-[

cu tastatura :D
se bazeaza p nijte obs matematice. enjoy  :wink:

M-ai spart varule...nu mi-as fi dat seama...bine c-am dat peste tine si m-ai luminat...

daca stiai cum se face atuncea de ce ai mai postat pe acest topic?ca sa-ti creasca post-urile probabil  :roll:

in ce ordine trebuie puse numerele in fisierul de iesire ?

trebuie sa le pui intr-o ordine , astfel incat daca  iei toate perechile de numere si le aduni, ar  trebui sa iti dea sumele din fisierul de intrare
oricum  exempele  din  enunt  sunt de mare  folos  :)

Adica (pentru exemplul din enunt) daca afisezi "1 2 3" iei 0 puncte pentru ca din sirul "1 2 3" Haralambie ar fi obtinut "3 4 5", si nu "4 5 3" cum ti se da din fisierul de intrare.

nu cred ca e gresit  daca  afisezi  " 1 2 3 "   pt ca haralambie formeaza toate perechile de numere,  si  oricare  ar  fi  ordinea numerelor  tot  aceleasi perechi se formeaza,  acum depinde si de evaluator  cum  testeaza solutia

Poate sa-mi zica si mie cineva testu 3 sau 6, k imi da WA.
Faza e, ca in rest, imi merge pt fiecare test. [-o<  :-s  :-#  :-&

Va rog!!!! :^o

Ai tratat cazul cand nu exista solutie?

Mersi! Asta era problema!  \:D/ You're  8)



Da'tot nu-mi iese. Zi si mie un caz cand e fara solutie!

nu-mi merge testul 6 (cu -1).. nu exista solutie cand 1+8*p nu e patrat perfect.. mai este alt caz?

Am testat cu un evaluator al meu pe teste generate aleator. Merge perfect. Problema e ca programul meu le afiseaza in ordine crescatoare (nu le ordonez dupa, asa le produce algoritmul). Cred ca evaluatorul la problema asta ar trebui schimbat! Doar raspunsurile "2 3 1" si "1 2 3" sunt acelasi lucru...
  Astept comentarii... :)

  Filip b.

Evaluatorul nu trebuie schimbat, e bun!.. De multe ori testarea cu teste random nu garanteaza punctaj maxim, fiindca pot exista multe cazuri speciale.. deci, nu te mai grabi sa presupui ca evaluatorul e gresit si cauta-ti greseala.

Ok, sorry... O sa-mi caut greseala... Desi iau in continuu 10 pct (doar la testele fara solutie!) iar cu evaluatorul meu imi da impecabil! Nu e nik... Poate imi dau seama ce are ( de nu imi ia NICI MACAR un test cu solutie )...
 
              Filip b.

Hm... Mare pacat ca nu imi da pentru nici un test cu solutie... Oricum, eu o facusem sa imi determine un raspuns indiferent in ce ordine erau scrise numerele la intrare.. Adica nu stiam dinainte ca ordinea era ceva de genul X1 + X2, X1 + X3, X1 + X4, X2 + X3, X2 + X4, X3+X4... Si ca sa aflu X1 pur si simplu calculam (v[1]+v[2]-v[4])/2...

:oops: MII DE SCUZE  :cry: ... cineva in graba caracteristica a uitat sa afiseze n-ul la inceputul fisierului de iesire...  :oops:

btw, nu uita ca exista butonul de edit!

si eu am probleme cu testu 6....nustiu de ce...

Ai testat sa vezi daca numerele care ti le genereaza programul dau toate sumele?                
de exemplu pentru:

nu exista rezultat intreg.

Declari o variabila de tip bool, si daca (x + x[j] != s[k]) var = false.
Evident, pentru var = fals, trebuie sa afisezi -1.

Later edit: Eu am pus aceasta conditie pe langa aceea ca N trebuie sa fie natural.

Spor :D

dap, stiu..stiu...ca nu-s...dap mah stiam de conditia asta...dap faza e ca daca pun conditiunea asta nu iau 4 teste de la 13 incolo dar celelalte le iau daca nu o pun si mai curios iau toate testele da nu iau testu 6.. . ff curios... creca ceva nu e bun in algo meu...

NU-ti ies 4 teste daca pui functia asta in sensu ca primesti WA sau TLE?

WA, bineintles...ca din timpm n-am cum sa ies////

Inseamna ca e bine  :)  . poate nu ai implementat bine functia care iti calculeaza sumele si iti afiseaza -1 in mai multe cazuri.

eu am rezolvat problema considerand k numerele din fisierul de intrare sunt date intr-o ordine aleatoare. cred k e mult mai interesant asa...

Da! Si eu am rezolvat la fel...

da... asta a fost intentia initiala... insa am lasat testele cam generoase :)

ar putea sa-mi dea si mie cineva o idee despre cum ati rezolvat, varianta generala adica cand numere sunt in ordine aleatoare..?

e ceva asemanator momentan la agora :P.

Si eu credeam ca nu te prinzi...  :D

am obtinut 95 p...imi da WA la T6.....e ceva special cu el?  pls help  #-o

Pentru a testa validitatea solutiei, comparati toate combinarile din numerele obtinute cu cele date in fisierul de intrare. Nu mai trebuie nimic altceva, si se incadreaza si in timp.

ok asta era mersi  =D>

cum se face asta pe cazul in care sumele nu sunt date in ordine?? eu am facut un back si nu am luat decat 15 puncte. Exista o rezolvare polinomiala?? dak nu atunci ce optimizari ar trebui facute asupra backului??

mie imi da o eroare ciudata la testul 3:

Rulez testul 3: eroare: timp 8ms: mem 256kb: Killed by signal 11(SIGSEGV).: 0 puncte

In rest toate bune si frumoase, 95 de puncte.
wtf??  ](*,)

si eu iau 95 de pcte cu un wa....
@Savin Tiberiu : eu am scris pe foaie mai multe exemple si am gasit o regula si pe baza aia am implementat...

ok, asta e o problema prea simpla sa nu iau 100 de p la ea...
ce are testul 6, ca vad ca toata lumea are probleme cu el? E singurul la care primesc WA.
Am pus conditia aia cu 1+8*n sa fie patrat perfect, daca nu e, afiseaza direct -1, daca e, atunci cauta suma cu algoritmul meu, si daca nu o gaseste, afiseaza -1.
Deci, exista o suma cu proprietatea respectiva... De ce primesc WA? (cu restul merge, am 95p)...
Vreo idee? Ce am uitat sa pun pe-acolo? :)

Si eu am stat vreo 10 minute si tot nu am reusit sa rezolv testul 6 cum trebuie. :sad:
Am luat 100 dupa ce am facut cum a spus ag3nt_junior  :wink:

asa nu mai e nevoie de nici un caz particular de tratat, nici o impartire dubioasa etc.
 :thumbup:

eu caut prima data cate valori are sirul initial ,(x=nr valorilor)... apoi, aflu prima valoare a sirului p=v[2]-v[1] (v- vectorul in care retin valorile citite), afisez aceasta valoare dupa care afisez, de la 1 pana la x-1, v-p.... pe exemplele din enunt si pe inca vreo 3 date de mine merge, totusi.. iau WA...

Pentru primul exemplu nu cred ca-ti da bine cum zici tu:
3
4 5 3

Daca primul element e p = 5-4 = 1 tu afisezi urmatorul sir, daca te-am inteles eu bine:
1 4 2

Gandeste-te cum poti formula problema matematic.

ups.. srry.. am gresit explicatia  :aha:.. fac diferenta dintre a doua si prima valoare.. aflu primul termen v[1]-p.. apoi din primele x-1 valori scad primul termen...

3
4 5 3

primul element e v[1]-(v[2]-v[2])     4-(5-4) = 3

si apoi din 4 si 5 il scad pe 3... => 3 1 2

Pai uite, pt 3 1 4 de exemplu tu ai:

primul termen: 1-3 = -2 , 3-(-2) = 5

5, -2, -1

Care nu e corect.

si care e solutia pt 3 1 4 ?

-1

Dar, din pacate, iei 100 cu un program care nu trateaza cazul cand numerele sunt nule :P.

Cred ca a uitat sa puna N.

3
3 1 4

Raspuns

3
0 3 1

desi in enunt se precizeaza ca numerele initiale sunt nenule... atunci solutia ar fi 0 3 1

Initial si programul meu afisa 0 3 1. Dar, daca ne luam dupa enunt, un raspuns care contine 0 nu este corect. Desi ambele variante iau 100 de puncte... ar trebui modificate ori niste teste ori enuntul.

asta cred ca ar trebui precizat la sectiunea imbunatatire teste.... oricum.. nu e posibil ca ideea mea sa ia macar cateva teste????

Nu sunt chiar asa de slabe testele :D.

Ideea nu e buna, formuleaza pe foaie matematic problema si o sa te prinzi :).

Am citit tot topicul, insa nu am reusit sa rezolv problema. Mi`am dat seama ca e vorba de un sistem de ecuatii, cu 3 ecuatii si 3 necunoscute. Sistemul e de forma

   a+b=x;
* a+c=y;         , unde x,y,z le cunoastem [ fiind sumele din fisierul de intrare ].
   b+c=z;

De aici ies foarte usor cele 3 necunoscute. De ex. a= (x+y-z) / 2. Formula asta cred eu k as putea sa o utilizez pt aflarea primului termen. Dar avand primul termen, nu observ ce as putea face. Poate cineva sa ma ajute?

Apoi stii b+a, c+a, ... si poti afla foarte usor restul numerelor.  :fool:

O sa ma mai gandesc sa vad. Probabil asta e sol de 100. Intre timp am facut ceva in genu:

-Am aflat cate numere are sirul initial [ am gasit o formula ] [ sa notez cu n cate nr are acest sir]
-Aflu primul termen folosind (v[1]+v[2]-v[3])/2
-Afisez primul termen apoi parcurg for i=1, n-1 si afizez v[ i ] - primul nr
A..da..si iau in considerare sa afizez -1 daca exista un v [ i ]  - primu `nr <=0

Cu o asfel de solutie iau 40 de puncte. Poate cineva sa `mi dea un caz care sa contrazica calitatea solutiei mele?

LE: Am gasit unde bushea. O sa mai incerc.

de fapt.. nu e bine cum zieti voi..(multumesc lui Marcu Florian pt k m-a corectat)
a=(v[ 1 ]+v[ 2 ]-v[ m ])/2;(m=numarul de numere din fisierul .out)
dak poate sami gaseasca cineva contra argument sunt mai mult decat fericit.

Tot pe forumul asta am vazut pe undeva, ca un mare intelept roman [nu stiu exact cine, insa poate imi spuneti voi numele  :D ] a zis: "Nu intreba de ce e gresit, ci demonstreaza de ce e corect." [sau cel putin cam asta era esenta, din ce imi amintesc eu].

ps: Din moment ce atata lume a luat 100 cu ideile de mai sus, nu vad de ce acele idei ar fi gresite.

iau 95 puncte
numi iese testul 3
da TLE

later edit: am uitat sa zic ca am folosit ce sa zis si am verificat sa nu deie -1 si tot nu merge

idei?

Iau "Killed by signal 8" pe toate testele...care poate fi cauza?...ma poate ajuta cineva??E prea multa sau prea putina memorie declarata?? :'(

Vezi ca imparti ceva la 0, sa nu imparti suma totala la o variabila pe care nu ai initializat-o.

sumele sunt date in ordine sau nu k sa nu ma apuc sa fac rezolvarea degeaba asa:P?

Da. Se vede asta din exemple.

S-ar putea modifica limita de timp la 0.1s  :-'

Cat timp nu exista solutii "proaste" care sa ia 100, nu vad de ce am face asta...

Ca sa reevaluam aproape 1000 de joburi?

Ok problema mi-a iesit in final. La inceput am pus un 1000 ca lavoare la vectorul in care citeam numerele din fisier. Era prea mic stiu. Dar luam 20 de puncte si mergea testul 6. Cand am marit la 25001 nu mai mergea testul 6. Bun Ma gandesc ca in fisierul de intrare intra un p = enorm si apoi sa zicem multe numere egale intre ele astfel incat depasea 1000 si era fragmentata secventa de numere de catre vector. Astfel atunci cand calculam numerele care trebuiau afisate programul stia doar 1000 de numere si nu se incurca cu secventa nasoala. Asta e? Totusi care e treaba. De ce pe 20 de puncte(1000 elemente maxime) mergea, iar pe 95 pct(25001 elemente maxime) nu mergea?  

Exista o explicatie logica...

Nu pot sa ti-o dau pentru ca ar trebui sa iti spun structura testului 6, iar acest lucru nu este permis.

Gandeste-te si poate iti dai seama singur ;)

ok, dar am rezolvat problema. am luat 100. oricum ceea ce am spus eu inainte e corect?

Nu stiu, mi s-a parut postul tau incoerent si nu am avut rabdarea sa il citesc atent.

nu inteleg care-i treaba cu 'secventa nasoala', dar in mod sigur iti trebuiau retinute toate cele 25 000 de numere din fisier pentru a rezolva, corect, problema. Wef are dreptate, postul tau este incoerent. poate daca mai explici mai clar, te-am putea ajuta.

Salutare... Am rezolvat zic eu bine problema , dar iau 95 de p... Am aflat cate numere sunt, suma lor, primul numar, precum si restul numerelor.

Am facut "proba" - am verificat daca adunand perechile de nr obtinute de mine se obtine sirul citit... Am facut de asemenea verificari si tot busesc testul 3. Din cate am impresia, raspunsul la T3 trebuie sa fie "-1" si nu inteleg ce alt caz special as fi putut tratat atunci cand stabilesc validitatea datelor de intrare... va rog , daca puteti, sa ma lamuriti. nu imi dau seama ce as putea gresi  ](*,) ](*,) ](*,)


LE : Iertati noobimea... Se pare ca nu afisa -1 in cea mai stupida exceptie... Pardon my foolness. Luai suta  :yahoo:

cum fac sa aflu cate numere sunt :)

Ia'ti cateva exemple (de la 2 la 10 numere de exemplu), si fa suma dintre fiecare doua, sa vezi cate numere obtii. E foarte usoara formula care trebuie dedusa.

multumesc. o sa vad:)

ok am gasit regula da voi km atzi mers invers
adik dak jtii nr final de elemente
sal afli pe cel initial???

Citeste ce s-a scris in topic, sau gandeste-te singur, Si scrie calumea, nu suntem pe mess, incearca sa fi coerent in posturi daca vrei sa te ajute cineva.

salut, as putea totusi sa-ntreb care este acea(citez) "stupida exceptie" la testul 2 pentru ca imi da TLE si nu prea imi dau seama care ar fi problema
imi explica pls cineva? ms

Nu afisezi -1 cand nu exista solutie.

Am citit topicul si am luat in calcul toate obs facute mai sus, insa nu inteleg de ce la testul 6 iau WA.
afisez -1 daca:
1. sqrt(n*8+1) nu apartine lui N
2 (s[1]+s[2]-s[n])/2 nu apartine lui N , n=nr de elemente din sirul initial
3 daca un termen al sirului initial e < 0
Nu vad unde as mai putea modifica sirul... :-k
Unde gresesc? :-/

incearca sa si verifici dupa ce ai construit solutia, daca executand pasii descrisi in problema ajungi la sirul initial... poate acolo e problema... eu verific si afisez "-1" in cazul in care gasesc o greseala in solutie...

Felicitari celor care au facut testul 6! =D&gt; M-am chinuit la el mai mult de 30 de minute  #-o :fighting: Oricum am luat 100 :winner1:

imi puteti da va rog niste indicii asupra testului cu numarul 3 pentru ca iau TLE aprox 252 ms fata de toate celelalte teste pe care le am corecte si le termina programul in max 8-12 ms;  am incercat deja totul nu mai stiu ce sa mai verific

Cat iti da pe:

da ms am gasit instantaneu greseala cu exmplul asta nu-mi vine sa cred cat de simplu era

ps: eu am verificat din greseala daca 1+p*8 e patrat perfect atunci afiseaza -1, asha mi se-ntampla intotdeauna :| ... graba

Poate cineva sa dea mai multe exemple pentru problema asta ?

Pentru primul exemplu daca afisez :
4
1 3 4 2

este ok ?

De ce testele din exemplu nu sunt in testul de verificare al problemei ?  :fighting:

Vreau sa las aici un comentariu, poate ajuta pe cei cu 95 puncte, incorect pe testul 6 : aveti 2 variante sa vedeti ca pe acel test rezultatul este -1 : ori faceti exact ce face evaluatorul, adica verificati pentru fisierul .out suma oricaror doua numere si ar trebui sa dea EXACT vectorul din fisierul de intrare (daca nu afisati -1 si asta e), sau puteti face o chestie pe care, daca o sa studiati mai atent o sa vedeti ca e corecta : suma numerelor din fisierul de intrare este divizibila cu suma numerelor din fisierul de iesire. Astfel, daca avem sumin si sumout, daca sumin % sumout != 0 afisati -1, altfel afisati solutia. Sper ca va ajuta  :thumbup:.
@super, nu e corect, vezi ca daca faci suma oricaror 2 elemente iti dau mai multe numere ;).

Numerele sunt date in ordinea:
x1+x2   x1+x3   x1+x4  ........  x1+xn
x2+x3   x2+x4   x2+x5  ........  x2+xn
:::::::::::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::
xn-1+xn

?

Da.  :D

Pentru testul 3 si 6 trebuie de verificat ca datele de intrare sa fie corecte.
Haralambie putea sa greseasca cand a scris pe foaie suma perechilor, si de aceea poate sa se obtina valori gresite.

Daca nu ar fi date in acea ordine ar fi semanat extrem de mult cu problema http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=527 , nu-i asa?

Daca numerele date sunt in ordine (x1 + x2, x1+x3, etc...) De ce nu se precizeaza asta in enunt? Mi se pare o observatie foarte importanta, si nu poti sa te iei dupa exemple pentru ca sunt multe probleme la care se dau exemple chiar unele cazuri particulare...

Intenția autorului era să genereze numerele din fișierul de intrare în ordine aleatoare.

Cum rezolv daca ordinea este random ?

1. determin n=numarul de numere din sirul initial
2. daca sirul initial este sortat crescator, atunci sirul final are subsecvente crescatoare de lungime n-1,n-2,...,2,1

primele trei numere din sirul initial le pot determina, da' nu stiu exact cum sa le determin pe restu

Testele la aceasta problema au fost imbunatatite.

Multumim lui Andrei Stanciu (http://www.infoarena.ro/utilizator/assa98) pentru ajutorul acordat.

Dupa modificarea testelor, mai sunt sumele in ordinea :
x1+x2, x1+x3, x1+x4.... x2+x3.....
sau sunt luate aleatoriu?

Sumele din fisierul de intrare sunt scrise aleator.

Ar trebui sa puneti la precizari ca numerele din fisierul de intrare sunt in ordine aleatoare. Eu m-am luat dupa comentarii si incerc de 2 zile sa fac problema cu numerele in ordine. Numai acum am ajuns la capatul comentariilor si vad ca nu mai sunt in ordine.

Multumim de atentionare. Se rezolva. :-)

Ordinea din fisierul de iesire are vreo importanta?

Ati updatat si ratingul pe stele la problema?
Cu noile teste nu mai e chiar de-o stea.

cum as putea afla numerele dupa ce aflu numarul de numere din fisierul de iesite?

 vezi diferenta dintre primele doua numere si iti dai tu seama dupa aia

apropo cum ai aflat numaru de elemente???

pai am obs faptul ca daca ai 6 numere in fisierul de iesire o sa faci sume de 5+4+3+2+1 si iti dau 15 perechi cum este in cel de intrare si am mai facut ceva obs si am reusit sa il aflu cate numere vor fi in cel de iesire folosindu-ma de cel de intrare

pai am obs faptul ca daca ai 6 numere in fisierul de iesire o sa faci sume de 5+4+3+2+1 si iti dau 15 perechi cum este in cel de intrare si am mai facut ceva obs si am reusit sa il aflu cate numere vor fi in cel de iesire folosindu-ma de cel de intrare. acuma sper ca este bine gandirea altfel corecteaza-ma ca sa refac.

ms de idee e foarte buna  :thumbup:

#include<iostream>
#include<fstream>
using namespace std;
ifstream f("sume.in");
ofstream g("sume.out");
int i,x,n,v[30000],y,z,t,r,a;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v;
        x=n;
        while(x!=0)
        {r++;
        x=x-r;}
        r=r+1;
    if(x<0)
        g<<-1;
    else
    {y=v[1];
    z=v[r];
    t=v[2];
    t=t-z;
    a=y+t;
    a=a/2;
    g<<r<<'\n'<<a<<" ";
    for(i=1;i<=r-1;i++)
        g<<v-a<<" ";}}
stie cineva de ce iau 0 ..pe exemplu merge :yahoo:  :angry: ](*,)

daca schimbi din while in care aflii nr de cifre din sirul intial
in lac de x!=0 cu x<=0
ar trebui sa iei 10 puncte

In 2013 parca problema a fost imbunatatita nu ? Numerele citite fiind acum perechi aleatori

Inainte numerele erau: de exemplu pt 4:   x1+x2 x1+x3 x1+x4 apoi x2+x3 x2+x4 si in final x3+x4
Intrebarea mea este: tot pentru 4 sunt complet aleatorii (x3+x4 x1+x3 x2+x4 ..etc) sau sunt la fel ca inainte, grupate ? dar totusi aleatori (x1+x3 x1+x2 x1+x4 si dupa x2+x4 x2+x3 si in final x3+x4)

Daca nu, problema este tot de o stea ?

Nu inteleg...
Ce perechi??? ](*,) :annoyed:

sa vad daca am inteles corect acum ordinea elementelor din fisierul de intrare nu mai este x1+x2,x1+x3,x1+x4,x2+x3,x2+x4 ...

ci poate fi in orice ordine aleatoriu sau e doar o alta ordine?

Orice ordine.

imi explica cineva cum ar trebui sa gasesc ordinea corecta?

Exista vreo problema daca le afisezi in alta ordine decat cea initiala ? ( adica le gasesc pe toate ,dar nu-mi dau seama cum sa le aranjez ca la inceput )

Am lasat si eu o rezolvare .... oricum as testa-o imi da rezultatul corect dar cand o urc aici imi da 0 puncte am verificat-o si cu exemplele de aici am generat si numere trece orice test aici ia 0 puncte si-mi zice WA




nu pot sa-mi dau seama ce este gresit .. scuze daca este prea evident si eu chiar nu vad o "banalitate"

Sincer, eu personal urasc problemele care par de mate xD

Se face cumva cautare binara dupa primul element(cel mai mic)?

Poate sa imi dea cineva o idee cum sa incep problema daca sumele sunt date in ordine aleatoare? ](*,)