100 - The 3n + 1 problem

[ithamar]

You dont know for sure that min < max

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

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

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.

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

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]

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

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

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]

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]

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]

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]

thank you for your response. it got accepted. Judge is very clever!

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

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.