1055 Puteri35

[•wefgef]

Aici puteţi discuta despre problema Puteri35.

[•vladtarniceru]

as avea nevoie de putin ajutor... iau TLE pe testele de la 7-10  (60 pct in total).am mers pe o idee cu baze de numeratie, si anume am mers de la 3 in sus si am testat pentru fiecare numar daca este preferat de unul sau chiar de amandoi copii(l-am descompus in baza 3 respectiv baza 5 si am pus conditia ca restul sa nu fie mai mare decat 1 (deci sa fie 0 sau 1)), apoi ma opresc cand am gasit primele n numere preferate ale fiecaruia... o solutie mai optima cum ar fi sau cum as putea sa-mi optimizez sursa?

Cod:

#include<stdio.h>
 FILE *f,*g;
    int n1,n2,i;
	int desc3(int nr){
		int r;
		while(nr){
			r=nr%3;
			nr=nr/3;
			if(r>1) return 0;
		}
		return 1;
	}
	int desc5(int nr){
		int r;
		while(nr){
			r=nr%5;
			nr=nr/5;
			if(r>1) return 0;
		}
		return 1;
	}
    int main(){
		f=fopen("puteri35.in","r");
		g=fopen("puteri35.out","w");
		fscanf(f,"%d",&n1);
		n2=n1;
		--n1;
		--n2;
		i=3;
		fprintf(g,"1\n1\n");
		while(n1 || n2){
			if(desc3(i) && n1){
				fprintf(g,"%d\n",i);
				--n1;
			}
			if(desc5(i) && n2){
				fprintf(g,"%d\n",i);
				--n2;
			}
			++i;
		}
		fclose(g);
		return 0;
	}

multumesc 
   

[•klamathix]

Schimbi solutia complet.

Ai observat ca numerele trebuie sa contina cifre de 0 sau 1 in baza 3 sau in baza 5. Atunci poti genera direct numerele corecte folosindu-te de reprezentarea in baza 2 a celor mai mici numere naturale. Si le interclasezi.


Exemplu : 12 = 1100 ( al 12-lea numar cautat de tine e 5 ^ 3 + 5 ^ 2 , respectiv 3 ^ 3 + 3 ^ 2 )

Spune daca vrei sa-ti detaliez , stiu ca n-am fost foarte coerent. Trebuia sa fie un hint:))

[•BitOne]

Pentru  N=20 si N=1000 cat va da ? Mie imi da :

Cod:

N=20
1
1
3
4
5
6
9
10
12
13

Cod:

N=1000
1
1
3
4
5
6
9
10
12
13
25
26
27
28
30
30
31
31
36
37
39
40
81
82
84
85
90
91
93
94
108
109
111
112
117
118
120
121
125
126
130
131
150
151
155
156
243
244
246
247
252
253
255
256
270
271
273
274
279
280
282
283
324
325
327
328
333
334
336
337
351
352
354
355
360
361
363
364
625
626
630
631
650
651
655
656
729
730
732
733
738
739
741
742
750
751
755
756
756
757
759
760
765
766
768
769
775
776
780
781
810
811
813
814
819
820
822
823
837
838
840
841
846
847
849
850
972
973
975
976
981
982
984
985
999
1000
1002
1003
1008
1009
1011
1012
1053
1054
1056
1057
1062
1063
1065
1066
1080
1081
1083
1084
1089
1090
1092
1093

[•vladtarniceru]

cred ca am inteles... deci fac generare de 0 si 1 pana la n in baza 2(de exemplu daca n=6, deci 110 in baza 2 nu am voie sa am 111 sau sa depasesc 3 cifre(sa am de exemplu 1000 sau 10110)), dar generarea trebuie sa fie in ordine(adica backtracking care ia mereu solutiile in ordine crescatoare) sau faci alta(si daca da cam cum ar fi ), retii solutiile intr-un vector apoi le sortezi si le afisezi?

[•vladtarniceru]

am vazut ca cei care au facut cu sume partiale(deci au folosit vector apoi au sortat) au luat majoritatea 70 pct, deci trebuie o sortare care sa sorteze crescator deci cred ca backtracking(daca nu exista o alta generare mai rapida pentru aceasta problema care genereaza crescator(daca exista chiar as vrea s-o aflu   ))...

ps:pentru SAlexandru
pentru N=20 mie imi da

Cod:

1
1
3
4
5
6
9
10
12
13
25
26
27
28
30
30
31
31
36
37
39
40
81
82
84
85
90
125
126
130
131
150
151
155
156
625
626
630
631
650

iar pentru N=1000 imi da ultimul numar 2440750

[•BitOne]

Ok, thanks dar pune raspunsurile intre tagurile [ code ] [ /code ] ( fara spatii ) ca sa nu ocupe un loc asa mare

[•miculprogramator]

Eu am luat 70 de puncte folosindu-ma de ideea cu sume. La ultimele 3 teste pe care iau MLE rezultatul dat de programul meu e bun. Ideea este ca nu trebuie sa retii numerele intr-un vector (asa am vazut in solutia oficiala).

@vlad : Algoritmul tau cu descompunerea in bazele 3 si 5 genereaza numerele deja sortate.

P.S : Rezultatele postate la testele cu n = 20 si n = 1000 sunt bune.

[•vladtarniceru]

am facut problema dupa ideea lui Mihai dar tot iau TLE pe 3 teste .am incercat sa vad ce optimizari as mai putea face, dar nu mai gasesc. ma puteti ajuta va rog?

Cod:

#include<fstream>
 using namespace std;
 ifstream f("puteri35.in");
 ofstream g("puteri35.out");
    long long n,ac1,ac2,a=1,b=1,v5[100],v3[100],i,n1,n2;
	int b23(int a){
		long long rez1=0,r,mrg=0;
		while(a){
			r=a%2;
			rez1=rez1+v3[mrg]*r;
			++mrg;
			a=a/2;
		}
		return rez1;
	}
	int b25(int a){
		long long rez1=0,r,mrg=0;
		while(a){
			r=a%2;
			rez1=rez1+v5[mrg]*r;
			++mrg;
			a=a/2;
		}
		return rez1;
	}
    int main(){
		f>>n;
		n1=n;
		n2=n;
		v3[0]=v5[0]=1;
		for(i=1;i<=30;++i) v3[i]=v3[i-1]*3;
		for(i=1;i<=20;++i) v5[i]=v5[i-1]*5;
		a=1;
		b=1;
		while(n1 || n2){
			if(ac1>ac2 || n1==0){
				if(n2){
					ac2=b25(b);
					--n2;
					++b;
				}
			}
			else
			if(n1){
				ac1=b23(a);
				--n1;
				++a;
			}
			if(ac1>=ac2 && (b25(b)>=ac1 || n2==0)){
				g<<ac1<<'\n';
			}
			else
			if(b25(b)<ac1){
				ac2=b25(b);
				g<<ac2<<'\n';
			}
			else
			if(ac1<=ac2 && (b23(a)>=ac2 || n1==0)){
				g<<ac2<<'\n';
			}
			else
			if(b23(a)<ac2){
				ac1=b23(a);
				g<<ac1<<'\n';
			}
		}
		g.close();
		return 0;
	}

multumesc 

[•deneo]

nu mai folosi streamuri - am folosit si eu dar nu am luat maxim - 100p se ia numai cu scanf si printf
P.S: in concurs a avut 8s timp de executie

[•an_drey_curent]

Determin numerele dorite folosind reprezentarea primelor N numere in baza 2 ( folosind operatii pe biti ),interclasez numerele, totusi iau 80 de pct, chit ca afisez printf sau streamuri. Ce as putea imbunatati spre exemplu la aceasta sursa? http://infoarena.ro/job_detail/732078

[•Steve]

Problema are limita de timp prea mica, am incercat si o sursa care lua inainte 100, acum maximul e de 80.
Am raportat problema aici.

LE: Am luat in final 100 cu diverse optimizari destepte de algoritm, dar oricum trebuie marita limita.

[•repp4radu]

Am incercat sa afisez 2 milioane de numere long long, fara sa fac nimic altceva in algoritm si am luat TLE pe ultimele 3 teste.
Cred ca ar trebui marita limita de timp, deoarece cu limita actuala nu intra nici macar afisarea.

[•Steve]

Am raportat problema mai demult.
Intra afisarea standard, si poti sa faci problema sa intre, dar trebuie optimizari cu operatii pe biti, ex. nu ai nevoie cand treci de la un numar la urmatorul sa construiesti complet noul numar deoarece primii biti raman la fel, asa ca poti sa bagi LSB. Vad ca inafara de mine mai sunt 2 persoane care au facut-o sa intre pe principiul asta. Daca nu vrei sa astepti pana se schimba limita, poti sa-mi dai un PM sa te ajut.

PS: N-ar strica 0.25 in plus la timp.

[•wefgef]

Am modificat limita de timp la 1.4