Piggy Banks
Time limit1sMemory limit128 MB
Given N, choose the order of incrementing two counters from (1,1) to (N,N) so that concatenating the pair as a number gives a prime as often as possible, and output the maximum count.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Math, Number theory
- Solved
- No attempts yet
Problem
Taeseok has two piggy banks. Initially, each piggy bank contains 1 won. Each day, he chooses exactly one piggy bank and adds 1 won to it. He stops saving when both piggy banks contain N won.
For a state where the first piggy bank contains a won and the second contains b won, write a followed by b to form one integer. If that integer is prime, call the state a good state. The initial state (1, 1), which forms 11, is not counted.
Taeseok may choose the saving order freely. Among all possible orders, find the maximum possible number of good states.
Input
The first line contains an integer N. (1 <= N <= 999)
Output
Print the maximum possible number of good states.