Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Основные напоминания для участника
Система оценки решений
Продолжительность каждого тура заключительного этапа олимпиады - 4,5 часа.
Во время туров участникам разрешается пользоваться любыми печатными материалами - литературой, личными записями, распечатками, но категорически запрещается использовать любые электронные устройства (в том числе плейеры, калькуляторы, телефоны), а также источники информации в электронном виде (например, флешки).
На каждом туре участники получат 4 задачи. Каждая задача оценивается из 100 баллов следующим образом.
По каждой задаче имеется 4 группы тестов:
- нулевая группа: тесты из условия, всегда идут в качестве первых тестов в наборе тестов задачи. Оцениваются 0 баллов.
- первая и вторая группы: каждая из групп оценивается в 30 баллов, при этом эти баллы ставятся только если проходят все тесты группы, если хотя бы один из тестов группы не проходит, ставится 0 баллов за соответствующую группу. На тестах первой и второй групп решение тестируется во время тура.
- третья группа: оценивается суммарно в 40 баллов, баллы складываются из суммы баллов за тесты группы. Каждый тест в этой группе оценивается независимо от других (то есть если какие-то тесты проходят, а какие-то тесты не проходят, то ставятся баллы за прошедшие тесты). На тестах третьей группы решение участника тестируется после окончания тура, только если оно полностью прошло тесты первой группы тестов.
Участник во время тура может сдавать решения задач. Общее число попыток сдачи решений ограничено 30 (суммарно по всем задачам тура). После тура будет проверяться и оцениваться лишь последнее сданное решение по каждой задаче.
Участникам во время тура доступны результаты проверки решений на нулевой, первой и второй группах тестов (решение тестируется до первого непрошедшего теста), а также известно, какие тесты (номера тестов) относятся к первой группе, и какие - ко второй. Сами тесты во время тура участникам не сообщаются.
Особенности работы с проверяющей системой
Программа на любом языке программирования должна завершаться с кодом возврата 0. В частности, программа на C всегда должна заканчиваться оператором return 0; Имена входных и выходных файлов должны быть написаны маленькими латинскими буквами. Не забывайте закрывать выходной файл (иначе он остается пустым).
Результат проверки
Обратите внимание, что ваше решение во время тура проверяется только на тестах из нулевой, первой и второй групп тестов. Проверка на третьей группе тестов будет проходить после окончания тура и проверяться будут только решения, проходящие полностью хотя бы первую группу тестов.
Результат проверки во время тура сообщается в следующем виде - около посылки будет стоять одно из нижеперечисленных сообщений.
| сообщение | когда возникает | возможная причина |
| ОК | решение прошло тесты из нулевой, первой и второй групп тестов | |
| Ошибка компиляции (compilation error) | компиляция программы завершилась с ошибкой |
|
| Неправильный ответ (wrong answer) | ответ не верен |
|
| Неправильный формат вывода (presentation error) | программа проверки не может проверить выходные данные, так как их формат не соответствует описанному |
|
| Превышено максимальное время работы (time-limit exceeded) | программа превысила установленный в условии лимит времени |
|
| Превышен максимальный размер памяти (memory limit exceeded | программа превысила установленный в условии лимит памяти |
|
| Ошибка выполнения (run-time error) | Программа завершила работу с ненулевым кодом возврата |
|
Особенности языков программирования и файловый ввод-вывод
Поскольку часто именно файловый ввод-вывод является основной проблемой начинающих участников олимпиад, мы подготовили небольшую памятку, демонстрирующую реализацию ввода-вывода на различных языках программирования.
Программа на любом языке программирования должна завершаться с кодом возврата 0. В частности, программа на C всегда должна заканчиваться оператором return 0; Имена входных и выходных файлов должны быть написаны маленькими латинскими буквами. Не забывайте закрывать выходной файл (иначе во многих языках он остается пустым).
Ввод-вывод будем демонстрировать на примере двух задач. Первая задача - в файле sum.in записаны два целых числа по модулю не превышающих 32000, в файл sum.out нужно вывести их сумму. Вторая задача - такая же, только числа не превышают 1010 (и не помещаются в 32-битный тип данных).
Примечание для программирующих на QBasic, Borland Pascal, Borland C: Жюри не гарантирует, что любую задачу олимпиады можно решить с использованием этих языков программирования.
Pascal, Delphi
Примечание для программирующих на Delphi: Имена стандартных модулей пишутся точно так же, как в документации (имеется в виду сочетание больших и маленьких букв) и только так. Например: Math, SysUtils.
| Первая задача | Вторая задача | Примечания |
var a,b:longint; begin assign(input,'sum.in'); reset(input); assign(output,'sum.out'); rewrite(output); read(a,b); writeln(a+b); close(input); close(output); end. |
var a,b:int64; begin assign(input,'sum.in'); reset(input); assign(output,'sum.out'); rewrite(output); read(a,b); writeln(a+b); close(input); close(output); end. |
Тип int64 существует в Delphi и Free pascal и отсутствует в Borland pascal. |
GNU C
| Первая задача | Вторая задача | Примечания |
#include <stdio.h>
int main(void)
{
long a, b;
FILE *fin, *fout;
fin = fopen("sum.in", "r");
fout = fopen("sum.out", "w");
fscanf(fin, "%ld%ld", &a, &b);
fprintf(fout, "%ld", a + b);
fclose(fin);
fclose(fout);
return 0;
}
|
#include <stdio.h>
int main(void)
{
long long a, b;
FILE *fin, *fout;
fin = fopen("sum.in", "r");
fout = fopen("sum.out", "w");
#ifdef WIN32
fscanf(fin, "%I64d%I64d", &a, &b);
#else
fscanf(fin, "%lld%lld", &a, &b);
#endif
#ifdef WIN32
fprintf(fout, "%I64d\n",a+b);
#else
fprintf(fout, "%lld\n",a+b);
#endif
fclose(fin);
fclose(fout);
return 0;
}
|
Примечание для программирующих на GNU C/C++: При выводе значений переменных типа long long под ОС Windows нужно использовать спецификатор %I64d, а при сдаче решений на проверку (для ОС Linux) - спецификатор %lld.
"Универсальный" код, который работает правильно под обеими системами, может выглядеть так:
#ifdef WIN32
printf("%I64d\n",ans);
#else
printf("%lld\n",ans);
#endif
|
GNU C++
| Первая задача | Вторая задача |
#include <fstream>
using namespace std;
int main ()
{
long a, b;
ifstream fin ("sum.in");
ofstream fout ("sum.out");
fin >> a >> b;
fout << a + b << endl;
fin.close ();
fout.close ();
return 0;
}
|
#include <fstream>
using namespace std;
int main ()
{
long long a, b;
ifstream fin ("sum.in");
ofstream fout ("sum.out");
fin >> a >> b;
fout << a + b << endl;
fin.close ();
fout.close ();
return 0;
}
|
Java
Программа должна находиться в единственном классе с именем Main (обязательно с большой буквы), метод main должен находиться внутри класса Main. Вложенные классы допускаются.
import java.io.*;
public class Main
{
public static void main(String[] args) throws Exception
{
StreamTokenizer in = new StreamTokenizer(
new BufferedInputStream(
new FileInputStream(new File("sum.in"))));
PrintStream out = new PrintStream(new File("sum.out"));
int a, b;
in.nextToken(); a = (int) in.nval;
in.nextToken(); b = (int) in.nval;
out.println(a + b);
}
}
QBasic
| Первая задача | Комментарий относительно второй задачи |
open "sum.in" for input as #1 open "sum.out" for output as #2 input #1,a,b print #2,a+b close #1 close #2 | В QBasic нет встроенного типа для работы с 64-битными числами, поэтому вторая задача может решаться только реализацией "длинной арифметики". |
Visual Basic
| Первая задача | Вторая задача |
|
При создании приложения нужно выбрать "консольное приложение" (Console Application). Module Module1
Sub Main()
FileOpen(1, "sum.in", OpenMode.Input)
FileOpen(2, "sum.out", OpenMode.Output)
Dim a As Integer
Dim b As Integer
Input(1, a)
Input(1, b)
Print(2, a+b)
FileClose(1)
FileClose(2)
End Sub
End Module
|
Module Module1
Sub Main()
FileOpen(1, "sum.in", OpenMode.Input)
FileOpen(2, "sum.out", OpenMode.Output)
Dim a As Long
Dim b As Long
Input(1, a)
Input(1, b)
Print(2, a+b)
FileClose(1)
FileClose(2)
End Sub
End Module
|
php, python
В скриптовых языках php, python отсутствует возможность потокового ввода данных, свойственного для языков Pascal, C и C++, то есть в этих языках нельзя простыми методами считать из входного файла последовательность целых чисел (действительных чисел, строк и т.д.), если неизвестно, находятся ли эти числа в одной строке или в разных строках.
Для ввода данных в этих языках предлагается считывать содержимое всего файла сразу в строковую переменную, а затем использовать стандартную функцию split для разбивки этой переменной на поля. Функция split игнорирует все начальные и конечные пробельные символы (то есть пробелы, символы табуляции и символы новой строки), а все прочие символы разбиваются на последовательности, состоящие из непробельных символов, пробельные символы являются разделителями для полученных последовательностей. В результате получается список, состоящий из строк непробельных символов, содержащихся в исходном файле. Например, если в исходном файле записана строка "1 2 abc" (количество пробелов неважно), то в полученном списке будет три элемента - "1", "2" и "abc".
В языке php имеется небольшое отличие - функция называется preg_split, при ее вызове в качестве аргумента необходимо явно указать регулярное выражение, которое задает разделитель полей (это /\s+/, в языках perl, python и ruby такое значение разделителя используется по умолчанию), и перед вызовом функции preg_split необходимо явно удалить начальные и концевые пробелы из строки функцией trim (в языках perl, python и ruby это делает сама функция split).
Можно пользоваться и другими способами ввода-вывода данных, поддерживаемых данными языками.
php
Решения первой и второй задач в php совпадают.
<?php
# Считываем весь файл при помощи функции file_get_contents,
# удаляем начальные и конечные пробелы при помощи функции trim
# результат разбиваем на поля функцией split по шаблону /\s+/,
# задающему последовательность пробельных символов в качестве разделителя
# и записываем результат в массив InputData
$InputData=preg_split('/\s+/', trim(file_get_contents('sum.in')));
# Теперь в элементах массива $InputData[0] и $InputData[1]
# записаны два входных числа.
# Запишем их сумму в переменную $Answer
$Answer=$InputData[0]+$InputData[1];
# Объявляем файл FOUT для вывода данных
$FOUT=fopen("sum.out","w");
# Выведем результат в файл FOUT
fputs($FOUT,$Answer);
# Закроем файл FOUT
fclose($FOUT);
?>
python
Решения первой и второй задач в python совпадают
#!/usr/bin/python
# Объявляем файлы FIN и FOUT для ввода-вывода данных
FIN = open("sum.in", "r")
FOUT = open("sum.out", "w")
# Считываем весь файл при помощи метода read(),
# результат разбиваем на поля по пробельным символам методом split()
# и записываем в список InputData
InputData = FIN.read().split()
# Теперь в элементах списка InputData[0] и InputData[1]
# записаны два входных числа в виде строк.
# Преобразуем их к типу int и запишем их сумму в переменную Answer
Answer = int(InputData[0]) + int(InputData[1])
# Выведем результат в файл
print >> FOUT, Answer
# Закроем файлы FIN и FOUT
FIN.close()
FOUT.close()