10200 - Prime Time

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

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!! :wink: :wink:
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.

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

thanxxxxxxxxxxxxxxx

Post by Riyad »

thanx buddy got it ac after so many submissions . u r semi hard core algo worked out perfectly well.
Bye
Riyad
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)

Post by mohiul alam prince »

riyad
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
Location: Dhaka, Bangladesh

10200 Prime Time

Post by kamrul »

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

Post by sohel »

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.
:wink:

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

Gratitude

Post by kamrul »

Now I got AC :D

Thank you Sohel.
Your trick helped me.

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

10200 - Prime Time

Post by nford85 »

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:

Post by Minilek »

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

Post by nford85 »

Thanks thats a great help :D

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

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

Post by branka »

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{
	static String ReadLn (int maxLg)
	{
	 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')) 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. :roll: :roll:
Thank you!!!

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Post by jhonny_yang »

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:

Post by Boss »

Hi branka i have the same problem, please tellme how solve the "You must read until the end of the file." in JAVA !!!

wainting for your soon answer, greetings Boss.

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:

Post by Boss »

Hi !!! in this problem i have a restlessness.
what is mean :: "You must read until the end of the file."

my program is in java, normaly i read from System.in.read();
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

Post by Ghust_omega »

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

Post by Sedefcho »

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

Post Reply

Return to “Volume 102 (10200-10299)”