100 - The 3n + 1 problem

[jfvs]

exactly, just that, you just need something like

Code: Select all

Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
             //your code
}

[mehta_bhavesh]

I have this problem accepted in Java on Programming Challenges website but get runtime error on UVA online judge. Here's the code. Can someone help?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main implements Runnable{

public static void main(String args[]) // entry point from OS
{
Main myWork = new Main(); // Construct the bootloader
myWork.run(); // execute
}

public void run() {
new ThreeNPlusOne().run();
}

class ThreeNPlusOne implements Runnable {

public void run() {
// My program here
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
// read the two integers
int i = in.nextInt();
int j = in.nextInt();
int maxLen = 0;
// send smaller integer first to maxCycleLen function
if (i > j) {
maxLen = maxCycleLen(j, i);
} else {
maxLen = maxCycleLen(i, j);
}
// print the input and max cycle length
System.out.printf("%d %d %d\n", i, j, maxLen);
}
System.exit(0);
}

/** Convenience function for checking if integer is even
* @param i
* @return boolean True if number is even
*/
boolean isEven(int i) {
if (i % 2 == 0)
return true;
else
return false;
}

/**
* Compute the max cycle length for any integer between i and j including the numbers i and j.
* For a number n, generate cycle as follows
* If number n is even then divide by 2
* If number n is odd then 3*n + 1
* Cycle ends when n = 1
*
* @param i first integer
* @param j second integer
* @return max cycle length
*/
int maxCycleLen(int i, int j) {
// Expect i < j
if ( i > j ) {
throw new AssertionError("first integer should be less than second integer.");
}
int maxLen = 0; // max cycle length
// start from first integer and work towards second integer
// compute cycle lengths for all integers in between
for(int p = i; p <= j; p++) {
int len = 1; // cycle len, starts with one as we'll always have 1 number in the cycle
int n = p; // don't change the iteration variable
// cycle ends when n becomes 1
while (n != 1 ) {
len++; // add one more to the cycle length
if (isEven(n)) {
n = n / 2;
} else {
n = 3*n + 1;
}
}
if (len > maxLen) {
// see if max cycle length changed
maxLen = len;
}
}

return maxLen;
}
}
}

[aaditya]

I am getting Run time error with this piece of code in ANSI C. Please help

int main()
{
int a,b,result;
do
{
scanf("%d",&a);
scanf("%d",&b);
if(feof(stdin))
break;
else
if(a>b)
result = count_max_cycle(b,a);
else
result = count_max_cycle(a,b);
printf("%d %d %d",a,b,result);
}
while(!feof(stdin));
return 0;
}

[aaditya]

It seems i am taking integer as an input though it should be "long int" . I will try with long int. Hope it works.

[aaditya]

long int does not work.. but it was required anyways.

plese suggest the problem with the code.

[shubhamgoyal]

Hi,
I have been trying to submit my code for problem 100 - 3n + 1 and though the code works well when I run it on my pc, UVa shows me a runtime error.
My code is as follows:-


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

class Problem100
{

static int memo[] = new int[1000000];
static int ans = 0;
static int a;
static int b;

public static void main(String args[])throws IOException
{
Scanner str = new Scanner(System.in);
while(str.hasNext())
{
int a = str.nextInt();
int b = str.nextInt();
for(int i = 0; i < 1000000; i ++)
memo = -1;
memo[1] = 1;
int c = 0;
for(int i = a; i <= b; i ++)
{
if(compute(i) > c)
c = compute(i);
}
System.out.println(a + " " + b + " " + c);
}
System.exit(0);
}

public static int compute(int i)
{
if(memo != -1)
return memo;
else
{
ans = 0;
if((i % 2) == 1)
ans = 1 + compute(3 * i + 1);
else
ans = 1 + compute(i / 2);
memo = ans;
return ans;
}
}
}

Please tell me what is wrong
Thanks.

[shubhamgoyal]

I figured out that the class name needs to be "Main" for the program to work.
Also, I removed DP since the integer array memo of 1Million elements could have been a potential source of problem.
But still, UVa gives me "Wrong Answer".
Please help.

My new code -


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

class Main
{
//static int memo[] = new int[3000000];
//static int ans = 0;
static int a;
static int b;
static boolean swapped;

public static void main(String args[])throws IOException
{
swapped = false;
Scanner str = new Scanner(System.in);
while(str.hasNext())
{
int a = str.nextInt();
int b = str.nextInt();
//for(int i = 0; i < 3000000; i ++)
// memo = -1;
//memo[1] = 1;
int c = 0;
if(a > b)
{
c = a;
a = b;
b = c;
swapped = true;
}
c = 0;
for(int i = a; i <= b; i ++)
{
if(compute(i) > c)
c = compute(i);
}
if(swapped == true)
System.out.println(b + " " + a + " " + c);
else
System.out.println(a + " " + b + " " + c);
}
System.exit(0);
}

public static int compute(int i)
{
if(i == 1)
return 1;
//if(memo != -1)
// return memo;
//else
//{
// ans = 0;
if((i % 2) == 1)
return (1 + compute(3 * i + 1));
else
return (1 + compute(i / 2));
//memo = ans;
//return ans;
}
}

[acsa]

I've tried the sample input and I got the results as the sample output on the problem page.
I also checked that my program can handle both i >= j and i < j case, where i and j are the inputs.
But when I submit my code, the system gives me WAs. :'(
May someone help me for checking whether the output format is wrong.
Thx a lot!

Code: Select all

#include <iostream>
using namespace std;

unsigned int method(unsigned int);
unsigned int maximumCycle(unsigned int, unsigned int);

int main(){

    while(true){
        unsigned int x, y;
        
        cin >> x >> y;
        if(cin.eof())
            break;
        
        cout << x << ' ' << y << ' ' << maximumCycle(x, y) << endl;
    
    }
    return 0;
}

unsigned int method(unsigned int target){
    unsigned int n = target;
    unsigned int count = 1;
    do{
        if(n % 2 == 0)
            n /= 2;
        else
            n = 3 * n + 1;
        count ++;
    }while(n != 1);
    
    return count;
}

unsigned int maximumCycle(unsigned int x, unsigned int y){
    unsigned int start = x > y ? y : x;
    unsigned int end = x > y ? x : y;
    unsigned int length = end - start + 1;
    unsigned int *cycle = new unsigned int[length];
    
    for(unsigned int i = 0; i < length; i++){
        cycle[i] = method(start + i);
    }

    unsigned int maximum = cycle[0];
    for(unsigned int j = 1; j < length; j++){
        maximum = cycle[j] > maximum ? cycle[j] : maximum;
    }
    
    return maximum;

}

[Betlista]

I just want to share something, I used code like this to parse input:

Code: Select all

BufferedReader br = ...
String line = br.readLine();
String[] ij;
while ( line != null ) {
    ij = line.split( " " );
    solve( ... );
    line = br.readLine();
}

I was getting Runtime error...

I changed my code to

Code: Select all

BufferedReader br = ...
String line = br.readLine();
String[] ij;
while ( line != null ) {
    ij = line.split( "[ ]+" ); // <- pattern change
    solve( ... );
    line = br.readLine();
}

...didn't help...

Finally, that one worked:

Code: Select all

BufferedReader br = ...
String line = br.readLine();
String[] ij;
while ( line != null ) {
    ij = line.trim().split( "[ ]+" ); // <- trim added
    solve( ... );
    line = br.readLine();
}

Correct output for:

Code: Select all

    210     201   

is

Code: Select all

210 201 8

Motivation for Reader usage instead of Scanner was, that for huge inputs Scanner usage ends in TLE while Reader does not and we do not know what to expect (now I know that you can use Scanner without TLE).

[Black Hat]

Would you tell me please whats wrong in this code? I got WA.

#include<stdio.h>

int main()
{
int i,j,n,I,J,cycle,x,y;
while((scanf("%d %d",&i,&j))!=EOF)
{
x=i;
y=j;
if(i>j)
{
y=i;x=j;
}
cycle=0;
for(I=x;I<=y;I++)
{
n=I;
for(J=1;n!=1;J++)
{
if(n%2==0) n/=2;
else n=(3*n)+1;
}
if(cycle<J) cycle=J;
}
printf("%d %d %d\n",i,j,cycle);
}
return 0;
}

[thefourtheye]

Code: Select all

/*
TASK:   3n+1
LANG:   C++
AUTHOR: thefourtheye
*/
#include <vector>
#include <fstream>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
//#define DEV "DEVMODE"
#ifndef DEV
#define fin  std::cin
#define fout std::cout
#else
ifstream fin  ("");
ofstream fout ("");
#endif
#define SIZE 1000001
int Table[SIZE];

int Solve (unsigned long n)
{
	if (n < SIZE && Table[n]) return Table[n];
	if ((n&1) == 0) return 1 + Solve(n>>1);
	else return 2 + Solve((3*n+1)>>1);
}

int main ()
{
	int Start = 0, End = 0, Max = 0, Count = -1;
	Table[1] = 1;
	while (fin >> Start >> End)
	{
		Max = 0;
		int ix = Start;
		int iy = End;
		if (Start > End)
		{
			ix = End;
			iy = Start;
		}
		for (int i = ix; i <= iy; i++)
		{
			Count = Solve(i);
			Table[i] = Count;
			if (Count > Max) Max = Count;
		}
		fout << Start << " " << End << " " << Max;
	}
	return 0;
}

Judge always says WA... Whats wrong with this code? And Can I see the test case for which my program failed?

[thefourtheye]

Hi Black Hat,

1) Has your program run fine with the sample inputs and outputs provided?

2) And if that works fine, please try and execute your program with the following input "1 1000000". (I mean to say, you need to optimize the program)

Would you tell me please whats wrong in this code? I got WA.

#include<stdio.h>

int main()
{
int i,j,n,I,J,cycle,x,y;
while((scanf("%d %d",&i,&j))!=EOF)
{
x=i;
y=j;
if(i>j)
{
y=i;x=j;
}
cycle=0;
for(I=x;I<=y;I++)
{
n=I;
for(J=1;n!=1;J++)
{
if(n%2==0) n/=2;
else n=(3*n)+1;
}
if(cycle<J) cycle=J;
}
printf("%d %d %d\n",i,j,cycle);
}
return 0;
}

[thefourtheye]

Found the problem in my code. Everything was correct except that end of line marker (endl). I just included and submitted. It worked like a charm.

Silly mistake but took two days for me to spot...

[zobayer]

you can get help from

here you will find more other problem.

you should never post spoiler links in the forum. let others think.. please remove the link.

[zobayer]

StringTokenizer will work better than split. Have you tried that?