Page 74 of 93
Re: 100
Posted: Fri Mar 13, 2009 11:54 am
by 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;
}
Re: If you get WA in problem 100, read me before post!
Posted: Fri Mar 13, 2009 1:52 pm
by 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;
}
Re: 100
Posted: Sat Mar 14, 2009 12:52 pm
by 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.
Re: 100
Posted: Sun Mar 15, 2009 9:49 pm
by 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!
Re: 100 Runtime Error
Posted: Sun Mar 15, 2009 11:50 pm
by 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.
Is it java problem?? Help pls!
Posted: Mon Mar 16, 2009 5:06 am
by 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();
}
}
}
Re: Is it java problem?? Help pls!
Posted: Mon Mar 16, 2009 6:00 am
by mf
The class which implements main() method in your program should be called 'Main', and it should be declared public.
Re: 100
Posted: Mon Mar 16, 2009 2:59 pm
by 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;
}
Re: 100
Posted: Mon Mar 16, 2009 4:16 pm
by mf
regis wrote: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;
Re: If you get WA in problem 100, read me before post!
Posted: Mon Mar 16, 2009 7:30 pm
by 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
Re: 100
Posted: Tue Mar 17, 2009 11:23 am
by 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.
Re: 100
Posted: Tue Mar 17, 2009 9:22 pm
by 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;'?
Re: 100
Posted: Wed Mar 18, 2009 10:17 am
by regis
You are right, but I don't agree completely with you, because the input in this problem is between 1 and 9999
Re: 100
Posted: Wed Mar 18, 2009 11:23 am
by mf
regis wrote: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.
Re: 100
Posted: Wed Mar 18, 2009 2:20 pm
by 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!