100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar »

You dont know for sure that min < max :wink:

Jenny
New poster
Posts: 1
Joined: Wed Jul 17, 2002 2:23 am
Location: Mexico
Contact:

Problem 100 Compile error

Post by Jenny »

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[28000];

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 [1000][3];
char line[20];
char numm[10];
char numn[10];

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]!=0)
{
if (line[0]!=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][0]=m;
result[t][1]=n;
result[t][2]=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][0],result[i][1], result[i][2]);
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.

Can anyone help please?[/c]
Jenny :)

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn »

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
Location: Bangladesh

Fix the input taking part

Post by imranul »

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

Post by Pokemonster »

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

Post by ec3_limz »

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

Post by NONAME_SUST »

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(){
.............................................
.............................................
Your code goes here..........
}
/* @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??

Post by Curt Schilling »

i don't know..
please reply..
[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]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by monika »

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?

Post by gigir »

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

Post by dawynn »

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

Post by gigir »

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 ??????

Post by pc5971 »

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[30001];
[/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[30001]; ???)
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:

Post by PMNOX »

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.

Post Reply

Return to “Volume 1 (100-199)”