10018 - Reverse and Add

[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

[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.

[tan_Yui]

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.

[tan_Yui]

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.

[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

[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;
}

[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.

[abhi]

thanks i got AC!!!!
but still my time is 0.039s.
how do i reduce it to 0.00 or atleast 0.010s ?

[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

[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.

[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 ?

[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;
          }     

[vinit_iiita]

In my code OUT PUT LIMIT is Excceding WHY ..??

[vinit_iiita]

I got it AC in .025s

[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;
}