Форум программистов, компьютерный форум, киберфорум
ZaMaZaN4iK
Войти
Регистрация
Восстановить пароль
Этот блог посвящён олимпиадному программированию.Если вы хотите узнать, что это такое и с чем его едят - милости просим.Если вы хотите чему-то научиться, что-то дополнить - добро пожаловать!

В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
Рейтинг: 5.00. Голосов: 1.

Общие сведения об олимпиадных задачах

Запись от ZaMaZaN4iK размещена 26.05.2013 в 16:47
Обновил(-а) ZaMaZaN4iK 26.05.2013 в 19:16

Итак, я хотел бы рассказать Вам о некоторых особенностях спортивного программирования.
Я буду рассказывать про личные олимпиады, а потом, может быть, расскажу и про командные.

Вообще, спортивное программирование - это решение задач.Да-да, это просто решение задач.Но задачи нужно решить эффективным методом, чтобы они прошли тесты... Но обо всём по порядку.

Обычное задание для олимпиады по программированию оформялется так:
Файл ввода\вывода: input.txt\output.txt
Ограничения:
256 мб оперативной памяти
3 сек

/*Условие задачи*/


Обьясним всё по порядку:
1.Файл ввода\вывода.Вы должны вводить исходные данные для задачи из файла и выодить результат в определенный файл.Обычно это файлы с именами input.txt\output.txt, но бывают и другие имена.
2.256 мб.Вместо этого числа могут быть и другие числа.Это значит, что Ваша программа должна использовать не более какого-то лимита оперативной памяти.Если использовали больше - ваша программа будет считаться как неправильно работающая.Нужно быть всегда очень внимательным при использовании памяти, иногда её не хватает и приходится идти на всякие ухищрения.
3.3 сек.Это число значит, что Ваша программа должна работать при тестировании не более n секунд.Если работает больше - ваше решение не засчитывается.Наиболее частая ошибка у программистов.В основном это проблема решается правильным выбором алгоритма.


Также в каждой задаче есть определенные ограничения на входные данные.Например:

Сравните 2 числа.Если A>B, выедите "Да", иначе "Нет".1<=A,B<=1000


Это значит, что числа А и B находятся в [1,1000].обратите внимание, тут не сказано, что это натуральные числа, они могут быть и дробные.


Так, с этим разобрались.Теперь узнаем, как же тестируются наши программы.
Есть жюри.Непредвзятое.Взяток они берут(проверено).И есть у них набор тестов.тесты - это входные и выходные данные.То есть, это данные, при которых эталонная программа при некоторых входных данных(эталонная программа - программа правильного решения нашей задачи, её обычно пишет автор задачи), даёт некоторые выходные данные.И наша программа запускается на этих тестах, и за каждый пройденый тест нам дается некоторое кол-во баллов.И потом баллы суммируются, и получается наш результат за задачу.Способы начисления баллов могут немного варьироваться.Также могут чуть-чуть по другому тестировать(группами тестов), но это погоды не делает.

И мы обязаны написать программу, которая на всех входных данных даст правильный ответ.Но бывают же у нас и ошибки, верно?=)

И вот тут есть список статусов, которые встречаются при решении задач:
Accepted!
Compilation Error
Wrong Answer
Presentation Error
Runtime Error
Time Limit
Memory Limit

Пройдемся по-порядку.
1.Accepted!(Принято) - Ура, ура, ура - решение прошло все тесты, и мы получили все баллы.Мы молодцы, ну или просто тесты плохие=). Я где-то видел, что Accepted - это ошибка жюри=)
2.Compilation Error - наше решение не скомпилировалось.Обычно это из-за опечаток.Но ещё частая причина - это разные компиляторы.То есть вы пишите программу и компилируете её в одном компиляторе, а её тестируют в другом.Как же такое может произойти?А всё просто - обычно(!) сдается файл-исходник, а не exe-шник.Вот такое и получается.Будьте всегда внимательны к используемым компиляторам.
3.Wrong Answer - очень частая ошибка - неправильный ответ.Ваш ответ не сошелся с ответом эталонной программы, или вы неправильно вывели(может пробел где-то лишний).Способ решения - искать ошибку в алгоритме и выводе.
4.Presentation Error - похожа на предыдующую.Вы вывели данные в неправильном формате.Просмотрите ещё раз вывод данных.
5.Runtime Error - ошибка во время исполнения.обычно связано с делением на 0 и выходом за границы массива.Будьте начеку!
6.Time Limit - ваше решение работает слишком долго.Решение - может она у вас где-то зацикливается.Ну или просто алгоритм слишком плохой.Решение - сменить способ решения или использовать более быстрые аналоги функций.
7.Memory Limit - превышен лимит по памяти.Используйте меньше памяти.

Есть ещё и другие варианты, но это самые основные.


Обычно используемые языки на олимпиадах - Pascal и С++.Используют и другие, например, Java, но меньше. Я настоятельно рекомендую всем переходить на С++, так как там очень мощная библиотека.Да и вообще, не стоит сравнивать 2 этих языка))

Также на олимпиадах могут запрещать пользоваться некоторыми библиотеками.Внимательно изучайте регламент.


Вот это всё - наиболее общие сведения, но этого для начала вролне хватит. Надеюсь, Вам было интересно=)
Размещено в Без категории
Просмотров 1666 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.