10200 - Prime Time

[Sedefcho]

Hi, Minilek !

I cover all your test cases.

And my algorithm is fast enough ( I have no problem with that ).

I continue getting WA.

I see you round the numbers ( the percentages )
as follows:
33.675 -> 33.68
33.674 -> 33.67
33.676 -> 33.68

Is this what the Online Judge expects ? I mean are you sure in
your test cases ?

[Sedefcho]

Input:

0 10000
40 40
1 10000
1 9999
0 9999
551 1807
3957 8978
2784 8208
8138 9707
3965 8178
843 8651
6055 9655
6399 8052
7362 8656
742 1185
2145 6359
3607 8999
6423 9662
5536 8242
1294 4157
32 99
932 4566
6155 7063
2196 5454
894 7486
8169 9119
9498 9894
2091 3582
7027 8695
164 9213
3814 8954
1810 3579
1650 5141
2250 8761
4747 7461
1490 6101
957 6483
3141 8145
2401 8385
5665 8128
187 2029
6026 7065
711 2433
5470 8488
7636 9741
1296 5452
5506 9657
3219 5235
2838 9813
4202 8091
3564 9268
500 9304
5166 7917
2950 3090
1686 5950
628 6788
2655 2684
3140 6826
249 5728
4621 6984
3983 8015
531 7121
4968 9176
7793 9508
8794 8798
2107 3331
1157 3939
2117 5647
6225 7135
6335 6781
4513 5934
5284 5362
1598 9093
7689 8254
6837 9504
992 9795
1291 6271
137 531
648 2779
5727 8757
1078 8805
1669 5237
1376 4944
383 4534
5833 6562
3279 7137
7064 7268
5058 6954
1540 5658
1411 8357
2604 6124
8124 8216
1388 8784
4672 8726
3468 8990
1040 1899
3925 8580
1135 2813
174 8908
1795 9827
2482 7880
5020 5164
1017 2412
1327 8812
1560 1971




Output:

41.49
0.00
41.48
41.48
41.49
46.14
38.51
39.15
37.01
38.51
40.39
37.57
37.24
37.92
47.75
40.47
38.59
37.04
37.94
42.18
79.41
42.67
39.93
40.72
40.62
37.75
38.29
41.89
37.57
41.26
38.61
42.54
41.44
39.37
38.05
40.76
41.23
39.22
39.31
38.07
48.35
39.81
44.86
38.13
37.42
41.45
37.55
40.75
38.72
38.33
38.60
40.53
37.79
34.04
40.73
41.50
46.67
39.98
42.92
38.45
38.76
41.56
38.01
36.95
20.00
40.57
42.29
40.36
38.42
37.81
38.12
35.44
39.55
38.87
36.88
39.77
41.08
58.73
44.65
38.27
40.11
41.33
41.64
43.95
39.59
39.67
31.22
38.43
40.76
39.86
39.93
40.86
39.84
38.22
38.75
44.30
38.83
43.60
41.41
39.21
39.29
44.83
43.91
39.79
42.72


Can someone having problem 10200 ACCEPTED
verify these INPUTs / OUTPUTs ?

I've found them in another thread dedicated to Problem 10200.

My program gives the same result.
But still I get WA.

What could be wrong ?

[..]

My AC program gives same output.

[Sedefcho]

Well, what could be wrong then ?!

Could it be related to some stupid
boundary case ?

Or to the fact that my program is written in Java?!

[Sedefcho]

Hi,

I had the following strange problem. I was trying to solve the
10200 problem and the algorithm was OK. In fact the
problem is not so hard.

I tried everything but I did not manage to get my JAVA program
Accepted by the Online Judge. It was giving WA all the time
( 20-30 submisssions ).

Finally I got frustrated and I decided to rewrite my program in C++
just in order to check if IT IS SOME stupid I/O TEST CASE
( or I/O JAVA problem ).

I took the JAVA code and almost literally copy-pasted it in
a simple C++ editor. I compiled it and submitted it.

The C++ program got "Accepted" in its first submission.

Is that not strange? What could be the reason ?

[Sedefcho]

Even if I specify C for language and not C++ the program
gets accepted.

[Sedefcho]

import java.util.StringTokenizer;

class Main {

private static final int MAX_INT = 10000;

private static int[] primality = new int[MAX_INT + 1];

private static void init(){
int i = 0;
int result = 0;
double j = 0.0;
int k;
for(i=0;i<=39;i++){
primality = 1;
}
for(i=40;i<=MAX_INT;i++){
result=i*i+i+41; // We have for sure that: (result % 2) == 1
j = Math.sqrt(result);
primality = 1;
for(k=3; k<=j; k+=2){
if(result % k == 0) {
primality = 0;
break;
}
}
}
}

public static void main(String[] args){
init();

String line = null;
StringTokenizer st = null;
int A;
int B;
int cntPrimesAB = 0;
String firstDigits = null;
String lastDigits = null;
double percent = 0.0;
int p = 0;
while ( (line = readLn(1000)) != null){
line = line.trim();
st = new StringTokenizer(line, "\t \r");
A = Integer.parseInt(st.nextToken().trim());
B = Integer.parseInt(st.nextToken().trim());
int A1 = A <= B ? A : B;
int B1 = A <= B ? B : A;
A = A1;
B = B1;

cntPrimesAB = 0;

for (int i=A; i<=B; i++){
cntPrimesAB += primality;
}

percent = ( ( 1.0 * cntPrimesAB ) / ( 1.0*( B - (A-1)) ) );
p = (int) ( percent * 100000 );
// double p0 = percent * 100;

// p = 36005;

if ( p % 10 >= 5){
p = ( p / 10 ) + 1;
}else{
p = p / 10;
}

firstDigits = "" + ( p / 100 );
lastDigits = ( (p % 100) < 10 ) ? "0" + (p % 100) : "" + (p % 100);
// System.out.println( percent );
// System.out.println( p0 );
System.out.println( ((firstDigits + ".") + lastDigits) );
}
System.out.println();
}


public static String readLn (int maxLg){
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 (java.io.IOException e){
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

}

[Sedefcho]

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

#define MAX_INT 10000

int primality[MAX_INT + 1];

int init(){

int i = 0;
int result = 0;
int k;

for(i=0;i<=39;i++){
primality = 1;
}

for(i=40;i<=MAX_INT;i++){

/* We know for sure that: (result % 2) == 1 */

result=i*i+i+41;
primality = 1;

for(k=3; (k*k)<=result; k+=2){
if(result % k == 0) {
primality = 0;
break;
}
}

}

return 0;
}


int main(char* argv[], int argc){

int A = 0;
int B = 0;
int cntPrimesAB = 0;
double percent = 0.0;
int p;
int firstDigits, lastDigits;
int i = 0;

init();


while ( ( scanf("%d %d", &A, &B) ) != EOF ){

/* printf("%d %d \n", A, B); */

cntPrimesAB = 0;
for (i=A; i<=B; i++){
cntPrimesAB += primality;
}

percent = ( ( 1.0 * cntPrimesAB ) / ( 1.0*( B - (A-1)) ) );
p = (int) ( percent * 100000 );

if ( p % 10 >= 5){
p = ( p / 10 ) + 1;
}else{
p = p / 10;
}

firstDigits = ( p / 100 );
lastDigits = ( p % 100 );

if (lastDigits <= 9){
printf("%d.0%d\n", firstDigits, lastDigits);
}else{
printf("%d.%d\n", firstDigits, lastDigits);
}

}

}

[Sedefcho]

No need to worry about it. My program has been correct.
There's some problem with the JAVA I/O here in the tests
for 10200.

I rewrote my Java program in C and the Online Judge
said "Accepted".

My thanks to all of you.

[Sedefcho]

No matter how hard I tried I did not manage to get my JAVA
program "Accepted".

The strange thing is that when I rewrote it in C ( using the
same logic, the same algorithm ) it got "Accepted" immediately.

See this:
http://online-judge.uva.es/board/viewtopic.php?t=7389

[chunyi81]

remove the System.out.println(); stmt in ur code. You are printing an extra line. System.out.println() is equivalent to printf("\n") in C/C++.

[Sedefcho]

Here is the end of my main function

===============================================
firstDigits = "" + ( p / 100 );
lastDigits = ( (p % 100) < 10 ) ? "0" + (p % 100) : "" + (p % 100);
// System.out.println( percent );
// System.out.println( p0 );
System.out.println( ((firstDigits + ".") + lastDigits) );
}
// System.out.println();
}

===============================================


The line in red is the one you offer me to
change , right ?

Well as you see I've commented it OUT.

And it doesn't work.

Of course I know what
System.out.println is.
And what System.out.print is.

And what the difference between them is.

Remove it yourself and send it to the Judge -
Language - Java, Problem#10200.

Actually if it was the System.out.println() problem I should
have got Accepted P.E. and not WA.

Try it out.

Or you mean I should remove some other System.out.println ?!

I don't see another good candidate.

[chunyi81]

Yes, the line in red was what I was referring to. The only possibility left I could think of is a crash resulting from executing the Java code. The OJ detects a crash in Java as a WA. I've read the input description myself, and unless there are blank lines in the input supplied by the OJ, or a blank line at the end of the input, I don't think your Java pogram for problem 10200 will crash.

[Sedefcho]

Well, anyway. I already have this problem ACC by using
my C program. I have posted the two progs here just in case this
could be of interest to someone else who could have same
difficulties.

[Larry]

Also, extra spaces doesn't always give you PE..