litceymos.ru 1

ЗАВДАННЯ РАЙОННОЇ ОЛІМПІАДИ З ОСНОВ ІНФОРМАТИКИ (ПРОГРАМУВАННЯ)

2009-2010 Н.Р.


Задача 1. Продаж паліндромів (77 балів)

Економічна криза боляче вдарила по українському селу. При цьому, підкосила вона не стільки стан сільського господарства, як моральний дух селян. Беззахисні сільські жителі злякалися, що можуть залишитися без товарів першої необхідності. Таких, наприклад, як числа-паліндроми... Так, так, ви правильно прочитали - паліндроми (Нагадаємо, що числами-паліндромами називають числа, які однаково читаються як зліва направо, так і справа наліво. Наприклад, 21512 є паліндромом, а 1210 - ні).

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

Сільські математики заспокоюють громаду, що паліндромів вистачить на всіх, адже вони завбачливо приготували для селян всі паліндроми, не більші за N. Але щоб до кінця розвіяти переживання сільської громади, потрібно сказати точно, скільки ж паліндромів приготували вчені.

Вхідні дані:

Єдине ціле число N.


Вихідні дані
:

Єдине число - кількість чисел-паліндромів не більших за N.


Обмеження:


1  N  1000000000000000000 (1018)

Приклад вводу 1:

11

Приклад виводу 1:

10

Підказка 1
:

Всі числа від 1
до 11 крім числа 10 є паліндромами.

Приклад вводу 2:

104

Приклад виводу 2:

19

Підказка 2:

До попередніх чисел додалися ще 22, 33, 44, 55, 66, 77, 88, 99 та 101.

Задача 2. Китайський календар (47 балів)


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

Китайський календар ділиться на цикли тривалістю по 12 років. Кожен із років має свій «зодіак» (тваринку). От наприклад, 2009 рік має Корову (ох), 2010 - Тигра (tiger). Отже, послідовність тваринок така: rat (пацюк), ох (корова), tiger (тигр), rabbit (кролик), dragon (дракон), snake (змія), horse (кінь), sheep (овечка), monkey (мавпа) , rooster (півень) , dog (собака), ріg (свиня). Цей календар циклічний, відповідно після ріg (свині) іде rat (пацюк), далі ох (корова) і т.д.

Це все б було добре, але у них є ще один цикл довжиною по 10 років. Цикл кольорів: teal (синьо-зелений), teal (синьо-зелекий), red (червоний), red (червоний), yellow (жовтий), yellow (жовтий) , white (білий), white (білий), black (чорний), black (чорний). Тобто кожен колір по два рази. Наприклад: 2009 - yellow (жовтий), 2010 - white (білий).

Ваше завдання: для заданого року N вивести рік за китайським календарем.

Вхідні дані:

Єдине число N – рік, для якого потрібно визначити, яка йому відповідає тварина і колір.

Вихідні дані:

Потрібно вивести два слова через пробіл, перше слово - колір, друге - тваринка, які відповідають заданому року.

Обмеження:

2009  N  1000000000 (109) .

Приклад вводу 1:

2009

Приклад виводу 1:

yellow ох


Приклад вводу 2:

2010

Приклад виводу 2:


white tiger



Задача 3. Економічна криза в рік бика (74 бали)

Після того як економічна криза накрила українське село, там почалися різноманітні заворушення та інші жахливі речі. Люди просто сходять з розуму від страху перед глобальною кризою. От для прикладу. Дядько Василь заперся у себе в підвалі вже як декілька днів і виходити звідти зовсім не збирається.

У селі є своя череда биків та корів. Відомо, що у ній зараз налічується N биків та М корів. Сільська громада вирішила у зв'язку з кризою трошки прорідити цю череду. Але ж якось не пасує у рік бика різати багато биків чи корів. Згідно древньої сільської мудрості співвідношення биків до корів у череді має бути А:В.

Було вирішено зробити наступним чином. Якщо биків у череді є більше ніж мало б бути згідно відношення А:В - то ріжуть одного бика. Якщо ж корів є більше ніж мало б бути згідно цього відношення — то ріжуть одну корову. Цей процес продовжують, поки не буде встановлено бажане відношення, або поки не виріжуть всю череду. От така у нас сільська логіка. Вам необхідно визначити, скільки ж залишиться биків та корів після нещадного вирізання.

Вхідні дані:

Чотири цілих числа через пробіл - N, М, А, В.

Вихідні дані:

Два цілих числа через пробіл - кількість биків та кількість корів, що залишаться, відповідно.

Обмеження:

1  N, М, А, В  1000000000 (109) .

Приклад вводу 1:

4 6 6 8

Приклад виводу 1:

3 4

Підказка 1:

Спочатку корів є більше ніж потрібно, тому ріжуть одну корову і залишається 4 бики та 5 корів. Потім виявляється, що кількість биків є завеликою і один з них покидає череду. Після цього ріжуть ще одну корову і аж тоді досягається відношення 6 до 8.

Приклад вводу 2:

4 1 2 3

Приклад виводу 2:

0 0

Підказка 2:

На жаль, відношення 2 до 3 так і не вдасться досягнути.