Page 18 of 19

Posted: Sun Jul 29, 2007 7:29 am
by safayat rahaman
why wrong answer.please help me .give me some critical input output.
here is my code_

Code: Select all

#include<stdio.h>

#include<math.h>
long power(long,long);
main()
{
long arr[10000];

long a,pwr,b,c,d,e,i,flag,n,flag1,n1,h2;
long j,wm,h,h1,NWM,H;
arr[0]=1;
arr[1]=2;
i=1;
for(j=3;j<10000;j=j+2)
{
	for(a=1;arr[a]<=sqrt(j);a++)
	  {
	  if(j%arr[a]==0)break;
	  }
if(arr[a]>sqrt(j))
	{i=i+1;
	arr[i]=j;

	}
}
for(;;)
{
scanf("%ld%ld",&wm,&h);
if(wm==0&&h==0)break;
if(h==1)
h2=wm;
else
h2=h;

n=1;b=0;flag1=0;n1=1;
if(wm-h>1&&h!=0)
{
for(a=1;arr[a]<=sqrt(h2);a++)
  {
  for(c=1;h2%arr[a]==0;c++)
   {h2=h2/arr[a];
   if(c==1)
   n=arr[a]*n;
   if(flag1==0)
   b++;
   }
   if(b!=0)flag1=1;
   if(h2==1)
   break;
  }
if(h2!=1)
n=n*h2;
if(power(n+1,b)!=wm)
	{n1=n;
	for(c=1;c<=b;c++)
	   if(b%c==0)
	   {
	   n=power(n1,c);
	   pwr=b/c;
	   if(power(n+1,pwr)==wm)
		{b=pwr;break;}
	   }
	}

if(h==1){NWM=b;n=1;}
else
NWM=(h-1)/(n-1);
}
if(wm!=h&&h!=0)
{if(wm-h==1)
  {NWM=1;b=1;n=h;}
H=power(n+1,b+1)-power(n,b+1);
}
else
  {
  if(wm==h==1)
   {
   NWM=0;
   H=1;
   }
  if(h==0)
   {
   NWM=1;
   H=wm;
   }
   }
  printf("%ld %ld\n",NWM,H);

 }
return 0;
}
long power(long n,long m)
	{
	long sum,a;
	sum=1;
	for(a=1;a<=m;a++)
	   sum=sum*n;
	return sum;
	}

Posted: Fri Aug 10, 2007 11:43 am
by DiogoPimenta
I'm getting WA too and my code calculates good anwsers on the examples given in the forum.
Can someone provide test inputs and AC results ?? So i can see if i'm getting any WA.

I also saw many AC posts that give answer to wrong input, I dont want that kind of input for my tests !!

Thanks

Getting Wrong Answer

Posted: Fri Aug 10, 2007 12:44 pm
by DiogoPimenta
I don't have math skills, so i try to solve this just using integers.

I find N and k (number of cat "generations") by cheking the reminders.

for the example input

216 125

I calculate like this

(N = 2)

216 % 2+1 = 0
125 % 2 = 1 // This reminder as to be 0 there is no such this as a HalfCat -> next N


(N=3)
216 % 3+1 = 0
125 % 3 = 2 // next N

... and so on

(N=5)
216 % 5+1 = 0
125 % 5 = 0

Here a possible N is found so we try to get to the end of the tree getting valid results and getting k as well

k = 1

216 / 5+1 = 36
125 / 5 = 25

Using same method now with the results

36 % 5+1 = 0
25 % 5 = 0 // if one of these were != 0 will would have to try next N

k++

36 / 5+1 = 6
25 / 5 = 5

6 % 5+1 = 0
5 % 5 = 0 // if one of these were != 0 will would have to try next N


k++

6 / 5+1 = 1
5 / 5 = 1

Ok! N = 5 and k = 3

if I don't get a result 1 and 1, and one of them is less than 1, then we will have to try another N

Still i get WA on the judge.
I've tested all input examples on the forum on another posts, and still my code calculates all corrected.

So please, provide me with some test inputs because i can't find no one with AC code that gets diferent anwsers than mine.

(sorry my bad english)

Thanks

Posted: Fri Aug 10, 2007 1:41 pm
by DiogoPimenta
I get same output, and still i get WA!!! Do you have more inputs to test ??

My code does not give an anwser when a bad input like 100 1 is given, and it doesn't loop forever, simply get to the next input. AND STILL I GET WA... provide-me with inputs please...

Posted: Fri Aug 10, 2007 6:21 pm
by DiogoPimenta
I get WA.

I've tested all inputs on the post and get the same anwsers, but i'm ignoring bad inputs like.

3 1
100 1
25 60
9 9

Please feed me with more inputs please

Thanks

Posted: Fri Aug 10, 2007 7:02 pm
by DiogoPimenta
Is

1 14

a valid input ??

Posted: Thu Aug 30, 2007 1:10 pm
by krap
I seem to get RTE too. Here is my code so if anybody sees something wrong, let me know guys!

Thanks in advance!

Code: Select all

#include <stdlib.h>
#include <iostream.h>
#include <math.h>

int main()
{

  unsigned int initialCatsHeight;
  unsigned int nofWorkingCats;

  int upperLimit = 200;
  int allInputs[1000] [2];
  int inputCount = 0;
  char input[50];

  do
  {
    cin.getline( input, 50 );

    char integer1[20];
    char integer2[20];
    bool otherString = false;
    int j = 0;

    for ( unsigned int i = 0; i < strlen( input ); i++ )
    {
      if ( input[i] == ' ' )
      {
        integer1[j] = '\0';
        otherString = true;
        j = 0;
      }
      else if ( otherString == false )
      {
        integer1[j] = input[i];
        j++;
      }
      else
      {
        integer2[j] = input[i];
        j++;
      }
    }

    integer2[j] = '\0';

    allInputs[inputCount] [0] = atoi( integer1 );
    allInputs[inputCount] [1] = atoi( integer2 );

    inputCount++;
  }
  while ( allInputs[inputCount - 1] [0] != 0 && allInputs[inputCount - 1] [0] != 0 );

  for ( int i = 0; i < (inputCount - 1); i++ )
  {
    initialCatsHeight = allInputs[i][0];
    nofWorkingCats = allInputs[i][1];

    if ( initialCatsHeight == 1 && nofWorkingCats == 1 )
    {
      cout << "0 1" << endl;
    }
    else
    {
      unsigned int nofNotWorkingCats = 1;
      unsigned int totalHeight = initialCatsHeight + nofWorkingCats;

      int catsInHat;
      int nofDifferentHeights;
      bool redAlert = false;

      for ( int i = 2; i <= upperLimit; i++ )
      {

        float r;
        float t;

        float exponent = 1.0 / ( float )( i - 1 );

        r = pow( nofWorkingCats, exponent );
        t = pow( initialCatsHeight, exponent );

        if ( t == r + 1 )
        {
          catsInHat = ( int )r;
          nofDifferentHeights = i;
          break;
        }

        if ( i == upperLimit )
        {
          redAlert = true;
        }
      }

      if ( !redAlert )
      {
        for ( int i = 1; i <= ( nofDifferentHeights - 2 ); i++ )
        {
          nofNotWorkingCats += ( float )pow( catsInHat, i );
        }

        double temp = 0.0;

        for ( int i = 1; i < ( nofDifferentHeights - 1 ); i++ )
        {
          double base = ( double )catsInHat / ( double )( catsInHat + 1 );
          temp += pow( base, i );
        }

        if ( ( temp - abs( temp ) ) != 0 )
        {
          double temp2 = temp * pow( 10.0, 9.0 );
          double fraction = temp2 - abs( temp2 );

          if ( fraction >= 0.5 )
          {
            fraction = ceil( fraction );
          }
          else
          {
            fraction = floor( fraction );
          }

          temp = abs( temp2 ) + fraction;
          temp = temp * pow( 10.0, -9.0 );
        }

        totalHeight += ( unsigned int ) ( temp * initialCatsHeight );
        cout << nofNotWorkingCats << " " << totalHeight << endl;
      }
    }
  }
}

Posted: Thu Aug 30, 2007 2:05 pm
by krap
Well you can see it as a tree but I believe that the total height is formed by both internal and external nodes.

Anyhow by having a glance at your code I could't understand what you're doing!

Would you mind extending in natural language?

Be well

Posted: Wed Oct 10, 2007 9:42 pm
by baodog
You have rounding error, try adding/subtracting a small epsilon.

Need help understand my comipler (Dev C++ 4.9.9.2)

Posted: Wed Jan 30, 2008 5:23 am
by mwiley63
I solved problem number 107 mathematically and fell apart when I came to testing my code in Dev C++. So I did some looking around on the forums and realized that it could have been due to my compiler as to why my numbers seemed incorrect.

So I decided to submit the problem to the online judge just to see what would happen, and I got an AC much to my surprise. I then uploaded the code to my school's ssh server, and it compiled fine on there running gcc 4.2.1 with the correct outputs.

This raises two questions.

Does the compiler used by Dev C++ treat unsigned shorts and longs different then the compiler used by the judge? Or is it functions from the math library that are treated differently such as pow? Could someone explain this to me?

I tried to download the gnu 4.1.2 compiler off the web and I am on windows. I could not figure out how to untar the compiler file in windows or how I would get dev C++ to use it. If anyone could offer me any help with this, I would appreciate it greatly.

TLE in 107(cats in hats)

Posted: Thu Jun 05, 2008 3:14 pm
by kbr_iut
thanx jan vi I solved the problem without using double.
one trick:::for those who cudnt solve it yet.
workers cat may be 1 and the height of the largest cat may be more than 1 (actually any number)...
so think about the input

Code: Select all

2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
0 0
etc.
if anyone still cudnt get the trick pm me...i will explain more.
output

Code: Select all

1 3
1 4
2 7
2 8
2 10
2 11
3 15
3 16
3 18

Re: WA in 107

Posted: Thu Jun 05, 2008 6:57 pm
by Jan
You can solve it using integer arithmetic only. However, there are many cases given in the board. Try them.

Re: Need help understand my comipler (Dev C++ 4.9.9.2)

Posted: Sat Aug 30, 2008 4:37 am
by subzero
sorry..pretty late

windows doesn't works fine with long long (even with long?)... I think it exists something like "int64"...

Re: 107 WA help plz.. :-(

Posted: Mon Dec 07, 2009 12:18 pm
by m.kavakebi
in case input is (x 1)
x must be powers of 2
so
this inputs are invalid
100 1
1000 1
10000 1

107 WA

Posted: Tue Aug 17, 2010 2:13 pm
by katagalan
I got WA with this code in 107 The Cat in the Hat problem. I use arithmetic solution for worker cat > 1 cases and deal separately when worker cat number is 1. My code generates right answers with below input data. So I can't figure out where gone wrong, does somebody know? Thanks!!

Code: Select all

#include <stdio.h>
#include <math.h>

long int h, nx;

long int findn(void);

int main(){
  long int n;
  
  while( scanf("%ld %ld", &h, &nx) != EOF){
    if( h==0 && nx==0 )
      break;
    else{
      if( h == 1 && nx != 1 )
        printf("1 %ld\n", nx);
      else if( nx == 1 ){
        n = 1;
        printf("%ld %ld\n", (long int)log2(h), ((h-nx)*(n+1))+nx);
      }
      else{
        n = findn();
        printf("%ld %ld\n", (nx-1)/(n-1), ((h-nx)*(n+1))+nx);
      }
    }
  }/*while input data*/

  exit(0);
}

long int findn(void){
  long int i;
  float x1, x2;
  float nsqr;
  
  nsqr = sqrt(nx);
  for(i=2; i<=nsqr; i++){
    x1 = log(nx)/log(i);
    x2 = log(h)/log(i+1);
    if( x1 == x2 )
      return i;
  }
  
  return nx;
}
Input:

Code: Select all

1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0
Output:

Code: Select all

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
29524 4017157
615441 1931252289
21 369
6 127
9 217