Этот блог посвящён олимпиадному программированию.Если вы хотите узнать, что это такое и с чем его едят - милости просим.Если вы хотите чему-то научиться, что-то дополнить - добро пожаловать!
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
Общие сведения об олимпиадных задачах
Запись от ZaMaZaN4iK размещена 26.05.2013 в 16:47
Показов 7993
Комментарии 0
|
Итак, я хотел бы рассказать Вам о некоторых особенностях спортивного программирования. Я буду рассказывать про личные олимпиады, а потом, может быть, расскажу и про командные. Вообще, спортивное программирование - это решение задач.Да-да, это просто решение задач.Но задачи нужно решить эффективным методом, чтобы они прошли тесты... Но обо всём по порядку. Обычное задание для олимпиады по программированию оформялется так: Файл ввода\вывода: 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 этих языка)) Также на олимпиадах могут запрещать пользоваться некоторыми библиотеками.Внимательно изучайте регламент. Вот это всё - наиболее общие сведения, но этого для начала вролне хватит. Надеюсь, Вам было интересно=) |
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 0
Комментарии
