202 - Repeating Decimals

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

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

Post by jahangirk » Mon Jun 28, 2004 9:14 am

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[100000];
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

Post by helmet » Mon Jun 28, 2004 10:12 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.

Post by jahangirk » Mon Jun 28, 2004 11:40 am

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 ;).

I didnt read ur algo so I dunno about TLE...

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

Post by shamim » Mon Jun 28, 2004 12:05 pm

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

Post by jahangirk » Mon Jun 28, 2004 8:06 pm

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

Post by shuniu » Fri Jul 02, 2004 9:01 pm

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
Location: bangladesh
Contact:

202-why WA?

Post by joshila21 » Sun Jul 11, 2004 11:17 pm

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[5000],numerator[5000];

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

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Fri Aug 27, 2004 6:27 am

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:

Post by Ryan Pai » Fri Aug 27, 2004 10:43 am

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.

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Fri Aug 27, 2004 3:24 pm

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

Post by nesqi » Thu Sep 30, 2004 4:28 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

Post by nesqi » Thu Sep 30, 2004 5:37 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:

Post by nghiank » Thu Oct 07, 2004 8:43 am

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

Post by Iwashere » Fri Feb 04, 2005 2:36 pm

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.

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

Post by shamim » Mon Feb 07, 2005 8:27 am

Hi, increase the table size to 4000, instead of 1000. :wink:

Post Reply

Return to “Volume 2 (200-299)”