Page 6 of 12
Re: 10018
Posted: Wed Mar 09, 2005 10:56 pm
by lonelyone
Code: Select all
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
char inverse[15];
unsigned long int inInt,outInt,temp;
int counter,check;
int i=0,j,n;
scanf("%d",&n);
while(i!=n)
{
scanf("%lu",&inInt);
outInt=0;
counter=0;
check=0;
while(inInt!=outInt || check!=1)
{
for(j=0;j<15;j++)
inverse[j]='\0';
temp=inInt+outInt;
inInt=temp;
for(j=0;temp!=0 && j<15;j++)
{
inverse[j]=(char)(temp%10+(int)'0');
temp=temp-temp%10;
temp/=10;
}
puts(inverse);
outInt=(long int)atol(inverse);
if(inInt==outInt)
{
check=1;
break;
}
counter++;
}
printf("%d %lu\n",counter,inInt);
i++;
}
}
http://acm.uva.es/p/v100/10018.html
i thought two method...but this one didn't work and can't get a.c...
another method is using "inverse long number"...
that's all, and it worked...
this method, i used an array to store inverse number and translate it
to long int number...
and the result should be correct, but it didn't get accepted..
could someome tried to find my bugs..
thanks a million

Re: 10018
Posted: Thu Mar 10, 2005 5:18 am
by tan_Yui
Hi, I checked your code and found bugs.
I used following I/O which are written on the log of this Folum.
Input :
3
2
99
429496295
Output :
1 4
6 79497
3 12574247521
Of course, input '2' and '99' are palindrome at initial state,
but according to this problem's statement, we should calc at least 1 time.
So answer are not '0 2' and '0 99'.
And, in the case of input '429496295', your code outputs wrong value.
This bug is maybe in the process of inverse.
Best Regards.
Re: 10018
Posted: Thu Mar 10, 2005 5:36 am
by tan_Yui
tan_Yui wrote:3 12574247521
.......
.......
And, in the case of input '429496295', your code outputs wrong value.
will yield a palindrome that is not greater than 4,294,967,295.
Sorry,
My comment might be wrong,
because I cannot distinguish whether '
not greater than 4,294,967,295' are '
input value' or '
resulting palindrome'.
Thank you.
Re: 10018
Posted: Thu Mar 10, 2005 7:11 am
by tan_Yui
tan_Yui wrote:Sorry,
My comment might be wrong,
because I cannot distinguish whether 'not greater than 4,294,967,295' are 'input value' or 'resulting palindrome'.
Now, I found my AC-code from PC and checked input '429496295'.
My code outputs the same wrong value '11 2893333982' as you,
but I re-submitted my code then got Accept.
So, '
not greater than 4,294,967,295' is '
resulting palindrome', and above input '429496295' was invalid value.
Thanks for your reading.
Re: 10018
Posted: Fri Mar 11, 2005 7:21 pm
by lonelyone
Code: Select all
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
char inverse[15];
unsigned long int inInt,outInt,temp,in,sum,product=10;
int counter,check;
int i=0,j,n;
scanf("%d",&n);
while(i!=n)
{
scanf("%lu",&inInt);
in=inInt;
outInt=0;
counter=0;
check=0;
while(inInt!=outInt || check!=1)
{
for(j=0;j<15;j++)
inverse[j]='\0';
temp=inInt+outInt;
inInt=temp;
for(j=0;temp!=0 && j<15;j++)
{
inverse[j]=(char)(temp%10+(int)'0');
temp=temp-temp%10;
temp/=10;
}
//puts(inverse);
sum=0;
for(j=0;inverse[j]!='\0';j++)
sum=sum*product+(inverse[j]-'0'); //avoid overflow
outInt=sum;
if(inInt==outInt)
{
check=1;
if(counter==0)
{
check=0;
counter++;
continue;
}
break;
}
counter++;
}
if(in==0)
{
printf("0 0\n");
continue;
}
printf("%d %lu\n",counter,inInt);
i++;
}
}
Thank you..
You are a nice guy. But what you thought did not get the point.
Because I wrote two methods, and I tried to compare them.
I found the input cases that you mentioned did not matter.
Code: Select all
sum=0;
for(j=0;inverse[j]!='\0';j++)
sum=sum*product+(inverse[j]-'0'); //avoid overflow
outInt=sum;
I thought atoi() would make the return number overflow.
So I change it, then it got a.c.
Eventually, thanks everyone who read these article.
Thanks a lot. You all are nice and lovely guys.
Thanks Guru & tan_Yui especially...
--
this method is not good.
Cause time is 0.021
But if you manipulate "unsinged long int number" counting(reverse it directly), and the time is 0.010

10018
Posted: Wed Dec 14, 2005 2:41 pm
by abhi
i get TLE......... i am just a beginner..... how do i make my code faster???
Code: Select all
#include<stdio.h>
int count=0;
long revadd(long x)
{
long temp,rem=0,revnum=0,ans=0,c=0;
temp=x;
do{
revnum=0;
while(x>0)
{
rem=x%10;
revnum=revnum*10+rem;
x=x/10;
}
ans=temp+revnum;
revnum=0;
c=ans;
while(c>0)
{
rem=c%10;
revnum=revnum*10+rem;
c=c/10;
}
count++;
x=ans;temp=ans;
}while(revnum!=ans);
return revnum;
}
int main()
{
long n;
int t;
scanf("%d",&t);
while(t--)
{ count =0;
scanf("%ld",&n);
printf("%d %ld\n",count, revadd(n));
}
return 0;
}
Posted: Wed Dec 14, 2005 3:40 pm
by chunyi81
Read the problem description:
You might assume that all tests data on this problem:
- will have an answer ,
- will be computable with less than 1000 iterations (additions),
- will yield a palindrome that is not greater than 4,294,967,295.
long is not enough for this problem. Use unsigned long, unsigned int or long long. The reason of the TLE of your code is most likely integer overflow.
Posted: Wed Dec 14, 2005 4:20 pm
by abhi
thanks i got AC!!!!
but still my time is 0.039s.
how do i reduce it to 0.00 or atleast 0.010s ?
Posted: Wed Dec 14, 2005 4:28 pm
by abhi
i changed unsigned long long to unsigned long after getting accepted in 0.039 and got AC in 0.016s
......but is there any other way to reduce it to 0.010 or 0.001 s
Posted: Thu Dec 15, 2005 4:48 am
by chunyi81
I am not very sure about. In fact, you code was faster than my own AC code which used cin/cout and ran in 0.082s. I managed to optimize my own code to get 0.016s but could not go any faster. However, I am not sure if working with the string representation of the numbers can be faster. Getting the first digit and last digit is fast, and reversing a string can be done using STL or your own reverse method. Adding the numbers in string form still uses additions only. This might be faster than using division, multiplication and modulo. But I have seen in an earlier thread that it is possible to get 0.010s using unsigned long. I am not sure how this can be done though.
There are also threads in this forum regarding fast I/O using fread/fwrite. You might want to check those out.
10018 - WA no way :(
Posted: Wed Jun 07, 2006 9:47 am
by fixit
Code: Select all
{function str2int(s:string):longint;
var liczba:longint;lol:integer;
begin
val(s,liczba,lol);
str2int:=liczba;
end;}
function int2str(l:int64):string;
var tmp:string;
begin
str(l,tmp);
int2str:=tmp;
end;
function reverse(a:int64):int64;
var j:int64;
begin
j:=0;
while a<>0 do
begin
j:=j*10+(a mod 10);
a:=a div 10;
end;
reverse:=j;
end;
function palindrom(l:int64):boolean;
var liczba:string;i:integer;a:boolean;
begin
a:=true;
if (l mod 11 = 0) then
begin
liczba:=int2str(l);
for i:=1 to (length(liczba) div 2) do
if liczba[i]<>liczba[length(liczba)-i+1] then
begin a:=false; break; end ;
end else
if not (l div 10=0) then a:=false;
palindrom:=a;
end;
var i,zestaw,count:integer;liczba:int64;
begin
readln(zestaw);
for i:=1 to zestaw do
begin
readln(liczba);count:=1;
liczba:=liczba+reverse(liczba);
while not palindrom(liczba) do
begin
inc(count);
liczba:=liczba+reverse(liczba);
end;
writeln(count,' ',liczba);
end;
end.
I tested it and it looks fine - but i gettin W/A
Can somebody help ?
OUT PUT LIMIT EXCCEDED
Posted: Fri Jul 07, 2006 5:04 pm
by vinit_iiita
Code: Select all
#include<iostream>
using namespace std;
bool pal(unsigned int x)
{
unsigned int a,b=0;
a=x;
while (a>0)
{
b=10*b+(a%10);
a=a/10;
}
if (b==x)
return false;
else
return true;
}
unsigned int rev(unsigned int n)
{ bool flag;
unsigned int m,t;
int c=0;
m=n;
flag=pal(n);
if(!flag){cout<<0<<" ";
return n;}
while (flag==true)
{
t=0;
while (m>0)
{
t=10*t+(m%10);
m=m/10;
}
t=n+t;
c++;
flag=pal(t);
if (flag==true)
{n=t;
m=t;
}
}
cout<<c<<" ";
return t;
}
int main()
{
int n,i=0;
cin>>n;
while (i<=n)
{
unsigned int a,b;
cin>>a;
b=rev(a);
cout<<b<<endl;
}
return 0;
}
Posted: Fri Jul 07, 2006 5:10 pm
by vinit_iiita
In my code OUT PUT LIMIT is Excceding WHY ..??
Posted: Fri Jul 07, 2006 6:18 pm
by vinit_iiita
I got it AC
in .025s
10018 WA - It seems all right on my computer
Posted: Fri Jul 14, 2006 5:38 pm
by pioneerLike
I've test all input datas which provided by other people.
It seems all right on my computer.
I used recursive func. to solve this problem, I know this is a bad way, but I think it should work?
So please give me some advice, thx.
Code: Select all
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long long add (long long a,char* buf1,char* buf2);
void rev (char* buf1,char* buf2);
long long int count = 0;
long long int add (long long p,char* buf1,char* buf2){
long long added,j,k;
char check1[100],check2[100];
sprintf(buf1,"%d",p);
rev(buf1,buf2);
j = atoi(buf1);
k = atoi(buf2);
added = j+k;
sprintf(check1,"%d",added);
rev (check1,check2);
count++;
if (strcmp(check1,check2) == 0) {
return added;
} else {
added = add (added,buf1,buf2);
}
}
void rev (char* buf1,char* buf2) {
int i,z;
z=0;
for (i=strlen(buf1)-1;i>=0;i--){
buf2[z] = buf1[i];
z++;
}
buf2[z] = '\0';
}
int main(){
long long p;
int N;
int i;
char buf1[100],buf2[100];
long long result;
scanf("%d",&N);
for (i=1;i<=N;i++){
scanf("%lld",&p);
count = 0;
result = add (p,buf1,buf2);
printf("%lld %lld\n",count,result);
}
return 0;
}