Page 71 of 93
Re: The 3n + 1 problem
Posted: Sat Aug 30, 2008 4:29 pm
by wmqwj
HI, passworder
In your algorithm, you assumed that i < j , and that's not correct
input might look like this:
in this case .. your algorithm fails...
try to swap the input to match your algorithm, but remember when you write the answer
write the input in the same order you took it,
and you'll get AC
Input
Code: Select all
1 10
100 200
201 210
900 1000
1000 900
Code: Select all
1 10 20
100 200 125
201 210 89
900 1000 174
1000 900 174
Good Luck,
Re: The 3n + 1 problem
Posted: Sat Aug 30, 2008 7:15 pm
by rajib_sust
u r code fail when i > j also make wrong answer for long data
it make overflow for int that why give wrong output
Re: If you get WA in problem 100, read me before post!
Posted: Wed Oct 01, 2008 8:24 pm
by nFec
Hi there,
I am trying to submit this problem the whole day.
All of my local testing goes very well, no exceptions no problems.
The first times I tried to submit i got Runtime Errors, when I catched all exceptions I naturally got Wrong Answer cause at least one case didn't get handled.
So here's my code:
Code: Select all
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) {
long[] currentNumbers = new long[2];
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
try {
while(stdin.ready()) {
String[] stringNumbers = stdin.readLine().split(" ");
currentNumbers[0] = Long.parseLong(stringNumbers[0]);
currentNumbers[1] = Long.parseLong(stringNumbers[1]);
long longestcycle = calculateLongestCycle(currentNumbers);
System.out.println(currentNumbers[0] + " " + currentNumbers[1] + " " + longestcycle);
}
} catch (NumberFormatException e) {
System.exit(1);
} catch (IOException e) {
System.exit(1);
} catch (Exception ex) {
System.exit(1);
}
System.exit(0);
}
private static long calculateLongestCycle(long[] numbers) {
long longest = 1;
for(long n = Math.min(numbers[0], numbers[1]); n <= Math.max(numbers[0], numbers[1]); n++) {
long currentLength = calculateLength(n);
if(currentLength > longest) {
longest = currentLength;
}
}
return longest;
}
private static long calculateLength(long n) {
long counter = 1;
while(n != 1) {
if(n%2 == 0) {
n = n/2;
} else {
n = 3*n + 1;
}
counter++;
}
return counter;
}
}
Using this input file:
Code: Select all
1 1
1 2
2 1
2 2
3 2
2 3
3 3
4 3
3 4
4 4
5 4
4 5
5 5
6 5
5 6
6 6
1 10
1 100
1 1000
1 10000
1 100000
999999 1000000
My code returns:
Code: Select all
till$ java _3nplus1/Main < 10_.txt
1 1 1
1 2 2
2 1 2
2 2 2
3 2 8
2 3 8
3 3 8
4 3 8
3 4 8
4 4 3
5 4 6
4 5 6
5 5 6
6 5 9
5 6 9
6 6 9
1 10 20
1 100 119
1 1000 179
1 10000 262
1 100000 351
999999 1000000 259
Which seems perfectly ok to me.
And of course, the example in and output match perfectly.
I guess, I have a problem with how the input is specified. Dunno.
Please help
Re: 100_Help
Posted: Mon Oct 06, 2008 6:46 pm
by lnr
There is related volume for this.
Re: If you get WA in problem 100, read me before post!
Posted: Sat Oct 18, 2008 8:13 pm
by talz13
I finally got TO getting a WA, after multiple REs... I guess the judge doesn't like packages.
Anyway, here's my code that gets WA:
Code: Select all
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
/**
* @param args
*/
public static void main(String[] args)
{
Main myWork = new Main();
myWork.begin(args);
}
void begin(String[] args)
{
ArrayList<long[]> numbers = null;
if (args.length > 0)
{
numbers = new ArrayList<long[]>();
numbers.add(parseLongs(args[0]));
}
else
numbers = getInput();
long displayInt = 0;
for ( int i = 0; i < numbers.size(); i ++)
{
displayInt = countCycles(numbers.get(i));
System.out.println(numbers.get(i)[0] + " " + numbers.get(i)[1] + " " + displayInt);
}
}
private static ArrayList<long[]> getInput(String[] input)
{
String currentLine = null;
ArrayList<long[]> numberPairs = new ArrayList<long[]>();
// while ((currentLine = Main.ReadLn (255)) != null && currentLine.length() > 1)
// {
// numberPairs.add(parseLongs(currentLine));
// }
while ((currentLine = getLine("")) != null)
{
numberPairs.add(parseLongs(currentLine));
}
return numberPairs;
}
private static ArrayList<long[]> getInput()
{
String[] input = new String[0];
return getInput(input);
}
private static long[] parseLongs(String input)
{
StringTokenizer tokenizer = new StringTokenizer(input);
long num1 = Long.parseLong(tokenizer.nextToken());
long num2 = Long.parseLong(tokenizer.nextToken());
long returnArray[] = new long[2];
returnArray[0] = num1;
returnArray[1] = num2;
return returnArray;
}
private static int countCycles(long[] input)
{
int currentCycles = 0;
int maxCycles = 0;
long[] bounds = new long[2];
for (int i = 0; i < input.length; i++)
{
bounds[i] = input[i];
}
// Make sure bounds are sorted:
Arrays.sort(bounds);
// start with lower bound, loop until upper bound:
for (long i = bounds[0]; i <= bounds[1]; i++)
{
long result = i;
currentCycles = 1;
while (result != 1)
{
if ((result & 1) > 0)
{
result = 3 * result + 1;
}
else
{
result = result / 2;
}
currentCycles++;
}
if (currentCycles > maxCycles)
{
maxCycles = currentCycles;
}
}
return maxCycles;
}
private static String getLine (String prompt)
{
System.out.print (prompt);
String result = new String();
System.out.flush();
try
{
BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
result = in.readLine();
if (result == null || result.equals(""))
return null;
}
catch (IOException ex)
{
System.err.println("An IOException ocurred: ");
}
return result;
}
private 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'))
{
car = -1;
break;
}
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
private static long[] parseInts(String input)
{
long[] returnLong = new long[2];
ArrayList<String> tempArrayList = new ArrayList<String>();
String[] tempArray = null;
tempArray = input.split(" ");
if (tempArray.length > 0)
{
for (int i = 0; i < tempArray.length; i++)
{
if (tempArray[i].length() > 0)
tempArrayList.add((String) tempArray[i]);
}
}
tempArray = (String[]) tempArrayList.toArray(new String[tempArrayList.size()]);
if (tempArray.length != 2)
return null;
for ( int i = 0; i < 2; i++)
{
try
{
returnLong[i] = Long.parseLong(tempArray[i]);
}
catch (NumberFormatException e)
{
System.out.println("Error processing input! Not a valid long!");
}
}
return returnLong;
}
}
I have tried, on my build:
extraneous spaces, before and after and in between a set of numbers
boundary conditions (1 1000000 works)
out of order values (i.e. 50 10)
not outputting anything extra, as far as i can tell
Re: If you get WA in problem 100, read me before post!
Posted: Wed Oct 29, 2008 10:52 am
by preeteesh
Hi Below is my code, i am always getting WA for it, it works fine on my local end...
#include <iostream>
#include <string>
#include <set>
using namespace std;
void func(int start_num, int end_num)
{
set<int> numbers_used;
int count = 0;
int total_count = 0;
for(int i=end_num; i>=start_num; i--)
{
count = 0;
int num = i;
if(!numbers_used.empty())
if(numbers_used.find(num)!=numbers_used.end()) // means it was able to find
continue;
if( num == 1)
{
count++;
numbers_used.insert(num);
continue;
}
while ( num != 1)
{
if(num >= start_num && num <= end_num)
numbers_used.insert(num);
// num is even
if( num % 2 == 0 )
{
num = num/2;
count++;
}
// Num is odd
else
{
num = 3*num + 1;
count++;
}
}
if( num == 1)
{
count++;
}
if(count > total_count)
{
total_count = count;
}
}
std::cout << start_num << " " << end_num << " " << total_count;
std::cout << "\n";
}
int main(int argc, char* argv[])
{
char input[500], *tokout;
int num;
char choice;
std::string line;
while ( (choice = cin.get()) != EOF)
{
line = line + choice;
}
cout<<endl;
while ( line.find('\n') != -1 )
{
std::string newline = line;
size_t pos;
pos = line.find('\n');
newline = newline.substr(0,pos);
line = line.substr(pos+1);
tokout = strtok((char *)newline.c_str()," "); //gets the first number
int count = 0;
int start_num = 0;
int end_num = 0;
while ( tokout != NULL ) //while loop to get the rest of the numbers
{
if(count == 0)
start_num = atoi(tokout);
else
end_num = atoi(tokout);
//cout << tokout << endl; //prints the first number
tokout = strtok(NULL," ");
count++;
}
func(start_num, end_num);
}
return 0;
}
Can someone tell me what can be cause of it, please help. I am using Visual studio 2005 to compile..!
Re: 100
Posted: Sun Nov 09, 2008 9:23 am
by amitwadhwa
I am not able to find the problem in the following code. The test cases are running fine and the output is consistent with the simple algorithm solution.
Can somebody point me to the problem in the following code. I am getting a Wrong Answer (WA). TIA.
Code: Select all
import java.io.IOException;
import java.util.StringTokenizer;
class Main {
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
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));
}
public static void main(String[] args) {
Main myWork = new Main(); // create a dynamic instance
myWork.Begin();
}
void Begin(){
String s;
int a,b, min, maxx;
StringTokenizer idata;
while ( (s = Main.ReadLn(255)) != null ) {
idata = new StringTokenizer (s);
a = Integer.parseInt (idata.nextToken());
b = Integer.parseInt (idata.nextToken());
if(a>b) { min = b; maxx =a;} else {min=a; maxx=b;}
System.out.println(a+" "+b+" "+p1(min,maxx));
}
}
public int p1(int i, int j){
int arr[]= new int[j-i+1];
int cycleLength=0;
int max=0;
int n=0;
for(int I=i;I<j;I++){
arr[I-i]=0;
n=I;
cycleLength=1;
while(n>1){
cycleLength++;
if (n%2 != 0)
n=3*n+1;
else {
n>>=1;
if(n>i && n < I){
cycleLength+=arr[n-i]-1;
break;
}
}
}
arr[I-i]=cycleLength;
if(cycleLength>max)
max=cycleLength;
}
return max;
}
}
Re: 100
Posted: Mon Nov 10, 2008 12:25 pm
by amitwadhwa
Sorry my mistake... had to do I<=j :-/
Re: 100 Time Limit Exceeded
Posted: Mon Nov 10, 2008 1:27 pm
by amitwadhwa
I have noticed that the system seems to give very large times for java solutions!
For Problem 100
Java naive algorithm was not accepted and Java solution with modified algo using DP algo gave 1.190 sec.
With C++, Naive algo: 1.170, and the DP algorithm: 0.300 secs
I used the Java input function as shown in the sample Java example code in the forum (Btw.. even a copy paste of that solution gives me a RTE)
How come?
Posted: Sat Nov 15, 2008 6:15 pm
by Irhadce
i tried to solve problem 100 and did like you all said I removed the swapping part so i get runtime error plus my solution is in FAQ part(in how to write you source code in UVA) and still get runtime error am i missing something?
here is the code:
#include <stdio.h>
int cycle(m)
int m;
{
int i = 1;
while (m != 1){
if (m % 2 == 0){
m = m/2;
}
else{
m = 3*m+1;
}
i++;
}
return i;
}
main()
{
int m,n,max,temp;
int mOriginal,nOriginal;
int i;
while (scanf("%d %d",&m,&n)==2){
mOriginal = m;
nOriginal = n;
max = cycle(m);
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max)
max = temp;
}
printf("%d %d %d\n",mOriginal,nOriginal,max);
}
}
Re: How come?
Posted: Sun Nov 16, 2008 9:57 am
by mf
Please put the code in [code]...[/code] tags, and post in an existing thread about this problem next time.
You've missed 'return 0' at the end of main().
Non-zero return value from main() is interpreted by the judge as a runtime error.
Re: How come?
Posted: Tue Nov 18, 2008 4:24 am
by Irhadce
Code: Select all
#include <stdio.h>
int cycle(m)
int m;
{
int i = 1;
while (m != 1){
if (m % 2 == 0){
m = m/2;
}
else{
m = 3*m+1;
}
i++;
}
return i;
}
main()
{
int m,n,max,temp;
int mOriginal,nOriginal;
int i;
while (scanf("%d %d",&m,&n)==2){
mOriginal = m;
nOriginal = n;
max = cycle(m);
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max)
max = temp;
}
printf("%d %d %d\n",mOriginal,nOriginal,max);
}
}
Irhadce
New poster
Posts: 1
Joined: Sat Nov 15, 2008 5:11 pm
* Private message
Re: How come?
Posted: Tue Nov 18, 2008 6:34 am
by Obaida
Then you should use return 0; with int main(), like
And try to pass this Input, you code failed here.
Input:
Output
Re: 100
Posted: Thu Dec 25, 2008 11:17 pm
by Anunnaki
I keep getting TL, and I don't understand why. Can someone look at my code and tell me if they see something?
Code: Select all
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int nCalc (int i, int j)
{
int n, a = 0;
vector<int> x;
do
{
int di = i;
for (n = 0; di != 1; n++)
{
if (n == 0)
{
continue;
}
if ((di % 2) != 0)
{
di = (3 * di) + 1;
continue;
}
else
{
di = di/2;
}
}
if (i == 1)
n = 1;
x.push_back(n);
for (int counter = 0; counter < x.size(); counter++)
{
if (x[counter] > a)
a = x[counter];
}
i++;
}while(i <= j);
return a;
}
bool errorCheck(int i, int j)
{
int const min = 1, max = 1000000;
bool valid;
if ((i < min) || (i > max))
{
cout << "\nError: Invalid input. Starting integer must be between " << min << " and " << max << ". Try again.\n\n";
valid = false;
}
else if ((j < min) || (j > max))
{
cout << "\nError: Invalid input. Ending integer must be between " << min << " and " << max << ". Try again.\n\n";
valid = false;
}
else
valid = true;
return valid;
}
int main()
{
int i, j, n;
vector<int> cycle;
string input;
vector<string> instr;
string const sentinel = "end";
bool valid;
cout << "Input Integers (enter nothing when finished):\n\n";
instr.clear();
cycle.clear();
for (int counter = 0; ; counter++)
{
do
{
getline(cin, input);
if (input == "\0")
{
break;
}
stringstream(input) >> i >> j;
valid = errorCheck(i, j);
}while(!valid);
if (input == "\0")
{
break;
}
else
{
n = nCalc(i, j);
cycle.push_back(n);
}
instr.push_back(input);
}
cout << "\n\n";
for (int counter = 0; counter < instr.size(); counter++)
{
cout << instr[counter] << " " << cycle[counter] << "\n";
}
cout << "\n\nPress ANY key to continue...";
getchar();
return 0;
}
Re: 100
Posted: Fri Dec 26, 2008 1:53 am
by mf
Try giving your program an input with i=1, j=1000000 - it'll take many hours to complete, which is too much. Time limit is only 3 seconds.
And don't print any extra messages, because your program's output is checked automatically by a quite dumb robot. Only output what problem statement tells you - a line with three numbers in it, for each input case.
Also you don't have to do any error checking. Even if there's any error in the input (and there isn't), nobody will read any of those error messages. If you want to get a feedback from judge on these errors, use assert() macro.