Задача A, 1 тур
    Гірший випадок буде коли перший гравець візьме максимум цукерок, а другий мінімум. Тому знайдемо максимум і мінімум в послідовності та виведемо їх різницю.

Задача B, 1 тур
    Зчитаємо перший рядок  та виведемо його. Потім зчитаємо 3 останні в масив, відсортуємо його будь-яким алгоритмом(порівнювати рядки можна звичайними операторами < та >). Та виведемо їх як це просять в умові.

Задача C, 1 тур
    Факторизуємо число звичайним алгоритмом пошуку простих дільників , тобто представимо число у вигляді: N= a1^b1*a2^b2*a3^b3*…, де a1, a2, a3, … - прості числа. Тоді відповіддю буде число S = (a1^0+a1^1+a1^2+..+a1^b1)*(a2^0+a2^1+a2^2+…+a2^b2)*… 

Задача D, 1 тур
     Шуканий трикутник лежить у вершинах даного багатокутника. Алгоритм рішення такий:
зафіксуємо одну вершину (припустимо це буде вершина i), будемо перебирати вершину  j від і+1 до N, а в кожній ітерації циклу будемо рушати деяку вершину К поки площа трикутника (i,j,k) – зростає. Максимум який буде досягатися при обрахунках і буде відповіддю на задачу. Нижче наведений псевдокод рішення:
for i=1..N
   {
       k = i+1;
       for j=i+1..N
    {
        If (k<=j) k= j+1;
        last = -1;
        while (k<=N)   
        {
            temp = square(i,j,k);
             if (temp > max) max = temp;
            if (temp < last) break;
            last = temp;
            k = k+1;
        }
      k = k-1;
    }   
   }
 
В Max – буде відповідь на задачу. 
Примітка: функція square повинна вертати подвоєну площу трикутника, бо так вона буде ціла. Також для неї потрібно використовувати тип int64. Щоб порахувати подвоєну площу без дійсних чисел потрібно використовувати формулу:
2*S = |(x1-x2)*(y1+y2) + (x3-x2)*(y3+y2) + (x1-x3)*(y1+y3)|

Задача E, 1 тур
     Перше рішення,яке набирало 30 балів є динамічне програмування за О(N*N):
A[1] = 0
A[i] = max(A[j]+|X[j]-X[i]|*C[j])+T[i] 1<=j<i
Позбудемось модуля , будемо мати дві формули з яких треба буде вибрати максимум:
A[i] = max(max(A[j]+X[j]*C[j]-X[i]*C[j]),max(A[j]-X[j]*C[j]+C[j]*X[i]))+T[i]
Нехай K1[i] = -C[i] , B1[i] = A[i] +X[i]*C[i] , K2[i] = C[i] , B2[i] = A[i] -X[i]*C[i], це є прямі з кутовими коефіцієнтами K1 та K2 та вільними  членами B1 та B2.
Отже кожен раз нам буде потрібно знаходити пряму яка перетинає нашу в максимальній по У координаті. Та створювати нові прямі і додавати їх до множини. Це можна зробити звичайною множиною прямих в кожен момент вона повинна додавати прямі тільки тоді коли вони хоча-б при одному Х є найвищими. Аналогічно треба і прибирати прямі з множини якщо вони в усіх точках в яких Х від -1000000 до 1000000 є ця пряма має менший У ніж у якоїсь іншої.
 
 На малюнку зображено червоними лініями ті прямі, які будуть входити в множини, а чорними ті, які не будуть.

Задача A, 2 тур
    Відповідь на задачу розкладається на  2 випадки:
K > N, відповідь: 2
K <= N, відповідь: (2*N+K-1)/K,

Задача B, 2 тур
    Задамо всі погані пари в матриці. Потім просто переберемо три смаки і за О(1)  перевіримо цю трійку на правильність.

Задача C, 2 тур
    Задамо найкоротші відстані від вершин A та B алгоритмом Дейкстри(нехай це будуть масиви D1 та D2). Переберемо вершину в якій будемо купляти товар, нехай це буде першина V, тоді відповіддю буде Min(D1[v]+D2[v]+Cost[v]), Cost[v] – ціна покупки товару в веришні v.

Задача D, 2 тур
     Якщо (a=1 та b=1) або (a=1 та c=1) або (b=1 та c=1) то відповідь “NO”.
Якщо інші критерії не виконались і виконалось хоча-б одна умова:  a mod 2=0 або b mod 2=0 або c mod 2=0, то відповідь “YES” в усіх інших випадках “NO”.

Задача E, 2 тур
     Нехай:
- d1[i,j] – кількість клітинок в які ми можемо походити вгору з клітнки(i,j) не перетинаючи дерев.
- d2[i,j] – кількість клітинок в які ми можемо походити вліво з клітнки(i,j) не перетинаючи дерев.
-d3[i,j] – кількість клітинок в які ми можемо походити вниз з клітнки(i,j) не перетинаючи дерев.
- d4[i,j] – кількість клітинок в які ми можемо походити вправо з клітнки(i,j) не перетинаючи дерев.
- e1[i,j] = min(d1[i,j], d2[i,j])
- e2[i,j] = min(d3[i,j], d4[i,j])
 
Синіми лініями позначено e1 для клітинок, червоними e2 для клітинки для яких ми будемо рахувати відповідь(тобто кількість трас кут яких співпадає з даною клітинко).

   Очевидно, що другий кут траси повинен лежати на тій самій діагоналі що містить і перший кут.  Зобразимо це на нашому малюнку:

Тому будемо рахувати всі дані для кожної діагоналі окремо. Будемо для кожної діагоналі підтримувати ті сині лінії що зображені на малюнку. Для кожного Х нам потрібно знати кількість синіх ліній, що починаються на даному Х, щоб взнавати суму кількостей на деякому відрізку нам допоможе дерево Фенвіка. Також нам треба зберігати кучу(по мінімум на горі), в якій будемо зберігати Х, що будуть закінченнями синіх ліній. Коли якийсь елемент стає менше ні можна (тобто його Х менший ніж тий на якому ми знаходимось) то його треба викинути із кучі і змінити відповідний елемент в дереві Фенвіка. Коли ми хочемо порахувати відповідь для клітинки, то просто викинемо з кучі все, що нам не потрібно та візьмемо в дереві Фенвіка потрібну суму, тобто таку що довжина нашої траси буде не менше L і сторона не буде більше ніж це можливо.

4 та 5 лютого буде проведено III етап Всеукраїнської олімпіади з інформатики (програмування). Олімпіада складається з двох турів, на кожен тур учням буде запропоновано по 5 задач різної складності. Кожна задача оцінюється в 100 балів.

Робота учасників підтримується в електронній системі доступ до якої здійснюється через «точку входу» за використанням персонального логіну та паролю. Система дозволяє читати умови задач, відсилати запитання щодо умов задач, та відсилати розв’язок для автоматичної його перевірки на спеціально підготовленому наборі тестів. Бажаємо всім успіхів ! 

18.12.11 з 10.00 розпочнуться міські та районні шкільні олімпіади з програмування Дніпропетровської області. Планується, що в олімпіаді приймуть участь більше ніж 1250 учасників з 45 районів області. Учасникам буде запропоновано п’ять алгоритмічних задач різної степені складності.

Вхід до системи проведення олімпіади.

Таблиця результатів. 

21. Почти простые числа

Почти простым числом будем называть число, которое представимо в виде произведения двух простых чисел. По заданному числу , ответьте является ли оно почти простым.

Входные данные
2 ≤ N ≤ 10⁹

Выходные данные
Необходимо вывести строку Yes, если число почти простое, или No, в обратном случае.

Пример

 
6

 
YES

 
8

 
NO

22. Научная проблема

Однажды профессор путешествовал в поезде. Наблюдая унылые пейзажи за окнами он решил придумать тему своей научной работы. Его посетила гениальная мысль: разработать эффективный алгоритм нахождения целого числа, которое в х раз меньше суммы всех чисел, которые меньше него. Так как у профессора нет компьютера в поезде, помогите ему решить эту проблему.

Входные данные
2 ≤ N ≤ 10⁹ + 7

Выходные данные
Вывести ответ на задачу.

Пример

 
1

 
3

 
2

 
5

23. Высшая математика

Вы строите дом. Предпочтительно, чтобы все стены были вертикальными, но у вас нет прибора, чтобы проверить это. Друг предложил как проверить перпендикулярна ли стена: вам нужно отойти от стены, затем измерить расстояние от вас до основания стены, высоту стены и расстояние от верха стены до вас. Друг сказал вам сделать это для всех стен, а затем он расскажет что делать дальше. К сожалению, когда вы закончили, на вашего друга упала балка и он попал в больницу. Это очень плохо, потому что у вас есть все измерения, но вам не понятно что с ними делать. Даны три стороны треугольника, определите , является ли он прямоугольным.

Входные данные
1 ≤ a, b, c ≤ 40000

Выходные данные
Вывести “yes” , если треугольник с заданными сторонами является прямоугольным и “no” если не является.

Пример

 
36 77 85

 
yes

 
40 55 69

 
no

24. Взаимнопростые

По заданному числу N, найти количество чисел, которые не больше N и взаимнопростые с N. Взаимнопростыми числами называются числа, НОД которых равен 1.

Входные данные
2 ≤ N ≤ 10⁹ + 7

Выходные данные
Вывести ответ на задачу.

Пример

 
9

 
6

25. Праздничное застолье

Организаторы олимпиады по математике решили устроить праздничный банкет. Было приглашено C участников и приготовлено P плюшек. Каждый участник съел Q плюшек и L плюшек осталось(L < Q). И теперь организаторам интересно, сколько плюшек съел каждый участник.

Входные данные
В первой и единственной строке входного потока дано два натуральных числа — P и L (2 ≤ L ≤ P ≤2³¹).

Выходные данные
Все возможные варианты ответа в возрастающем порядке. Если нет подходящего числа, то вывести «impossible»

Пример

 
10 0

 
1 2 5 10

 
13 2

 
11

 
300 98

 
101 102

 
1000 997

 
impossible

26. Предсказание Панорамикса

Простым числом называется число, которое имеет ровно два различных делителя: единицу и само себя. Например, числа 2, 7, 3 являются простыми, а 1, 6, 4 — нет. Следующим после x простым числом называется наименьшее простое число, большее x. Например, после 2 следующим простым является 3, а после 3 следующим простым является 5. Учтите, что для каждого числа есть ровно одно следующее простое. То есть 5 не является следующим простым для 2. Однажды, холодным апрельским утром Панорамикс предсказал, что скоро освободится Какофоникс из своей смирительной рубашки, и чёрный день наступит для жителей галльской деревни. Этот день, после третьей порции волшебного снадобья, определился друидом очень просто: если в некоторый день Астерикс и Обеликс побьют ровно x римских солдат, где x — простое число, а на следующий день они побьют ровно y римских солдат, где y — следующее после x простое число, то стоит ждать конца света, ибо ничто не сможет сдержать Какофоникса с его адской песней. Вчера галлы побили n римских солдат и оказалось, что число n — простое! Сегодня их жертвами стал отряд из mримлян (m > n). Определите, стоит ли ждать чёрного дня после сегодняшней победы Астерикса и Обеликса?

Входные данные
В первой и единственной строке входного потока дано два натуральных числа — n и m (2 ≤ n < m ≤ 50). Гарантируется, что число n — простое.

Выходные данные
Выведите YES, если число m оказалось следующим простым после n, или NO в противном случае.

Пример

 
3 5

 
YES

 
7 11

 
YES

 
7 9

 
NO

27. Последняя цифра A^B

Требуется написать программу, которая находит цифру, на которую оканчивается число A^B.

Входные данные
Входной файл состоит из единственной строки, содержащей два целых числа A и B, разделенных пробелом (1 ≤ A,B ≤ 10000).

Выходные данные
В выходной файл выведите цифру, на которую оканчивается A^B.

Пример

 
2 2

 
4

 
3 7

 
7

 
24 9

 
4

28. Наилучший делитель

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше. Дано число N. Найдите такой его делитель (само число N и единица считаются делителями числа N), который лучше любого другого делителя числа N.

Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N < 2³¹).

Выходные данные
В выходной файл выведите ответ на задачу.

Пример

 
10

 
5

 
239

 
239

29. Отважные воздухоплаватели

Десять математиков летели на воздушном шаре над Тихим океаном. Когда они пересекали экватор, они решили отметить это событие и открыли бутылку шампанского. К сожалению, пробка пробила дыру в воздушном шаре. Водород начал вытекать, а шар — снижаться. Скоро он упадёт в океан, и все воздухоплаватели будут съедены голодными акулами. Но пока ещё не всё потеряно. Один из воздухоплавателей может выпрыгнуть, пожертвовав собой, чтобы его друзья смогли пожить чуть дольше. Осталась только одна проблема — кто будет этим человеком. Есть честный способ решить этот вопрос. Сначала каждый из математиков напишет целое число a_i, не меньшее 1 и не большее 10 000. После чего они найдут волшебное число N, равное количеству положительных делителей произведения a₁*a₂*...*a₁₀. Например, количество положительных целых делителей числа 6 равно 4 (делители 1, 2, 3, 6). Герой (математик, который будет выброшен) определится последней цифрой числа N. Ваша задача — найти эту цифру.

Входные данные
Ввод содержит десять целых чисел, каждое число в отдельной строке.

Выходные данные
Выведите одну цифру от 0 до 9 — последнюю цифру N.

Пример

 
1
2
6
1
3
1
1
1
1
1

 
9

30. Проверка на простоту

Проверьте, является ли число простым.

Входные данные
2 ≤ N ≤ 10⁹

Выходные данные
Необходимо вывести строку prime, если число простое, или composite, если число составное.

Пример

 
5

 
prime

 
7

 
prime

 
9

 
composite

 
2

 
prime