100 - The 3n + 1 problem

[Absum]

I have a problem, my code looks like this:

Code: Select all

#include <stdio.h>

int getiterations(int i) {
    int c = 1;

    while (i > 1) {
        if (i % 2 != 0)
            i = (3 * i) + 1;
        else
            i = i / 2.0;
        c++;
        if (c == 2) {
            /* Do stuff */
        }
    }
    return c;
}


int main(int argc, char *argv[]) {
    while (!feof(stdin)) {
        int i, j, a, c = 0;
        scanf("%d %d", &i, &j);
        for (a = i; a < j; a++) {
            int iter = getiterations(a);
            c = (iter > c ? iter : c);
        }
        printf("%d %d %d\n", i, j, c);
    }

    return 0;
}

Which too me looks quite alright, and when i try to run it it looks alright too.
But the judge won't accept it. Is it the in and output handeling thats wrong?

[pmenace]

hmm... the sample Pascal solution tle's on me.
6300392 Time limit exceeded PASCAL 3.000

[emotional blind]

Consider the case where i > j.

[Absum]

Thanks, finally figured it out and that case was one of two logical errors in my code. The other was in the for loop.

[hj1387]

i exam this code in vc++ dev c++ was ok but get runtime error
please help me

#include <iostream>
using namespace std;

void sort(long int&,long int&);
long int op(long int);
long int cycle(long int);

int main()
{
char ch;long int n,m;long int cyc,maxcyc;
long int num1[20];long int num2[20];long int mcyc[20]; int i,j=0;

cout << "please insert integer numbers between 0-1000000 \n";
cout << "(each two number in line for finish input, insert 0 )\n";

do
{ cin >> n ; if (n==0) break;
cin >> m ; if (m==0) break;
num1[j]=n ; num2[j]=m ; j++ ;
}while (n*m!=0);

for (i=0;i<j;i++)
{ n=num1 ; m=num2 ;
if (!( n>0 && m>0 && n<1000000 && m<1000000)) {mcyc=-1;continue;}
sort(n,m);cyc=1;maxcyc=1;
for (long int k=n;k>=m;k--)
{ cyc=cycle(k);
if (cyc==0) { maxcyc=cyc;break;}
if (cyc>maxcyc) maxcyc=cyc;
}
mcyc=maxcyc;
}

for (i=0;i<j;i++)
{ if (mcyc==-1) cout <<num1<<' '<<num2<<' '<<"out of rang\n";
else if (mcyc==0)
cout <<num1<<' '<<num2<<' '<<"Overflow\n" ;
else cout <<num1[i]<<' '<<num2[i]<<' '<<mcyc[i]<< endl;
}
cout << "continue ... (insert character) ";cin >> ch;
return 0;
}

void sort(long int& n,long int& m)
{
if (n<m)
{ long int temp;temp=n;n=m;m=temp;}
}

long int op(long int k)
{
if (k%2) k=3*k+1;
else k=k/2;
return k;
}

long int cycle(long int numb)
{ long int t=1;
while (numb!=1)
{ if (numb>715827882 && numb%2!=0) {t=0;break;}
++t;numb=op(numb);
}
return t;
}

[mf]

Firstly, don't output anything extra, like "please insert integer numbers ...". Your code is judged by a machine, and such phrases in the output are just meaningless garbage to it. And you only can get 'wrong answer' for outputting garbage.

Secondly, you shouldn't make assumptions on the number of tests. I'm sure it's much greater than 20, that's why you got runtime error. In general, structure of a C++ solution to this problem should be like:

Code: Select all

while (cin >> i >> j) {     // while there's one more test to be solved...
    solve it;
    cout << i << " " << j << " " << answer << endl;
}

[hj1387]

thanks mf
i get Accepted

[the_barnacle]

I finally got it to accept my program but now it says it takes too long. I don't expect it to be fast as it's about as straight forward as one could make it, but I'm concerned my input is getting stuck in an infinite loop.

This is my input block, anyone know if this should work or not?

Code: Select all

Scanner getInput = new Scanner(System.in);
String input;
int start;
int stop;
while (getInput.hasNextLine() && (input = getInput.nextLine()).length() != 0)
{
	Scanner newLine = new Scanner(input);
	start = newLine.nextInt();
	stop = newLine.nextInt();
		      
	computeSet(start, stop);
}

[vencentd]

HELP!!!WHY i always get Running time error ,but it is OK in my computer--i even test the case : 1 50000 and
50000 1.
,here is my code:

Code: Select all

#include<stdio.h>
int analysis(char* string, int* infor);
int main(void){
	int store[100100];
	 int i,k;
	int c=0;
	int count=0;
	int input[2];
	int array[100100];
	int max=0;
	char in[100];
	c=(int)gets((char*)in);
	memset(store,0,1500);
	while(c!=(int)NULL){
		printf("%s",in);
		c=0;
		analysis((char*)&in,(int*)&input);
		for(i=input[0];i<=input[1];i++){
			k=i;
			if(store[i]==0){
				while(k!=1){
					if(k%2==1){
						k=k*3+1;
					}else if(k%2==0){
						k=k/2;
					}
					count++;
				}
				count++;
				store[i]=count;
				array[c]=count;
			}else{
				array[c]=store[i];
			}
			count=0;
			c++;
		}
		for(i=0;i<(input[1]-input[0]);i++){
			if(max<array[i]){
				max=array[i];	
			}

		}
		printf(" %d\n",max);
		max=0;
		c=(int)gets(in);
	}
	return 0;
}
int analysis(char* string ,int * infor){
	int k=0;
	int i=0;
	int temp=0;
	for(;k<2;k++){
		while(string[i]!=' '&string[i]!='\0'){
			temp=temp*10+(int)string[i]-48;
			i++;
		}
		infor[k]=temp;
		i++;	
		temp=0;
	}
	if(infor[0]>infor[1]){
		i=infor[1];
		infor[1]=infor[0];
		infor[0]=i;
	}
}

[vinu76jsr]

following is my code which returns a TLE I am new and its almost 6 hrs and 16 submissions straight to but couldn't get correct somebody please help

Code: Select all

import java.io.BufferedReader;
import java.util.*;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
        try{
        int x=0;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while (x==0) {
            String line = reader.readLine();
            if (line == null) {
                x=1;
            }
            if(x!=1){
            	

            StringTokenizer tokenizer = new StringTokenizer(line);
            int num1 = Integer.parseInt(tokenizer.nextToken());
            int num2 = Integer.parseInt(tokenizer.nextToken());
            if(num1>10000||num2>10000/||num1<0||num2<0)break;
            int temp,countmax=1,count,min,max; 
            if (num1 < num2) { min=num1; max=num2; } else { min=num2; max=num1; }
            for(int i=min;i<=max;i++)
            {
              count=1;
              temp=i;
              while(i!=1)
              {
                 if((i%2)==1)
                    i=i*3+1;
                 else
                    i=i/2;
                 count++;
              }
              if(countmax<count)
                 countmax=count;              
              i=temp;
          	}
          	System.out.println(num1+" "+num2+" "+countmax);  
          }            
        }    
    }
}
}

[Obaida]

Well I need to know a faster method about 100.
Last year when i get admitted in ACM then i solved 100 in time limit 0.900
it was ok since last few days. But i don't know why my program time limit now become 3.553!!!
After that i edited my program and resend it, then got Accepted in 1.270 my question is I saw in the problems ranking there are solutions taking only 0.000 second!!!
Now my question how it's possible and what is the method for it??????
Can some body explain it to me.

[x140l31]

Hi,
It works, The problem was that when I was printing the output if the inputs are 20 10, I print it as 10 20 in the wrong order. I don't know how does it matter.. but anyway it has accepted the solution.

-- Thanks

The integers i and j must appear in the output in the same order in which they appeared

¿?¿?¿?


why I've got PE?????

Code: Select all

code removed get AC

[Ron]

To x140l31,

Code: Select all

System.out.println(line + " " + c);

line contains a '\n' also...
so you have to print i and j before it, when you take values in integers.
then print c .

your remaining code is ok...!!!

[Obaida]

Can some one help me with better algo??? to get accepted quicker.

[x140l31]

To x140l31,

Code: Select all

System.out.println(line + " " + c);

line contains a '\n' also...
so you have to print i and j before it, when you take values in integers.
then print c .

your remaining code is ok...!!!

ok thanks!!!

but... why when i'm proving it in console, it doesn't print this '\n' ????