1087 Doi

[•pauldb]

Aici puteţi discuta despre problema Doi.

[•andunhill]

Imi da si mie cineva o idee? Nu gasesc deloc solutia desi parea cea mai usoara.

[•SpiderMan]

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 .

[•andunhill]

M-am gandit si la solutia asta dar nu cred ca intra in timp pentru un numar de 500 cifre.

[•SpiderMan]

Ce ziceai ? http://infoarena.ro/job_detail/507378

[•Bit_Master]

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             ?

[•SpiderMan]

Dar nu tot timpul, x < y in cazul tau ?

[•hunter_ionutzzz]

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 

[•skull]

IN:

Cod:

7
1000
65
47
651
251
984318494894851312348949845645645645184948948513184948948513
4849448646843129849848445645645645445645645645184984944868494486

OUT:

Cod:

13
8
8
14
11
265
286

Succes! 

[•toni2007]

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.

[•vladtarniceru]

dar de ce este necesar sa scri numarul in baza 2, nu merge si fara, sau e pentru optimizare?

[•toni2007]

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.

[•skull]

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.

[•hunter_ionutzzz]

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.

[•ms-ninja]

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

[•SpiderMan]

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 .

[•toni2007]

http://infoarena.ro/job_detail/507469

[•intermediar]

Nu inteleg de ce nu merge sursa.Va rog daca puteti sa-mi da-ti o indicatie .... Multumesc

[•SpiderMan]

Da-ne tu indicatii cum ai facut si poate te putem ajuta ....

[•Alexandru13]

ce am gresit aici:( nu inteleg. o mica explicatie va rog ?
sunt incepator pe aici.
plz

Cod:

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

[•vladtarniceru]

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 

[•Alexandru13]

multumesc!!!  o sa incerc

[•lucian666]

am o problema .....la numerele impare nr de operatii mi-l afiseaza ca find chiar numarul......o sugestie ceva...

[•PlayLikeNeverB4]

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.

[•cipri_tom]

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?