MWC '15 #6 P2: Breadwinners

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Flowright has registered in a bread eating contest, in which he will be competing against N (1 \le N \le 500\,000) competitors for the grand prize of a toaster! To win, he must eat more slices of bread than all the other competitors at the tournament. Being a contrarian individual, Flowright wishes to lose against each competitor. Flowright has confidence in his abilities, but he also has a strange compulsion to eat a prime number of bread slices in each round.

Wanting to know his chances of losing, Flowright has determined C_i (1 \le C_i \le 10^4), the number of slices that his competitors can eat per round. As Flowright is very hungry, help him determine the maximum number of slices he can eat in each round while still losing to his competitors.

Note: For 50% of points, N \le 10^5 and C_i \le 10^3.

Input Specification

On the first line, one integer N representing the number of competitors.

On the second line, N space separated integers C_i, representing the amount of bread that the i^{th} competitor can eat.

Output Specification

Output N lines, with the i^{th} line representing the largest number of bread slices Flowright can eat while still losing against the i^{th} competitor. If there is no way that Flowright can lose the round, output no can do.

Sample Input

5 7 1

Sample Output

no can do

Explanation of Sample Output

In the first two rounds, Flowright can eat 3 and 5 slices respectively. In the third round, there is no valid number of slices that Flowright can eat and still lose.


There are no comments at the moment.