Page 79 of 93
Re: 100
Posted: Sat Feb 20, 2010 3:44 am
by DzMx
Hi Can anyone review my code and check why is it sending a RTE? im removing trailing and leading spaces so... please help
Code: Select all
public class Main {
static long count;
static long max;
static long[] array;
public static void main(String args[]) throws java.io.IOException{
java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
array= new long[10000001];
String line;
while ((line=reader.readLine())!=null) {
if (line == null) {
// end of file
break;
} else if (line.length() == 0) {
break;
} else {
line=line.trim();
String[] entradas = line.split(" ");
long firstO = Long.valueOf(entradas[0]);
long secondO = Long.valueOf(entradas[entradas.length-1]);
long first=firstO;
long second=secondO;
if (first > second) {
long temp = second;
second = first;
first = temp;
}
for(long i=second;i>=first;i--){
count=calculaNumeros(first,i);
if(count>max){
max=count;
}
}
out.print(firstO+" ");
out.print(secondO+" ");
out.println(max);
max=0;
count=0;
}
}
out.flush();
}
public static long calculaNumeros(Long i, Long j) {
if(array[j.intValue()]>0){
return array[j.intValue()];
}else{
if(j==1){
return 1;
}
if(j%2==0){
long m=1+calculaNumeros(i,j/2);
array[j.intValue()]=m;
return m;
}else{
long m=1+calculaNumeros(i,(j*3)+1);
array[j.intValue()]=m;
return m;
}
}
}
}
100 RTE Help pls!
Posted: Sat Feb 20, 2010 4:02 am
by DzMx
Heres my code hoping any help, it throws me a RTE i have removed leading and trailing spaces but it still throws me the error, test inputs (the ones from the problemset ) are showing correct solution, so if you have another inputs they will be helpful too. thx
Code: Select all
public class Main {
static long count;
static long max;
static long[] array;
public static void main(String args[]) throws java.io.IOException{
java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
array= new long[10000001];
String line;
while ((line=reader.readLine())!=null) {
if (line == null) {
// end of file
break;
} else if (line.length() == 0) {
break;
} else {
line=line.trim();
String[] entradas = line.split(" ");
long firstO = Long.valueOf(entradas[0]);
long secondO = Long.valueOf(entradas[entradas.length-1]);
long first=firstO;
long second=secondO;
if (first > second) {
long temp = second;
second = first;
first = temp;
}
for(long i=second;i>=first;i--){
count=calculaNumeros(first,i);
if(count>max){
max=count;
}
}
out.print(firstO+" ");
out.print(secondO+" ");
out.println(max);
max=0;
count=0;
}
}
out.flush();
}
public static long calculaNumeros(Long i, Long j) {
if(array[j.intValue()]>0){
return array[j.intValue()];
}else{
if(j==1){
return 1;
}
if(j%2==0){
long m=1+calculaNumeros(i,j/2);
array[j.intValue()]=m;
return m;
}else{
long m=1+calculaNumeros(i,(j*3)+1);
array[j.intValue()]=m;
return m;
}
}
}
}
Thanks fpnc.
Posted: Sat May 15, 2010 1:42 pm
by mintae71
Re: 100
Posted: Sun May 16, 2010 10:44 am
by pmc123
I do not understand why I keep getting "Wrong Answer" with this code.
It produces the right output for all samples I've seen, including ones posted here. In anyone can help, I'd appreciate it.
sample in
10 20
20 10
1 1
1 2
1 3
1 4
2 2
2 3
2 1
3 1
1 1000000
1 10
100 200
201 210
900 1000
sample out
10 20 21
20 10 21
1 1 1
1 2 2
1 3 8
1 4 8
2 2 2
2 3 8
2 1 2
3 1 8
1 1000000 476
1 10 20
100 200 125
201 210 89
900 1000 174
Code: Select all
//snip java template stuff
class myStuff implements Runnable {
public void run() {
// Your program here
String input;
while ((input = Main.ReadLn(20)) != null) {
if (input.length() == 0) {
break;
}
String inputs[] = input.split(" ");
int start = Integer.parseInt(inputs[0]);
int end = Integer.parseInt(inputs[1]);
int realStart = Math.min(start, end);
int realEnd = Math.max(start, end);
int max = 0;
for (int i = realStart; i <= realEnd; i++) {
max = Math.max(getCycleLength(i), max);
}
System.out.println(start + " " + end + " " + max);
}
System.out.println("");
}
private int getCycleLength(int i) {
int count = 0;
while (i > 1) {
if ((i & 1) == 0) {
i = i / 2;
} else {
i = 3 * i +1;
}
count++;
}
count++;
return count;
}
// You can insert more classes here if you want.
}
how to communicate with the judge?
Posted: Thu May 20, 2010 5:17 pm
by ahaarrestad
Hi.
I'm trying to learn how to communicate with the judge.... I found the "3n+1" problem suitable for this task.
I keep getting "wrong answer" when using this code:
Code: Select all
public static void main(String[] args){
Scanner input = new Scanner(System.in);
String nextLine = null;
Scanner line = null;
while(input.hasNextLine() && (nextLine = input.nextLine()).length()>0){
line = new Scanner(nextLine);
long min=0;
long max=0;
min=line.nextLong();
max=line.nextLong();
int maxLength=0;
int temp=0;
long start = System.currentTimeMillis();
for(long i=min;i<=max;i++){
temp=count2(i);
maxLength=Math.max(temp, maxLength);
}
long end = System.currentTimeMillis();
System.out.println(min+" "+max+" "+maxLength);
System.err.println((end-start)+"ms");
}
}
Does any of you know if this should work and it's just my code in "count2" which is giving out the wrong answers? (it does of cause comply with the answers in the text and the timelimit)
regards
Asbjørn Aarrestad
Re: how to communicate with the judge?
Posted: Thu May 20, 2010 9:06 pm
by ahaarrestad
Got it.
By looking at the example (
http://acm.uva.es/problemset/data/p100.java.html), and the hints on how to start submitting solutions (
http://online-judge.uva.es/board/viewto ... f=1&t=3015) I got it.
* output exactly what they ask (don't swap input parameters)
Re: The 3n + 1 problem
Posted: Tue Jun 08, 2010 9:12 pm
by khiosa
I cannot figure out why my code is wrong. Can anyone please help? C++
Code: Select all
#include <iostream>
#include <algorithm>
inline int length(unsigned int n)
{
unsigned int length = 1;
while( n != 1)
{
length++;
if((n%2) == 1)
n = 3*n+1;
else
n = n/2;
}
return length;
}
int main()
{
unsigned int i = 0, j = 0;
while( std::cin >> i >> j)
{ if( (i > 0 && j > 0 && j < 10000 && i < 10000) )
{
unsigned int max = 0;
unsigned int a = std::min(i,j);
unsigned int b = std::max(i,j);
for(; a <= b; a++)
{
unsigned int l = length(a);
if(l > max)
max = l;
}
std::cout << i << " " << j << " " << max << '\n';
}
}
return 0;
}
Edit : FIXED, just remove the if statement checkign whether the values are in-bound
Re: The 3n + 1 problem
Posted: Tue Jul 20, 2010 8:48 am
by Cat4eg
How can I solve compilation error in this code (
http://www.programming-challenges.com):
Code: Select all
#include <map>
#include <iostream>
typedef std::map<int, int> MapIntInt_t;
void Display(int i, int j, const MapIntInt_t&);
int MapIt(MapIntInt_t&, int);
int main()
{
MapIntInt_t mapBuffer;
mapBuffer.insert(std::make_pair(1, 1));
int first, second, i, j;
while (std::cin >> i >> j)
{
if (i < j)
first = i, second = j;
else
first = j, second = i;
for (int k = first; k <= second; ++k)
MapIt(mapBuffer, k);
Display(i, j, mapBuffer);
}
return 0;
}
int MapIt(MapIntInt_t& mapBuffer, int n)
{
MapIntInt_t::iterator mapIterator = mapBuffer.find(n);
if (mapIterator != mapBuffer.end())
return mapIterator->second;
mapBuffer.insert(std::make_pair(n, 1));
mapIterator = mapBuffer.find(n);
int k;
if (n % 2 == 0)
k = n / 2;
else
k = n + n + n + 1;
mapIterator->second += MapIt(mapBuffer, k);
return mapIterator->second;
}
void Display(int i, int j, const MapIntInt_t& mapBuffer)
{
std::cout << i << " " << j << " ";
int maxPath = 0, first, second;
if (i < j)
first = i, second = j;
else
first = j, second = i;
MapIntInt_t::const_iterator k = mapBuffer.find(first);
do
{
int tmp = k->second;
if (tmp > maxPath)
maxPath = tmp;
++k;
} while (k->first != second);
std::cout << maxPath << std::endl;
// int k = 1;
// for (MapIntInt_t::const_iterator i = mapBuffer.begin(); i != mapBuffer.end(); ++i, ++k)
// std::cout << k << ". [" << i->first << "] = " << i->second << std::endl;
}
The 3n + 1 problem
Posted: Fri Aug 13, 2010 9:07 am
by platipino
http://uva.onlinejudge.org/index.php?op ... problem=36
here is what id did for the problem
Code: Select all
#include <iostream>
using namespace std;
int kChains (long long number ,int counter )
{
if (number == 1 )
return ++counter;
else if (number % 2 == 0)
return kChains (number / 2 , ++counter);
else
return kChains(number * 3 + 1 , ++counter);
}
int main ()
{
long long a,b ;
while ( cin >> a >> b )
{
int max = 0;
for ( int i = a ; i <= b ; i++ )
{
int j = kChains(i,0);
if (j > max )
max = j;
}
cout << a << " " << b << " " << max << endl;
}
return 0;
}
and ther result is wrong answer
why ?
thanks for upcomming replies
Re: The 3n + 1 problem
Posted: Fri Aug 13, 2010 6:32 pm
by helloneo
100 The 3n + 1 problem Time limit exceeded
Posted: Fri Sep 03, 2010 1:53 pm
by imifeng
Here is my code:
How to change it?
Code: Select all
#include <stdio.h>
void cycle(int a);
int cl;
int main(void)
{
unsigned int i, j, max;
int k, Up, Lower;
extern int cl;
while (scanf("%d %d", &i, &j))
{
max = 0;
Up = i > j ? i : j;
Lower = i < j ? i : j;
for ( k = Lower; k <= Up; k++ )
{
cl = 0;
cycle(k);
if ( cl > max )
max = cl;
}
printf("%d %d %d\n", i, j, max);
}
return 0;
}
void cycle(int n)
{
++cl;
while ( 1 != n )
{
if ( 0 == n%2 )
{
n = n/2;
++cl;
}
else
{
n = 3*n + 1;
++cl;
}
}
}
Memoization
Posted: Sat Sep 04, 2010 4:55 am
by feysal
Your code is calculating same values more than once.
Suppose you have input like this
In first test your code will calculate all cycle lengths for values from 100 to 200.
In second test it will recalculate again the cycle lengths for values from 150 to 200.
You can avoid this repeating calculations by using an array to store previously results.
It will speed up your program even if there is a single input test.
See
http://en.wikipedia.org/wiki/Memoization
P. S. I think you must not create another thread if there is one about your problem, use it
Re: 100 The 3n + 1 problem Time limit exceeded
Posted: Sat Sep 04, 2010 4:43 pm
by mf
No, that shouldn't be a problem. A straightforward code without memoization is intended to pass.
I think the error is here - "while (scanf("%d %d", &i, &j))". It must be "while (scanf("%d %d", &i, &j) == 2)".
Re: 100 The 3n + 1 problem Time limit exceeded
Posted: Sun Sep 05, 2010 8:38 am
by feysal
Yes, you're right, sorry
problem 100 runtime error!!!
Posted: Tue Sep 07, 2010 7:10 pm
by Turelim
Code: Select all
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws IOException{
Scanner in=new Scanner(new File("in.txt"));
PrintStream cout=System.out;
int maxCycle=0,cycles;
while(in.hasNextLine()){
String line=in.nextLine();
StringTokenizer tok=new StringTokenizer(line);
int a=Integer.parseInt(tok.nextToken());
int b=Integer.parseInt(tok.nextToken());
int min=Math.min(a,b);
int max=Math.max(a,b);
for(int i=min;i<=max;i++){
cycles=1;
int j=i;
while(j>1){
if(j%2==0) j=j/2;
else j=j*3+1;
cycles++;
}
maxCycle=(maxCycle<cycles)?cycles:maxCycle;
}
cout.printf("%d %d %d\n", a, b, maxCycle);
}
}
}
hi, always i send my code to the oj, i received a runtime error, can you help me with my code?, it's my first time using oj, i will appreciate your help
