•pauldb
|
|
« : Decembrie 05, 2010, 13:50:24 » |
|
Aici puteţi discuta despre problema Doi.
|
|
|
Memorat
|
Am zis
|
|
|
•andunhill
|
|
« Răspunde #1 : Decembrie 05, 2010, 20:09:54 » |
|
Imi da si mie cineva o idee? Nu gasesc deloc solutia desi parea cea mai usoara.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #2 : Decembrie 05, 2010, 20:31:14 » |
|
Poti sa faci o abordare de tip greedy : daca numarul e par, atunci il imparti la 2, daca e impar faci asa : te duci pe doua cazuri .... unul incrementand, unul decrementand. Pentru fiecare caz, mergi pana ajungi la un numar impar. Vezi in care caz ajungi mai departe, si iei acel numar, incrementand solutia. Exemplu avem numarul 15. E impar, deci vedem cazurile : 1. Daca il incrementam, avem 16, e par deci il impartim la 2, 16 / 2 = 8, 8 par => 8 / 2 = 4, 4 = par => 4 / 2 = 2, 2 par => 2 / 2 = 1. 2. Daca il decrementam, avem 14, e par deci il impartim la 2, 14 / 2 = 7. Se vede ca in primul caz am facut 4 pasi, si in al doilea am facut doar 1 pas. Deci avem pana acum sol = 5. Avem 1, iarasi 2 cazuri. 1. Daca il incrementam, avem 2, e par deci il impartim la 2, avem 2 / 2 = 1. 2. Daca il decrementam, avem 0 => am ajuns la final. Solutia finala o sa fie 5 + 1 = 6 .
|
|
« Ultima modificare: Decembrie 05, 2010, 20:40:54 de către Simoiu Robert »
|
Memorat
|
|
|
|
•andunhill
|
|
« Răspunde #3 : Decembrie 05, 2010, 21:13:07 » |
|
M-am gandit si la solutia asta dar nu cred ca intra in timp pentru un numar de 500 cifre.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #4 : Decembrie 05, 2010, 21:31:48 » |
|
|
|
|
Memorat
|
|
|
|
•Bit_Master
|
|
« Răspunde #5 : Decembrie 05, 2010, 21:40:25 » |
|
fie x = 2^a cea mai mare putere a lui 2, mai mica decat nr y = 2^b cea mai mica putere a lui 2, mai mare decat nr Ranspunsul nu e
daca x<y a + n-x altfel b + y-n ?
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #6 : Decembrie 05, 2010, 21:49:20 » |
|
Dar nu tot timpul, x < y in cazul tau ?
|
|
|
Memorat
|
|
|
|
•hunter_ionutzzz
Strain
Karma: 2
Deconectat
Mesaje: 15
|
|
« Răspunde #7 : Decembrie 06, 2010, 17:25:35 » |
|
nu afisati pls un fisier de intrare sau un exemplu ca mie acasa imi da rezultat corect pt orice numar dar am scos 0 pct si nu stiu dc
|
|
|
Memorat
|
|
|
|
•skull
Client obisnuit
Karma: 17
Deconectat
Mesaje: 75
|
|
« Răspunde #8 : Decembrie 06, 2010, 19:57:47 » |
|
IN: 7 1000 65 47 651 251 984318494894851312348949845645645645184948948513184948948513 4849448646843129849848445645645645445645645645184984944868494486
OUT: Succes!
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #9 : Decembrie 06, 2010, 20:58:27 » |
|
Deci solutia ar fi in felul urmator:
Scri numarul in baza 2. Notezi cu x lungimea grupei de 1 din coada numarului. Daca x = 1 atunci e clar ca o sa scazi 1 din numar, altfel vei aduna 1, micsorand numarul de biti de 1. Daca e 0, imparti la 2.
Exemplu
A = 110001000111 B = 101010101010
Pt A vei aduna 1 la ultima grupa, transformandu-se in 110001001000, apoi imparti de 3 ori la 2, apoi scazi 1, etc. Pt B vei scadea de fiecare data 1, pt ca nu sunt grupe de 1 de lungime mai mare de 1.
Sper ca ai inteles ce-am zis, n-am explicat prea bine.
|
|
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #10 : Decembrie 06, 2010, 21:17:13 » |
|
dar de ce este necesar sa scri numarul in baza 2, nu merge si fara, sau e pentru optimizare?
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #11 : Decembrie 06, 2010, 21:50:13 » |
|
Eu asa am facut. Nu prea vad cum ai face altfel sa vezi cati de 1 ai consecutiv. E posibil sa fie si alte solutii.
|
|
|
Memorat
|
|
|
|
•skull
Client obisnuit
Karma: 17
Deconectat
Mesaje: 75
|
|
« Răspunde #12 : Decembrie 06, 2010, 21:56:11 » |
|
Merge si sa-i aduni numarului 1, respectiv sa-i scazi 1, iar apoi sa verifici care dintre cele doua noi numere se imparte de mai multe ori la 2(il imparti efectiv). Intra in timp destul aproape de limita aceasta abordare, insa iei 100.
|
|
|
Memorat
|
|
|
|
•hunter_ionutzzz
Strain
Karma: 2
Deconectat
Mesaje: 15
|
|
« Răspunde #13 : Decembrie 06, 2010, 22:01:05 » |
|
ms pt test uitasem sa pun o simpla conditie si am pierdut 100 de pct la runda 1 (.. si eu am facut cu baza 2 ... numa ca eu aducem numarul la forma 1000...0 care era o putere de 2 si atuncea rasounsu era nr de cifre din 100...0 plus nr de operatii efectuate pt a ajunge akl : ex 1001101 se face 1001100 apoi 1010000 si in final 1000000 deci raspuns 10 si mio iesit 100 pct.
|
|
|
Memorat
|
|
|
|
•ms-ninja
Strain
Karma: 2
Deconectat
Mesaje: 6
|
|
« Răspunde #14 : Decembrie 07, 2010, 07:25:29 » |
|
da, toni, am descoperit si eu solutia asta, pe aproape cum ai explicat-o tu, doar ca nr de operatii este trecerea numarului in baza 2 + cate operatii efectuezi ca sa ajungi la o putere de-a lui 2 apropiata, stiu ca suna ilogic, un ex.63=11111 astaa inseamna 5 cifre, adik s=5; aduni un 1 si rezulta 1000000s-a marit numarul de cifre + operatia s=7 si gata, exceptie fac numerele care incep cu 110 in baza 2 pt ca acolo e caz special si numarul 3 mai este caz special
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #15 : Decembrie 07, 2010, 15:16:01 » |
|
Merge si sa-i aduni numarului 1, respectiv sa-i scazi 1, iar apoi sa verifici care dintre cele doua noi numere se imparte de mai multe ori la 2(il imparti efectiv). Intra in timp destul aproape de limita aceasta abordare, insa iei 100.
Uite solutia ta cu timpi zic eu foarte buni http://infoarena.ro/job_detail/507378 .
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #16 : Decembrie 07, 2010, 16:36:12 » |
|
|
|
|
Memorat
|
|
|
|
•intermediar
Strain
Karma: 1
Deconectat
Mesaje: 1
|
|
« Răspunde #17 : Decembrie 09, 2010, 13:12:53 » |
|
Nu inteleg de ce nu merge sursa.Va rog daca puteti sa-mi da-ti o indicatie .... Multumesc
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #18 : Decembrie 09, 2010, 15:37:16 » |
|
Da-ne tu indicatii cum ai facut si poate te putem ajuta ....
|
|
|
Memorat
|
|
|
|
•Alexandru13
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #19 : Decembrie 09, 2010, 21:25:44 » |
|
ce am gresit aici:( nu inteleg. o mica explicatie va rog ? sunt incepator pe aici. plz http://#include<fstream> using namespace std; #define InPut "doi.in" #define OutPut "doi.out" int c,t,i,nr,a; int main() { ifstream fin ( InPut ); ofstream fout ( OutPut ); fin>>t; for(i=1;i<=t;i++) { fin>>a; nr=0; while(a!=0) { if(a%2==0) { c=a/2; nr++; } else { c=a-1; nr++; } a=c; } fout<<nr<<"\n"; } return 0; } Editat de moderator : Foloseste tag'urile [ code ] si [ /code] cand postezi cod
|
|
« Ultima modificare: Decembrie 10, 2010, 09:06:02 de către Gabriel Bitis »
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #20 : Decembrie 09, 2010, 21:49:50 » |
|
cred ca erorile tale ar putea fi urmatoarele: 1.ar fi http-ul ala de la inceput dar cred ca a aparut de la site 2.ai grija ca implementarea trebuie pe nr mari 3.nici solutia nu e buna, tu poti si sa aduni nu numai sa scazi, citeste solutia lui robert simoiu din acest topic si incearca sa o faci pe numere mari pentru 100 de puncte (operatiile pe numere mari le gasesti in articolul cu smenuri de programare) bafta
|
|
|
Memorat
|
|
|
|
•Alexandru13
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #21 : Decembrie 10, 2010, 17:10:40 » |
|
multumesc!!! o sa incerc
|
|
|
Memorat
|
|
|
|
•lucian666
Client obisnuit
Karma: 16
Deconectat
Mesaje: 84
|
|
« Răspunde #22 : Ianuarie 30, 2011, 16:36:14 » |
|
am o problema .....la numerele impare nr de operatii mi-l afiseaza ca find chiar numarul......o sugestie ceva...
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #23 : Ianuarie 30, 2011, 20:58:04 » |
|
De unde sa stie lumea ca ce gresesti tu? Posteaza ideea sau o parte din sursa de la programul tau... dar a fost deja explicata destul de detaliat ideea mai sus.
|
|
|
Memorat
|
|
|
|
•cipri_tom
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #24 : Februarie 15, 2011, 20:29:55 » |
|
oare de ce ar vrea cineva sa incrementeze numarul? asta nu e clar ca te va duce catre un numar mai mare de operatii? aveti cumva vreun contra-exemplu?
|
|
|
Memorat
|
|
|
|
|