Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

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

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

Приведем условную классификацию олимпиадных задач:

  • Арифметика - математические задачи, работа с большими числами (длинная арифметика), такие задачи, как правило, требуют знания формул, умение их применять, а код программ может быть небольшим
  • Геометрия - геометрические задачи, здесь может быть описана какая либо ситуация взаимодействия тел на плоскости и в пространстве
  • Динамическое программирование - задачи, направленные на выявление рекуррентных соотношений
  • Сортировка и последовательности - работа с данными, представленными в виде массива
  • Графы - задачи с графами (структурами данных, основаных на вершинах и ребрах)
  • Рекурсия - задачи на поиск с рекурсивным перебором вариантов

Конечно же задачи могут сочетать в себе сразу несколько направлений и часто бывает сложно конкретную задачу отнести к тому или иному разделу.

Любая олимпиадная задача подразумевает входные и выходные данные. Т.е. в формулировке задания обязательным образом описан формат входных и выходных данных, а Ваша программа должна считать эти данные, обработать и вывести результат в установленном формате. Чаще всего чтение происходит из некоторого файла INPUT.TXT, а вывод в некоторый файл OUTPUT.TXT . Т.е. для решения олимпиадных задач нужно уметь работать с файлами: читать, создавать и писать в них, а вот знания графических функций вряд ли Вам пригодятся. Стоит заметить, что многие системы, например http://acm.timus.ru, используют консольный режим ввода-вывода и работа с файлами в них не приветствуется. Данный сайт позволяет сдавать задачи как с использованием вышеупомянутых файлов, так и без них. Вариант ввода-вывода Вы выбираете сами. Помимо условия задачи, правил ввода и вывода информации на каждую задачу накладываются ограничения на время выполнения и используемую Вашей программой оперативную память.

Приведем пример формулировки олимпиадной задачи по программированию (Задача №1 в текущей системе из раздела Архив задач):

A+B

(Время: 1 сек. Память: 16 Мб Сложность: 2%)

Требуется сложить два целых числа А и В.

Входные данные

В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 109.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — сумму чисел А и В.

Пример

INPUT.TXTOUTPUT.TXT
12 35

Эта классическая простая задача используется для ознакомления участников с системой автоматической проверки и соответствует всем критериям правильной постановки олимпиадной задачи. При решении этой задачи необходимо из входного файла input.txt (либо с клавиатуры), расположенного в текущей папке (где и Ваша программа) считать 2 целых числа и вывести их сумму в выходной файл output.txt (либо на экран). Ограничения по памяти в 16Мб и времени 1 сек. весьма условны, так как такая простая задача потребует минимальную память и выполнится за минимальный промежуток времени (операция сложения выполнится мгновенно, современные ЭВМ способны выполнять 108 таких операций в секунду). Каждая задача имеет пример входных и выходных данных (часто даже несколько примеров), это позволяет участникам более однозначно понять содержание задачи. В данном примере в разделе "Пример" отражен пример входных данных "2 3" и выходных "5", это означает, что 2+3=5.

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

В мире предпочтение отдается языку С++, но в России по-прежнему классическим языком программирования остается Pascal, а именно, большинство олимпиадных задач в России решается на Delphi. Мы же рекомендуем осваивать язык С++, который со временем станет наиболее популярным и в нашей стране. Далее мы в основном будем использовать язык С++ для рассмотрения примеров решения задач. Здесь можно ознакомиться с различными средами разработки программ на С++ на примере решения задачи "А+В".

Теперь Вы можете ознакомившись с работой системы, сдать задачу "A+B" на этом сайте здесь.



Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483