691 Fibo

[•astronomy]

Aici puteţi discuta despre problema Fibo.

[•andrici_cezar]

ce are problema mea ........ nu inteleg de loc

[•wefgef]

Numerele nu incap pe longint. Trebuie sa implementezi numere mari. Gasesti un articol care sa te ajute aici.

[•andrici_cezar]

am incecat si imi da eroare de compilare??? am incercat int64
dar nu merge

[•gabitzish1]

int64 nu inseamna numere mari.
Retine numerele sub forma de vectori.

[•andrici_cezar]

ms am luat 50 puncte... dati-mi si mie niste teste mai mare sa vad daca imi da bn... adica 1000000, 500000,600000,etc

[•razyelx]

Nr-ele nu sunt deloc mari. Maximul nu depaseste 1 000 000 asta inseamna ca iti intra in long, dar inseamna mult mai mult de atat. Daca chiar vrei sa incerci foloseste long long.
Iar nr-ele de forma palindrom sunt destul de putine. Ok cred ca ti-am dat destule indicii. Bafta!

[•Florian]

Generez toate numerele in baza doi ( cu reprezentarile binare ale unui contor de la 1 la 2^16). Reprezentarile binare care sunt palindroame le transform in numar in baza 10 [considerandu`le scrise in sistem fibo), iar daca numerele in baza 10 sunt mai mici ca n, incrementez solutia. Problema e ca iau WA. Nu inteleg de ce ar fi nevoie de numere mari [reprezentarea binara o tin sub forma de vector]. Poate cineva sa ma ajute? Problema e banala, insa ...

[•Protoman]

Tu generezi toate posibilitatile pana la 2^16.
Poti incerca altceva: sa generezi doar jumatate din numar si apoi sa ii faci oglinda pastrand complexitatea

Prin "Oglinda" ma refer la:
ai generat 10010
oglinda care o faci tu va fi: 10010 + 01001 sau 1001 0 + 1001 din astea iti vor iesi palindroamele:
1001001001
100101001

[•Florian]

Intr-adevar. E buna indicatia. Multumesc. Totusi, nu inteleg de ce 010 nu este luat in considerare in exemplu.... Poate cineva sa ma lamureasca?

[•astronomy]

In general numerele incep cu o cifra nenula.

[•gabor_oliviu1991]

daka imi da eroarea

user.cpp:47: error: 'strrev' was not declared in this scope

inseamna ca nu are compilatoru functia strrev ?

[•astronomy]

Da, strrev nu este ANSI C.

[•gabor_oliviu1991]

am facut un fel de brute la problema asta... am luat toate numerele de la 1 la 1 mil, leam transformat in baza 2, leam facut in baza fibonaci si daca erau mai mici ca N incrementam ceva. iau TLE pe 7 teste, deci iau 40 de pct. am incercat sa fac si cu preprocesare... tot asa, iau un iterator de la 1 la un milion si bag numerele intrun vector. de aici fac o cautare binara la cel mai mare numar mai mic decat N si afisez pozitia lui. de ce nu stiu, dar mie imi baga in vector doar pana pe la 17000. o idee sau daca am ceva gresala la implementare. merci anticipat off-topic: HAI ROMANIA!!!

LE: cu a doua varianta iau 50 de pct.

LE2: am luat in sfarsit 100. ideea e ca la ultimul test N depaseste 1 milion

[•brainwashed20]

Ce as putea sa mai imbunatatesc la sursa asta ca sa imi iasa si ultimul test, ca practic solutia e cea oficiala..

Cod:

#include<cstdio>  
#include<cstring>
#include<bitset>

using namespace std;
  
#define DIM 31

int N, M=30, sol=1;

int fib[DIM] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269}; 
  
inline int verif(int val) {  
    int max=0;  
	register int i=M;
	bitset <DIM> aux;
	
	while(val<fib[i]) 
		--i;
	val-=fib[i]; aux[i]=1;  
	if(i>max) 
		max=i; 
	
	for(; i && val; --i) {  
		while(val<fib[i]) 
			--i;
		val-=fib[i];  
		aux[i]=1;  
	}  
	
	for(i=1; i<=max/2; ++i) 
		if(aux[i]!=aux[max-i+1]) return 0;  
	
	return 1; 
}  
  
int main() {	
    freopen("fibo.in","r",stdin);  
    freopen("fibo.out","w",stdout);  
      
    register int i;
	
	scanf("%d",&N);  
      
    for(i=2; i<=N; ++i)  
        sol+=verif(i);   
      
    printf("%d\n",sol);  
  
    return 0;  
}  

[•SebiSebi]

Cat trebuie sa dea pentru 1 000 000 ? Multumesc anticipat!

[•SpiderMan]

Cod:

1795

[•TheNechiz]

10x