Дистанционные семинары Оглавление Перед тем, как читать дальше, рекомендуем ознакомиться с разделом как пользоваться представленными материалами . В настоящий момент доступны материалы следующих занятий: Занятия 2004-05 учебного года Занятие 0 Введение: требования к решениям олимпиадных задач, работа с файлами
Занятие 1 Знакомство с олимпиадными задачами.
Занятие 2 Метод динамического программирования.
Занятие 3 Метод динамического программирования (продолжение).
Занятие 4 Графы - введение.
Занятие 5 Графы: поиск кратчайшего пути, обход в ширину.
Занятие 9 Графы. Каркас. Алгоритмы Прима и Краскала.
Занятия 2005-06 учебного года Занятие 10 Длинная арифметика.
Занятие 11 Длинный корень.
Занятие 12 Рекурсия - 1.
Занятие 13 Графы. Обход в глубину.
Занятие 14 Рекурсия - 2. Перебор.
Занятие 0. Введение: требования к решениям олимпиадных задач, работа с файлами. Если вам доводилось участвовать в олимпиадах по информатике и чтение входных данных из файла не вызывает у вас трудностей, то это занятие вы можете пропустить. Что такое олимпиадная информатика? Что нужно для успешного участия в олимпиадах по информатике? Как показывает практика, только лишь знания языка программирования для этого явно не достаточно. Вообще, оказывается, что олимпиадные задачи по информатике лежат где-то на стыке математики и программирования. И очень часто оказывается, что решая эти задачи школьники не только участся программировать, но и осваивают какие-то новые разделы математики (или старые, но с новой точки зрения :-) ). Для успешного участия в олимпиаде по программированию школьник должен не только владеть языком программирования, но и уметь придумывать и реализовывать алгоритмы решения задач, оценивать время их работы, тестировать и отлаживать свои программы. И целью подготовки к олимпиадам является, в конечном счете, не победа в той или иной олимпиаде, а формирование алгоритмического мышления, умения понимая, как решается задача, записать ее решение на языке программирования, способности тестирования и отладки программ. Как проверяются решения и что из этого следует Исторически сложилось так, что решения на олимпиадах по программированию проверяются автоматически. Ваша задача написать программу, которая по заданным входным данным вычисляет и выводит выходные данные. Когда вы сдаете решение на проверку, проверяющая программа "подсовывает" вашему решению тестовые наборы входных данных, запускает вашу программу и затем анализирует выданный им результат. При этом ответ именно анализируется, а не сравнивается с правильным - то есть если в задаче возможно несколько правильных ответов, то как правило (если в условии не указано иное) можно выводить любой из них. Поскольку программа проверяется автоматически, это накладывает на программу-решение некоторые ограничения. Она должна выводить ответ строго в описанном в условии формате (то есть, например, если программа вдруг выведет в ответ два числа в перепутанном порядке или вместо числа-ответа надумает написать слово "ответ" и потом уже сам ответ, проверяющим компьютером это будет воспринято как полностью неправильное решение - он не сможет, да и не будет пытаться искать, а в чем же вы ошиблись). Второе следствие из автоматической проверки - как правило, тесты по задаче составляются так, чтобы "покрыть" все возможные случаи. В том числе и максимальные. То есть если, например, в условии написано, что "во входном файле записано N чисел и N не превышает 1000", то тест на N=1000 (или очень близкое к нему число) почти наверняка будет. Так что если по условию что-топлохое возможно, оно будет. Еще одна традиция олимпиадных задач, корректность входных данных. То есть, если это особо не написано в условии, не требуется проверять корректность входных данных - входные данные будут полностью соответствовать описанному в условии формату и удовлетворять всем указанным ограничениям. Ваше решение должно читать входные данные из входного файла (его имя обычно указано в условии задачи) в описанном формате, решать задачу, и выводить результат в выходной файл (его имя тоже обычно указывается в условии). Программа должна всегда завершаться с кодом 0 (иначе тестирующая программа считает, что в ходе работы произошла ошибке) - то есть командой halt(0); или просто дохождением до конца на паскале, или return 0; - на C. Рекомендуем также на эту тему почитать здесь. Работа с файлами Считывать информацию из текстового файла также просто, как с клавиатуры. То же касается и вывода в файл. Возникают лишь небольшие отличия. Для работы с файлами мы должны завести переменные специального типа "файл". Далее, перед тем, как работать с этой переменной, нужно "связать" ее с конкретным файлом, и открыть этот файл. После того, как вся необходимая информация из файла считана (записана), файл нужно не забыть закрыть. Более подробно рассмотрим просто примеры программ на разных языках для решения такой задачи: из файла x.in вводятся два числа, и их сумму нужно вывести в файл x.out. BASIC C PASCAL
open "x.in" for input as #1 open "x.out" for output as #2 input #1,a,b print #2,a+b close #1 close #2 #include <stdio.h> int main(void) { long a, b; FILE *fin, *fout; fin = fopen("x.in", "r"); fout = fopen("x.out", "w"); fscanf(fin, "%ld%ld", &a, &b); fprintf(fout, "%ld", a + b); fclose(fin); fclose(fout); return 0; } var a,b:longint; var fi,fo:text; begin assign(fi,'x.in'); reset(fi); assign(fo,'x.out'); rewrite(fo); read(fi,a,b); writeln(fo,a+b); close(fi); close(fo); end.
Для программирующих на паскале. Если во входном файле записаны только числа, то для чтения лучше всего пользоваться командой read - она сама пропускает пробелы и переходы на новую строку. Таким образом, вам не важно, как идут эти числа - в одну строку, с переводами строки и т.д. Если же в файле записана текстовая информация - то (при чтении строк) команда read читает информацию из текущей строки (столько символов, сколько входит в строковую переменную), когда достигнут конец строки - возвращается пустая строка. А команда readln читает информацию из текущей строки и переходит на следующую (независимо от того, достигнут конец строки или нет). Несколько советов участникам олимпиад Прежде всего хотим отметить, что для участия в олимпиаде вы должны уметь работать с текстовыми файлами (считывать и записывать информацию): это не сложно - скорее всего, вы с легкостью разберетесь, как это делается, посмотрев приведенный ниже пример. Однако лучше всего попробовать работать с файлами до того, как вы придете на олимпиаду. Если вы участвуете в олимпиаде впервые, советуем вам также заранее посмотреть примеры предлагаемых на олимпиадах задач, например, в архивах олимпиад, представленных на нашем сайте. На олимпиадах, если иное не указано в условии задачи, все входные данные считаются корректными, то есть файлы, которые подаются на вход вашей программе при проверке строго соответствуют описанным в условии форматам, а все значения - указанным ограничениям. Вы не должны в своей программе проверять корректность входных данных. С другой стороны, выходные данные (результат работы вашей программы) вы должны выводить в формате, описанном в условии задачи, не добавляя никаких посторонних комментариев. Все решения проверяются автоматически, и если выходной файл содержит постороннюю информацию или если его формат не соответствует описанному в условии, он будет признан неправильным. Ваша программа не должна ничего выводить на экран (если это особо не оговорено в условии задачи), а также ждать какого-либа ввода пользователя. Распространенной ошибкой является ситуация, когда после окончания работы программа ждет нажатия какой-либо клавиши. При автоматической проверке никто эту клавишу нажимать не будет, и программа будет считаться превысившей предел времени (то есть зависшей или неэффективной). Что делать, если ваше решение проходит не все тесты Давайте для начала рассмотри
