Задача №111702. Оптимальная последовательность
У нас есть две кучки камней, изначально в каждой по одному камню. За один ход можно добавлять один камень в одну из кучек, если в ней меньше N камней. Игра заканчивается, когда в обеих кучках будет N камней.
Не странно, что в нашей школе любят простые числа. Поэтому позиция в игре считается хорошей, если после приписывания к количеству камней в первой кучке количества камней во второй кучке получится простое число.
Например, если в первой кучке 12 камней, а во второй 7, то позиция хорошая, т.к. число 127 простое.
Ваша задача найти такую последовательность ходов, при которой можно перейти из начальной позиции (1, 1) в конечную (N, N) через максимально возможное число хороших позиций. Например, для N = 4 одна из искомых последовательностей такова: 1; 1 -> 2; 1 -> 3; 1 -> 4; 1 -> 4; 2 -> 4; 3 -> 4; 4
Входной файл содержит одно число N. Гарантируется, что 1 ≤ N ≤ 999.
Выведите максимально возможное число хороших позиций для данного N (в приведенном примере оно равно трем: 31, 41, 43).
4
3