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

Moderator: Board moderators

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
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
Morning
Experienced poster

Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

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]
Eobyn
New poster

Posts: 4
Joined: Wed Oct 15, 2003 11:42 pm

Eobyn wrote: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).

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 -
zack
New poster

Posts: 9
Joined: Sun Oct 12, 2003 2:08 am

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

Jo
Eobyn
New poster

Posts: 4
Joined: Wed Oct 15, 2003 11:42 pm

### Can manage to get it right

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

}[/cpp]
mathmoi
New poster

Posts: 1
Joined: Mon Oct 27, 2003 12:25 pm

### trouble with problem #100

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
New poster

Posts: 3
Joined: Thu Nov 20, 2003 2:53 am

### i solved it

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?

snake79
New poster

Posts: 3
Joined: Thu Nov 20, 2003 2:53 am

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++;
}
}[/cpp]
nobody10_ca
New poster

Posts: 9
Joined: Tue Jan 06, 2004 7:33 am

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;
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]
Virko
New poster

Posts: 4
Joined: Fri Jan 16, 2004 6:02 pm

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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### help needed

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]
nightdog
New poster

Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

junbin wrote: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;
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]
Virko
New poster

Posts: 4
Joined: Fri Jan 16, 2004 6:02 pm

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 1010 1`
Code: Select all
`1 10 2010 1 20`

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

little joey wrote: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 1010 1`
Code: Select all
`1 10 2010 1 20`

I tryed that too, but I still get WA ?
Virko
New poster

Posts: 4
Joined: Fri Jan 16, 2004 6:02 pm

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

PreviousNext