PEG Test - Halloween 2014
Problem D: Prime Street
Alex and Ben have found a peculiar street in their neighborhood this Halloween night.
On this street, houses on the left side of the street are numbered with consecutive prime numbers starting from 2, and houses on the right side of the street are numbered with consecutive composite numbers starting from 4. Each side of the street has 100000 houses. The index of a house is the position of a house from the start of the street. For example, house 3 is index 2 on the left side of the street, and house 8 is index 3 on the right side of the street. What's even more peculiar, is that each house will always give the amount of candy equal to its house number.
Index: 1 2 3 4 5 6 7 8 9
Left House #: 2 3 5 7 11 13 17 19 23
Right House #: 4 6 8 9 10 12 14 15 16
Alex will trick or treat on the left side, and Ben will trick or treat from the right side. They will begin trick-or-treating at a house with the same index, and can cover a range of K houses. Alex and Ben want their final yield of candy to be as close as possible. However, because Alex has run into some trouble with the Brap Lesh Mafia, he must pay the Brap Lesh Mafia N units of candy immediately after trick-or-treating.
Determine the index of the house that Alex and Ben should start at such that, after Alex pays N units of candy, they finish with the minimum difference in candy.
Input Format
There will be one line of input containing two integers N and K (0 ≤ N ≤ 1015; 1 ≤ K ≤ 100000).
Output Format
Output a single integer, the index of the house that Alex and Ben should start at such that they finish with the minimum difference in candy amount. If multiple solutions exist, print the smallest one.
Sample Input 1
0 5
Sample Output 1
3
Explanation 1
Alex does not owe any candy in this case. Starting from house at index 3, Alex and Ben will both collect 53 units of candy. This is the optimal solution.
Sample Input 2
5 2
Sample Output 2
6
Explanation 2
Starting at index 6, Alex will collect 13+17 = 30 pieces of candy, and Ben will collect 12 + 14 = 26 pieces of candy. After paying off his debt, Alex will have only 1 less piece of candy than Ben. This is the optimal solution.
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 07, 2014
Author: frenzybenzy
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)