Київський Національний університет імені Тараса Шевченка
Збірник олімпіадних задач
(умови, вказівки та розв’язки)
Київ – 2004
ЗМІСТ
0. Вступ. Чемпіонат світу з програмування під егідою ACM
1. Рекурсія та ітерація
2. Найбільший спільний дільник. Найменше спільне кратне
3. Числа Фібоначчі та пов’язані з ними задачі
4. Числа Каталана
5. Генерація комбінаторних об’єктів
6. Підрахування комбінаторних об’єктів
7. Обчислювальна геометрія. Точка. Пряма. Відрізок. Кут
8. Жадібні алгоритми
9. Прості числа
10. Групи та задачі на розфарбування
11. Послідовності та підпослідовності
ЧЕМПІОНАТ СВІТУ З ПРОГРАМУВАННЯ ПІД ЕГІДОЮ ACM
Щорічно на Україні та у світі проводиться велика кількість олімпіад з інформатики та програмування різного рівня. Найсерйознішим та найпрестижнішим змаганням є Першість Чемпіонату Світу з програмування серед студентів вищих навчальних закладів, який щорічно проводить асоціація комп’ютерної техніки (Association for Computer Machinery) АСМ, зі штаб-квартирою у Нью-Йорку (http://www.acm.org). Офіційна сторінка змагань: http://acm.baylor.edu. Студентські змагання стимулюють наукову діяльність Вузу, допомагають обдарованій молоді реалізувати свої можливості, мають велике значення при визначені рівня розвиненості комп’ютерних наук у вузі.
Першість світу проводиться в три етапи: національні олімпіади, регіональні олімпіади, які проводять за географічним принципом у 30 регіонах (http://icpc.baylor.edu/past) та фінал першості світу, в якому беруть участь близько 60-команд – переможців та призерів регіональних олімпіад (http://icpc.baylor.edu/icpc/finals/default.htm) .
Популярність цих змагань, які визначають престиж країни у галузі інформаційних технологій, дуже велика. Достатньо сказати, що у 2003/2004 навчальному роках тільки у регіональних олімпіадах першості світу взяли участь 3850 команд з 1329 університетів з 68 країн світу. Загальна ж кількість учасників першості світу, враховуючи команд-учасників національних першостей, приблизно оцінюється у 24 – 25 тисяч!
Європейські країни розпочали участь у цих змаганнях з 1991 року, а Східно – Європейські – з 1995 р. З тих пір американським командам рідко щастило стати чемпіоном світу. Зате частіше за інших перемогу святкували команди зі східної Європи: 1998 – Чехія, 2000, 2001, 2004 – Росія, 2003 – Польща. Нажаль, серед цих країн поки не з’явилася Україна, і причини цього є чисто організаційними та фінансовими.
Українські команди беруть участь у першості світу з програмування з 1995 року. З 1997 по 2000 рік у Південно – Східно – Європейській олімпіаді постійно брали участь команди лише трьох українських університетів: Київського національного університету (КНУ), Вінницького державного технічного університету (ВДТУ) та Одеського національного університету ім. І.Мечнікова (ОНУ), але кращими досягненнями команд були місця у першій призовій шістці.
З 2001 р. проведення цієї олімпіади було організовано у три етапи: внутрішні університетські олімпіади, регіональні олімпіади за географічною ознакою (Південний, Північний, Західний, Східний), фінал у Вінницькому Державному Технічному Університеті, в якому беруть участь команди – переможці регіональних олімпіад. Три призери фіналу Всеукраїнської олімпіади отримують фінансування від Міністерства освіти і науки для участі у півфіналі першості світу в Бухаресті. Право участі в олімпіаді за власні кошти отримують також інші команди, що отримали кращі результати у Вінниці.
Вже перші організаційні кроки одразу принесли помітні результати. У 2001 і 2002 роках в олімпіаді в Бухаресті взяли участь вже 8 українських команд. При цьому у 2001 р. українські команди мали кращий неофіційний показник – середню кількість задач, розв’язаних однією командою А вже у 2002 році українські команди посіли 1, 2, 6 і 10 місця серед 44 учасників. Тим самим, вперше в історії, обидва місця в фіналі, виділені Бухарестському півфіналу, посіли команди українських університетів – КНУ і НТУУ „КПІ”. При цьому, в фіналі першості світу команда КНУ посіла 9 місце і отримала бронзові медалі. Команда НТУУ „КПІ” посіла місця з 30 по 42, разом з командами таких відомих університетів як, Гарвардський університет, університет Корнеля, університет Торонто, університет Міннесоти, державні університети Санкт-Петербурга та Нижнього Новгорода (http://icpc.baylor.edu/icpc/Finals/2003medals-web.htm).
З 14 по 17 жовтня 2004 року у Бухаресті відбулися чергові півфінальні змагання з програмування під егідою ACM у південно-східному регіоні (http://www.acm.ro/index.php/ACM2004/ContestResults). Україну представляли 11 команд. У залікову десятку серед українських команд попали:
Київський національний університет імені Тараса Шевченка – 3 місце (керівник – Віталій Бондаренко);
Київський Політехнічний інститут, фізтех – 8 місце (керівник – Ірина Жданова);
Харківський національний університет радіоелектроніки – 9 місце (керівник – Олександр Вечур);
Перемогу у змаганні святкували команди Бухареста та Софії.
Слід відмітити, що за право бути спонсором першості світу йде справжня боротьба між провідними комп’ютерними фірмами світу. АСМ навіть встановила обмеження терміну спонсування – три роки. Останніми роками спонсорами першості світу були AT&T, Microsoft, IBM. Саме ІВМ виборола собі привілею бути спонсором два терміни поспіль і не хоче віддавати цього права і надалі. За даними преси на організацію останньої першості світу ІВМ витратила більше 40 млн. доларів США. ІВМ пропонує спеціальні анкети і вручає свої рекламні матеріали кожному учаснику першості світу, починаючі з півфіналу. Учасники фіналу, особливо ж переможці, отримують персональні запрошення на роботу у відділення фірми у різних країнах.
Рівень українських студентів дозволяє їм стабільно бути серед кращих команд світу. Але для цього треба працювати всім загалом – і студентам, і викладачам, і науковцям і бізнесменам. І прикладом такої роботи є Росія, яка за п’ять років так організувала підготовку студентів, що три роки чемпіонами світу ставала команда Санкт-Петербурзьського університету точної механіки і оптики (2000, 2001, 2004). А у 2000 році, єдиний раз в історії два перших місця посіли дві команди з одного міста – Санкт–Петербурга. Наприклад, у 2003 року у фіналі другими буди студенти Московського державного університету, третіми - Санкт-Петербурзьського університету точної механіки і оптики, сьомими – Саратовського державного університету. У 2004 році результати Росії ще покращилися. Перемогу святкували знову студенти Санкт-Петербургу, а університети Пермі та Іжевську отримали відповідно золоті та срібні нагороди, довівши тим що рівень викладання комп’ютерних дисциплін в їх університетах не гірший за Масачусетс (срібло) та Гарвард (бронза).
Основними розділами комп’ютерних дисциплін, знаннями яких повинен володіти студент для вдалого виступу на світовій арені, є суто математичні дисципліни (математичний аналіз, алгебра), а також дискретна математика, методи оптимізації, обчислювальна геометрія, теорія чисел, побудова та аналіз алгоритмів. Окрім теоретичних та практичних занять необхідно тренуватися, приймаючи участь у дистанційних олімпіадах. У світі є багато WEB сторінок, які допомагають молоді у тренувальному процесі:
http://acm.timus.ru - Уральський університет (Росія);
http://acm.sgu.ru - Саратовський університет (Росія);
http://acm.zju.edu.cn - університет ЖеЙанг (Китай);
http://neerc.ifmo.ru - університет Санкт-Петербургу (Росія);
http://acm.uva.es - університет Вальядолід (Іспанія);
На наведених сторінках зібрана велика кількість задач, які пропонувалися на попередніх змаганнях. Працює система Online judge. На цих же сторінках часто проводяться дистанційні змагання у реальному часі, участь в яких дає можливість молоді оцінити свої знання та можливості. Наприклад, сторінка http://www.topcoder.com пропонує студентській молоді не тільки грошові призи за перемогу у змаганнях, а й забезпечує їх роботою.
РЕКУРСІЯ ТА ІТЕРАЦІЯ
Рекурсією називається такий спосіб організації обробки даних, при якому програма викликає сама себе або безпосередньо, або із інших програм.
Ітерацією називається такий спосіб організації обробки даних, при якому деякі дії багатократно повторюються, не приводячи при цьому до рекурсивних викликів програм.
Теорема. Довільний алгоритм, реалізований у рекурсивній формі, може бути переписаний в ітераційній формі та навпаки.
ЗАДАЧІ