infoarena

Aici puteţi discuta despre problema Zero (http://infoarena.ro/problema/zero).

Imi da si mie cineva un hint, o idee ca nu prea stiu cum sa abordez problema.  :-k

PD :)

eu am facut a[i ][j]=nr. de i cifre cu j zerouri consecutive(fix), dar nu iau decat 10 puncte.. ce e gresit in rationamentul meu?

Nu ai nevoie de matrice, merge pe vector. Poate te ajuta problema Timus 1081.

este suficienta memorie ;) stiu alea de pe timus.. eu insa nu inteleg de ce nu merge asa.. pt a afla nr. cu cel mult p cifre 0 consecutive: a[n][0]+a[n][1]+..+a[n][p] si cel putin q: a[n][q]+..+a[n][n-1]
ce e gresit?  :-k

La b) faci prin eliminare. Scazi din numarul total de numere in baza b pe cele cu cel mult q zerouri.

cred ca trebuie sa scazi cele cu cel mult q-1 zero-uri.. da tot nu m-am lamurit
asta e echivalent cu a aduna cele cu fix q zero-uri cu cele cu fix q+1 zero-uri .. etc.
nu?

Da, e acelasi lucru. La inceput am facut cum zici tu. Dar mi-am dat seama ca greseam la calcul si apoi am facut prin diferenta.

poate sa-mi dea si mie mai multe exemple..ca am alta solutie fata de PD...:D
ok, astept

pai poti sa implementezi solutia bkt si sa-ti dai singur mai multe exemple  :D

io nu pricep un lucru la b) daca ar fi q=5 si undeva in l=15 ar fi 6 zerouri consecutive nu ar mai conta de restul cifrelor sau fiecare zero trebuie sa faca parte dintr-u grup de q zerouri. Ca am vazut o sugestie de Tytus care o facut problema(si multe multe altele) ca ar trebui sa facem a) si pt b) si sa facem diferenta dintre nr total de cazuri si cele obtinute ,dar in cazul asta apar si alte nr care io zic ca nu se numara in mod normal.

help mee!!!!

Daca este o secventa de 6 zerouri consecutive restul cifrelor nu mai conteaza. Nu toate zerourile trebuie sa fie in secvente de 6.

ce-mi place cum suna enuntu

lol 1 e mai >=2 =))
editare: yeap, se mai intampla

Toate grupurile de 0 din numar trebuie sa fie de cel putin q pentru a fi luate in considerare pentru solutia 2 sau doar unul?  :|

Cel putin unul

Imi poate spune cineva unde e problema aceea Timus 1081 ?
Am incercat cu Google, dar nu am gasit decat un ziar...  :(

  http://acm.timus.ru/problem.aspx?space=1&num=1081

tot iau 5p la problema asta (cu WA in rest)
am gasit ca
e gresit?... am implementat si pe numere mari si nu vrea...

Nu e chiar asa formula :wink: Daca tot nu vrea cu formula... fa o dinamica...

pot sa fie oricate cifre de 0, mai putin prima din numar. trebuie sa nu ai o subsecventa de lungime P cu cifre de 0.

fara numere mari iei 65 de puncte.

bah daca nu iti ieasa dinamica ... incearca back .. a incercat alexthero si a scoso de 100 cu bkt ;)

Imi spune cineva cat va da pe:

?

Later edit: nevermind...

cam ce complexitate ar trebui sa scot la problema asta?

Mai puneti si voi niste exemple k nu inteleg ce trebuie sa aflu  ](*,) sau ziceti ce trebuie sa afisez? kte numere sunt consecutive cu p sau mai putine 0 (sau q sau mai multe zerouri) - maxim sau ce?

La datele de iesire este pus subtitlul "Date de intrare"   :D

[LE] cred ca ar trebui modificate si restrictiile pentru p si q in 1<=p,q <=l-1, deoarece si pentru p,q =1 sunt solutii (asa cum este si in exemplu)

am incercat, de fun, o rezolvare cu back, 75 de puncte, cu tle-uri, bineinteles
cine face back de 100 ? :D

 :evil:

stiam postu', da' cum o fi facut?
eu am facut back pe forma numarului, gen x0xxx00x...
ceea ce mie mi se pare ca e O(L * 2^(B-1)) O(L * 2^(L-1))
daca ma mai gandesc fac backu' O(2^(B-1)) O( 2^(L-1))  :-k 

le: recursiv e usor O(2^(L-1)) dar timpul e mai mare

ele: :)) am luat 80 cu un fel de back recursiv
http://infoarena.ro/job_detail/204406 (http://infoarena.ro/job_detail/204406)

si functia (evident, nu e back, dar asa i-am zis) :

explicatie: functia merge la pasul urmator pe 1 sau 0, crt tine nr curent de zerouri succesive, max pe cel maxim, iar nzero pe cel total de zerouri

mie mi se pare haios :D
nu ma ajuta nimeni sa iau 100 asa ? :))

nu-mi vine sa cred!!!
am facut o mica optimizare si mi-a intrat in timp absolut genial
http://infoarena.ro/job_detail/204416 (http://infoarena.ro/job_detail/204416)
 :yahoo:  :evil: :evil: :evil:

Salut! Am incercat si eu sa fac problema cu dinamica si as vrea daca se poate sa-mi spuna cineva ce gresesc in rationament. Fac v[j]=cate nr de i cifre au ultimele j cifre consecutive de 0. Cum pe prima pozitie nu se poate pune 0,v[1][0]=(b-1).
Am observat recurenta: v[j]=(v[i-1][0]+v[i-1][1]+...+v[i-1][b-1])*(b-1),daca j=0 si v[j]=v[i-1][j-1] altfel.
Raspunsul pt pct.a) este: v[l][0]+...+v[l][p] ,iar pt pct b) v[l][q]+...+v[l][l-1]. Mersi anticipat  :evil:

Nu e corect. De exemplu daca tu ti-ai dori sa numeri toate numere care au maxim 2 de 0 consecutivi, ai numara si numere de forma x000x00.

Asta e prima problema de pe infoarena pe care o vad in care exemplul contrazice restrictiile problemei.  8)

P si Q (2 ≤ P,Q ≤ L-1)

zero.in
3 2 1 2

L = 3
B = 2
P = 1
Q = 2

Poate asa primim un exemplu mai sugestiv. :D


___________Dupa aproape un an_____________________

Corecteaza careva problema? Vad ca a ramas gresita asa atata timp.

Cat da pe ex: 20 20 19 19 ?

Asa mi-a dat formula pt. pct. a(de fapt si la b e cam acelasi lucru)
(l-i)*(b-1)^(l-x), i de la 1 la p  +  (b-1)^l
totusi nu inteleg dc iau numai 5p  :fool:
poate sa-mi explice cineva unde am gresit rationamentul sau macar cineva cu sursa de 100 sa posteze niste teste
raman dator :D

Problema se rezolva cu programare dinamica. Este nevoie de operatii pe numere mari. Slabe sanse sa gasesti vreo formula.  :ok:

am vazut si eu la indicii ca se foloseste PD. :-'
deci eu am gandit ca daca avem i zerouri consecutive putem sa le asezam in l-i moduri iar pe celelate pozitii putem pune orice nr. din baza aceea fara 0 deci (b-1)^(l-i). deci formuala pt. i zero-uri este
(l-i)*((b-1)^(l-i))
unde gresesc?

Poti pune mai multe secvente de i zerouri, nu doar una singura.

Daca L<=20 trebuiesc citite cu char nu?

Poate sa ma ajute si pe mine cineva cu un banal tutorial pentru char? Unde as putea sa gasesc ceva? Vreau doar elemente de baza.

Uite aici: http://www.cplusplus.com/doc/tutorial/ntcs/
 :D
citirea o poti face asa:

Am gasit si eu tutorialu` de pe cplusplus.com, da` e foarte mic ca sa zic asa :P
Am habar cum citesc caractere, fie ele cate unu` sau mai multe, da` nu stiu cum sa imi dau seama ce caracter am citit.
De exemplu cu numerele romane: Citesc XII cum "atribui" lui X valoarea 10 si lui I valoarea 1 ca sa le pot aduna?

Ati putea sa mutati restictiile problemei intr-o categorie separata ca la restul problemelor. Asa nu e acelasi stil.

________________________________________________________


http://infoarena.ro/job_detail/558926 (http://infoarena.ro/job_detail/558926)
Eu iau 80 fara numere mari. Cred ca s-au schimbat intre timp testele asa ca am postat aici cat iei acum.

Dar dc oare s-au pus restrictiile sa-ti trebuiasca numere mari? Adica 20^20 are doar 8-9 cifre in plus fata de cat iti incape pe long long. Ar fi incaput pe long long long...  :D daca exista.

Îmi dă și mie cineva un indiciu la testul 17?  Mă chinui de câteva ore și tot nu iese :aha:.
Nevermind  :yahoo:

salut. pe sursa asta http://infoarena.ro/job_detail/851037?action=view-source iau 0 puncte. daca fac exact aceeasi relatie de recurenta pe long long, iau 80. poate sa imi spuna si mie cineva ce e gresit, eventual sa imi dea un test, ceva?

 #-o :fighting: