mersi

jvm-ul sigur merge bine? e prima data cand tirmit solutii in Java si nu in C++, si imi tot spune ca nu coincide numele clasei publice cu numele fisierului sursa. Schimba cumva evaluatorul numele sursei cat o evalueaza? daca da, in ce il schimba?

deci... intrebarea e care e numarul maxim de coliziuni care pot aparea? (coliziune= moment in care doua sau mai multe fire incearca sa incrementeze variabila in aproape acelasi timp; daca asta se intampla variabila va fi incrementata numai de un fir, si anume de primul, sau nu va fi incrementata deloc? );

Multumesc mult amandurora!

buna! m-am tot gandit la problema asta, si as avea cateva idei:
1)daca fixez un sir si un 1 din el, sa spunem ca am x1y (x=nr de cifre din stanga lui 1 pe care l-am fixat, y= acelasi nr din dreapta)
  daca cele trei siruri date au lungimile a,b,c, atunci noi vrem
        x+t1*a+u1*b+v1*c=y+t2*a+u2*b+v2*c=min
   se cere acel min nr natural care se poate scrie sub cele doua forme de mai sus, cu t1,u1,...v2 naturale
  problema e ca nu stiu cum sa-l aflu si mai trebuie sa sa fixex un sir si un 1 din el
2)prima oara m-am gandit ca sol bruta ar fi cu o parcurgere in latime, dar mi-am dat seama ca nu merge, pt ca lungimile sirurilor nu sunt egale; as putea sa folosesc dijkstra, dar nu mi-e clar care e graful (sursa e sirul vid, dar de unde stiu cate destinatii am, trebuie sa pot sa tin vectorul de distante si nu stiu cum sa numerotez nodurile; la parcurgerea in latime as fi putut sa expandez nodurile pe pparcurs, fara sa stiu graful de la inceput);

mi-ar putea da cineva un hint de cum sa folosesc dijkstra aici? macar sa stiu cam la ce complexitate ar trebui sa ajung, ca sa stiu daca pot sa folosesc ideea cu fixatul unui 1

da, de aici era . mersi de ajutor!

eu nu inteleg o chestie legata de memorie: am la dispozitie 16384kB=16384*1024B
eu folosesc 3 vectori de int-uri si unul de char-uri: 16384*1024>1000000(3*4+1) . totusi mie imi da segmentation fault (pe calculatorul meu la fel: cand definesc nmax=1000 sau ceva mic, merge). are cineva vreo idee de la ce poate fi? nu cred ca algoritmul e de vina, l-am comentat si am lasat doar declaratiile, si tot nu merge

mi-ar putea da cineva un link catre solutia oficiala? eu nu am gasit-o

da, stiu (am gasit diverse discutii pe forumuri despre asta). problema e ca la facultate  facem tot felul de demonstratii pt complexitatile diverselor operatii pe avl-uri, iar eu nu stiu inca exact de sunt si ce fac:D, asa ca m-am apucat acum de ele.

ok. mersi. ma voi uita pe ele

am vazut articolul, dar eu nu de teorie duc lipsa:D. eu as vrea niste probleme ca sa vad ca am inteles bine ce inseamna avl-uri si ce pot ele sa faca. mersi oricum de raspuns!

Vreau sa invat AVL-uri, dar nu am vazut problema in arhiva educationala . stie cineva probleme foarte simple de pe infoarena care sa se rezolve folosind avl-uri (foarte simple adica sa aplic cat mai direct teoria, fara alte smecherii/observatii)?

cum ar trebui sa calculez restul impartirii unui numar scris in baza B la un numar p, in baza 10?
de exemplu, daca am numarul 12 (in baza 4) si vreau sa-l impart la 7, cat e restul? 6 (il transform pe 12(4)=6(10), impart la 7 si afisez restul in baza 10) sau 7(10)=13(4) si restul este 12?

numerele alea din matrice, cele diferite de zero, cat de mari/mici pot fi ("intregii" din cerinta inseamna ca sunt int-uri?). si inca o intrebare, conteaza la ceva ce valoare are o casuta, atata timp cat ea e diferita de 0? daca nu, de ce sa nu spunem pur si simplu ca e o matrice cu 0 si 1?

a da, asa e. de data asta nu cere rezultatul modulo ceva, ci chiar numarul. multumesc!

nu cred ca am inteles bine cerinta
"singura operatie permisa este stergerea unei cifre pentru ca cei doi copii sa se impace." de fapt, din exemplu, pot sa sterg oricate, si din subsirul care ramane scris, fac un numar. daca e div cu k, il numar.
eu am facut cu dinamica, asa: (dp[ i ][j]=numarul de numere care restul j la impertirea cu k, considerand doar primele i cifre=> raspunsul va fi, la final, in dp[n][0])
//initializarea/ v[] e sirul initial de cifre...

Cod:

 for(i=1;i<=n;i++)dp[i][v[i]%k]=1;//cifra asta pot sa iau si singura, neimperecheata cu nimic din fata

  for(i=1;i<n;i++){
     for(j=0;j<k;j++){
        dp[i+1][j]+=dp [ i ] [j];
        dp[i+1][(j*10+v[i+1])%k]+=dp [ i ] [j];//daca consider a (i+1)-a cifra
     }
  }

dar iau doar 10 puncte cu incorect pe restul
cerinta s-a schimbat semnficativ in ultimul timp? va ca se vorbeste de numere mari; in plus, sunt multe surse de 100p care au un timp de aproape 2secunde

Salut!

Eu am facut problema asta in doua moduri (facut adica da raspunsul corect, dar ia tle pe 7 teste din 10, in ambele moduri)
Am notat cu l1 numarul de laturi de tip 1 vandute pana acum (catete verticale), l2 numarul de laturi de tip 2 (catete orizontale)
si l3 numarul de laturi de tip trei (ipotenuze)
Primul e brut:
  fac doua foruri in care fixez l1 si l2 (l3 se deduce, este k-l1-l2). am trei functii:
      suma1(l1,l2,l3), suma2(l1,l2,l3) si suma3(l1,l2,l3) care calc. valoare parcelei de tip 1 (respectiv 2, 3), stiind ca am vandut deja l2 si l3 laturi de tipul l2 si resp l3; sursa e aici http://infoarena.ro/job_detail/636657?action=view-source
A doua solutie am incercat sa o fac o parcurgere in latime; mie mi s-a parut o solutie mai buna ca prima, dar, desi tot doar trei teste intra in timp, ea ia chiar mai mult

initial am in coada nodul (0,0,0,0) cu semnif ca la sf zilei 0, am vandut 0 laturi l1, 0 laturi l2 si castigul este 0 (pe l3 nu e nevoie sa-l tin, se deduce, este (ziua-l-l2))
expandarea nodului (ziua,l1,l2,castig) duce la adaugarea in coada a inca trei noduri:
       (ziua+1,l1,l2,castig+suma3(l1,l2,ziua-l1-l2+1)) daca vand latura 3,
       (ziua+1,l1+1,l2,castig+suma1(l1+1,l2,ziua-l1-l2)) daca vand latura 1,
       (ziua+1,l1,l2+1,castig+suma2(l1,l2+1,ziua-l1-l2)) daca vand latura 2. expandez pana la generatia k, inclusiv.
din tot ce am pus vreodata in coada aleg maximul, dpdv al castigului.
mi s-a parut o sol mai buna ca prima, pt ca chem functiile de suma de mai putine ori decat in primul caz...
sursa e aici: http://infoarena.ro/job_detail/637095?action=view-source
Imi poate spune cineva, pe scrut, care era ideea? sumele pe bucati oricum trebuiesc calculate,nu? si ele iau mult timp...

in enunt termenul "subsir" este folosit in sensul lui matematic? adica daca s1,..sn este sirul dat.
s_a1, s_a2, ...s_an este subsir al sirului dat daca a1<a2<...<an (dar nu neaparat a1,a2.. consecutive)

"abc" si "aabbcccc" sunt in ordine alfabetica, dar, de exemplu, "adt" este? adica caracterele trebuie sa fie consecutive in alfabet, sau doar pozitiile lor sa fie in ordine crescatoare?

nu stiu daca m inteles clar cerinta. pentru n=3 raspunsul e 2 (sau 1?)

da, mersi. de scris scrie "rezultate partiasle disponibile", dar e ok, imi arata la toate testele ce am luat

eu nu-mi vad punctajul deloc, scrie doar evaluare completa

ok. mersi de linkuri, mi se paruse mie ca era prea usor sa fie asa:)

are cineva vreo idee ce e cu testul 9? ca iau tle pe ea, am incercat sa citesc intr-un buffer numerele si dupa aia sa parsez, dar merge chiar si mai incet. in general, am incercat cam tot ce mi-a trecut prin cap sa mearga mai rapid, dar tot tle iau....
asta e ceea ce fac:

Cod:

int x=n-1;
for(i=0;i<x;i++){
    if(diag[i]>0){
      //sunt pe linia i din "matrice"
      coloana[i]=diag[i];
      if(coloana[i]>max){max=coloana[i];}
      for(j=i+1;j<n;j++){
        coloana[j]=coloana[j-1]+diag[j];
        if(coloana[j]<=0)break;
        if(coloana[j]>max){
            max=coloana[j];
        }
      }
    }
}

datele le citesc cu stream-uri, in varianta care am vazut ca e cea mai rapida:
http://infoarena.ro/job_detail/631145

Mersi! Tare chestia cu reevaluarea surselor deja trimise
@Dragos: am trimis si o sursa cu ideea ta, cu buffer-ul; a scazut  fff tare timpul, nu ma asteptam sa fie mai rapid parsatul caracter cu caracter decat cititul direct din fisier; pare o chestie f utila, mersi frumos!