10200 - Prime Time

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
I suggest to use "semi-hardcode".

Code: Select all

``````for(i=0;i<=10000;i++){
result=i*i+i+41;
if(result%2!=0){
j=sqrt(result);
for(k=3;k<=j;k+=2){
if(result%k==0) break;
}
if(k>j) primality[i]=1;
}
}
``````
So, in the main function you just check from the range a to b, how many times primality=1 occurs and just count the percentage!!
Hope it helps!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

thanxxxxxxxxxxxxxxx

thanx buddy got it ac after so many submissions . u r semi hard core algo worked out perfectly well.
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
i think ur algo is not good for prime time

1. u collect ur prime by samims algo
2. then u will store the equations value is prime or not(it will be stored in the another array(MMM[]))
3.then u take input and chake is this input is prime or not then count

prince
10-11-2003

kamrul
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am

10200 Prime Time

I m getting TLE for This Problem
Can anyone tell me what is the problem with my algo.

It runs well for the worst inputs

as:
0 10000
[cpp]
Code Removed
[/cpp]

Thanks.
Last edited by kamrul on Wed Dec 31, 2003 11:28 am, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Wrong Approach

Hi Kamrul,
Your algorithm is correct in terms of accuracy but not for the time limit.
From your code, it looks like you are checking for prime for every number in the range. Why don't you first process all the numbers before the loop and store it in an array. And for every case just check for validity from the array.

hope it helps.

kamrul
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am

Gratitude

Now I got AC

Thank you Sohel.

nford85
New poster
Posts: 3
Joined: Sun Dec 28, 2003 5:15 am

10200 - Prime Time

Hi

This seems to be an unusual request for this particular problem - from a preliminary search i did most people seemed to have problems with getting into the time limit. I can get into the time limit but somehow I just get WA every time. Can someone supply me with some sample inputs and outputs so I can try and find the problem myself?

Thanks
Nick

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
good luck

Input:

Code: Select all

``````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:

Code: Select all

``````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
``````

nford85
New poster
Posts: 3
Joined: Sun Dec 28, 2003 5:15 am
Thanks thats a great help

branka
New poster
Posts: 4
Joined: Fri Sep 10, 2004 2:21 pm

10200, What does it mean???????

HALO!!!
What does mean: "You must read until the end of the file." ??

All other problems had something like Problem number 694: " A line that contains two negative integers follows the last case."

Is it posible, that i get TLE because it doesn't read the last line??

Here is my code in Java:

Code: Select all

``````/* @JUDGE_ID: 50020MM 10200 java */
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.lang.Object;

class Main{
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main(String[] args)
{
Main myWork = new Main();
myWork.Begin();
}
void Begin(){
java.text.DecimalFormat dec = new java.text.DecimalFormat(",##0.00");
String input;
StringTokenizer idata;
int a, b, stevec, k, rezultat, rez;
double j, procent, st;

while((input = Main.ReadLn (255)) != null)
{
idata = new StringTokenizer (input);

a = Integer.parseInt(idata.nextToken());
b = Integer.parseInt(idata.nextToken());
stevec = 0;

if((a>b)||(a>10001)||(b>10001)){
break;
}//if
rezultat = a*a + a + 41;
if(b<40){
System.out.println("100.00");
}
else{
for(int i=a;i<=b;i++){
if((rezultat%2!=0)||(rezultat%3!=0)){
j=Math.sqrt(rezultat);
for(k=5;k<=j;k+=2){
if(rezultat%k==0){
break;
}//if
}//for
if(k>j){
stevec++;
}//if
}//if
rezultat = rezultat+2*i+2;
}//for
st = b - a + 1;
procent = (Math.round(((stevec*100)/st)*100))/100.0;
String str = dec.format(procent).toString();
System.out.println(str.replace(',', '.'));
}//else
}//while
}//Begin
}//Main
/*@END_OF_SOURCE_CODE*/

``````
Or is it something wrong with my algoritem???

Pleas help me, I am really loosing my head on this one.
Thank you!!!

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am
why this problem comes to prime number? that's a faktorial .. using bignum library to solve this prob. it's easy

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:
Hi branka i have the same problem, please tellme how solve the "You must read until the end of the file." in JAVA !!!

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:
Hi !!! in this problem i have a restlessness.
what is mean :: "You must read until the end of the file."

but, if i must to read from a file, how is the name of the file ???
System.in by default is keyboard

waiting for yours soon answer, greetings Boss !!

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
HI !! to all here a topic that can be usefull
http://online-judge.uva.es/board/viewto ... e9f0d2617d

This topic ist about java I generaly dont code in java but I see this and I believe maybe helps
Hope it Helps
Keep posting !!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Can somebody give any test cases.

How should we round the percentages ( the answers ).
If we have
37.568% should we print 37.56 or 37.57