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
pioneerLike
New poster
Posts: 2
Joined: Fri Jul 14, 2006 5:34 pm

10018 [TLE] - Checked some place that may occur error,but...

Post by pioneerLike »

Well......
I solve the problem in "int arrays".
It runs great on my computer, but obviously, OJ didn't think so.
Plz look at my code and give me some suggestions, thanks alot!

1:28AM, Taiwan.

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int count = 0;
int digits = 0;

void rev (int* int1,int* int2,int digits) {
         int i,j=0;
         for (i=digits-1;i>=0;i--) {
            int2[j] = int1[i];
            j++;
         }
}

unsigned long itoi (int* a , int digits) {
    int i;
    unsigned long result=0;
    for (i=0;i<digits;i++) {
        result = result*10 + a[i];
    }
    return result;
}

int main(){
    int N;
    int i,j;

    int int1[100],int2[100];
    char buf[100];
    unsigned long result;

    scanf("%d",&N);

    for (i=1;i<=N;i++){
    
        count = 0;
        
        scanf("%s",buf);
        digits = strlen(buf);
        for (j=0;j<digits ;j++) {
            int1[j] =(int)(buf[j] - '0');
        }
        
        while (1) {
        
              rev(int1,int2,digits);  /*Reverse*/
              
              for (j=0;j<digits;j++) {            /*Checking if the "Reverse&Add" is over*/

                  if (int1[j] != int2[j]) {
                     break;
                  }
              }
              if ( !(j<digits) && count != 0 ) {
                 break;
              }
              
              result = itoi(int1,digits) + itoi(int2,digits); /*Add*/

              sprintf(buf,"%U",result);
              digits = strlen(buf);
              for (j=0;j<digits;j++) {
                  int1[j] =(int)(buf[j] - '0');
              }

              count++;
        }

        printf("%lu %lu\n",count,result);

    }

    return 0;
}

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

Re: 10018 [TLE] - Checked some place that may occur error,bu

Post by tan_Yui »

Hi, pioneerLike.
My machine(Borland C++ Compiler 5.5) also get TLE with your code for sample input.
If your execution code can get any result still now, it's better to check the compiler or replace it with other one, I think.

Code: Select all

              sprintf(buf,"%U",result);
Change %U -> %lu, because 'result' is unsigned long type.
You'll get Accepted, after this change. :)

Best regards.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

In your code, you have

Code: Select all

sprintf(buf1,"%d",p); 
.
.
.
sprintf(check1,"%d",added); 
Why are you converting a long long to -> int -> to string?

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton »

deleted
Last edited by newton on Sat Sep 23, 2006 6:26 am, edited 1 time in total.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Runtime Error CUP TIME is 0.002

Post by 58050zz »

Runtime Error CUP TIME is 0.002
can somebody tell me where is the problem
really thanks

Code: Select all


#include <iostream>
using namespace std;
#include <fstream>
#include <string>
#include <cmath>
//#include <iomanip>
//#include <vector>
//#include <list>
//#include <set>  // multiset class-template definition
//#include <algorithm>
//cout << left << setw( 10 ) << "Account" << setw( 13 ) 
#include <cstdio> 
#include <cstdlib> 
const unsigned int kirgsimal[10]
	={1,10,100,1000,10000,
		100000,1000000,10000000,100000000
		,1000000000
		};
unsigned int Centesimal(const unsigned int &kriNum)
{
	//計算有幾位數
	unsigned int i=10,iCentesimal=1;
	while(true)
	{
		if((kriNum/i)==0)
			break;
		else{
			++iCentesimal;
			i*=10;
		}
	}
	//
	return iCentesimal;
}
unsigned int Reverse(const unsigned int &kriNum,const unsigned int &kriCentesimal)
{
	int icCentesimal=0;

	int iTarget=0;
	while(kriCentesimal>icCentesimal)
	{
		iTarget+=
		(	(kriNum % kirgsimal[icCentesimal+1])
			/ kirgsimal[icCentesimal]
			) * kirgsimal[kriCentesimal-icCentesimal-1];
		++icCentesimal;
	}
	return iTarget;
}
bool theRule(const unsigned int &kriNum,const unsigned int &kriCentesimal)
{
	unsigned int iHalf=kriCentesimal/2;
	unsigned int iReverse=Reverse(kriNum,kriCentesimal);
	unsigned int i1,i2;
	for(int i=1;i<=iHalf;++i)
	{
		i1=(kriNum%kirgsimal[i])
			/kirgsimal[i-1];
		i2=(iReverse%kirgsimal[i])
			/kirgsimal[i-1];
		if(i1!=i2)
			return false;
	}
	return true;
}
void Add(const unsigned int &kriNum,unsigned int *iprgAnsTime
			,unsigned int *iprgAnsNum,const unsigned int ki_cCase)
{

	unsigned int iTimes_Re=0;
	unsigned int iNum=kriNum;
	unsigned int iCentesimal=Centesimal(iNum);
	do{
		
		iNum=iNum+Reverse(iNum,iCentesimal);		
		
		++iTimes_Re;
		iCentesimal=Centesimal(iNum);
	}while(!theRule(iNum,iCentesimal));

	iprgAnsTime[ki_cCase]=iTimes_Re;
	iprgAnsNum[ki_cCase]=iNum;

}
#define MAX 9999
int main(void) {  
        
	unsigned int cInput[MAX];
    //ifstream inClientFile( "01.txt", ios::in );
	//string line;	
	
	int i_nCase,i_cCase=0;
	cin>>i_nCase;
	unsigned int iprgAnsTime[MAX];
	unsigned int iprgAnsNum[MAX];
	while (i_cCase<i_nCase)
	{
		cin>>cInput[i_cCase++];		
	} 

	i_cCase=0;
	while (i_cCase<i_nCase)
	{
		Add(cInput[i_cCase],iprgAnsTime
			,iprgAnsNum,i_cCase);	
		i_cCase++;
	} 

	i_cCase=0;
	while (i_cCase<i_nCase)
	{
		
		cout<<iprgAnsTime[i_cCase]<<' '
			<<iprgAnsNum[i_cCase]<<endl;
		i_cCase++;
	}

	//system("pause");        
	return 0; 
}


Steven Luck
New poster
Posts: 13
Joined: Sat Dec 02, 2006 7:51 am
Location: Indonesia
Contact:

10018 - WA

Post by Steven Luck »

I still get WA with this code:

Code: Select all

Deleted after AC
Can anyone help?
Thanx.
Last edited by Steven Luck on Wed Dec 06, 2006 4:30 pm, edited 1 time in total.
"The Only Thing For The Triumph of Evil is For a Good Man to Do Nothing"

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy »

change "%lu" to "%ld"


Best of luck....
Last edited by joy on Sat Dec 02, 2006 4:35 pm, edited 1 time in total.
form kisui na ... class tai asol....
iF U hv d class u get the form....

Steven Luck
New poster
Posts: 13
Joined: Sat Dec 02, 2006 7:51 am
Location: Indonesia
Contact:

Post by Steven Luck »

I don't catch it, if the data will yield a palindrome that is not greater than 4,294,967,295, shouldn't it be enough with unsigned long??

And, if s is used to store the string of the unsigned long, 11 should be enough, isn't it?

Btw, I've tried using long long and changing s to s[110], but the output is not:
3 12574247521
but:
15 1266996621

Can u explain it further to me?
Thanx.
"The Only Thing For The Triumph of Evil is For a Good Man to Do Nothing"

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Steven Luck wrote:I don't catch it, if the data will yield a palindrome that is not greater than 4,294,967,295, shouldn't it be enough with unsigned long??
And, if s is used to store the string of the unsigned long, 11 should be enough, isn't it?
You are right. But the identifier for 'unsigned long' is '%lu' not '%ld'. Hope it helps. And dont open a new thread if there is one already. Try to post in the existing threads. 10018 has almost 30 threads already.
Ami ekhono shopno dekhi...
HomePage

Steven Luck
New poster
Posts: 13
Joined: Sat Dec 02, 2006 7:51 am
Location: Indonesia
Contact:

Post by Steven Luck »

Ok, thanx. I'll post in the same thread next time :)
"The Only Thing For The Triumph of Evil is For a Good Man to Do Nothing"

Steven Luck
New poster
Posts: 13
Joined: Sat Dec 02, 2006 7:51 am
Location: Indonesia
Contact:

Post by Steven Luck »

Still don't get it. After changing the %ld with %lu (unsigned long), for the input:

Code: Select all

1
429496295
I get:

Code: Select all

11 2893333982
And, using long long (%lld, right?), I get:

Code: Select all

15 1266996621
Shouldn't it be:

Code: Select all

3 12574247521
??

Here's the new code:

Code: Select all

Deleted after AC
Anything wrong with the algorithm?
Last edited by Steven Luck on Wed Dec 06, 2006 4:32 pm, edited 1 time in total.
"The Only Thing For The Triumph of Evil is For a Good Man to Do Nothing"

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Read the description again. The problem states....
will yield a palindrome that is not greater than 4,294,967,295
So, your input is not a valid one. And 2nd thing - your code is correct, except one line. Imagine that the given input is a plaindrome. Then what should be the output? Read the problem description again to find a suitable answer :D.
Ami ekhono shopno dekhi...
HomePage

Steven Luck
New poster
Posts: 13
Joined: Sat Dec 02, 2006 7:51 am
Location: Indonesia
Contact:

Post by Steven Luck »

I found out that the last code I posted was already correct. Since I read the topic from the other posts saying the testcase

Code: Select all

1
429496295
will ouput

Code: Select all

3 12574247521
, I thought my code was wrong. I just realize that it's not a valid input.
Thanx, Jan and Joy.
"The Only Thing For The Triumph of Evil is For a Good Man to Do Nothing"

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

10018 WA, just a palinedrome be printed or not?

Post by deadangelx »

I code a "longLongIntAdd" function to try to use string add string to avoid int overflow. And I try some data to test. The answer seems right. But I still got WA. What's wrong with this code? Help!!
1.just a palinerdome be printed or not
2.overflow int be printed or not

now I didnt print above but still WA

Code: Select all

#include <stdio.h>
#include <string.h>

int longLongIntAdd(char s1[],char s2[]);
int lessThanInt(char s[]);

main()
{
  int i,x,d,num,mid,flag,count,digit;
  char buf[100][BUFSIZ],re[100][BUFSIZ],record[BUFSIZ];
  while(fgets(record,BUFSIZ,stdin)!=NULL) 
    {if(1<=(num=atoi(record))&&num<=100) break;}
  x=i=0;
  while(i<num) 
  {
    fgets(buf[i],BUFSIZ,stdin);
    buf[i][(d=strlen(buf[i])-1)]='\0';
    i++;
  }
  while(x<num)
  {
    flag=count=0;
    /* check if just a palinedrome */
    d=strlen(buf[x])-1; i=0;
    if(d<0) mid=0; else mid=d/2;
    while(buf[x][i]==buf[x][d])
    {
      if(i>=mid) {flag=1; break;}
      i++; d--;
    }
    /* end -- check if just a palinedrome */
    
    while(!flag)
    {
      d=strlen(buf[x])-1; i=0;
      while(d>=0) {re[x][d]=buf[x][i]; d--; i++;}
      re[x][i]='\0';
      digit=longLongIntAdd(buf[x],re[x]);
      if(digit==BUFSIZ||lessThanInt(buf[x])<0) break;
      d=strlen(buf[x])-1; i=0;
      if(d<0) mid=0; else mid=d/2;
      while(buf[x][i]==buf[x][d])
      {
        if(i>=mid) {flag=1; break;}
        i++; d--;
      }
      count++;
      if(flag) {printf("%d %s\n",count,buf[x]); break;}
    }
    x++;  
  }
}

int longLongIntAdd(char s1[BUFSIZ],char s2[BUFSIZ])
{
  int i,j,temp,lend,digit;
  char d[BUFSIZ];
  i=strlen(s1)-1;
  j=0;
  lend=0;
  while(i>=0)
  {
    temp=(s1[i]-48)+(s2[i]-48)+lend;
    lend=0;
    if(temp>9) {temp-=10; lend=1;}
    d[j]=temp+48;
    j++; i--;
  }
  if(lend>0)
  {
    if(j==BUFSIZ)
      return BUFSIZ;
    d[j]=49; 
    if(j<(BUFSIZ-1)) d[(j+1)]='\0';
  }
  else d[j]='\0';
  j=strlen(d)-1;
  i=0;
  while(j>=0)
  {
    s1[i]=d[j];
    j--; i++;
  }
  s1[i]='\0';
  return i;
}

int lessThanInt(char s[BUFSIZ])
{
  char d[11]={'4','2','9','4','9','6','7','2','9','5','\0'};
  int i;

  if((i=strlen(s))>10) return -1;
  if(i<10) return 1;
  return (i=strcmp(d,s));
}
thanks everyone.
Last edited by deadangelx on Tue Feb 13, 2007 6:02 pm, edited 4 times in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

There are many threads on this problem..
Try to search first and don't make a new thread if there is one already..

Post Reply

Return to “Volume 100 (10000-10099)”