Главная

KCC 2 :: задачи

KCC 2 :: решения

KCC 2 :: результаты

KCC 1

KCC 1 :: задачи

KCC 1 :: решения

KCC 1 :: результаты

Логика — главное оружие программиста. Она позволяет решать сложнейшие задачи, ориентироваться в незнакомых областях и познавать необходимые технологии.

Что такое Kerch Coding Contest?

KCC — Керченское Состязание Программистов. Приглашаем всех желающих принять в нем участие. Если Вы знакомы с современными языками программирования, имеете голову на плечах и мозги в ней, регистрируйтесь и решайте задачи! Участвовать могут абсолютно все, независимо от возраста, профессии и вероисповедания, участие бесплатное.

Первое соревнование начнется 23 июля 2007 и будет длиться неделю. За это время все желающие смогут ознакомиться с заданиями и выполнить их. Поскольку программирование очень многогранно, задания будут касаться самых разных его областей. Планируется 7 задач по числу дней на разную тематику, но заставляющие думать и проверяющие, насколько программист умеет решать нестандартные задачи, требующие мышления и смекалки. В условии задачи будут приведены имена файлов, входного и выходного, и их форматы. Ваша задача — написать код на любом доступном языке так, чтобы он по указанным правилам генерил из входного файла верный выходной.

Задача считается решенной, только если она проходит все тесты.

Призовой фонд

Начальный призовой фонд - 20$ (101 гривна).

Как получена эта цифра? Опытному программисту вполне достаточно для решения всех семи задач 3-4 часов. В Киеве медиана зарплат по PHP 700$ (2 задачи), по C++ 1000$ (5 задач), т.о. средний киевский программист с квалификацией, усредненной по задачам, получает ~900$ в месяц. В месяце 168 рабочих часов. Четыре из них будут стоить ~21.4 доллара. Таким образом, призовой фонд этого соревнования составляет сумму, которую получает профессиональный программист в Киеве за работу по выполнению этих задач. Призовой фонд распределяется в отношении 60:40 между первым и вторым победителем. Данные по медиане зарплаты взяты с http://www.developers.org.ua/salary-db/data/salary-by-year/2007. Выплата призов осуществляется через WebMoney, Яндекс.Деньги, или при личной встрече.

Призы вручаются только если призер набрал больше 0 баллов :) Приз за первое место вручается только если решения отправили более 10 участников, а за второе — если более 20.

Опыт Первого KCC...

...многому научил. К примеру, предлагавшиеся задачи, сделанные по мотивам собеседований в программистских фирмах, не могли однозначно определить сильнейшего. Иногда даже опытные программисты ставились задачами в тупик, не потому, что им не хватало умения решать задачи, а потому, что они не сталкивались в своей работе с какими-то тонкостями языков. Второй KCC этого недостатка лишен:

  • Выбирайте любой из популярных языков, предложенных организаторами для выполнения любой задачи.
  • Задачи не требуют уметь ни работать с БД, ни использовать AJAX, ни перехватывать на уровне ядра IRP. Для решения этих задач нужно уметь думать.
  • Больше не нужно дописывать чужой код — вся программа будет написана полностью Вами.

О задачах

Схема 7 задач, охватывающей, хотя бы приблизительно, большинство сфер программистской деятельности, была признана очень удачной и в общих чертах была сохранена и здесь.

  • Низкоуровневое. В век экспертных систем и великолепных игр кто-то должен писать ПО, на котором все это будет работать — системное ПО. Стихия этих программистов — биты и байты, потоки и пакеты, семафоры и мутексы. Для того, чтобы зорко стоять на страже спокойствия usermode, бойцы невидимого ПО должны великолепно знать, где и какой бит лежит, филигранно писать код, чтобы не допустить BSOD. Эта категория потребует от Вас умения не только рисовать формы в Delphi, но и понимать, как работает наш железный друг. Расслабтесь: драйвера и руткиты писать не придется. Есть способы определить, кто Вы, бог или пользователь компьютера, и проще. Одна задача будет предложена в этой категории.
  • Веб. Глобальная Паутина все туже и туже затягивает весь мир. Кто же ее строит? Люди, чьим трудом обычный текст, размеченный специальным образом, и обычно хранящийся в БД, превращается в целый мир, полный общения и необозримых возможностей. Умение чувствовать слова и воспринимать их не только как текст, но и как сумму технологий, используемых для его хранения, передачи и отображения — вот что понадобится Вам, чтобы успешно решить две задачи этой категории.
  • Прикладное. Компьютер был бы пустой жестянкой, если бы прикладные программисты не написали для него Miranda и Firefox, Heroes of Might and Magic и Maple, Semagic и Total Commander. Что должен уметь прикладной программист, в первую очередь? Пользоваться гуглом :). И своей головой. И все остальное. Три задачи в этой категории.
  • Исследовательское. Представьте себе, если бы Windows 1.0 был последней операционной системой, выпущенной Microsoft. Google так и остался бы маленьким студенческим проектом. WinAMP бы не вышел из пре-альфы, а Линус Торвальдс, выложив свое детище на всеобщее обозрение, забыл бы про него. Мало только написать программу — ее нужно развивать! А для этого надо обладать особым талантом — талантом исследователя. Для единственной задачи из этой категории абсолютно точное решение не известно, вполне возможно, что его не существует вообще. Но именно такие задачи ставит непредсказуемая жизнь, и долг настоящего Программиста — ответить на него!

Доступные языки

Были выбраны, учитывая их популярность и востребованность. Для каждого был подобран хороший компилятор, доступный бесплатно в той или иной версии.

  • Язык ассемблера. Дань уважения. MASM32 9.0.
  • C++. Необозримая мощь. Visual C++ 2005.
  • Java. Любимое кофе прикладников. JDK 1.5.0.08.
  • C#. Ультрасовременное детище Microsoft. Visual C# 2005.
  • PHP. Язык, которым говорит Web. PHP 5.2.0.
  • Perl. Язык скобочек и черточек. ActivePerl 5.8.8.
  • Python. Напиши это за две минуты. ActivePython 2.4.1.
  • Pascal. Вестник из глубины веков. Free Pascal 1.0.4.
  • Basic. Для любящих простоту. Free Basic 0.16b.

Проверка решений осуществляется на следующей платформе: Celeron-1700, 768MB DDR400, Windows XP SP2. Ограничение на время работы на каждом тесте — 2 секунды, по памяти — 128 MiB.

Оценивание задач

Шесть задач - зачетные, т.е. плюс или минус (решение прошло все тесты или нет). Одна — оптимизационная.

Способ передачи данных в программу и вывода результата - файлы input.txt, output.txt

Баллы за зачетную задачу могут быть равны 1, 1.2, 1.4, 1.6, 1.8, 2.0 в зависимости от того, сколько человек ее правильно решили. Сначала сортировка идет по числу верных решений, затем по числу отсылок всего (обратная). Т.о., чем меньше задачу решило людей и чем меньше прислано решений, тем больше за задачу баллов. При обоих одинаковых параметрах сортировка идет по номеру задачи.

Пример

Всего решенийИз них верныхПроцент верныхМестоБаллы
14125%31.4
2000%62.0
39333%11.0
42150%41.6
52150%51.8
64250%21.2

За решение по оптимизационной задаче дается от 0 до 4 баллов, в зависимости от того, какой рейтинг получил участник по отношению к лидеру (если рейтинг лидера ненулевой), округленные до десятых.

Пример

РейтингБаллы
1. Вася43004.0
2. Петя38003.5
3. Коля15001.4
4. Лена9000.8
5. Миша00.0
6. Степа00.0

Результаты оглашаются после окончания соревнования.

Вопросы для самопроверки

Считаете себя эрудированным и разносторонним программистом? Попробуйте ответить на эти вопросы.

  1. Что такое UML?
  2. Для чего используются профайлеры?
  3. Чем WTL отличается от wxWidgets?
  4. Какой алгоритм используется для генерации выпуклой оболочки N точек?
  5. Чему равно число самодвойственных функций над xn?
© Izolda, 2007