`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Завдання 4-го Real-Time туру NetOI-2009 (13/02/10)
Задача Baksis
 

Задача Baksis

    В абсолютно нам чужій і жахливо корумпованій країні бригада з N старателів мила золото, причому кожен зсипав видобуток у свій мішечок. Бригадир, щоб Чесна Влада Країни закрили очі на їх витівки, велів підготувати 2 хабарі – Великому Столичному Босові (ВСБ) і Маленькому Місцевому Цареві (ММЦ). Хитрий Бригадир знав, скільки грамів золота намив кожен із старателів. Він вишикував їх у шеренгу, а потім, керуючись Вищими Міркуваннями, пройшов уздовж шеренги від початку до кінця, вказуючи пальцем на тих, хто повинен із неї вийти, а таких в будь-якому випадку буде не менше 2-х. Той, що вийшов першим, зробив крок вперед, а другий – назад, третій – знову вперед, четвертий – знову назад... У будь-якому випадку кількість тих, хто робив крок вперед, дорівнює кількості тих, хто робив крок назад. Зрозуміло, що кожен наступний із тих, хто виходить, стояв спочатку в шерензі правіше тих, які вийшли раніше.
    Далі Хитрий Бригадир велів «переднім» віддати свій видобуток для хабара Великому Столичному Босові, а «заднім» - Маленькому Місцевому Цареві. І ось тут-то і стали зрозумілими Вищі Міркування: різниця між сумами грамів золота, що йдуть на хабарі Великому Столичному Босові і Маленькому Місцевому Цареві, має бути максимальною. Допоможіть Хитрому Бригадирові реалізувати Вищі Міркування.

 Технічні умови

   Програма Baksis читає з клавіатури число N (2 ≤ N≤ 32767), а далі P1, P2, ..., PN (1≤Pi ≤ 100 000) цілих чисел, де Pi – видобуток старателя, що стоїть в шерензі на і-му місці. Шеренга нумерується від лівого краю, починаючи з одиниці. Всі числа розділені пропусками.
    Програма виводить на екран одне число – максимально можливу різницю між хабарами.

  Приклади

Введення
 2    10000   1
Виведення
 9999

Введення
7  7  6  2  4  8  1  5
Виведення
12

Введення
4  1  2  3  4
Виведення
-1

Задача Lottery

     Є лотерея, що проводиться за правилами: грають N (2 ≤ N ≤ 500 000) осіб, кожен гравець називає будь-яке K-значне (2 ≤ K ≤ 17) число в системі числення з основою M (2 ≤ M ≤ 10). Усі числа порівнюються з виграшним числом, і ті гравці, числа яких співпали з виграшним лише у 1-ій цифрі, отримують виграш c1; у 1-ій та 2-ій — c2 (причому не додатково до c1, а замість c1), у 1-ій, 2-ій та 3-ій — c3 і т.д. Гарантовано, що 1 ≤ c1 ≤ c2 ≤ … ≤ cK ≤ 4000. Вгадані цифри повинні починатися з 1-ої і йти підряд (зокрема, якщо не вгадана 1-а цифра, виграшу не буде незалежно від кількості подальших вгаданих ). Числа, що їх називають гравці, а також виграшне число, можуть починатися з нулів.

     Ведучий лотереї має можливість схитрувати: не брати виграшне число випадково, а підібрати його, знаючи, які числа назвав кожен із гравців. Яку найменшу суму виграшів йому все ж доведеться виплатити?

 Технічні умови
    Програма Lottery читає з клавіатури кількість цифр у кожному числі K, основу системи числення M, кількість гравців N, а далі N штук K-цифрових чисел, потім суми виграшів c1, c2, ..., cK. Усі вхідні дані записані в один рядок, будь-які сусідні числа («звичайні» чи в системі числення з основою M) розділені рівно одним пропуском.

    Програма виводить на екран два числа, розділені одним пропуском —мінімальну суму, яку все ж доведеться виплатити (її виводити у десятковій системі), та виграшне число, яке підбирає ведучий (його треба вивести як K-цифрове в системі числення з основою M, у разі потреби — з нулями спереду). Якщо є різні виграшні числа, при яких треба виплатити однакову мінімальну суму, вивести найменше з них.

 Приклад
     Введення
     2  2  5  00  10  01  00  11  7  35
     Виведення
    42  10
 


Задача Billiard

    У Петрика і Василька вдома є великий стіл, поверхня якого має форму еліпса. Хлопці іноді граються, катаючи по його поверхні маленькі металеві кульки. Кульки завжди запускають з деяких «улюблених» точок на краю столу, намагаючись влучити у інші «улюблені» точки, теж розміщені на краю столу. Всього таких «улюблених» точок N (7≤N≤200 000), і кожна з них може бути стартом або фінішем.
   Одного разу до хлопців прийшли друзі (загальна кількість дітей виявилася рівною M, де 2≤M≤10 000, і  всі вирішили пограти в дану гру. Кожен вибрав для своєї кульки «трасу», кінці якої розміщені у двох (гарантовано різних) «улюблених» точках.
   Напишіть програму, яка з’ясує, чи вдалося гравцям обрати «траси» так, щоб вони не перетиналися (ні всередині столу, ні в «улюблених» точках). Програма повинна або повідомляти, що вибрані «траси» справді не мають перетинів, або знаходити будь-яку одну пару «трас», що перетинаються (всередині столу або мають спільний край).
 Технічні умови
     Програма Billiard читає з клавіатури спочатку два числа: N (7≤N≤200 000) і M (2≤M≤10 000) — кількість «улюблених» точок та кількість «трас»; далі M пар натуральних чисел — номери тих «улюблених» точок, які є кінцями відповідної «траси». Нумерація «улюблених» точок починається з 1 і відповідає порядку обходу навколо столу за годинниковою стрілкою. Гарантовано, що всі «улюблені» точки лежать на еліпсі–краю стола.
    Програма має вивести на екран два числа через пропуск. Якщо вибрані дітьми «траси» не перетинаються (і не мають спільних країв), це мають бути два числа –1. Інакше треба вивести два натуральні числа — номери будь-яких двох «трас», що перетинаються (або мають спільний край). Нумерація «трас» задається порядком опису цих «трас» у вхідних даних. Якщо можливі різні правильні відповіді, вивести будь-яку одну з них.

 Приклади

Введення
7  3  2  4  7  1  6  3
Виведення
1  3

Введення
100  2  1  17  42  64
Виведення
-1  -1

Задача Meet

   Лабіринт має форму квадрата  nxn,  який розбитий на одиничні клітинки. Деякі клітинки зайняті стінами. На двох різних вільних клітках знаходяться два роботи. Роботи одночасно виконують одну з команд: N - переміщення на одну клітку на північ, S - на південь, W - на захід і E - на схід. Якщо клітка, на яку робот повинен перейти, зайнята стіною або не існує, команда ігнорується, при цьому робот залишається на місці. За яку мінімальну кількість команд роботи зможуть зустрітися (опинитися на одній клітці)?
Технічні умови
Програма Meet читає з клавіатури розмір лабіринту n (2<=n<=50) і кількість зайнятих стінами кліток К,  далі пари чисел - координати цих кліток, далі ще дві пари чисел - координати роботів.
   Програма виводить на екран мінімальну кількість команд, необхідних для зустрічі. Якщо роботи не зможуть зустрітися, програма виводить -1.

 Приклад

     Введення
     8  6  2  4  3  3  4  6  5  7  7  4  6  3  5  3  2  7
     Виведення
     9

Задача Lucky2

  Назвемо натуральне число   S-щасливим, якщо добуток його цифр дорівнює S. Знайдіть k-е за величиною S-щасливе число.

 Технічні умови

  Програма Lucky2 читає з клавіатури через пропуск натуральні числа S (2<=S<=1000000) і k (1<=k<=10000). Програма виводить на екран шукане число. Якщо для заданого S жодного S-щасливого числа не існує, програма виводить -1.

 Приклад
     Введення
     60  5
     Виведення
     435


Завдання підготували  Г.Непомнящий,  Ю.Пасіхов,  І.Порубльов

 

  

© LIKT 1998-2024