Задано два цілі числа. Треба вивести третє, таке що одне з двох чисел не вході є меншим за третє, а інше — більше.
Якщо \(|a-b| \le 1\), то таке зробити неможливо. Інакше відповідь існує. Наприклад, завжди підходить число \(min\{a, b\} + 1\).
Задано рядок символів. Потрібно сказати, скільки символів треба вставити в рядок, щоб жодні два символи підряд не були однаковими.
Щоб два однакові символи підряд перестали бути двома однаковими символами підряд, достатньо вставити поміж них будь-який інший символ. Тому відповідь — кількість пар однакових символів підряд.
Набір кубиків розташовано на прямокутнику, у кожній клітинці прямокутника є декілька кубиків, поскладаних один на одного. Треба вивести послідовність, у якій їх забирати, щоб на кожному кроці кількості кубиків у клітинках утворювали незростаючі послідовності в кожному рядку й у кожному стовпці.
У задачі є багато можливих розв’язків. Наприклад, можна йти по рядках знизу вверх, по кожному рядку справа наліво й повністю забирати всі кубики з клітинок у такому порядку. Легко бачити, що при такому порядку забирання кубиків необхідна умова завжди буде підтримуватися.
Задано набір з \(n\) чисел, кожне з яких від 1 до 4. Потрібно розбити цю множину на дві з однаковою сумою.
Очевидно, для кожної з можливих ваг \((1..4)\) нас цікавить, скільки котів з такою вагою припаде Зенику. Тому достатньо перебрати всі четвірки чисел \((c_1, c_2, c_3, c_3)\), які позначають, скільки котів певної ваги отримає Зеник. Якщо існує четвірка, для якої \(1 \cdot c_1 + 2 \cdot c_2 + 3 \cdot c_3 + 4 \cdot c_4 = \frac{s}{2}\) — розділити котів можна, інакше — ні (тут \(s\) — загальна вага всіх котів).
Задано масив чисел. Видалимо з нього всі такі елементи, що елемент ліворуч від них є більшим. Повторюємо такий процес, поки масив міняється. Треба сказати результуючий масив.
Зрозуміло, що з масиву видаляться всі такі елементи, що десь праворуч від них є більший елемент, а всі решта залишаться. Тому будемо йти справа наліво і підтримувати максимум на суфіксі. Якщо поточне число менше за максимум, то воно видалиться. Інакше воно увійде в результуючу послідовність.
Задано розміри прямокутника, який треба покрити плиткою \(2 \times 1\). Одну з клітинок покривати не можна. Потрібно сказати, чи можна покрити всі клітинки, крім заданої. Якщо так — вивести розбиття.
Неважко побачити, що коли \(n\) або \(m\) є парними, то відповіді не існує. Адже в такому разі загальна кількість клітинок, які потрібно покрити, є непарною, тому це неможливо.
Коли \(n\) та \(m\) є непарними, покриття все ще може бути неможливим (другий тест з умови). Розфарбуємо прямокутник у шаховому порядку. Причому пофарбуємо верхню ліву клітинку в білий колір. У такому разі білих клітинок на одну більше, ніж чорних. Оскільки одна плитка покриває одну білу та одну чорну клітинки — нам потрібно, щоб кіт спав на білій. Клітинка біла, якщо \(x+y\) — парне число.
Якщо ж \(n\) та \(m\) є непарними, а \(x+y\) — парним, прямокутник можна розфарбовувати так. Неважко з правої сторони відрізати смужку довжиною 2:
(Так само можна відрізати смужку розміром 4, 6, 8, ..., тобто будь-яку парну довжину.)
Аналогічно по інших сторонах:
Після цього або вся площа буде закладеною, або ж залишиться квадрат \(3 \times 3\), усередині якого є виділена клітинка. Такий квадрат легко розфарбувати — достатньо розкласти 4 плитки «по колу» від виділеної клітинки.
Задано дерево, у якому \(k\) вершин є позначеними. Потрібно розбити ці вершини на пари так, щоб не було двох пар, для яких шляхи між вершинами перетинаються.
Підвісимо дерево за довільну вершину. Знайдемо найнижчу вершину, для якої кількість позначених вершин у піддереві (включно з нею) більша за один. Тоді зрозуміло, що якщо кількість для цієї вершини є більшою за два, то відповіді не існує, адже хоча б два шляхи точно будуть проходити через цю вершину. Якщо ж ця кількість є рівною 2, то спаруємо ці вершини та видалимо їхні позначення. Цей процес потрібно повторювати, допоки залишаються позначені вершини.
Цей процес найкраще симулювати алгоритмом пошуку в глибину, де рекурсивна функція повертає позначену вершину, яка залишились у піддереві.