## 100 - The 3n + 1 problem

Moderator: Board moderators

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
You dont know for sure that min < max Jenny
New poster
Posts: 1
Joined: Wed Jul 17, 2002 2:23 am
Location: Mexico
Contact:

### Problem 100 Compile error

Hi,

I have a problem compiling my program (100)

*@JUDGE_ID: 21223NA 100 C++ "Dynamic Programming with Recursion"*/

"@BEGIN_OF_SOURCE_CODE"

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

int num;

int llena(long n)
{ long b;

if (num[n]!=0)
return num[n];
else
{ if (n%2==0)
{ b=n/2;

num[n]=llena(b)+1;
}
else
{ b=3*n+1;
num[n]=llena(b)+1;
}
}

return num[n];
}

main()
{

int i, j, k, n;

int t, m;
int result ;
char line;
char numm;
char numn;

memset (line, 0, sizeof(line));
memset (numm, 0, sizeof(numm));
memset (numn, 0, sizeof(numn));
memset (result, 0, sizeof (result));

gets (line);

t=0;

while (line!=0)
{
if (line!=0)
{ k=0;
for (i=0; i< strlen(line); i++)
{ if (line==' ')
break;
numm=line;
}
for (i++;i<strlen (line); i++)
{ if (line=='\n')
break;
numn[k]=line;
k++;
}

m=atoi(numm);
n=atoi(numn);

j=0;
k=1;

for (i=0; i< n*4; i++)
{ if (i==pow(2,j))
{ num=k++;
j++;
}
else
num=0;

}

for (i=m; i<=n; i++)
{ if (num==0)
llena(i);

}

j=0;
for (i=m; i<=n; i++)
if (num>j)
j=num;

result[t]=m;
result[t]=n;
result[t]=j;
t++;

memset (line, 0, sizeof(line));
memset (numm, 0, sizeof(numm));
memset (numn, 0, sizeof(numn));

gets (line);

}

}

for (i=0; i<t; i++)

printf("\n %d %d %d", result[i],result[i], result[i]);
return 0;

}

"@END_OF_SOURCE

I receive the following compiling error messages:

Here are the compiler error messages:

00954922_24.c:131: unterminated string or character constant
00954922_24.c:131: possible real start of unterminated constant

--

But it compiles in my computer.

Another doubt I have is about the input and output. I have read the "how to submit" webpage, but I still have some doubts. First, do I have to get the input, process each case and send all the answers gathered? Or can I simply process one, send the result, process the second one, send its result, etc?
In this program I process everything, save the answers in an array and finally print all. I think I am wrong, but do not know. I get a compile error message, but it can compile in my computer.

Jenny dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
Sorry, I haven't looked closely at your program to help with the compile error. But I can help on this:

The judge doesn't care when you output your data -- as long as your output matches the solution. So you are perfectly free to process each test case and output the answer for each test case before proceeding to process the next case.

In fact, it's probably advisable to send the output for each testcase before proceeding, rather than storing the answers for one final submission. It is quite possible that the judge may provide more input cases than your array is expecting / can handle.

imranul
New poster
Posts: 12
Joined: Fri Jul 19, 2002 6:28 pm

### Fix the input taking part

There's nothing wrong in the logic..but the way of taking input is not right.

change the code of taking input :

replace the lines -> while(!feof(stdin))
and -> scanf("%d%d",&min,&max)

write it in the following way:

while(2==scanf("%d%d",&min,&max))

and your program will get accepted.
Life is like a box of Chocolates,
you never know what you're going to get...

Pokemonster
New poster
Posts: 10
Joined: Mon Jul 01, 2002 11:15 pm
Location: Germany
I guess the problem lies with your "@BEGIN_OF_SOURCE_CODE" and "@END_OF_SOURCE" statements. as far as I know, it's only @END_OF_SOURCE without the '"'.
I guess that's where the string/constant compiler errors come from...

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### why you got compile error

Hello.

If you have submitted the code by e-mail, the end of source tag should be @end_of_source_code, or in upper case, not @end_of_source. Otherwise, the OJ will compile anything added in the e-mail after the code.

Try again. Good luck!

NONAME_SUST
New poster
Posts: 8
Joined: Tue Jul 23, 2002 9:15 am

### WHY U MADE A SMALLER PROBLEM A SERIOUS ONE

Hello,
This is a tiny problem but u have coded hundreds of lines. I think u have a problem with the string processing. Moreobver try to add these lines always before and after ur source code..

/* @BEGIN_OF_SOURCE_CODE */
/* @AUTHOR_ID: 1212AW 100 C++ */
#include<stdio.h>
void main(){
.............................................
.............................................
}
/* @END_OF_SOURCE_CODE */

You can solve the problem recursively...don't bother with dynamic programmin...
HEY WANT TO GET SOL.TRY ON http://www.uvexam.zzn.com from 1st September

Curt Schilling
New poster
Posts: 1
Joined: Thu Jul 25, 2002 7:22 pm

### WA 100 why??

i don't know..
[c]/* @JUDGE_ID: 2XXXXFZ 100 C */
#include <stdio.h>
int verify(int k)
{
int temp;
temp=k%2;
if(temp==0)
return 0;
else
return 1;
}
main()
{
int n1, n2, count, hold, maxcount=0, max, min;
while(scanf("%d %d",&n1,&n2)==2)
{
if(n1<n2)
{
hold=n1;
min=n1;
max=n2;
}
else
{
hold=n2;
min=n2;
max=n1;
}
while(min<=hold&&hold<=max)
{
count=1;
n1=hold;
while(n1!=1)
{
if(verify(n1)==1)
n1=3*n1+1;
else
n1=n1/2;
count++;
}
if(count>maxcount)
maxcount=count;
hold++;
}
printf("%d\t%d\t%d\n",min,max,maxcount);
}
}
@END_OF_SOURCE_CODE [/c]

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
This problem has been discussed so often, why does everybody ask the same questions again (and always in a new thread)? Too lazy to look at older threads?
You have to print the values like they are in the input.

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am
Hi,

Please note that you have not initilaized maxcount in each cycle.
Hence your program would give incorrect results from second time onwards.

e.g. Run your program with inputs, say (1, 20)
you will get correct result i.e. 21
Now give inputs as (1,1)
and It'd still give 21 as answer!

-Monika

gigir
New poster
Posts: 2
Joined: Wed Aug 14, 2002 12:25 pm

### 100 3n+1 Problem What is wrong with this code?

I know there is a lot of questions about 100. I did all of the things that were offered in the earlier posts but i still can't make it through.

Here is my code:
[c]
#include<stdio.h>

int i,j,max,temp,temp2;

int hesapla(int input) {
int i=1;
if (input == 1) return 1;
do {
if (input % 2 == 1 ) input = 3*input+1;
else input=input/2;
++i;
} while(input!=1);
return i;
}

int main() {

while(scanf("%d %d",&i,&j)==2){
temp=i;temp2=j;

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

max=hesapla(i);

for ( ; i<=j; i++) {
if ( hesapla(i+1) > max ) max = hesapla(i+1);
}

printf("%d %d %d\n",temp,temp2,max);
}

return 0;

}[/c]

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
I think this is your issue:
for ( ; i<=j; i++) {
if ( hesapla(i+1) > max ) max = hesapla(i+1);
}

This goes through the loop for every number from i through j, but it calculates the cycle on the i+1 value. So when i = j, it will calculate the cycle for j+1! Change the loop control to only process while i < j and you should be OK.

David

gigir
New poster
Posts: 2
Joined: Wed Aug 14, 2002 12:25 pm
thank you for your response. it got accepted. Judge is very clever!

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

### Memory dimensions ??????

I solved the problem 100 (again 100 ?!?!) and it was accepted, but it didn't like my enough because it runed for 4.500 sec. and 384 Kb. So I decided to improve my solution... So I declared an array

[c]
int x;
[/c]

before [c]main[/c] to be an global parameter... In my function I have something like

[c]
if ((n<=30000) && (x[n]>0)) return x[n];
[/c]

and after

[c]
if (n<=30000) x[n]=v;
[/c]

I received an "Invalid memory..." message... I have some questions:

1. Can I declare (in C for Unix) global parameters ?
2. How much memory I can use (It work int; ???)
3. Can you explain how can I obtain an 0.000 sec ... Is it an trick ???

Carmen[/code]

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
i have also solved this proglem in 0.120s with 4000 kb memory, i don't know how to get 0.000s,
i used 1000000 table of short to get this score.