e-olymp
Məsələlər

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

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

Пусть есть множество A, содержащее все натуральные числа от 1 до N. требуется разбить его на два непересекающихся множества A1 и A2 (A1A2 = Ø, A1 U A2 = A). Обозначим N1 и N2 - количества элементов, а S1 и S2 - сумм всех элементов в множествах A1 и A2 соответственно, ΔN = |N1-N2|, ΔS = |S1-S2|. Задаются два критерия оптимальности: один из них на величину ΔN, другой - на ΔS. Критерии могут требовать максимальности или минимальности величин.

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

Входные данные

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

Выходные данные

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri
Sample 1
2
S max
N max

Sample 2
8
S min
N max
Çıxış verilənləri
Sample 1
0
2 1 2

Sample 2
5 1 2 3 4 8
3 5 6 7
Mənbə III International Summer School Programming in Sevastopol 2012