## 202 - Repeating Decimals

Moderator: Board moderators

jahangirk
New poster
Posts: 5
Joined: Sat Jun 26, 2004 11:15 pm

### 202 Repeating decimal. Why TLE somebody help me plzz

I am getting Time limit exceed. To me i have created an efficient algo and it is giving me correct answer if anybody have better logic than mine plz help me

[cpp]#include <stdio.h>
#include<iostream>
using namespace std;

int Z;
int num, den;
int i=0;
void init();

int main()
{
cin>>num;
cin>>den;
int flag=0;
int num1 = num;
int den1 = den;

while(1)
{
flag=0;
int zb=0;
int digit=0;
cout<<num1<<"/"<<den1<<" = ";
init();
int check = num1/den1;
if(check > 0)
{
cout<<check<<".(";
int temp = check * den1;
num1 = num1 - temp;
}
else
cout<<"0.(";
int count = 0;
while(1)
{
count++;
num1=num1 * 10;
zb= num1 % den1;
if( zb == 0)
{
cout<<num1/den1;
cout<<")";
cout<<"\n"<<"\t1 = number of digits in repeating cycle\n";
flag=1;
}
if(flag==1)
{
break;
}

if( Z[num1] != -1 )
{
if(count > 50)
cout<<"...";
if(check <= 0)
cout<<")";
cout<<"\n\t"<<(digit-Z[num1])<<" = number of digits in repeating cycle\n";
flag=1;
}
if(flag==1)
{
break;
}
if(count <= 50)
cout<<num1/den1;

Z[num1]= digit;

num1 = num1%den1;

digit++;
}
i++;
cin>>num>>den;
num1 = num;
den1 = den;
}

return 0;
}

void init()
{

for(int i= 100000;i>0; i--)
{
Z= -1;
}
}
Last edited by jahangirk on Mon Jun 28, 2004 11:30 am, edited 2 times in total.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am
I wasnt right.

In the process I got AC for this problem.

Try 275 for ideas on this problem.
Last edited by helmet on Fri Jul 02, 2004 1:18 pm, edited 1 time in total.
Just another brick in the wall...

jahangirk
New poster
Posts: 5
Joined: Sat Jun 26, 2004 11:15 pm

### i think my program result is correct on ur intputs as well.

helmet wrote:I dunno why ur code is TLE but I can tell u why it will be WA anyways.

Try input of
3 4
99 99
99 100

I dont quite think the desired result is got .

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
jahangirk:

There is no breaking condition in your program, to cause it to terminate. It expects to take input forever. For this reason it is getting TLE.

jahangirk
New poster
Posts: 5
Joined: Sat Jun 26, 2004 11:15 pm

### Then plz tell me wht is the breaking condition

shamim wrote:jahangirk:

There is no breaking condition in your program, to cause it to terminate. It expects to take input forever. For this reason it is getting TLE.

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

### 202 - Correcting the PE

I noticed lots of people got PE on 202. Reason is that the problem left out some details in the output format. The tricky thing being, there should be an empty line FOLLOWING each test case (notice it is FOLLOWING, not "between" like most problems).

The sample output looks like this:

Code: Select all

``````76/25 = 3.04(0)
1 = number of digits in repeating cycle
[emptyline]
5/43 = 0.(116279069767441860465)
21 = number of digits in repeating cycle
[emptyline]
1/397 = 0.(00251889168765743073047858942065491183879093198992...)
99 = number of digits in repeating cycle
[emptyline]``````
Getting PE may not matter to some people, but it bugged me for a while.

joshila21
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Contact:

### 202-why WA?

i don't know what is wrong with this code.
it seems OK! to me.
can anyone help me to findout the mistake?

#include <stdio.h>

int fraction,numerator;

int main()
{
int i,j,k,n,a,b,remainder_a_b,rem,sd=0,exception,minus_;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(sd)printf("\n");
(rem=a,i=0,k=0,exception=0,minus_=0);
remainder_a_b=(a%b);
numerator[i++]=a;
a=remainder_a_b*10;
while(1)
{
while(b>a)
{
numerator=a;
for(j=0;j<i;j++)
if(a==numerator[j])
{
minus_=j;
goto L1;
}
i++;
a*=10;
fraction[k++]=0;
}
for(j=0;j<i && k;j++)
if(a==numerator[j])
{
minus_=j;
break;
}
if(j<i && k)break;
numerator[i++]=a;
fraction[k++]=a/b;
remainder_a_b=(a%b);
if(remainder_a_b)
a=remainder_a_b*10;
else
exception=1;
}
L1:
if(exception)
printf("%d/%d = %d.",rem,b,rem/b);
else
printf("%d/%d = %d.",rem,b,rem/b);
if(!minus_)printf("(");
for(j=0;j<k;j++)
{
if(minus_ && k-(k-minus_+1)==j && !exception)printf("(");
printf("%d",fraction[j]);
if(j==49)
{
printf("...");
break;
}
}
if(exception)
printf("(0)\n 1 = number of degits in repeating cycle\n");
else
{
if(minus_)k=k-minus_+1;
printf(")\n %d = number of degits in repeating cycle\n",k);
}
sd=1;
}
return 0;
}
be a good man

GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:
Yet another program that should be correct, handles all test output found on the forums without a hitch (even the input that doesn't correspond to the problem description) and still gets WA. What's up with this problem?

[cpp]
#include <iostream>
#include <string>

#define MAX 10000
#define LONGEST_VISIBLE 50

using namespace std;

/*********************************************************/
/* Globals */

int num, denom, pattern_length;
bool used[MAX];
int position[MAX];

/*********************************************************/
/* Functions */

void init(void)
{
for (int i = 0; i < MAX; i++)
used = false;
}

/* Returns the string of decimals to print, and sets the pattern_length */
string decimals(void)
{
int index = 0; // decimal position
string dec = "";
int rem = num % denom;
while (!used[rem])
{
used[rem] = true;
position[rem] = index++;
rem *= 10;
if (index <= LONGEST_VISIBLE)
dec = dec + char(rem / denom + '0');
rem %= denom;
}
pattern_length = index - position[rem];
if (index > LONGEST_VISIBLE)
dec = dec + "...";
dec = dec.substr(0, position[rem]) + "(" + dec.substr(position[rem]) + ")";
return dec;
}

int main(int argc, char **argv)
{
while (cin >> num >> denom)
{
init();
cout << num << "/" << denom << " = " << (num / denom) << "." << decimals() << endl << " " << pattern_length << " = number of digits in repeating cycle" << endl << endl; }
return 0;
}
[/cpp]
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
GPI,

I copied your code and put it through my compiler and then ran it against the sample input. The answers all looked correct except the pattern length always seemed to lag a test case behind. For example, the output for test case 2 was case 1's pattern length.
I think the cause is:

[cpp]cout << num << "/" << denom << " = " << (num / denom) << "." << decimals() << endl << " " << pattern_length << " = number of digits in repeating cycle" << endl << endl;[/cpp]

Since operator<< is basically a function call, and the order of evaluation of function call arguments is arbitrary, it's a bad idea to have arguments depend on it (namely, pattern_length depends on decimals() having already been called).
I'm always willing to help, if you do the same.

GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:
Brilliant! It worked first try!

That had really been bugging me, because I knew there couldn't have been anything wrong with my logic. It was too simple! Now I know the problem was with my understanding of the language, and I can rest easy. Thanks again!
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

nesqi
New poster
Posts: 5
Joined: Thu Sep 30, 2004 4:18 pm
Input:
1 2971
1 251
1 613

Output:
1/2971 = 0.(00033658700774150117805452709525412319084483338943...)
2970 = number of digits in repeating cycle

1/251 = 0.(00398406374501992031872509960159362549800796812749)
50 = number of digits in repeating cycle

1/613 = 0.(00163132137030995106035889070146818923327895595432...)
51 = number of digits in repeating cycle

However... I too get WA.

Valladolid realy sucks. It takes you 60 min to solve a problem and then it takes 5*60 min to find some fucking insignificant crap error that gives you WA. It's even common with faulty input!

#

nesqi
New poster
Posts: 5
Joined: Thu Sep 30, 2004 4:18 pm
I found my problem...

Test this one:

Input:
260 606

Output:
260/606 = 0.(4290)
4 = number of digits in repeating cycle

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:
try this one
Input
1 2999

Iwashere
New poster
Posts: 20
Joined: Mon Aug 11, 2003 1:50 pm
Location: Singapore

### 202: Repeating Decimals TLE

why why TLE?

Code: Select all

``````Deleted after AC
``````
Last edited by Iwashere on Mon Feb 07, 2005 3:10 pm, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Hi, increase the table size to 4000, instead of 1000. 