10018 - Reverse and Add

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Re: 10018

Post 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 :lol:

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10018

Post 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.
Last edited by tan_Yui on Thu Mar 10, 2005 7:12 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10018

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

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10018

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Re: 10018

Post 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. :D

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 :lol:

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

10018

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



chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

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

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi »

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

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi »

i changed unsigned long long to unsigned long after getting accepted in 0.039 and got AC in 0.016s 8)
......but is there any other way to reduce it to 0.010 or 0.001 s

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

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

fixit
New poster
Posts: 5
Joined: Tue Jun 06, 2006 7:39 pm

10018 - WA no way :(

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

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

OUT PUT LIMIT EXCCEDED

Post 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;
          }     
win

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita »


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

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita »


I got it AC :D in .025s
win

pioneerLike
New poster
Posts: 2
Joined: Fri Jul 14, 2006 5:34 pm

10018 WA - It seems all right on my computer

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

Post Reply

Return to “Volume 100 (10000-10099)”