202 - Repeating Decimals

[jahangirk]

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

[helmet]

I wasnt right.

In the process I got AC for this problem.

Try 275 for ideas on this problem.

[jahangirk]

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

[shamim]

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]

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]

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]

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

[GreenPenInc]

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]

[Ryan Pai]

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

[GreenPenInc]

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!

[nesqi]

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]

I found my problem...

Test this one:

Input:
260 606

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

[nghiank]

try this one
Input
1 2999

[Iwashere]

why why TLE?

Code: Select all

Deleted after AC

[shamim]

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