ВВЕДЕНИЕ В ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ   
Этот раздел предназначен для пользователей, начинающих осваивать программирование и служит ознакомительным аспектом с областью олимпиадного программирования. Если Вы пока не знаете что из себя представляют олимпиадные задачи, как они представлены и какие критерии оценки для проверки решения существуют, то этот раздел именно для Вас.

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

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

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

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

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

A+B
(Время: 1 сек. Память: 16 Мб Сложность: 2%)
Требуется сложить два целых числа А и В.

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

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

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

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

Пример

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

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

Turbo Pascal 7.1
Borland C++ 3.1
Borland Delphi 7.0
Microsoft Visual C/C++ 7.1
MinGW Developer Studio 2.05
Borland C++ Builder 5.0
Java 2 SDK 1.5
В мире предпочтение отдается языку С++, но в России по-прежнему классическим языком программирования остается Pascal, а именно, большинство олимпиадных задач в России решается на Delphi. Мы же рекомендуем осваивать язык С++, который со временем станет наиболее популярным и в нашей стране. Далее мы в основном будем использовать язык С++ для рассмотрения примеров решения задач.

Приведем пример решения рассмотренной выше задачи о сложении двух чисел на языках С и Pascal:

//Реализация задачи №1 "A+B" на C

Код:
#include < stdio.h >

long a,b;

int main(){
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%ld%ld",&a,&b);
  printf("%ld",a+b);
  return 0;
}

{Реализация задачи №1 "A+B" на Pascal}

Код:
var a, b : longint;

begin
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  read(a, b);
  write(a + b);
end.

//Реализация задачи №1 "A+B" на Java

Код:
import java.util.*;
import java.io.*;

public class Main{ //имя класса должно быть Main
  public static void main(String[] argv) throws IOException{
    new Main().run();
  }
  PrintWriter pw;
  Scanner sc;
  public void run() throws IOException{
    sc = new Scanner(new File("input.txt"));
    int a=sc.nextInt(), b=sc.nextInt();
    pw = new PrintWriter(new File("output.txt"));
    pw.print(a+b);
    pw.close();
  }
}

'Реализация задачи №1 "А+В" на Basic

Код:
open "input.txt" for input as #1
open "output.txt" for output as #2
input #1,a#,b#
print #2,a#+b#
close #1
close #2

Отредактировано Санчоус (2011-10-22 17:37:43)