If you get WA in problem 100, read me before post!

[Morning]

i've tried your code and i got the WA but not CE
Submitting problems using mail seems have some problem.I use the hotmail,my code which can get AC when i use the online juge system always get CE if i send my code to judge@uva.es .So,try to use the Valladolid ACM Online Judge(submit your problem online) in the
http://onlinejudge.uva.es/problemset/
hope this will help u

[Eobyn]

I don't understand why my code doesn't work.
I keep getting WA. Can you see anything wrong?

[c]
#include <stdio.h>
#include <string.h>

#define TABLE_SIZE 2500000

unsigned short s_length[TABLE_SIZE];

unsigned short cycleLength(unsigned long n) {
unsigned short length = (n > TABLE_SIZE) ? 0 : s_length[n];

if( length == 0 ) {
/* cycle length of n not computed yet */

if( n & (unsigned int)1 ) {
/* odd */
length = 1 + cycleLength(3 * n + 1);
}else {
/* even */
length = 1 + cycleLength(n / 2);
}

if( n < TABLE_SIZE ) {
s_length[n] = length;
}
}

return length;
}

int main() {
unsigned int i, j, k;
unsigned short max;
unsigned short length;

memset(s_length, 0, sizeof(s_length));
s_length[1] = 1;

while( scanf(" %u %u", &i, &j) == 2 ) {
max = 0;

if( i > j ) {
k = i;
i = j;
j = k;
}

for(k = i ; k <= j; k++) {
length = cycleLength(k);

if( length > max ) {
max = length;
}
}
printf("%d %d %d\n", i, j, max);
}

return 0;
}
[/c]

[zack]

I don't understand why my code doesn't work.
I keep getting WA. Can you see anything wrong?

[c]


if( i > j ) {
k = i;
i = j;
j = k;
}

for(k = i ; k <= j; k++) {
length = cycleLength(k);

if( length > max ) {
max = length;
}
}
printf("%d %d %d\n", i, j, max);
}

return 0;
}
[/c]

I think it's a problem with the result presentation. The problem says the I and J vars are presented in input order.

The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Example (your code):

input:

i = 20
j = 10

must swap
k = i = 20
i = j = 10
j = k = 20

result
i = 10; j = 20

now it computs and shows:
10 20 -function result max-

should be
20 10 - function result max -

[Eobyn]

Thanks. Already found out my error. And found out a bug to. Its posted on another topic though.


Jo

[mathmoi]

Hi,

It's now 3 hour i try to get the 100 problem to work I continualy get an WA, this is the first time i submit a program, so maybe I do something wrong. I already read about some common bug and correct them, but it still dont work.

Here is my code, thx
[cpp]

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#ifdef WIN32
typedef unsigned __int64 ui64;
#else
typedef unsigned long long ui64;
#endif

vector <string> Tokenize(string s, char cDelimiteur);
int CycleLenght(ui64 n);

void main()
{
int iCmp, i, j;
string s;
vector<string> tokens;

getline(cin, s);
tokens = Tokenize(s, ' ');

while (tokens.size() == 2)
{
int iPlusLong = -1;
i=atoi(tokens[0].c_str());
j=atoi(tokens[1].c_str());

if (i>j)
{
int tmp = i;
i = j;
j = tmp;
}

iPlusLong = CycleLenght((ui64)i);
for (iCmp = i+1; iCmp <= j; iCmp++)
{
int iTmp;
iTmp = CycleLenght((ui64)iCmp);
if (iTmp > iPlusLong)
{
iPlusLong = iTmp;
}
}

cout <<tokens[0] <<' ' <<tokens[1] <<' ' <<iPlusLong <<endl;

getline(cin, s);
tokens = Tokenize(s, ' ');
}
}

int CycleLenght(ui64 n)
{
int lenght = 1;
while (n != 1)
{
//cout <<n <<' ';
if (n % 2 != 0)
{
// n est impair soit odd
n = 3 * n + 1;
}
else
{
// n est pair soit even
n = n / 2;
}
lenght++;
}

return lenght;
}

vector <string> Tokenize(string s, char cDelimiteur)
{
string strTmp;
vector <string> tokens;

unsigned int i;
for(i = 0; i < s.length(); i++)
{
if (s[i] != cDelimiteur)
{
strTmp += s[i];
}
else
{
tokens.push_back(strTmp);
strTmp = "";
}
}

if (strTmp != "")
{
tokens.push_back(strTmp);
}

return tokens;
}[/cpp]

[snake79]

hello, here's my code. I got WA too

Code: Select all

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

using namespace std;

int main(void)
{
   float i,j,ii,jj,n,t,ripetizioni;
   unsigned long int max=0,conta,mem[1000001],x;
   char buf[81];
   for (x=1;x<=1000000;x++) mem[x]=0;
   mem[x]=1;
   for (x=2;x<1000;x++)
   {
   n=x;
   while (n!=1)
      {
      if (n/2 != floor(n/2))
         {
            n=n*3+1;
         }
      else
         {
            n=n/2;
         }
      mem[x]++;

      }
   }

   for (x=1000;x<10000;x++)
   {
   n=x;
   while (n>=1000)
      {
      if (n/2 != floor(n/2))
         {
            n=n*3+1;
         }
      else
         {
            n=n/2;
         }
      mem[x]++;

      }
   mem[x]+=mem[(int)n];
   }

   for (x=10000;x<100000;x++)
   {
   n=x;
   while (n>=10000)
      {
      if (n/2 != floor(n/2))
         {
            n=n*3+1;
         }
      else
         {
            n=n/2;
         }
      mem[x]++;

      }
   mem[x]+=mem[(int)n];
   }

   for (x=100000;x<=1000000;x++)
   {
   n=x;
   while (n>=100000)
      {
      if (n/2 != floor(n/2))
         {
            n=n*3+1;
         }
      else
         {
            n=n/2;
         }
      mem[x]++;

      }
   mem[x]+=mem[(int)n];
   }


   while (cin >> i >> j)
      {
      if(i < 0 || i > 1000000 || j < 0 || j > 1000000)
         exit(0);
      ii=i;jj=j;
      if (i>j)
        {
        float temp=i;
        i=j;
        j=temp;
        }
      max=0;
      for(t=i;t<=j;t++)   
         {
         n=t;
         conta=1;
         while (n>=1000000)
            {
            if (n/2 != floor(n/2))
               {
                  n=n*3+1;
               }
            else
               {
                  n=n/2;
               }
            conta++;
            }
         conta+=mem[(int)n];
         if (conta> max) max=conta;
         }
      printf("%.0f %.0f %ld\n",ii,jj,max);
      }
   return 0;
}


i know it is not well programmed but pre-calculating all the numbers is very fast (running time on acm server is about 3 seconds) I don't know where i recieve WA. Ovviously the sample input and the sample output are corresponding. Please help me. Bye

[snake79]

I got accepted only changing variables type from float to double... it's strange, I think there are no numbers to compute that are above 10^38....

but with old version i had:
(input) 1 999999
(output) 1 999999 502

with the new one:
(input) 1 999999
(output) 1 999999 525

could anyone clarify that?

thanks in advance.... bye!

[nobody10_ca]

I got AD on when using submit-o-matic
this is my first time using the online judege system, anything I can do to not get AD again?
also, 1000000 is too big for int and long (when calculating cycle length), anything I can do to calculate integers above 10^10?
btw, I use C++
[cpp]#include <iostream>
#include <fstream>


using namespace std;
int func(long n);
int main()
{

long a, b, highest;

while (cin>>a>>b)
{
cout<<a<<" "<<b<<" ";
if (a>=b)
{
long temp=b;
b=a;
a=temp;
}
highest=func(a);
for (long i=a+1; i<=b; i++)
{
if (func(i) > highest)
highest=func(i);
}
cout<<highest<<endl;
}
return 0;
}

int func(long n)
{
long total=1;

while (n!=1)
{
if (n%2==1)
n=3*n+1;
else
n=n/2;
total++;
}
return total;
}[/cpp]

[Virko]

I got WA ??? Could anyone tell me what's wrong ?

[pascal]Var N,K,J,E,C,Max : LongInt;
OK : Boolean;

Begin
While Not Eof Do
Begin
Max := 0;
Read(N,K);
If (N = 0) Or (K = 0) Then Exit;
If K > N Then
Begin
For E := N To K Do
Begin
J := E;
While (C < 1000000) And (OK = False) And (J > 0) Do
Begin
If Odd(J) = True Then J := J * 3 + 1 Else J := J Div 2;
Inc(C);
If (J = 1) Then OK := True;
End;
C := C + 1;
If C > Max Then Max := C;
C := 0;
OK := False;
End;
WriteLn(N,' ',K,' ',Max);
End;
End;
End.[/pascal]

[junbin]

I think after you read the 2 numbers, you're supposed to flip them around so that you loop from the smaller one to the bigger one.

[nightdog]

i keep getting Time Exceeded, can anyone enlighten me on how to make the algorithm faster?

[c]
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct data {
float i,j,result;
struct data *next;
};

int main() {
float swap,i, j,input,result, maxcycle;
struct data *start=NULL, *cur,*prev;
while((scanf("%f %f", &i, &j)) != EOF) {
float maxcycle = 0;
if(!((cur) = (struct data *) malloc(sizeof(struct data)))) {
perror("malloc");
exit(1);
}
if(!start) {
start= cur;
start->next = NULL;
prev = start;
}
cur->i=i; cur->j = j;
if(i > j) {
long swap = i;i = j; j= swap;
}
for(input=i;input<=j;input++) {
float count=1,n=input;
while(n != 1) {
count++;
if((n/2) != floorf(n/2))
n = (3*n)+1;
else
n /= 2;

}
if(count > maxcycle)
maxcycle =count;
}
cur->result=maxcycle;
prev->next= cur;
cur->next = NULL;
prev = cur;
}

for(cur=start; cur;cur=cur->next) {
printf("%.0f %.0f %.0f\n", cur->i, cur->j, cur->result);
}
exit(0);
}

[/c]

[Virko]

I think after you read the 2 numbers, you're supposed to flip them around so that you loop from the smaller one to the bigger one.

Did that, but still WA ?

Here is code:

[pascal]Var N,K,J,E,C,TN,TK,Max : LongInt;
OK : Boolean;

Begin
Max := 0;
Read(TN,TK);
If (TN = 0) Or (TK = 0) Then Exit;
If (TK < 1000000) And (TN < 1000000) Then
Begin
N := TN;
K := TK;
If TN > TK Then Begin N := TK; K := TN; End;
Write(N,' ',K,' ');
For E := N To K Do
Begin
J := E;
While (C < 1000000) And (J >= 1) And (OK = False) Do
Begin
Inc(C);
If J > 1 Then If Odd(J) = True Then J := J * 3 + 1 Else J := J Div 2;
If (J = 1) Then OK := True;
End;
If C > 1 Then C := C + 1;
If C > Max Then Max := C;
C := 0;
OK := False;
End;
WriteLn(Max);
End;
End.[/pascal]

[little joey]

Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for input

Code: Select all

1 10
10 1

the correct answer is

Code: Select all

1 10 20
10 1 20

[Virko]

Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for input

Code: Select all

1 10
10 1

the correct answer is

Code: Select all

1 10 20
10 1 20

I tryed that too, but I still get WA ?

[little joey]

Your code only reads two numbers and then stops (unlike the code you previously posted). Also you don't initialise the integer C the first time around the loop.
Just a couple of observations; there can be still more errors.