1087 Doi

[•eudanip]

Uite un exemplu. Pentru n=15 cel mai bine e sa incrementezi cu 1 sa obtii 16 ca pe orma sa poti impartii la 2 de 4 ori. Daca decrementezi cu 1 si obtii 14 o sa observi ca ai mai multe operatii.

[•SpiderMan]

De accea se foloseste o strategie greedy, vazand la fiecare pas alegerea optima.

[•fulgerulnegru]

algoritmul dat la raspuns are o greseala pentru cazul in care este Multiplu de 3 inmultit cu o putere a lui 2

[•SpiderMan]

Ne poti da un exemplu si cat da programul acela ?

[•fulgerulnegru]

Cod:

01.#include<fstream> 
02.using namespace std; 
03.long long int nr; 
04.ifstream in ("doi.in"); 
05.ofstream out ("doi.out"); 
06.int main (){ 
07.long long int n,i,j; 
08.in>>n; 
09.for(i=0;i<n;i++){ 
10.    
nr=0; 
11.in>>j; 
12.while(j>0){ 
13.if(j%2==0){ 
14.j=j/2; 
15.nr++; 
16.continue; 
17.} 
18.if(((j-1)/2)%2==0){ 
19.if((j-1)==0){ 
20.nr++; 
21.break; 
22.} 
23.else{ 
24.nr+=2; 
25.j=(j-1)/2; 
26.} 
27.continue; 
28.} 
29.if((j-1)/2==1){ 
30.    
nr+=3; 
31.    
break; 
32.} 
33.if(((j+1)/2)%2==0){ 
34.    
j=(j+1)/2; 
35.    
nr+=2; 
36.} 
37.} 
38.out<<nr<<"\n"; 
39.} 
40.in.close(); 
41.out.close(); 
42.return 0; 
43.}.

nu inteleg de ce iau numai 40 de puncte unde gresesc

[•fulgerulnegru]

iti pot de un exemplu daca folosesc strict algoritm dat la solutie cand vrei sa vezi pentru 3 iti va da 4 deorece 3=2*1+1 unde k =1 aplicand rezolvarea de la problema se duce pe ramura a doua deoarece nu este k par

[•SpiderMan]

Pentru 3, folosind STRICT algoritmul acela, o sa ai rezultatul 3, pentru ca din 3 + 1, sau 3 - 1, alegi 3 - 1, pentru ca mergi mai mult. Adica 3 - 1 = 2, cum 2 par => 2 / 2 = 1. Si acum scazi o unitate si gata. Daca ai fi la 3 + 1, ai avea 4 / 2 = 2, 2 / 2 = 1, iar apoi 0, ceea ce o sa iti dea rezultatul 4. Cum 3 < 4, alegi rezultatul 3.

[•alexutzu29]

Cod:

#include <iostream>
#include <math.h>
#include <cstdio>
using namespace std;
int main(){
    freopen("doi.in","r",stdin);
    freopen("doi.out","w",stdout);

long long n,a[1000],i,c=0;
cin>>n;
for(i=1;i<=n;i++)
    cin>>a[i];

for(i=1;i<=n;i++)
{
    c=0;
    while(a[i]!=0)
 {//calculam pt nr par
    if(a[i]%2==0)
        {a[i]=a[i]/2; c++;}

    //partea a doua pt nr impar
    else if(a[i]%2==1)
        {a[i]--; c++;}
}
    cout<<c<<'\n';
}


return 0;
}

Da-ti si voi un ochi va rog ! 

[•PlayLikeNeverB4]

1) Trebuie sa iei in calcul si posibilitatea de a aduna 1, nu doar de a scadea.
2) Trebuie sa lucrezi cu numere mari din cauza restrictiilor problemei.

P.S.: Inainte sa intrebi ceva, o idee buna e sa verifici daca nu cumva au avut si altii aceeasi problema.

[•valentin.harsan]

nu inteleg ce gresesc
poate sa se uite cineva pe sursa mea, va roog

Cod:

#include<stdio.h>
#include<string.h>

int t,nrr[505],nr[505],a1,nu,a2,nr2[505];
char a[510];

void imp(int v[]) {
	int i,t=0;
	for(i=v[0];i>0;--i) {
		t=t*10+v[i];
		v[i]=t/2; t%=2;
	}
	for(;v[v[0]]==0;--v[0]);
}
int smax(int a1,int a2) {
	if(a1>a2) return a1;
	return a2;
}
void add(int a) {
	int i,t=0; nrr[1]+=a;
	for(i=1;t || i<=nrr[0];++i,t/=10) {
		t+=nrr[i];
		nrr[i]=t%10;
	}
	nrr[0]=smax(i-1,nrr[0]);
}
void add2(int a) {
	int i; nr2[1]-=a;
	for(i=1;i<=nr2[0];++i) {
		if(nr2[i]<0) {
			nr2[i]+=10;
			nr2[i+1]--;
		}
	}
	for(;!nr2[nr2[0]] && nr2[0]!=0;--nr2[0]);
}

bool cmp() {
	int j;
	if(nrr[0]!=nr2[0]) return 0;
	for(j=nrr[0];j>0;--j)
		if(nrr[j]!=nr2[j]) return 0;
	return 1;
}

int main() {
	int i,w;
	freopen("doi.in","r",stdin);
	freopen("doi.out","w",stdout);
	scanf("%d",&t);
	for(w=1;w<=t;++w) {
		scanf("%s",&a); a1=strlen(a);
		nu=0; nr[0]=0;
		for(i=a1-1;i>=0;--i)
			nr[++nr[0]]=a[i]-'0';
		while(nr[0]!=0) {
			++nu;
			if((nr[1]&1)==0)
				imp(nr);
			else {
				a1=0;
				for(i=0;i<=nr[0];++i)
					nrr[i]=nr[i];
				add(1);
				while((nrr[1]&1)==0) {
					++a1;
					imp(nrr);
				}
				a2=0;
				for(i=0;i<=nr[0];++i)
					nr2[i]=nr[i];
				add2(1);
				if(!nr2[0])
					break;
				while((nr2[1]&1)==0) {
					++a2;
					imp(nr2);
				}
				if(a2>a1) {
					if(cmp())
						nu+=a1;
					else
						nu+=a2;
					for(i=0;i<=nr2[0];++i)
						nr[i]=nr2[i];
				}
				else {
					if(cmp())
						nu+=a2;
					else
						nu+=a1;
					for(i=0;i<=nrr[0];++i)
						nr[i]=nrr[i];
				}
			}
		}
		printf("%d\n",nu);
	}
	return 0;
}

[•ctlin04]

Va rog ajutati-ma cu testele 2 si 8 ca nu ma prind, am facut solutia in care incersc sa merg pe doua cazuri cind adun sau scad 1.  

[•PlayLikeNeverB4]

Nu stiu daca are legatura cu testele, dar ar trebui sa bagi in seama warningurile compilatorului, in special asta:

Cod:

warning: control reaches end of non-void function

pentru cazul cand numerele sunt egale.

[•ericutzdevil]

Apucandu-te de problema abia dupa ce realizezi ca se fac 3 operatii cu numere mari...