Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 | 2 | 3 |

 

  Вопрос: Второе керченское состязание программистов Добавлено: 17.07.07 14:42  

Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 

Ответить

  Ответы Всего ответов: 34  

Номер ответа: 16
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #16
Добавлено: 24.07.07 20:40
Fever, включи мозг и сразу допрешь :) Решаются остальные не просто, они просто выглядят, в чем ты и убедишься, если попытаешься прислать решения :)

Ответить

Номер ответа: 17
Автор ответа:
 -АлександР-



Вопросов: 55
Ответов: 1008
 Web-сайт: sham.clan.su
 Профиль | | #17
Добавлено: 24.07.07 23:57
1 действительно интересное, но в контексте как-то не выглядит =)
2-7 на сообразительность, интересные, на логику и математику, респект

но первое как ни старался, даже не понял о чем речь

Ответить

Номер ответа: 18
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #18
Добавлено: 25.07.07 15:49
Первое на реверсинг протокола

Ответить

Номер ответа: 19
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #19
Добавлено: 25.07.07 17:18
Отвечая на вопросы, возникшие у участников
1. Это задача на реверсинг бинарного протокола. Если вы знаете архитектуру ЭВМ, вам не составит труда восстановить спецификацию этого протокола и написать его парсер.
2. В строке не может быть других заглавных букв, кроме как в начале предложения.
3. «из которых путем замены одной или двух букв на другую» следует читать как «из которых путем одной или двух замен одной из букв на другую».
4. Не происходит ошибки более чем на одну ноту + не происходит выход за пределы верной октавы. Т.е.
do можно заменить do re
re ~ do re mi
mi ~ re mi fa
...
la ~ sol la si
si ~ la si
5. На какой стадии происходит округление, понятно из условия задачи.

Как минимум задачи 2-5 доступны даже для самых слабых участников, начинающих программистов, только-только ознакомившихся с синтаксисом какого-нибудь языка программирования.

Ответить

Номер ответа: 20
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #20
Добавлено: 28.07.07 15:23
Кажеццо, самым крутым программистом митуя окажется shuffle :)

Ответить

Номер ответа: 21
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
 Профиль | | #21 Добавлено: 28.07.07 19:04
поясните про дамадж, ниче не понял.

Ответить

Номер ответа: 22
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
 Профиль | | #22 Добавлено: 28.07.07 22:48
короче по первому надо еще примеров, есть предположения, но они могут быть как верны, так и ошибочны.

По дамаджам - нифига не понятно!!!

Ответить

Номер ответа: 23
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #23
Добавлено: 30.07.07 18:54
В связи с тем, что не все желающие успели поучаствовать, соревнование продлевается еще на неделю, до полуночи между воскресеньем 5-го и понедельником 6-го августа.

Ответить

Номер ответа: 24
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #24
Добавлено: 31.07.07 13:19
Dark Brand : примеров к первой задаче достаточно, возможно, ты на неверном пути.
В 5-й примеров, включая тест из условия, иллюстрирующий округление, также вполне достаточно.

Ответить

Номер ответа: 25
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
 Профиль | | #25 Добавлено: 31.07.07 13:23
В первой аздаче - видимо намек на Microsoft, нужно отсюда плясать но я не знаю есть ли у них подобные форматы...

По поводу дамаджа - хоть убей не пойму что там. Уже 100 раз перечитывал условие.

Ответить

Номер ответа: 26
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #26
Добавлено: 01.08.07 11:31
Нет там никаких намеков на M$, и реальным протоколом это тоже не является.
Задачу по дамаджам сдали уже несколько человек, некоторые даже правильно, так что стукни в аську и попробуй объяснить, что именно тебе не понятно.

Ответить

Номер ответа: 27
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #27
Добавлено: 06.08.07 11:06
KCC2 завершен, итоги подведены и доступны на сайте.

Абсолютным победителем стал dromit. Увы, не повезло shuffle, его 7-я программа содержала досадный баг в вводе символов, если бы он его исправил, то занял бы первое место с солидным отрывом.

Следующее соревнование, KCC3, пройдет в форме открытого чемпионата, вероятно, этой зимой.

Краткий разбор задач приведен ниже:


Задача №1
Удивительно, но с этой задачей никто не справился. Решено было предложить ее нескольким крупным сообществам программистам с целью выяснить, решабельна ли она.

Задача №2
Самая простая задача, с которой справились все участники, кроме одного.

Задача №3
Несложная задача, но, к сожалению, все участники, кроме одного, не учли, что границей слова может являться любой символ, не относящийся к русскому алфавиту, а один участник (DillerXX) был максимально близок к верному решению но, к сожалению, забыл, что Ё — это тоже буква русского алфавита.

Задача №4
Простейшая задача, в которой нужно просто вычислить 2^n * 3^m, где n — число нот do и si, а m — число остальных нот. Единственная сложность, которая была упомянута в условии, это то, что такое число может получиться очень большим (вплоть до 7.2*10^23), больше и максимума типа int (32-битный) и даже long long (64-битный). Поэтому следовало использовать длинную арифметику. Двое участников реализовали ее сами, один использовал встроенный в Java класс BigInteger, а двое других, видимо, не слышали о длинной арифметике.

Задача №5
Как и было сказано в условии, написание компьютерных игр — задача совсем непростая. 4 из 5 участников не заметили, хотя это было указано в условии, что дамадж нужно округлять по правилам математического округления. Кроме того, хотя было очевидно, что удар должен наноситься по школе с минимальным резистом, один участник пришел к выводу, что дамадж должен равномерно распределяться между школами.

Задача №6 (C++)
Единственная задача, в которой требовалось некоторое знание математики. Очевидно, что минимальное и максимальное фокальное расстояние лежат на большой полуоси, так что a = (max + min) / 2. Малую полуось можно найти, используя основное свойство фокального расстояния в эллипсе, т.е. из уравнения 2*sqrt(((max-min)/2)^2 + b^2) = max+min; b = sqrt(max*min). Обратите внимание на красоту этих соотношений, большая полуось — среднее арифметическое минимального и максимального фокального расстояния, а малая — среднее геометрическое. Напомним, что a и b — коэффициенты в каноническом уравнении эллипса x^2/a^2 + y^2/b^2 = 1, а заодно модули абсциссы и ординаты пересечения эллипса с осями координат.

Т.к. эллипс симметричен, то его длина равна 4 длинам эллипса в одной четверти, а ее, в свою очередь, можно посчитать с помощью определенного интеграла int(sqrt(1+diff(f(x), x)^2), x=0..a), выразив y через x явно в виде f(x) = b*sqrt(1-x^2/a^2). Общеизвестно, что такой интеграл не выражается в элементарных функциях, но настолько часто встречается в науке и технике, что для него создана специальная функция (в Maple она обозначается EllipticE), так что длину дуги эллипса можно посчитать, используя такую Maple-программу:

w1:=0.00005; w2:=2;
a := (w1+w2)/2; b := sqrt(w1*w2);
evalf(4*a*EllipticE(sqrt(a^2-b^2)/a));
Таким образом, методов расчета искомой длины несколько: можно посчитать интеграл напрямую, к примеру, методом Симпсона; можно разложить эллиптический интеграл в ряд Тейлора и вычислять EllipticE явно; можно поискать другие методы явного вычисления EllipticE; можно найти хорошие приближенные формулы (например, второе приближение Рамануджана); можно попытаться подобрать ответ дихотомией. Самое главное, как оказалось, в этой программе — не забыть, что из файла вводится все-таки минимальное и максимальное фокальные расстояния, а не коэффициенты канонического уравнения.

Задача №7 (C++)
Возможности для оптимизации в этой программе очень сильно варьируются, но для написания успешного алгоритма обязательно нужно выполнять следующие операции: максимально оптимизировать операцию взятия отдельного символа, распознавать well-formed тесты (например, в первоначальном тест-сете присутствовала строка из 19-ти символов «я», и только решение DillerXX выдавало на нем наиболее короткий вариант без циклов «-...................», что давало ему непоборимое преимущество), хранить «метки», т.е. куски памяти, из которых можно быстро получить ряд других используемых букв и т.д., для лучшего понимания ознакомьтесь с решением DillerXX.

Тест для программистов
UML — язык графического описания для объектного моделирования в области разработки программного обеспечения, простой путь изобразить кружочками и стрелочками, как должна быть построена программа. Используется повсеместно, где нужно написать что-либо существенно сложнее Helloworld.
Профайлер — в общем случае программа, собирающая некоторые характеристики работы программы, как правило, их используют для поиска узких мест в производительности программы, к примеру, профайлер позволяет определить, какая функция или какой участок кода в программе работает дольше всего и даже определить при каких условиях.
Хотя и WTL и wxWidgets — набор библиотек для создания и работы с графическим интерфейсом пользователя, используя «родные» функции операционной системы для создания элементов управления и т.п., WTL имеет существенно более узкую область применения: только Windows и только C++. wxWidgets же поддерживает значительное количество языков (C++, конечно, в их числе) и значительное число платформ и графических API.
Для генерации выпуклой оболочки обычно используют алгоритм Грэхема.
Самодвойственная функция — такая булева функция, что инвертируя ее аргументы мы получим инвертированный результат. Таким образом, вектор ее значений длины 2^n полностью определяется первой его половиной. Поэтому число таких функций 2^(2^n/2). Класс самодвойственных функций является одним из 5 предполных классов Поста и играет важнейшую роль в дискретной математике, теоретическом фундаменте всех компьютеров.



Баллы, набранные участниками

Код                1   2   3   4   5   6   7                Первые 6 Всего
1. dromit           +   -   +   -   +   (69524,90) 3.0   3.8      6.8
2. DillerXX         +   -   +   -       (93683,64) 4.0   2.2      6.2
3. shuffle          +   -   +   +   -   (46711,46) 2.0   3.6      5.6
4. Malissa          +   -   -   -   -   (58779,34) 2.5   1.0      3.5
5. romantic         -   -   -   -   -    ;(2600,00) 0.1   0.0      0.1
Число верных    0   4   0   3   1   1  
Число отправок  0   5   5   5   5   4  
Баллы           2.0 1.0 1.8 1.2 1.4 1.6


Немного статистики

Всего было прислано 29 решений общим размером 52 572 байт (в прошлом году всего 11), из которых верными оказались 14 (в прошлом году 5). Из 29 решений 18 на C++, 6 на C#, 4 на Pascal и 1 на Java. Среди верных 14 решений уже 10 на C++, 2 на Pascal и по одному на Java и С#.


Желаем всем программистам побольше смекалки и смелости для решения своих программистских задач и удачи в поиске тех, кто готов за них хорошо заплатить! )

Ответить

Номер ответа: 28
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
 Профиль | | #28 Добавлено: 06.08.07 11:13
про дамадж все равно не понятно - решение в студию!

Ответить

Номер ответа: 29
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #29
Добавлено: 06.08.07 23:05
На сайте выложены решения всех участников, посмотри решение shuffle

Ответить

Номер ответа: 30
Автор ответа:
 HACKER


 

Разработчик Offline Client

Вопросов: 236
Ответов: 8362
 Профиль | | #30 Добавлено: 07.08.07 00:04
Я понял прикол керченских олимпиад :) Те задачи которые не требуют математики, их условие запутано так, чтобы без 0,5 её и не пытались разобрать. Остальные задачи, условия которых ясны - требуют хорошие знания математики. В прочем не удивлён, аналогично построены большенство олимпиад по программированию, за что я их и не люблю.

Ответить

Страница: 1 | 2 | 3 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам