VM7WC '15 #1 Gold - JHK - DMOJ: Modern Online Judge

VM7WC '15 #1 Gold - JHK

Points: 10

Time limit: 2.5s

Memory limit: 256M

Author:

Problem type

JHK (whose true name shall not be revealed) is one of Mr. Ing's favourite students. In light of the recent successful defense of the Ingdom, JHK decides to celebrate by preparing for this year's Putnam contest. On week one of his Seven Week Challenge, JHK decides he wants to study prime numbers. Write a program to help him solve the following problem.

Define the Junghoon-value (or the J-value for short) of a positive integer $i$ ~i~ to be the least number of primes (not necessarily distinct) required to yield a sum of $i$ ~i~. For example, the number $8$ ~8~ can be formed using the primes $2,2,2,2$ ~2,2,2,2~ OR $3,5$ ~3,5~, therefore its J-value is 2. Note: If no combination of primes sum to $i$ ~i~, its J-value is undefined.

Help ~~Junghoon~~ JHK find the number of positive integers less than or equal to $N$ ~N~ $(1 \le N \le 7\,000)$ ~(1 \le N \le 7\,000)~ with J-value of exactly $K$ ~K~ $(1 \le K \le N)$ ~(1 \le K \le N)~.

Input Specification

One line containing two space-separated integers, $N$ ~N~ and $K$ ~K~.

Output Specification

Print the number of positive integers less than or equal to $N$ ~N~ with J-value of exactly $K$ ~K~.

Hint

It would be helpful to know the Sieve of Eratosthenes.

Sample Input

5 1

Sample Output

Comments

1

FatalEagle commented on Jan. 9, 2015, 4:44 a.m. ← edit 2 →

If your solutions TLE on Python 3, you can try submitting in PyPy 3 (which is a faster interpreter for Python 3).

2

Butane commented on Jan. 8, 2015, 10:43 p.m. ← edited →

Is there a reason that my second submission for this problem was removed? I had solved it a while back

0

thorthugnasty commented on Jan. 9, 2015, 8:23 p.m. ← edited →

This is an in school contest and although outside participation is accepted we don't like to see our top ranks filled by non-Massey students. Plus it's not a very serious competition so I didn't think it would be a big deal. Sorry if this caused any tears or emotional outbursts. Note: I don't think I'll delete outside submissions anymore because that would mean work.

5

FatalEagle commented on Jan. 9, 2015, 8:37 p.m. ← edited →

While removing contest participations or contest submission records is within the rights of the contest organizer to a reasonable extent, deleting submissions is a misuse of privilege. To remove a user from the rankings, simply remove their contest participation instead of deleting submissions, or make it clear the unofficial participants should join some amount of time after the contest begins.

4

quantum commented on Jan. 8, 2015, 11:08 p.m. ← edit 2 →

Found missing submission #27250 inside logs. thorthugnasty apparently deleted it, ask him for the reason.

https://i.imgur.com/3oowLt1.png