100 - The 3n + 1 problem

[zack]

Got AC. Using integer. Wasn't checking i <= j just i < j.

[maverick]

can some one help me

errors:

usr/lib/crt1.o: In function `_start':
/usr/lib/crt1.o(.text+0x18): undefined reference to `main'
collect2: ld returned 1 exit status

code :
#include<stdio.h>
int funky(int ,int );
int main(void)
{
int i,j,max;
scanf("%d %d",&i,&j);
printf("\n%d %d %d\n",i,j,max=funky(i,j));
}

int funky(int i, int j)
{
/* @JUDGE_ID: 38086XE 100 C */
int n,CycleCount,max=0,k;
for(k=j;k>=i;k--)
{
n=k;
CycleCount = 1;
while( n!= 1)
{
CycleCount++;
if(0 == n%2)
n = n/2;
else
n = 3*n+1;
}
if(max<CycleCount) max = CycleCount;
}
return(max);
}
@end_of_source_code

[Morning]

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

[Eobyn]

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]

While trying to understand why my code didn't work (I kept getting WA) i discovered something intersting.

Here is the cyle for number 704511 :

704511
2113534
1056767
3170302
1585151
4755454
2377727
7133182
3566591
10699774
5349887
16049662
8024831
24074494
12037247
36111742
18055871
54167614
27083807
81251422
40625711
121877134
60938567
182815702
91407851
274223554
137111777
411335332
205667666
102833833
308501500
154250750
77125375
231376126
115688063
347064190
173532095
520596286
260298143
780894430
390447215
1171341646
585670823
1757012470
878506235
2635518706 : > 32 bit signed int. (int OR long)
1317759353
3953278060 : > 32 bit signed int. (int OR long)
1976639030
988319515
2964958546 : > 32 bit signed int. (int OR long)
1482479273
4447437820 : > 32 bit unsigned int. (unsigned int OR unsigned long)
2223718910 : > 32 bit signed int. (int OR long)
1111859455
3335578366 : > 32 bit signed int. (int OR long)
1667789183
5003367550 : > 32 bit unsigned int. (unsigned int OR unsigned long)
2501683775 : > 32 bit signed int. (int OR long)
7505051326 : > 32 bit unsigned int. (unsigned int OR unsigned long)
3752525663 : > 32 bit signed int. (int OR long)
11257576990 : > 32 bit unsigned int. (unsigned int OR unsigned long)
5628788495 : > 32 bit unsigned int. (unsigned int OR unsigned long)
16886365486 : > 32 bit unsigned int. (unsigned int OR unsigned long)
8443182743 : > 32 bit unsigned int. (unsigned int OR unsigned long)
25329548230 : > 32 bit unsigned int. (unsigned int OR unsigned long)
12664774115 : > 32 bit unsigned int. (unsigned int OR unsigned long)
37994322346 : > 32 bit unsigned int. (unsigned int OR unsigned long)
18997161173 : > 32 bit unsigned int. (unsigned int OR unsigned long)
56991483520 : > 32 bit unsigned int. (unsigned int OR unsigned long)
28495741760 : > 32 bit unsigned int. (unsigned int OR unsigned long)
14247870880 : > 32 bit unsigned int. (unsigned int OR unsigned long)
7123935440 : > 32 bit unsigned int. (unsigned int OR unsigned long)
3561967720 : > 32 bit signed int. (int OR long)
1780983860
890491930
445245965
1335737896
667868948
333934474
166967237
500901712
250450856
125225428
62612714
31306357
93919072
46959536
23479768
11739884
5869942
2934971
8804914
4402457
13207372
6603686
3301843
9905530
4952765
14858296
7429148
3714574
1857287
5571862
2785931
8357794
4178897
12536692
6268346
3134173
9402520
4701260
2350630
1175315
3525946
1762973
5288920
2644460
1322230
661115
1983346
991673
2975020
1487510
743755
2231266
1115633
3346900
1673450
836725
2510176
1255088
627544
313772
156886
78443
235330
117665
352996
176498
88249
264748
132374
66187
198562
99281
297844
148922
74461
223384
111692
55846
27923
83770
41885
125656
62828
31414
15707
47122
23561
70684
35342
17671
53014
26507
79522
39761
119284
59642
29821
89464
44732
22366
11183
33550
16775
50326
25163
75490
37745
113236
56618
28309
84928
42464
21232
10616
5308
2654
1327
3982
1991
5974
2987
8962
4481
13444
6722
3361
10084
5042
2521
7564
3782
1891
5674
2837
8512
4256
2128
1064
532
266
133
400
200
100
50
25
76
38
19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1
704511 704511 243


As you can see, while computing the cycle length the number excedes the MAX_UINT. This means that if your "cycle length" function uses 32 bit integers it wont reach a correct result. In fact if you use int's, at some point the variable will wrap around to a negative value.
Now whats really wrong about this is that online-judge accepts programs that wield wrong answers.

Under windows environment I use unsigned __int64 as a 64 bit integer variable type. Under linux I think its long long, not sure though.

[c]
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define TABLE_SIZE 2500000

#ifdef WIN32
typedef unsigned __int64 UINT64;
#else
typedef ? UINT64;
#endif

/* 704511 */

unsigned short s_length[TABLE_SIZE];

unsigned short cycleLength(UINT64 n) {
unsigned short length = (n <= 0 || n > TABLE_SIZE) ? 0 : s_length[n];

/* if( n > UINT_MAX ) {
printf("%15I64d : > 32 bit unsigned int. (unsigned int OR unsigned long)\n", n);
}else
if( n > INT_MAX ) {
printf("%15I64d : > 32 bit signed int. (int OR long)\n", n);
}else {
printf("%15I64d\n", n);
}
*/
if( length == 0 ) {
/* cycle length of n not computed yet */

if( n & (UINT64)1 ) {
/* odd */
length = 1 + cycleLength(3 * n + 1);
}else {
/* even */
length = 1 + cycleLength(n / 2);
}

if( n > 0 && n < TABLE_SIZE ) {
s_length[n] = length;
}
}

return length;
}

int main() {
unsigned int i, j, k, n1, n2;
unsigned short max;
unsigned short length;

memset(s_length, 0, sizeof(s_length));
s_length[1] = 1;

while( scanf(" %u %u", &n1, &n2) == 2 ) {
max = 0;

if( n1 < n2 ) {
i = n1;
j = n2;
}else {
i = n2;
j = n1;
}

for(k = i ; k <= j; k++) {
length = cycleLength(k);

if( length > max ) {
max = length;
}
}
printf("%d %d %d\n", n1, n2, max);
}

return 0;
}

[/c]

[shamim]

I think your answer for 1 1000000 is bit too long.

There is a popular sticky post concerning this problem. Please see it.

[zack]

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

Example (your code):

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 -

[Eobyn]

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


Jo

[mathmoi]

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 != cDelimiteur)
{
strTmp += s;
}
else
{
tokens.push_back(strTmp);
strTmp = "";
}
}

if (strTmp != "")
{
tokens.push_back(strTmp);
}

return tokens;
}[/cpp]

[Nguyen Viet Bang]

Hi

I'm new to Java and I'm really dissappointed with my unsuccess on problem 100 3n+1 . I believe there must be an bug in the input code :
Note the third last line

[java]static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}[/java]


if (car == '\n') is entered , means a "enter" to terminate the input stream (otherwise I don't know how to end my manual input ) ,'car' = 13 and (car < 0) will be false , then the if statement will not be executed . Then it will not return a 'null' , but a string Then a bug appears !

Pls other tell me how u can overcome this problem ? Thnx a lot !!!

further , it i want to test my prog with the test data from the text file , could any one show me how to do ?

Best regards ,

bang

[Niaz Morshed]

Try to take the thing positively… then u will get positive answer (accepted). Negative thinking can only bring u a negative reply ( i,e WA)

[sohel]

CUT

[snake79]

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]

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?

thanks in advance.... bye!

[Future]

I got a TLE...

The number may exceed 2^31, so I don't think we can make a array to save the length to reach "1" for each number.