Задача Diamonds. Запрошуючи гостей на день народження, Її Величність Королева Франції (ЇВКФ) прозоро натякнула, що кожний гість має подарувати їй чотири брильянти із сумарною масою рівно N карат – для королівських підвісків. При цьому ЇВКФ додала обов’язкові умови:

1) усі маси каменів – натуральні числа карат;

2) кожний набір відрізняється від будь-якого іншого набором мас каменів (хоча б двох!);

3) у наборі маси каменів можуть бути якими завгодно, якщо вони задовольняють першим двом умовам.

Якою може бути за цих умов найбільша кількість гостей S?

Технічні умови. Програма Diamonds зчитує зі стандартного пристрою введення значення N (4<=N<=6761) і виводить на пристрій стандартного виведення значення S.

Приклади

КОМЕНТАР. Для N=7 маємо набори: 1+1+1+4, 1+1+2+3, 1+2+2+2 і S=3.

Задача Cake. Мама спекла на день народження Малюка пиріг у формі опуклого багатокутника. Після закінчення свята гості почали дорікати, що їм дісталося мало пирога, а все з’їв Карлсон. Малюк знає, що Карлсон завжди їсть лише один трикутний шматок, але ріже пиріг так, щоб отримати якнайбільше. Допоможіть порахувати, скільки пирога насправді з’їв Карлсон.

Технічні умови. Програма Cake читає з клавіатури кількість вершин багатокутника N, що задає пиріг (3<=N<=2000) і далі через пропуск N рядків по 2 розділених пропуском цілих числа, які не перевищують 10000000 за абсолютною величиною - координати вершин у порядку обходу за або проти годинникової стрілки. Програма виводить на екран одне дійсне число – площу трикутного шматка, який з’їв Карлсон.

Приклади.

Введення

4

2 2

5 1

7 4

4 7

Виведення 10.5000000000

Введення

3

0 0

0 5

12 5

Виведення 30.0000000000

Коментар. У другому прикладі Карлсон дійсно з’їв весь пиріг.

Задача Pill. Коротуни з Квіткового міста несподівано захворіли. Доктор Пілюлькін, як завжди, виміряв кожному коротунові температуру, але забув, яка температура вважається нормальною, головне, щоб у всіх була однакова. У Пілюлькіна є червоні і сині пігулки. Червона пігулка підвищує температуру тіла на один градус, а синя знижує (теж на один градус). Яка мінімальна кількість пігулок знадобиться докторові, щоб вилікувати усіх коротунів?

Технічні умови. Програма Pill читає з клавіатури кількість коротунів N (1<=N<=100000) і далі N чисел через пропуск - температуру чергового коротуна t_i (1<=i<=N, 1<=ti<=1000000000). Програма виводить на екран шукану кількість пігулок.

Приклади

Введення
2 3 7

Виведення
4

Введення
3 1 6 4

Виведення
5

Коментар

У першому прикладі один із способів: даємо першому коротунові три червоні пігулки, а другому - одну синю. У другому прикладі перший коротун отримує 3 червоних пігулки, другий - 2 сині.

Задача Diode. Проблема енергозбереження є дуже актуальною. І в цьому сенсі перспективними видаються світлодіодні світильники. Хай ми маємо світильник у вигляді прямокутної матриці N x M. У кожній комірці знаходиться світлодіод, який може світитися або ні. Генеральний Конструктор (ГК) може обрати якусь комірку і зробити перемикання - поміняти стан усіх світлодіодів у її рядку та її стовпці на протилежний. Наприклад, якщо ГК обрав комірку (2,2), то світильник, що мав вигляд (див. рис.1) потім матиме вигляд (див рис.2)

Таким чином, за 1 перемикання змінять свій стан на протилежний N+M-1 світлодіод. Виконуючи таку операцію певну кількість раз, ГК хоче досягнути стану, аби всі світлодіоди світилися. Цікаво, що в нього вийде.

Технічні умови. Програма Diode читає з пристрою стандартного введення кількість тестів Т (від 2 до 10), а далі Т груп рядків: у першому рядку кожної групи 2 числа N і M (2<=N,M<=1000), а далі N по M чисел 0 чи 1 через пропуск у кожному - 0, якщо відповідний світлодіод світиться, і 1 – якщо ні. Програма виводить одним рядком без пропусків послідовність з Т цифр 2 та 3. (2 – якщо відповідний світильник вдалося ввімкнути повністю, 3- якщо ні).

Приклад

Задача Schools. У нашому районі n сіл, деякі з них з’єднані дорогами, що ніде не перетинаються. У кожному селі одна школа. Директор департаменту освіти отримав наказ, згідно якого з метою економії в районі повинна залишитись лише одна школа, а з інших шкіл учнів возитимуть шкільні автобуси. Райдержадміністрація виділяє один літр бензину на один кілометр на кожного учня. Директор знає, скільки учнів навчається у кожній школі. Також відомі відстані між селами. Допоможіть визначити, яку школу потрібно залишити, щоб мінімізувати витрати бензину.

Технічні умови. Програма Schools читає з клавіатури цілі числа n (1<=n<=100) - кількість сіл, та через пропуск m – кількість доріг. Далі програма читає через пропуск m трійок чисел – номери сіл i, j (1<=i,j<=n, i<>j), що з’єднує дорога, та s – довжина дороги s (натуральне число, що не перевищує 100). Далі через пропуск програма читає n натуральних чисел a_i, що не перевищують 100 – кількість учнів у і-й школі. Гарантується, що по дорогах можна проїхати між будь-якими двома селами. Будь-які два села з’єднані не більше ніж однією дорогою. Кожна дорога описується один раз. На всіх дорогах дозволяється рух у двох напрямках. Якщо кілька шкіл забезпечать мінімум витрат бензину, директор вибирає школу з найменшим номером.

Приклад

Введення
3 3 1 2 8 2 3 2 3 1 6 10 6 4

Виведення
1

Коментар. Якщо вибрати першу школу, треба 8*6+6*4=72, якщо другу –  8*10+2*4=88, якщо третю –  6*10+2*6=72  літрів бензину.