eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Оптимальное разбиение

Оптимальное разбиение

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Пусть есть множество A, содержащее все натуральные числа от 1 до N. требуется разбить его на два непересекающихся множества A_1 и A_2 (A_1A_2 = Ø, A_1 U A_2 = A). Обозначим N_1 и N_2 - количества элементов, аS_1 и S_2 - сумм всех элементов в множествах A_1 и A_2 соответственно, ΔN = |N_1-N_2|, ΔS = |S_1-S_2|. Задаются два критерия оптимальности: один из них на величину ΔN, другой - на ΔS. Критерии могут требовать максимальности или минимальности величин.

Ваша задача - найти разбиение, являющееся оптимальным в смысле первого из заданных критериев. Если таких разбиений несколько, то следует выбрать из них оптимальное в смысле второго критерия. Если же и таких несколько, то можно выводить любое из них.

Вхідні дані

В первой строке входного файла задаётся натуральное число N (1N10^6). Во второй и третьей строках определяются первый и второй критерии соответственно. Первый символ каждой из этих строк определяет оптимизирующую притерием величину ("N" для величины ΔN или "S" для ΔS), а далее через пробел - требование критерия на эту величину ("min" - требование минимальности, "max" - требование максимальности соответствующей величины).

Вихідні дані

В выходной файл необходимо вывести две строки. Первая из них определяет множество A_1 разбиения, вторая - множестов A_2. Первое числ в строке - количество элементов в множестве, а за ним следуют значения всех элементов в множестве в порядке возрастания.

Приклад

Вхідні дані #1
2
S max
N max
Вихідні дані #1
2
3
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь