Шахматная комбинаторика

Автор задачи: Сергей Штейнер

Задачу добавил: shtserg

Успешно сдано решений: 3

Дано натуральное число n, 1 <= n <= 10⁵⁰.

Необходимо определить, какое наибольшее число фигур определённого типа можно расставить на шахматной доске 8n×8n так, чтобы они не били друг друга.

Во входном файле записано число n и ещё один символ через пробел для обозначения типа фигур, для которых ставится эта задача,

'K' для короля, 'Q' для ферзя, 'R' для ладьи, 'N' для коня ('K' уже занята ;) ), 'B' для слона.

Пример

input.txt

1 R

output.txt

Замечание.

Решения, верно работающие для определённого типа фигур, будут оцениваться в 18 баллов для каждого типа.

Решения, верно работающие при 8n <= 10⁹, наберут не менее 45 баллов.