100 - The 3n + 1 problem

[regis]

Please, could you help me?
I have runtime error. I guess problem is in reading input with while, when I don't use it I get wrong answer
What's wrong with my while?

Code: Select all

#include <iostream>
using namespace std;


//stack
class stos{
	long licznik;
	long rozmiar;
	long* tablica;
	public:
		void push(long a);
		long top();
		long pop();
		long empty();

		~stos(void){};

		stos(void)
		{
			licznik=0;
			rozmiar=0;
		}

		stos(long a)
		{
			licznik=0;
			rozmiar=a;
			tablica=new long[rozmiar*sizeof(long)];
			for(long i=0; i<rozmiar; ++i)
			 tablica[i] = 0;
		}
};

long stos::empty(void)
{
	return licznik == 0;
}

void stos::push(long a)
{
	tablica[licznik++]=a;
}

long stos::top(void)
{
	if(empty())
	{
		return 0;
	}
	else
		return tablica[licznik-1];
}

long stos::pop(void)
{
	if(empty())
	{
		return 0;
	}
	else
		licznik--;
}


int main()
{
	int k=0;
	long zmienna;
	long wejscie;
	long max;
	int licznik;

	long tab[10001];

	for(k=2;k<10001;k++)
		tab[k]=0;
	tab[0]=1;
	tab[1]=1;

	int i,j,orygi,orygj;

	while(scanf("%d %d",&orygi,&orygj)==2)
	{
	//in case of input not in order
		if(orygi>orygj)
		{
			i=orygj;
			j=orygi;
		}
		else
		{
			i=orygi;
			j=orygj;
		}

		stos stosik(100*j);

		max=0;
		zmienna=0;
		wejscie=0;
		licznik=0;

		for(k=i;k<j+1;k++)
		{
			wejscie=k;
			licznik=0;
			zmienna=k;
			while (tab[zmienna]==0)
			{
				stosik.push(zmienna);
				if (wejscie%2 == 0) 
					wejscie = wejscie / 2;
				else if (wejscie%2 == 1) wejscie = 3*wejscie+1;
				if (wejscie <= j)
				{
					zmienna = wejscie;
				}
				licznik++;
			};
			tab[k]=tab[wejscie]+licznik;
			if(tab[k]>max) 
			{
				max=tab[k];
			}
			wejscie = tab[wejscie]+1;
			while (stosik.empty() == false)
			{
				tab[stosik.top()]=wejscie;
				wejscie++;
				stosik.pop();	
			}
		}
		printf("%d %d %d\n",orygi,orygj,max);
	}

	return 0;
}

[kis]

hi, here's my code (get WA), plz help me.

Code: Select all

#include <iostream>

#define nn 1000000

using namespace std;

int seqL[nn];

int howL(long long n) {
	if (n == 1)
		return 1;
	else
		if (n<nn) {
			if (seqL[n] == 0)
				seqL[n] = 1+howL(n & 1? n*3+1: n/2);
			return seqL[n];
		} else
			return 1+howL(n & 1? n*3+1: n/2);
}

int main(){
	memset(seqL,0,nn);
	int i,j,maxL = 0;
	for (i = 1; i<1000000; ++i)
		seqL[i] = howL(i);
	while (cin >> i >> j) {
		if (maxL != 0)
			cout << maxL << endl;
		cout << i << ' ' << j << ' ';
		maxL = 0;
		if (i>j) {
			seqL[0] = i;
			i = j;
			j = seqL[0];
		}
		for (; i<=j; ++i)
			if (seqL[i]>maxL)
				maxL = seqL[i];
	}
	if (maxL != 0)
		cout << maxL;
}

[regis]

I've got answer accepted Reading from input wasn't the problem, just had to remove stack and table and make it as simple as it gets. It's not so fast, but it's working. Right now I'm trying to optymize it.

[vizardo]

I don't know why but i got response as Runtime error.. here is my code...

Code: Select all

import java.util.Scanner;

class Problem161{
	
	public static long cycle_length(long num){
		long count = 1;
		
		while (num != 1){
			if (num%2 == 0){
				num = num / 2;
			}
			else{
				num = num * 3 + 1;
			}
			count++;
		}
		
		return count;
	}
	
	public static void main(String args[]){
		try{
			Scanner scanner = new Scanner(System.in);
			
			String str = scanner.nextLine();
			
			while (str != null && !str.equals("")){
				long i = Long.parseLong(str.split(" ")[0]);
				long j = Long.parseLong(str.split(" ")[1]);
				
				long a;
				long b;
				
				if (i < j){
					a = i;
					b = j;
				}
				else{
					a = j;
					b = i;
				}
				
				
				long max = 0;
				
				for (long k = a; k <= b; k++){
					long temp = cycle_length(k);
					if (max < temp){
						max = temp;
					}
				}
				
				System.out.println("" + i + " " + j + " " + max);
				
				str = scanner.nextLine();
			}
		}
		catch (Exception e){
			System.exit(0);
		}
	}
}

Thank you!

[Jan]

You have to download JDK. Search for 'JDK for windows' in google. (windows is just for example here, correct it for your os). Download and install it. It will help.

[vizardo]

I'm a newbie here.. I have tried 2 questions, the 3n+1 problem and Minesweeper problem. I'm not sure whether my code is wrong or it is java problem, but I always get Runtime Error from the judge. I've looked through the code so many times but I still can't find the reason. Help me pls...!

100 - 3n+1 problem

Code: Select all

import java.util.Scanner;

class Problem161{
	
	public static long cycle_length(long num){
		long count = 1;
		
		while (num != 1){
			if (num%2 == 0){
				num = num / 2;
			}
			else{
				num = num * 3 + 1;
			}
			count++;
		}
		
		return count;
	}
	
	public static void main(String args[]){
		try{
			Scanner scanner = new Scanner(System.in);
			
			String str = scanner.nextLine();
			
			while (str != null && !str.equals("")){
				long i = Long.parseLong(str.split(" ")[0]);
				long j = Long.parseLong(str.split(" ")[1]);
				
				long a;
				long b;
				
				if (i < j){
					a = i;
					b = j;
				}
				else{
					a = j;
					b = i;
				}
				
				
				long max = 0;
				
				for (long k = a; k <= b; k++){
					long temp = cycle_length(k);
					if (max < temp){
						max = temp;
					}
				}
				
				System.out.println("" + i + " " + j + " " + max);
				
				str = scanner.nextLine();
			}
		}
		catch (Exception e){
			System.exit(0);
		}
	}
}

10189 - Minesweeper

Code: Select all

import java.util.Scanner;

class Problem162{
	
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		
		int number = 1;
		
		while (n != 0 && m != 0){
			String line[] = new String[n];
			char ch[][] = new char[n][m];
			String result[][] = new String[n][m];
			
			scanner = new Scanner(System.in);
			
			for (int i = 0; i < n; i++){
				line[i] = scanner.nextLine();
			}
			
			for (int i = 0; i < n; i++){
				ch[i] = line[i].toCharArray();
			}
			
			for (int i = 0; i < n; i++){
				for (int j = 0; j < m; j++){
					if (ch[i][j] == '*'){
						result[i][j] = "*";
					}
					else{
						int count = 0;
						
						for (int a = i-1; a <= i+1; a++){
							if (a < 0 || a >= n){
								continue;
							}
							
							for (int b = j-1; b <= j+1; b++){
								if (b < 0 || b >= m){
									continue;
								}
								
								if (a == i && b == j){
									continue;
								}
								
								if (ch[a][b] == '*'){
									count++;
								}
								else{
									continue;
								}
								
								
							}
						}
						
						result[i][j] = String.valueOf(count);
					}
				}
			}
			
			//display
			System.out.println("Field #" + number + ":");
			for (int i = 0; i < n; i++){
				for (int j = 0; j < m; j++){
					System.out.print(result[i][j]);
				}
				System.out.println("");
			}
			System.out.println("");
			
			number++;
			
			n = scanner.nextInt();
			m = scanner.nextInt();
		}
	}
}

[mf]

The class which implements main() method in your program should be called 'Main', and it should be declared public.

[regis]

Hi, could you help me? I'm trying to memorize previous results and speed up my solution, but I always get Runtime Error. I know the problem is with getting out from the while loop and I don't know why. Please help me

Code: Select all

#include <iostream>

int main()
{
	long k=0;
	long wejscie;
	long max;
	long licznik;

	long tab[10001];

	for(k=2;k<10001;k++)
		tab[k]=0;
	tab[0]=1;
	tab[1]=1;

	long i,j,orygi,orygj;

	//petla czytajaca wejscie
	while(scanf("%d %d", &orygi, &orygj)==2)
	{
	//in case of input not in order
		if(orygi>orygj)
		{
			i=orygj;
			j=orygi;
		}
		else
		{
			i=orygi;
			j=orygj;
		}

		max=0;

		for(k=i;k<j+1;k++)
		{
			wejscie=k;
			licznik=1;

			while(wejscie!=1)
			{
				if (wejscie%2 == 0) 
					wejscie = wejscie / 2;
				else if (wejscie%2 == 1) 
					wejscie = 3*wejscie+1;

				licznik++;

				//sprawdzamy, czy istnieje juz wartosc w tablicy by przerwac petle
				if(wejscie<10001)
				{
					if(tab[wejscie]!=0)
					{
						//I'VE GOT PROBLEM WITH THIS LINES
						licznik = licznik + tab[wejscie] - 1;
						break;
					}
				}
			}
			//szukamy maxa
			if (licznik>max)
			max=licznik;
			//zapamietujemy wynik
			tab[k]=licznik;
		}
		printf("%d %d %d\n",orygi,orygj,max);
	}

	return 0;
}

[mf]

Code: Select all

				if(wejscie<10001)
				{
					if(tab[wejscie]!=0)
					{
						//I'VE GOT PROBLEM WITH THIS LINES
						licznik = licznik + tab[wejscie] - 1;
						break;
					}
				}

I think the problem is actually caused by the following line, because you don't check that k < 10001 there:

//zapamietujemy wynik
tab[k]=licznik;

[amrupam]

Hi, can any one understand what is the problem with my code

Code: Select all

#include <stdio.h>

unsigned long i,j,a,b;
unsigned  long length(unsigned long);


int main(int argc, char *argv[] ) {
  while ( !feof(stdin)){    
        scanf("%u %u",&i,&j);
        unsigned  long x,max=0,y;

        //swap variables
      if(i>j){a=j;b=i;}
        else {a=i;b=j;}
      
    //gets maximum length  
   for(unsigned  long k=a;k<=b;k++)
        {
            x=length(k);    
            if(max<x) {max=x;}   
        }
        printf("%u %u %u\n",i,j,max);   

    }
    return 0; 
}

unsigned long length(unsigned long n)
{
         
   unsigned long length=1;
   while (n!=1){
      length++;
      if ((n&1)!=0)
         n = 3*n+1;
      else
         n /= 2;
   } 
   return length;
}

this code shows the following output
1 1 1
1 10 20
837799 837799 525
1 1000000 525

[regis]

Thank you, but that's not the problem. When I'm applying values to tab[k] I'm still in for loop with values of k from i to j. I've checked, and program runs OK without these lines:

Code: Select all

licznik = licznik + tab[wejscie] - 1;
break;

So I assume that problem lies there but I don't know why. When I compile it and check with my Visual C++ 2008 Express Edition I don't get any runtime errors at all
I also checked line like this instead of problematic lines:

Code: Select all

long test_variable = licznik + tab[wejscie] - 1;

and still no error.

[mf]

Add this assert to your code:

Code: Select all

             //zapamietujemy wynik
             assert(0 <= k && k < sizeof(tab)/sizeof(tab[0]));
             tab[k]=licznik;

When I run your program on input '1 999999' (worst-case input), this assert is triggered and your program crashes.

What other proof do you need that there's an error in the line `tab[k]=licznik;'?

[regis]

You are right, but I don't agree completely with you, because the input in this problem is between 1 and 9999

[mf]

You are right, but I don't agree completely with you, because the input in this problem is between 1 and 9999

Why do you think so? No, the numbers in the input are between 1 and 999999.

[regis]

Ha! There's difference in problem description. If you look at website, they say input is between 1 and 999999 but if you check out pdf file the input is between 1 and 9999. I've downloaded pdf file and worked on it and that's why I get errors (I've assumed that max input is 9999 and in fact it is 999999). Where should I call this bug to? I've already written to them using "Contact us" panel, is it enough?
Anyway, thank you mf, without your help I wouldn't notice it. I've submitted corrected code, it's not perfect because I can only declare size of table equal 200000 but it is still something, I've managed to get 0.02 sec time Oh yeah!