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

[Codemonkey2000]

Code: Select all

#include<iostream>

int foo(long num)
{
   long c=num;
   long iter=1;
   while (c!=1)
   {
      if ((c%2)==0)
         c/=2;
      else
         c=c*3+1;
      iter++;
   }
   return iter;
}

int main()
{
   long i,j,tmp,max;
   while (std::cin>>i>>j)
   {
      std::cout<<i<<" "<<j<<" ";
      if (i>j)
      {
         tmp=i;
         i=j;
         j=tmp;
      }
      max=0;
      for (long x =i;x<=j;x++)
      {
         tmp=foo(x);
         if (tmp>max)
            max=tmp;
      }
      std::cout<<max<<std::endl;
   }
}


There is something definitely wrong with the pascal compiler. I translated the code from pascal into c++ and got AC.

[blackfire]

Plz Help with my java code

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
   Arbol tree;
   int cont;
   int de;
   public static void main(String args[])
   {
      Main myWork = new Main();
      myWork.Begin();
   }
   public int teur(long n)
   {
      int temp = tree.buscar(n);
      //System.out.println(n);
      if(n==1)
         return 1;
      else
      {
         if(temp==0)
         {   
            cont ++;
            temp = 1 + teur(((n%2)==0)?n/2:(3*n+1));
            tree.insertaNodo(n, temp);
         }
         de++;
      }
      return temp;
   }
   public void Begin()
   {
      String input;
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      tree = new Arbol();
      cont = 0;
      de = 0;
      int a, b, min, max, mayor, c;
      try{
         while((input = in.readLine())!=null)
         {
            a = Integer.parseInt(input.split(" ")[0]);
            b = Integer.parseInt(input.split(" ")[1]);
            if(a < b ){ min = a; max = b;}else{min = b; max = a;}
            mayor=-1;
            for(long n = min; n<=max; n++)
            {
               c = teur(n);
               if(c>mayor) mayor = c;
            }
            out.println(a + " " + b + " " + mayor);
            out.flush();
         }
      }catch(Exception ex){System.exit(0);}
   }
   class Arbol
   {
      Nodo raiz;
      public Arbol()
      {
         raiz = null;
      }
      public void insertaNodo(long d, int c)
      {
         if(raiz==null)
         {
            raiz = new Nodo(d, c);
         }else{
            Nodo aux = new Nodo(d, c);
            Nodo actual = raiz;
            if((d%2)==0)
            {
               if(actual.getRight()==null)
                  actual.setRight(aux);
               }else{
               if(actual.getLeft()==null)
                  actual.setLeft(aux);
               else
                  insertaHijo(actual.getLeft(),aux);
            }
         }
      }
      public void insertaHijo(Nodo rama,Nodo aux)
      {
         while(rama!=null)
         {
            if(rama.getData()<aux.getData())
            {
               if(rama.getLeft()!=null)
               {
                  rama = rama.getLeft();
               }else{
                  rama.setLeft(aux);
                  return;
               }
            }else{
               if(rama.getRight()!=null)
               {
                  rama = rama.getRight();
               }else{
                  rama.setRight(aux);
                  return;
               }
            }
         }
      }
      public int buscar(long d)
      {
         if(raiz==null)
            return 0;
         else
         {
            Nodo actual = raiz;
            if(raiz.getData()==d)
               return raiz.getCount();
            else
            {
               if((d%2)==0)
               {
                  return busquedaR(raiz.getRight(),d);
               }else{
                  return busquedaR(raiz.getLeft(),d);
               }
               
            }
         }
      }
      public int busquedaR(Nodo rama, long d)
      {
         
         while(rama!=null)
         {
            if(rama.getData()==d)
            {
               return rama.getCount();
            }else{
               if(rama.getData()<d)
               {
                  rama = rama.getLeft();
               }else{
                  rama = rama.getRight();
               }
            }
         }
         return 0;
      }
   }
   class Nodo
   {
      long dato;
      int count;
      Nodo izq;
      Nodo der;
      public Nodo(long d, int c)
      {
         dato = d;
         count = c;
         izq = null;
         der = null;
      }
      
      public long getData()
      {
         return dato;
      }
      public int getCount()
      {
         return count;
      }
      public Nodo getLeft()
      {
         return izq;
      }
      public Nodo getRight()
      {
         return der;
      }
      public void setLeft(Nodo n)
      {
         izq = n;
      }
      public void setRight(Nodo n)
      {
         der = n;
      }
   }
}


I get WA error for a month

[knascj]

Help!
I received a runtime error

#include<stdio.h>
#include<stdlib.h>

int main()
{
int i,j,a[100],b[100],c[100];
int aux,cont=0,n,p,cl,max_cl=0;//cl-cycle lenght
while (scanf("%d %d",&i,&j)!=EOF)
{
if(i>j)
{
aux=i;
i=j;
j=aux;
aux=1;
}

for(n=i;n<=j;n++)
{
cl=1;p=n;
while(p>1)
{
if(p%2==0)p=p/2;
else p=3*p+1;
cl++;
}

if(max_cl<cl)max_cl=cl;

}

if(aux==1)
{
aux=i;
i=j;
j=aux;
}

a[cont]=i;
b[cont]=j;
c[cont]=max_cl;
cont++;


}

for(n=0;n<cont;n++)
printf("%d %d %d\n",a[n],b[n],c[n]);

system("pause");
}

[dustfinger]

Submission number: #6245490
Language: c++
browser: firefox

I keep getting WA for my result. Actually, once I submit to the judge I end up back at the problem page, but when I goto my submissions then I see that the verdict was "Wrong Answer". Is that how it is suppose to work? My time is always 0.000. I programmed it so that it would accept any number of arguments as long as 1 == argc %2 since the first argument is the program name. So here is an example run on my own system.

Code: Select all

./a.out 10 1 100 200 201 210 900 1000
10 1 20
100 200 125
201 210 89
900 1000 174

What I find surprising is that my code finishes in 0 time. It seems to be outputting correct results, so if they had some case that I had not considered I would still think that my program would last longer than 0 time. This makes me wonder if something else is wrong. I can submit my code if anyone is interested in helping me. Is it proper etiquette to fill the thread with ones code?

Sincerely,

dustfinger

[mf]

You should take input from stdin.

i.e. it should work with

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out

[dustfinger]

mf,

You are correct! I made the appropriate change so that my code now reads from standard input and I got the Accepted verdict with a runtime of 0.720

Sincerely,

dustfinger

[dustfinger]

knascj,

I compiled your code and ran it with the following input:

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out
10 1 20
200 100 125
201 210 125
900 1000 174
sh: pause: command not found

I then I removed the System call

Code: Select all

system("pause");

and I ran the code again:

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out
10 1 20
200 100 125
201 210 125
900 1000 174

I compiled your code using gcc version 4.1.2 (Gentoo 4.1.2 p1.0.2)

dustfinger.

[hszeeks]

hi, i am newbie..
I've just in this forum and also just a few days joining online judges, and the only language i can is pascal..
anybody plis can help me solving the 100 problem using pascal?
i just don't understand c, c++, and i don't even understand the problem..
am i wrong defining the problem in this way:
look for the maximum cycle length between two integer from the input..
maximum cycle length: number printed as output from the algorithm given as the problem

i tried this code:

uses crt;

var a:integer;

begin
clrscr;
write('Input: ');readln(a);
if a=1 then exit;
write(a, ' ');
while a>1 do begin
if a mod 2 = 1 then begin a:=a*3+1;write(a, ' ');end;
if a mod 2 = 0 then begin a:=a div 2;write(a, ' ');end;
end;
readln;
end.

i just wrote the algorithm, input 22, and the output is the same as in the problem, now i just need to write codes to count it, and then apply it to the input (numbers between 2 integer) isn't it?
i am really confused and not knowing what to do know..
anybody can help me by subscribing the code maybe?

[mf]

There's a sample Pascal solution to this problem on the site - http://online-judge.uva.es/problemset/data/p100.p.html

[pmenace]

hmm... the sample Pascal solution tle's on me.
6300392 Time limit exceeded PASCAL 3.000

[hj1387]

i exam this code in vc++ dev c++ was ok but get runtime error
please help me

#include <iostream>
using namespace std;

void sort(long int&,long int&);
long int op(long int);
long int cycle(long int);

int main()
{
char ch;long int n,m;long int cyc,maxcyc;
long int num1[20];long int num2[20];long int mcyc[20]; int i,j=0;

cout << "please insert integer numbers between 0-1000000 \n";
cout << "(each two number in line for finish input, insert 0 )\n";

do
{ cin >> n ; if (n==0) break;
cin >> m ; if (m==0) break;
num1[j]=n ; num2[j]=m ; j++ ;
}while (n*m!=0);

for (i=0;i<j;i++)
{ n=num1[i] ; m=num2[i] ;
if (!( n>0 && m>0 && n<1000000 && m<1000000)) {mcyc[i]=-1;continue;}
sort(n,m);cyc=1;maxcyc=1;
for (long int k=n;k>=m;k--)
{ cyc=cycle(k);
if (cyc==0) { maxcyc=cyc;break;}
if (cyc>maxcyc) maxcyc=cyc;
}
mcyc[i]=maxcyc;
}

for (i=0;i<j;i++)
{ if (mcyc[i]==-1) cout <<num1[i]<<' '<<num2[i]<<' '<<"out of rang\n";
else if (mcyc[i]==0)
cout <<num1[i]<<' '<<num2[i]<<' '<<"Overflow\n" ;
else cout <<num1[i]<<' '<<num2[i]<<' '<<mcyc[i]<< endl;
}
cout << "continue ... (insert character) ";cin >> ch;
return 0;
}

void sort(long int& n,long int& m)
{
if (n<m)
{ long int temp;temp=n;n=m;m=temp;}
}

long int op(long int k)
{
if (k%2) k=3*k+1;
else k=k/2;
return k;
}

long int cycle(long int numb)
{ long int t=1;
while (numb!=1)
{ if (numb>715827882 && numb%2!=0) {t=0;break;}
++t;numb=op(numb);
}
return t;
}

[mf]

Firstly, don't output anything extra, like "please insert integer numbers ...". Your code is judged by a machine, and such phrases in the output are just meaningless garbage to it. And you only can get 'wrong answer' for outputting garbage.

Secondly, you shouldn't make assumptions on the number of tests. I'm sure it's much greater than 20, that's why you got runtime error. In general, structure of a C++ solution to this problem should be like:

Code: Select all

while (cin >> i >> j) {     // while there's one more test to be solved...
    solve it;
    cout << i << " " << j << " " << answer << endl;
}

[hj1387]

thanks mf
i get Accepted

[vencentd]

HELP!!!WHY i always get Running time error ,but it is OK in my computer--i even test the case : 1 50000 and
50000 1.
,here is my code:

Code: Select all

#include<stdio.h>
int analysis(char* string, int* infor);
int main(void){
   int store[100100];
    int i,k;
   int c=0;
   int count=0;
   int input[2];
   int array[100100];
   int max=0;
   char in[100];
   c=(int)gets((char*)in);
   memset(store,0,1500);
   while(c!=(int)NULL){
      printf("%s",in);
      c=0;
      analysis((char*)&in,(int*)&input);
      for(i=input[0];i<=input[1];i++){
         k=i;
         if(store[i]==0){
            while(k!=1){
               if(k%2==1){
                  k=k*3+1;
               }else if(k%2==0){
                  k=k/2;
               }
               count++;
            }
            count++;
            store[i]=count;
            array[c]=count;
         }else{
            array[c]=store[i];
         }
         count=0;
         c++;
      }
      for(i=0;i<(input[1]-input[0]);i++){
         if(max<array[i]){
            max=array[i];   
         }

      }
      printf(" %d\n",max);
      max=0;
      c=(int)gets(in);
   }
   return 0;
}
int analysis(char* string ,int * infor){
   int k=0;
   int i=0;
   int temp=0;
   for(;k<2;k++){
      while(string[i]!=' '&string[i]!='\0'){
         temp=temp*10+(int)string[i]-48;
         i++;
      }
      infor[k]=temp;
      i++;   
      temp=0;
   }
   if(infor[0]>infor[1]){
      i=infor[1];
      infor[1]=infor[0];
      infor[0]=i;
   }
}


[dreadlord]

printf ("Hello, world\n");

I've thought that a possible method to improve efficiency in this algorithm could be to store not only cycle values for numbers as they are being computed, but also the maximum of each one of the input intervals.

This could help to save time if further intervals may be decomposed in pieces and some of these pieces are already computed intervals, but this means that a proper data structure should be maintained to store and query already computed intervals, so if further intervals cannot be decomposed into already computed ones, or this info is of little help, it could be even more expensive in terms of time.

Any of you have already tried or considered this? Any clue about whether it could worth the effort?

Thanks!