100 - The 3n + 1 problem
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 100 - The 3n + 1 problem
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
Your code is only processing the first pair of integers. You need to continue to read until EOF.
Change:
cin >> i >> j;
to:
while(cin >> i >> j) {
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
Your code is only processing the first pair of integers. You need to continue to read until EOF.
Change:
cin >> i >> j;
to:
while(cin >> i >> j) {
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 11
- Joined: Mon Mar 09, 2015 10:30 am
Re: 100 - The 3n + 1 problem
how to reduce the run time ?? i get accepted 0.690s
Re: 100 - The 3n + 1 problem
i got time exceeded error, anyone know how can i reduce this time?
Code: Select all
#include <stdio.h>
void swap( long int* x, long int* y)
{
long int temp;
temp = *x;
*x = *y;
*y = temp;
}
int main(){
long int i,j, act_value, aux, count, max;
while (scanf("%d %d" , &i, &j) != EOF){
max=0;
printf("%d %d", i, j);
if (i>j) swap (&i, &j);
for (act_value=i;act_value<=j; act_value++){
aux= act_value;
count=1;
while(aux!=1){
if(aux%2 ==1) aux =(aux*3)+1;
else aux=aux/2;
count++;
}
if (count>= max) max =count;
}
printf(" %d \n",max);
}
return (0);}
-
- New poster
- Posts: 11
- Joined: Mon Mar 09, 2015 10:30 am
Re: 100 - The 3n + 1 problem
write another function who can calculate the max length , then just call from main . dont know why this way reduce time , its work for me.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 100 - The 3n + 1 problem
fiamma, use %ld for long int. Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!
Re: 100 - The 3n + 1 problem
I have posted this code and got wrong answer. What is the problem here? Thanks in advance.
The code is in ANSI C
The code is in ANSI C
Code: Select all
#include <stdio.h>
int f(int i);
int main()
{
int num1, num2, n, i, j, h;
while(scanf("%d %d", &num1, &num2) == 2){
n = 0;
for(i=num1; i<=num2; i++){
j = f(i);
if(n < j) {
n = j;
h = i;
}
}
printf("%d %d %d\n", num1, num2, n+1);
}
return 0;
}
int f(int n)
{
int i;
for(i=0; n!=1;i++){
if(n%2){
n = 3 * n + 1;
}
else if(!(n%2)){
n = n / 2;
}
}
return i;
}
-
- New poster
- Posts: 15
- Joined: Wed Jul 23, 2014 12:57 am
Re: 100 - The 3n + 1 problem
Your f function isn't working properly. If 1 is inputted the output should be 1 however in your case the output is 0.
Re: 100 - The 3n + 1 problem
i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.
Code: Select all
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
typedef unsigned long int_t;
map<int_t, int_t> record;
void calc(int_t);
int main()
{
int_t a = 0, b = 0, m = 0;
int_t l = 0, r = 0;
bool first = true;
while(scanf("%ld%ld", &l, &r) == 2)
{
if(l > r) a = r, b = l;
else a = l, b = r;
for(int_t i = a; i <= b; ++i)
calc(i);
m = 0;
for(int_t i = a; i <= b; ++i)
m = m > record[i] ? m : record[i];
if(first) printf("%ld %ld %ld", l, r, m + 1);
else printf("\n%ld %ld %ld", l, r, m + 1);
first = false;
}
return 0;
}
void calc(int_t t)
{
queue<int_t> a;
while(t != 1)
{
if(record[t] != 0) break;
a.push(t);
if(t % 2 == 0)
t /= 2;
else
t = 3 * t + 1;
}
int_t base = record[t];
while(!a.empty())
{
if(record[a.front()] != 0) break;
record[a.front()] = a.size() + base;
a.pop();
}
}
Re: 100 - The 3n + 1 problem
oh i got my solution accepted.TamceJoe wrote:i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.Code: Select all
#include <cstdio> #include <queue> #include <map> using namespace std; typedef unsigned long int_t; map<int_t, int_t> record; void calc(int_t); int main() { int_t a = 0, b = 0, m = 0; int_t l = 0, r = 0; bool first = true; while(scanf("%ld%ld", &l, &r) == 2) { if(l > r) a = r, b = l; else a = l, b = r; for(int_t i = a; i <= b; ++i) calc(i); m = 0; for(int_t i = a; i <= b; ++i) m = m > record[i] ? m : record[i]; if(first) printf("%ld %ld %ld", l, r, m + 1); else printf("\n%ld %ld %ld", l, r, m + 1); first = false; } return 0; } void calc(int_t t) { queue<int_t> a; while(t != 1) { if(record[t] != 0) break; a.push(t); if(t % 2 == 0) t /= 2; else t = 3 * t + 1; } int_t base = record[t]; while(!a.empty()) { if(record[a.front()] != 0) break; record[a.front()] = a.size() + base; a.pop(); } }
i thought there is no new line at the end of the output because the output on udebug does not show a new line
Re: 100 - The 3n + 1 problem
and use queue & map cost about 0.7s but do the calculate every time only cost 0.2s
xd
xd
Re: 100 - The 3n + 1 problem
I am trying to submit my own version of The 3n+1 problem but i get the same result: Runtime Error. I edited many times my code but i am still getting this error and I don't know the reason. I hope you can help me, what i can do to get an AC.
I write my last edited code in the following lines:
I will appreciate any comments or guidelines. Thanks!
I write my last edited code in the following lines:
Code: Select all
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args)
{
new Main().run();
}
long Fef(long x)
{
long cicles = 0;
long temp = x;
while (temp != 1)
{
if (temp % 2 == 0)
{
temp = temp /2;
cicles++;
}
else
{
temp = 3 * temp + 1;
temp = temp / 2;
cicles = cicles + 2;
}
}
cicles++;
return cicles;
}
long MaxF(long from, long to)
{
long maximum = -1;
for (long i = from; i <= to; i++)
{
long result = Fef(i);
if (result > maximum)
maximum = result;
}
return maximum;
}
private final long MAX = 1000000; // the maximum value accepted
public void run()
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer idata;
String line = null;
try {
line = br.readLine();
long from_value = 0;
long to_value = 0;
while ( line != null )
{
idata = new StringTokenizer(line);
while(idata.hasMoreTokens())
{
if( from_value <= 0 && idata.hasMoreTokens() )
from_value = Long.parseLong(idata.nextToken());
if( to_value <= 0 && idata.hasMoreTokens() )
to_value = Long.parseLong(idata.nextToken());
if( from_value > 0 && to_value > 0 )
{
long from, to;
if (from_value > to_value)
{
from = to_value;
to = from_value;
}
else
{
from = from_value;
to = to_value;
}
if( from > 0 && to < MAX)
System.out.printf("%d %d %d\n", from_value, to_value, MaxF(from, to));
from_value = -1;
to_value = -1;
}
}
line = br.readLine();
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
-
- New poster
- Posts: 1
- Joined: Fri May 06, 2016 5:34 pm
Re: 100 - The 3n + 1 problem
Hi there,
I am having trouble getting it to work in python. I keep getting a time limit exceeded. Any suggestions would be much appreciated. Here is my code:
import sys
from sys import stdin
def main():
for line in stdin:
curr_line=line.split()
if curr_line[0]<=curr_line[1]:
min_num=int(curr_line[0])
max_num=int(curr_line[1])
else:
max_num=int(curr_line[0])
min_num=int(curr_line[1])
maxCycleLength =0
for curr_num in range(min_num,max_num+1):
currCycleLength =1
while curr_num!=1:
currCycleLength +=1
if curr_num%2==0:
curr_num=curr_num/2
else:
curr_num=3*curr_num+1
maxCycleLength=max(currCycleLength,maxCycleLength)
print(curr_line[0],curr_line[1],maxCycleLength,sep=" ")
return
main()
sys.exit()
I am having trouble getting it to work in python. I keep getting a time limit exceeded. Any suggestions would be much appreciated. Here is my code:
import sys
from sys import stdin
def main():
for line in stdin:
curr_line=line.split()
if curr_line[0]<=curr_line[1]:
min_num=int(curr_line[0])
max_num=int(curr_line[1])
else:
max_num=int(curr_line[0])
min_num=int(curr_line[1])
maxCycleLength =0
for curr_num in range(min_num,max_num+1):
currCycleLength =1
while curr_num!=1:
currCycleLength +=1
if curr_num%2==0:
curr_num=curr_num/2
else:
curr_num=3*curr_num+1
maxCycleLength=max(currCycleLength,maxCycleLength)
print(curr_line[0],curr_line[1],maxCycleLength,sep=" ")
return
main()
sys.exit()
-
- Experienced poster
- Posts: 139
- Joined: Wed May 18, 2011 3:04 pm
Re: 100 - The 3n + 1 problem
Try input:
To avoid TLE, you should use memoization to store the results calculated, use it directly instead of calculating it again.
For example, n = 21, the sequences below produced:
so, when you got the steps of 21, you can calculate the steps of 64 by add 1 step.
Code: Select all
999999 1
For example, n = 21, the sequences below produced:
Code: Select all
21 64 32 16 8 4 2 1
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.
Re: 100 - The 3n + 1 problem
someone plz help why am i getting TLE:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
int main()
{
int i,j,min,max,maximum=0;
while(scanf("%d%d",&i,&j))
{ max=max(i,j);
min=min(i,j);
maximum=0;
while(min<=max)
{
int count=1;
int k=min;
while(k>1)
{
k=(k%2)?(3*k+ 1):(k>>1);
count++;
}
min++;
if(count>maximum) maximum=count;
}
printf("%d %d %d\n",i,j,maximum);
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
int main()
{
int i,j,min,max,maximum=0;
while(scanf("%d%d",&i,&j))
{ max=max(i,j);
min=min(i,j);
maximum=0;
while(min<=max)
{
int count=1;
int k=min;
while(k>1)
{
k=(k%2)?(3*k+ 1):(k>>1);
count++;
}
min++;
if(count>maximum) maximum=count;
}
printf("%d %d %d\n",i,j,maximum);
}
return 0;
}
Re: 100 - The 3n + 1 problem
Your straightforward solution is very slow. Read this thread for better solution. At least read post of metaphysis above yours.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman