infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 04, 2007, 14:07:46



Titlul: 318 Buline
Scris de: Adrian Diaconu din Martie 04, 2007, 14:07:46
Aici puteţi discuta despre problema Buline (http://infoarena.ro/problema/buline).


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 04, 2007, 16:02:12
Problema asta e asemanatoare cu secventa.Deosebirea e ca nu se da k.


Titlul: Răspuns: 318 Buline
Scris de: Bogdan-Cristian Tataroiu din Martie 04, 2007, 17:06:14
Nu e nevoie de deque-uri aici, spre deosebire de secventa.


Titlul: Răspuns: 318 Buline
Scris de: Barca Cristian Mihai din Martie 05, 2007, 23:15:21
Ai putea sa faci si deque intradevar (eu asa am facut  :-'). Dublezi sirul, defapt mai adaugi primele N - 1 elemente la coada, faci sume partiale si astfel poti calcula secventa de suma maxima de lungime <= N (care reprezinta si raspunsul problemei).  :peacefingers:


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 06, 2007, 00:49:02
Cum adica sume partiale?


Titlul: Răspuns: 318 Buline
Scris de: Tabara Mihai din Martie 06, 2007, 08:10:58
Cum adica sume partiale?

Adica daca ai un sir de valori.
Cod:
sum[i] = sum[i-1] + a[i].
Se calculeaza asa
Cod:
sum[0] = 0;
for ( i = 1 i <= n; ++i )
      sum[i] = sum[i-1] + a[i];// a retine valorile sirului

( suma valorilor pana la pozitia i inclusiv ).Sumele partiale te ajuta sa afli care e spre exemplu suma intre doua valori [i,j] astfel
Cod:
( suma[i] - suma[j] ).


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 06, 2007, 09:21:53
Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu?
Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?


Titlul: Răspuns: 318 Buline
Scris de: Tabara Mihai din Martie 06, 2007, 09:33:54
Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu?
Si maximul ala ce ar trebui sa reprezinte ?

Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?
Te referi la secventa de suma maxima sau la sumele partiale ?
 


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 06, 2007, 10:13:13
Pai maximul sumei(nu asta trebuia sa afisezi)?
Citat
Te referi la secventa de suma maxima sau la sumele partiale ?
Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele:
-1 2 3 4 5.
s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam:
s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior).


Titlul: Răspuns: 318 Buline
Scris de: Tabara Mihai din Martie 06, 2007, 10:37:24
Pai maximul sumei(nu asta trebuia sa afisezi)?
Citat
Te referi la secventa de suma maxima sau la sumele partiale ?
Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele:
-1 2 3 4 5.
s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam:
s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior).


Poi tu zici bine, insa nu cred ca merge faza cu sumele partial pur si simplu calculate si afisat maximul.Trebuie sa calculezi secventa de suma maxima, care poate incepe oriunde in sir.
Dar ce spui tu e corect, numai ca nu asta e solutia problemei.

Si eu la "buline" lucrez acuma dar nu imi dau seama ce naiba gresesc. Imi da  "Suma Gresita" si am facut ca in solutie.  :-k Still working on that!  :-'


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 06, 2007, 10:47:38
Pai tu cum ai facut Barca Crisitian Mihai?


Titlul: Răspuns: 318 Buline
Scris de: Barca Cristian Mihai din Martie 06, 2007, 14:08:15
Pei dupa ce am pus in coada primele N - 1 elem si am facut sume partiale...in deque o sa-mi bag suma partiala minima la un pas astfel incat secventa sa nu-mi depaseasca N elemente...si la fiecare pas i aleg si smax = MAX(S[ i ] - St[s1], smax) (unde St este deque-ul meu iar s1 primul pivot, pozitia sumei partiale minime, iar S este vectorul de sume partiale). In ce priveste constructia deque-ului ar trebui sa incerci pe o foaie sa vezi cum sta treaba.  :peacefingers:

Ca sfat ti-as zice sa lucrezi problema Secventa...


Titlul: Răspuns: 318 Buline
Scris de: Iacob Eduard din Martie 06, 2007, 22:06:07
Chiar la asta lucram  :wink:


Titlul: Răspuns: 318 Buline
Scris de: Florian Marcu din Martie 11, 2007, 20:24:03
Am gasit aproximativ aceeasi rezolvare k Barca Cristian Mihai.....da` iau 0 puncte :oops: o sa mai incerc:weightlift: :roll:


Titlul: Răspuns: 318 Buline
Scris de: Radu Zernoveanu din Martie 20, 2007, 16:50:00
nu inteleg de ce iau numai 80 de puncte  :?
am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n ,  dar nu merge decat pe 8 teste  ](*,)


Titlul: Răspuns: 318 Buline
Scris de: Gabriel Bitis din Martie 29, 2007, 17:27:49
eu iau doar primele 3 teste apoi imi da SIGSEV.. care e problema?? imi explica cineva si mie?


Titlul: Răspuns: 318 Buline
Scris de: Codrea Marcel din Martie 29, 2007, 17:37:56
http://infoarena.ro/documentatie/evaluator

Cod:
11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.


Titlul: Răspuns: 318 Buline
Scris de: Florian Marcu din Februarie 09, 2008, 14:19:53
nu inteleg de ce iau numai 80 de puncte  :?
am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n ,  dar nu merge decat pe 8 teste  ](*,)

La fel patesc si eu. Iau WA pe testele 8 si 9. Poate cineva sa imi spuna ce as putea gresi? Pe testele mele imi da corect.


Titlul: Răspuns: 318 Buline
Scris de: Andrei Misarca din Aprilie 25, 2008, 21:12:56
Si eu patesc tot asa  ](*,)

LE : Mi-am gasit greseala... acu iau si io 100 :yahoo:


Titlul: Răspuns: 318 Buline
Scris de: Adrian Draghici din Martie 02, 2009, 19:29:22
cred ca este o greseala in exemplu, la ordinea in care sunt asezate biletele.. sau nu am inteles eu bine.


Titlul: Răspuns: 318 Buline
Scris de: Florian Marcu din Martie 02, 2009, 19:33:32
Nu ai inteles tu bine.  :)

[ Ti-as explica, daca ai spune cum 'intelegi' tu. ]


Titlul: Răspuns: 318 Buline
Scris de: Adrian Draghici din Martie 02, 2009, 20:23:18
a, scuze. ma derutase numerotarea de la explicatie, credeam ca reprezinta numarul de buline :)


Titlul: Răspuns: 318 Buline
Scris de: Sergiu-Ioan Ungur din Martie 23, 2009, 20:52:35
Exista vreun caz particular? Nu stiu de ce pic testele 8 si 9. Imi da suma gresita. Chiar nu stiu ce am putut gresi :-k. Daca imi poate da cineva vreun test mai dubios i'as fii recunoscator.


Titlul: Răspuns: 318 Buline
Scris de: Florian Marcu din Martie 23, 2009, 21:18:21
Eu picam testele 8 si 9, daca atunci cand faceam subsecventa de suma maxima, in for, puneam   "if(a[  i ] <= 0 ) " in loc de " if(sc<=0) ". [ if-ul ala care reseteaza suma curenta, daca aceasta este negativa]. Vezi, poate faci si tu aceeasi greseala.  :)


Titlul: Răspuns: 318 Buline
Scris de: Sergiu-Ioan Ungur din Martie 26, 2009, 08:52:47
Mersi oricum, dar eu fac cu sume partiale :-k.
[later edit]
A rezolvat cineva problema calculand secventa de suma minima?


Titlul: Răspuns: 318 Buline
Scris de: aladin aladinn din Iulie 23, 2009, 20:59:03
Cineva care a facut problema de 100 poate sa imi trimita un test mai mare apropiat de limite ca nu pot sa imi dau seama ce gresesc...sau un hint cum sa fac...iau doar 20,si iau testele pe care nu le iau cei cu 80 :-k


Titlul: Răspuns: 318 Buline
Scris de: Cotirlea Anamaria din Octombrie 05, 2009, 17:54:05
Si eu am probleme cu testele 8 si 9. Cum le-ati rezolvat? Nu-mi dau seama ce are.  :sad:


Titlul: Răspuns: 318 Buline
Scris de: UBB Bora Dan din Septembrie 25, 2012, 18:41:35
Sal.. stie careva de ce imi zice evaluatorul:
Cod:
Contactează autorul problemei: A apărut o eroare în rularea evaluatorului pe testul 1: Killed by signal 11(SIGSEGV).: timp 0ms: mem 248kb 
?


Titlul: Răspuns: 318 Buline
Scris de: Visan Radu din Septembrie 25, 2012, 18:51:39
Pune numele fisierelor corect.  :-'


Titlul: Răspuns: 318 Buline
Scris de: Strimbu Alexandru din Decembrie 22, 2013, 19:49:51
Am incercat sa rezolv problema fara deque, folosind subsecventa de elemente consecutive de suma maxima, dar iau doar 20 de puncte (pe testele carora celorlalti nu le merge).
Cod:
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

int a[400010];

int main()
{
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    int n,i,x,y,s=0,p,l=0,smax=INT_MIN,pmax=0,lmax;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        if(y==0)
            a[i]=a[i+n]=-x;
        else
            a[i]=a[i+n]=x;
    }
    p=1;
    for(i=1;i<=2*n;i++)
    {
        s+=a[i];
        l++;
        if(s>smax)
        {
            if(l+p-1>n+p-1)
                break;
            smax=s;
            pmax=p;
            lmax=l;
        }
        if(s<=0)
        {
            if(i>n)
                break;
            p=i+1;
            l=0;
            s=0;
        }
    }
    fout<<smax<<" "<<pmax<<" "<<lmax;
    return 0;
}


Titlul: Răspuns: 318 Buline
Scris de: Dinu Radu din Decembrie 23, 2013, 12:59:52
Iei doar 20 de puncte fiindca in rezolvarea ta poti sa iei un element de mai multe ori , lucru nepermis in problema . De exemplu cand ai toate numerele pozitive , sursa ta va lua fiecare element de 2 ori ceea ce e gresit. Deaia subsecventa ta trebuie sa aiba lungime cel mult n.


Titlul: Răspuns: 318 Buline
Scris de: Strimbu Alexandru din Decembrie 23, 2013, 18:57:45
Programul meu nu cred ca ia un numar de mai multe ori. Am verificat pentru toate numerele pozitive.
Folosesc ca si conditie:
Cod:
if(l+p-1>n+p-1)
                break;


Titlul: Răspuns: 318 Buline
Scris de: Dinu Radu din Decembrie 23, 2013, 21:36:57
Da , nu m-am uitat in sursa ta , am banuit doar. Oricum la tine in sursa mi se pare foarte ciudat faptul ca iesi cand subsecventa ta depaseste lungimea n . Pot exista si alte subsecvente, de lungime mai mica sau egala cu n si de suma mai mare ca smax care se termina in elementul la care tu iesi din for sau dupa el . De-aia ar trebui sa faci cu un deque. Nu prea cred ca ai cum sa faci fara.