[Incepatori][Concurs Nr. 29]Numere Lychrel

[tw8]

Se citeste de pe prima linie a fisierului "c29i.in" numarul N. Pe urmatoarele N linii, se gasesc N perechi de numere de forma "a b". Pentru fiecare pereche de numere, sa se afiseze in fisierul de iesire "c29i.out" numarul de numere Lychrel din intervalul [a,b].
Restrictii si precizari:

• 0<N<=10.000
• 0<a<b<2^15
• Numerele vor fii considerate Lychrel daca nu se obtine un palindrom in mai putin de 100 de iteratii.
• Nu se va folosii preprocesare

Ce este un numar Lychrel:
http://en.wikipedia.org/wiki/Lychrel_number

[Th3 P!mp]

Buna seara  >-

vad ca o sa fiu eu primul care 'incearca'

am pus in arhiva si un fisier de testare cu N = 10000 unde fiecare pereche e intre 10 -> 10000
have fun

O seara placuta

[DarkByte]

Am si uitat de concurs :| Pana in ce data mai e deschis?

[tw8]

^
Stai linistit, mai ai o saptamana la dispozitie .

[tw8]

@Th3 P!MP: Nu stiu exact de ce, dar programul tau nu imi ruleaza. E posibil sa fie de la antivirus sau asa ceva - numai ce l-am schimbat si nu il stapanesc prea bine .
Daca functioneaza corect, vei fii declarat castigator. Voi decide asta dupa ce iti vei posta aici sursa, pentru ca mie nu mi-ai trimis-o pe mail - rusinica ).

Apropo ... eu astazi voi pleca din tara pentru vreo 10 zile si nu stiu sigur daca voi avea acces la internet. Te rog sa alegi tu o tema pentru concursul de programare si sa o postezi maine, daca nu te deranjeaza.

Bafta !

[Th3 P!mp]

Sursa

Code: [Select]

#include <iostream>
#include <fstream>

using namespace std;
ofstream output;

bool isPoli(int* arr, int length)
{
for(int i=0; i<length/2; i++)
if(arr[i] != arr[length-i-1])
return false;
return true;
}

bool isLishel(int* numArray, int length, int depth)
{
/* IF I REACH DEPTH OF 100 JUST LEAVE IT ...
* ... CAN CHANGE TO ANY DEPTH ... JUST NEED
* TO HAVE VERY FAST CPU
*/
if(++depth == 100)
return false;

int rest = 0;
int *fin = new int[length+1];

for(int i = 0 ; i < length; i ++)
{
fin[i] = (numArray[i]+numArray[length-i-1]+rest)%10;
rest = (numArray[i]+numArray[length-i-1]+rest)/10;
}
int l = length;
if(rest != 0)
{
l++;
fin[length] = rest;
}

if(isPoli(fin, l) || isLishel(fin, l, depth))
{

return true;
}

return false;
}

int main()
{
int num, *arr;
int num2 = 0;
int length = 0;

arr = new int[30];
int *pre = new int[32769];
int idx = 0;
int numberOfNumbers = 0, startIndex, finIndex;
for(int ww = 0; ww< 32769; ww++)
pre[ww] = 0;

ifstream from;


output.open("c29i.out");
from.open("c29i.in");

from >> numberOfNumbers;
cout << "I read " << numberOfNumbers << " pairs of numbers ..." << endl;
system("pause");
cout << "Starting program " << endl;
int gasite = 0;
for(int k=0; k<numberOfNumbers; k++)
{
from >> startIndex;
from >> finIndex;
for(int i=startIndex ; i<finIndex ; i++)
{
if(pre[i] == 2)
{
output << "  ~> " << i << endl;
gasite++;
}
else if(pre[i] == 0)
{
num = i;
length = 0;
while(num!= 0)
{
arr[length++] = num%10;
num/=10;
}
if(!isLishel(arr, length, 0))
{
pre[i] = 2;
gasite++;
}
else
{
pre[i] = 1;
}
}
}
output << "Line - " << k << " " << "found between " << startIndex << " and " << finIndex << " : " << gasite <<endl;
gasite = 0;
}

cout << "Complete..." << endl;
return 0;
}
output pt 1 -> 30000
"Line  0 found between 1 and 32000 : 1267"

am atasat si un fisier cu informatii mai "detaliate" despre cum arata fiecare numar dupa 100 de iteratii :p

daca vrea careva sa vada cum arata un numar la adancime 2000000000 ... nu are decat ... numa sa schimbe in cod )

executabilul de mai sus nu este valabil pentru ca am modificat din memset(pre, 0, 32...) in

Code: [Select]

for(int ww = 0; ww< 32769; ww++)
pre[ww] = 0;... aparent memset-ul imi faulta array-ul

am uitat sa iti trimit sursa , era sa o si pierd ca am instalat W7 si am crezut ca a sters c-ul .. da face windows.old si am regasito   <:-P

[o sa gasesc o problema .. frumoasa  )]