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

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

1 секунда

256 мегабайтів

Легка

Нехай є множина $A$ , що включає всі натуральні числа від $1$ до $N$ . Потрібно розділити цю множину на дві неперетинні підмножини $A_{1}$ A_1 і $A_{2}$ A_2 ( $A_{1} \cap A_{2} = \emptyset$ A_1 \cap A_2 = \varnothing, $A_{1} \cup A_{2} = A$ A_1 \cup A_2 = A). $N_{1}$ N_1 і $N_{2}$ N_2 — кількість елементів, $S_{1}$ S_1 і $S_{2}$ S_2 — сума всіх елементів у множинах $A_{1}$ A_1 і $A_{2}$ A_2 відповідно. Визначимо $Δ N = ∣ N_{1} - N_{2} ∣$ \Delta N = |N_1 - N_2| та $Δ S = ∣ S_{1} - S_{2} ∣$ \Delta S = |S_1 - S_2|. Є два критерії оптимальності: один стосується величини $Δ N$ , інший — $Δ S$ . Критерії можуть вимагати максимізації або мінімізації цих величин.

Ваше завдання — знайти розбиття, яке є оптимальним за першим із заданих критеріїв. Якщо таких розбиттів декілька, оберіть серед них оптимальне за другим критерієм. Якщо і таких декілька, можна вивести будь-яке з них.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число $N$ ( $1 \leq N \leq 1 0^{6}$ 1 \leq N \leq 10^6). У другому і третьому рядках визначаються перший і другий критерії відповідно. Перший символ кожного з цих рядків вказує на оптимізовану величину (N для величини $Δ N$ або S для $Δ S$ ), а далі через пробіл — вимога критерію для цієї величини (min — вимога мінімізації, max — вимога максимізації відповідної величини).

Вихідні дані

У вихідний файл потрібно вивести два рядки. Перший рядок визначає множину $A_{1}$ A_1 розбиття, другий — множину $A_{2}$ A_2. Перше число в рядку — кількість елементів у множині, а за ним слідують значення всіх елементів у множині в порядку зростання.

Приклади

Приклад 1