СГАУ :: Олимпиадное программирование

Типы соревнований: Virtual и Upsolving

В архиве соревнований вы можете заметить, что почти все сорвенования имеют два вида: Virtual (виртуальное соревнование) и Upsolving (дорешивание). Виртуальное сорвенование будет иметь для вас свою обычную длительность, в нём решения других участников, уже игравших его раньше, будут появляться по мере того, как они сдавались во время игр тех участников. После того, как виртуальное сорвенование закончилось, вы уже не сможете сдавать туда задачи. Дорешивание — это просто бесконечно длинное соревнование, в которое можно заходить в любое время и сдавать туда решения, которые не получилось написать на обычном или виртуальном туре.

Вердикты

Здесь находится список вердиктов, которые может получить ваше решение. Мы сообщаем номер теста, но не сообщаем расход времени и памяти.

WA — Wrong Answer. Ответ, выведенный вашим решением, неверен. Sad but true.
PE — Presentation Error. Ваше решение вывело какую-то ерунду, даже отдаленно не похожую даже на неправильный ответ. Например, если в задаче требуется вывести целое число, а вы выводите строку из маленьких латинских букв, вы получите этот вердикт.
TL — Time Limit Exceeded. Ваше решение работает слишком долго на одном из наших тестов. Проверьте, сколько операций выполняет ваша программа, и не входит ли она в бесконечный цикл.
ML — Memory Limit Exceeded. Ваше решение потребляет слишком много памяти. Проверьте размеры ваших структур данных.
RE — Runtime Error. Причинами этого вердикта может стать деление на ноль, выход за границу массива, переполнение стека в результате бесконечной рекурсии и другие подобные ситуации.
CE — Compilation Error. Ваша программа не компилируется. Проверьте, правильно ли вы выбрали язык программирования при отправке. В любом случае, при вердикте Compilation Error вам будет доступен вывод компилятора, так что вы сможете определить, что ему не понравилось в вашем идеальном коде. Это особенно касается компиляторов C++ и Pascal, т.к. вы можете пользоваться другими компиляторами (MS Visual C++ или Delphi). Штрафные попытки при ошибках компиляции не начисляются.
SV — Security Violation. Вы попытались выполнить запрещенное действие. Жюри обязательно посмотрит вашу программу и, если это была намеренная попытка дестабилизировать работу системы, вычислит вас по IP.
OK — Accepted. Наши тесты настолько слабые, что ваше неправильное решение умудрилось на всех них дать правильный ответ. Вы должны радоваться, потому что Accepted, полученные на контесте, не принято перетестировать.

Ввод и вывод

В системе используется стандартный консольный ввод-вывод (stdin/stdout).

Вывод в поток ошибок

Ваша программа может выводить в поток ошибок (stderr). Например, это может быть отладочная информация. Тестирующая система игнорирует поток ошибок, так что это не может стать причиной вердиктов WA или PE. Однако надо помнить, чтоб на вывод тратится время, поэтому, если вы будете выводить слишком много, вы рискуете получить вердикт TL.

Допустимые символы

Пожалуйста, не используйте в своих исходниках нестандартные символы. К ним, в том числе, относятся русские буквы. Если вы отошлете подобное решение, вам придет вердикт CE.

Переменная ONLINE_JUDGE

На сервере установлена переменная ONLINE_JUDGE. С ее помощью можно различать запуск программ на сервере и на вашем локальном компьютере. Например, если вы предпочитаете пользоваться файловым вводом и выводом вместо стандартного, вы можете использовать для этого переменную ONLINE_JUDGE. Чтобы подробнее показать, как это можно использовать, приведем примеры для каждого языка программирования.

Pascal:

{$IfDef ONLINE_JUDGE}
writeln('This text will be printed on the server');
{$Else}
writeln('This text will be printed on your local computer');
{$EndIf}

C++:

#ifdef ONLINE_JUDGE
printf("This text will be printed on the server\n");
#else
printf("This text will be printed on your local computer\n");
#endif

Java:

boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
if (ONLINE_JUDGE) {
	System.out.println("This text will be printed on the server");
} else {
	System.out.println("This text will be printed on your local computer");
}

C#:

#if ONLINE_JUDGE
Console.WriteLine("This text will be printed on the server");
#else
Console.WriteLine("This text will be printed on your local computer");
#endif

Размер стека

Вы можете не волноваться насчет размера стека: он в тестирующей системе установлен максимально возможным.

Перевод строки

Тестирующая система работает на операционной системе Linux, так что перевод строки состоит из одного символа LF ('\n', ASCII-код 10). В Windows переводы строки состоят из двух символов CR и LF ('\r' и '\n', ASCII-коды 13 и 10). Будьте внимательны, если это влияет на ваше решение.

Особенности компиляторов

Pascal

Версия компилятора — Free Pascal 2.6.4

Строка компиляции:

fpc -dONLINE_JUDGE -O2 -Xs -Sgic -viwn -Mdelphi -XS [src] -o [out]

Пример решения задачи A+B:

var a, b: longint;
begin
	read(a, b);
	writeln(a + b);
end.

C++

Версия компилятора — GNU C++ 5.3.1

Строка компиляции:

g++ -std=c++11 -Wall -O2 -DONLINE_JUDGE -fno-optimize-sibling-calls -fno-strict-aliasing -static [src] -o [out] -lm

В некоторых контестах также доступен компилятор языка C — GNU C 5.3.1. Все сказанное выше и ниже про C++ верно и для C, если это возможно. Тем не менее, если вы по какой-то причине любите решать задачи на C, мы рекомендуем вам как можно скорее прекратить это бесполезное занятие и начать писать на C++.

Стоит обратить внимание на ввод и вывод 64-битных целых чисел функциями scanf и printf. Спецификатор "%I64d" не работает, используйте спецификатор "%lld", например:

long long x;
scanf("%lld", &x);
printf("%lld", x);

unsigned long long y;
scanf("%ulld", &y);
printf("%ulld", y);

Примеры решения задачи A+B:

Решение с использованием C-style ввода-вывода.

#include <cstdio>
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d\n", a + b);
}

Решение с использованием потокового ввода-вывода.

#include <iostream>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";
}

Обратите внимание, что ввод-вывод через cin / cout работает медленнее, чем через scanf / printf. Так что если в задаче требуется считывать большие объемы данных, сразу используйте scanf / printf.

Java

Версия Java — 1.8.0_73

Строка запуска:

java -DONLINE_JUDGE -Xmx512M -Xss256M -Duser.language=en -Duser.region=US -Duser.variant=US -jar [jar]

В некоторых тестирующих системах есть ограничения на имя класса, использование вложенных классов и т.д. У нас этого нет: вы можете использовать любое имя классов, любое количество вложенных классов. Локаль автоматически выставлена как "en-US", так что вывод чисел с плавающей точкой через, например, System.out.println или PrintWriter.println будет работать правильно (если по умолчанию установлена русская локаль, вместо десятичной точки будет отображаться запятая).

Примеры решения задачи A+B:

Короткое решение с использованием java.util.Scanner.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		System.out.println(a + b);
	}
}

Однако класс java.util.Scanner очень медленный, и с ним можно получить вердикт TL. Поэтому мы приведем еще один механизм ввода-вывода, быстрый и самый популярный.

Решение с использованием java.io.BufferedReader, java.util.StringTokenizer и java.io.PrintWriter.

import java.io.*;
import java.util.*;

public class Main {
	private static BufferedReader in;
	private static StringTokenizer tok;
	private static PrintWriter out;

	private static String readToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}
	
	private static int readInt() throws IOException {
		return Integer.parseInt(readToken());
	}
	
	public static void main(String[] args) throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		int a = readInt();
		int b = readInt();
		out.println(a + b);
		in.close();
		out.close();
	}
}

C#

Версия компилятора — Mono C# 4.2.1.0

Строка компиляции:

gmcs -define:ONLINE_JUDGE -optimize+ [src] -out:[out]

Пример решения задачи A+B:

using System;

public class Solution
{
    public static void Main()
    {
	string[] tokens = Console.ReadLine().Split(' ');
	int a = int.Parse(tokens[0]);
	int b = int.Parse(tokens[1]);
	Console.WriteLine(a + b);
    }
}

Стоит учитывать, что ввод и вывод с использованием Console.ReadLine() и Console.WriteLine() может быть медленный, и в некоторых случаях надо писать собственную реализацию. Также, один из способов ускорить вывод - добавлять выходные данные в StringBuilder, а потом один раз вывести этот StringBuilder.

Типы данных

Просматривая решения некоторых участников, жюри убедилось в том, что не все знают, что, оказывается, существуют типы данных для 64-битных целых чисел. Поэтому мы решили опубликовать список всех числовых типов данных.

Pascal

Знаковые типы

Тип данных	Размер	Диапазон значений
`shortint`	1 байт	`[-128 … 127]`
`smallint`	2 байта	`[-32768 … 32767]`
`longint`	4 байта	`[-2147483648 … 2147483647]`
`int64`	8 байт	`[-9223372036854775808 … 9223372036854775807]`

Беззнаковые типы

Тип данных	Размер	Диапазон значений
`byte`	1 байт	`[0 … 255]`
`word`	2 байта	`[0 … 65535]`
`longword`	4 байта	`[0 … 4294967295]`
`qword`	8 байт	`[0 … 18446744073709551615]`

Вещественные типы

Тип данных	Размер	Диапазон значений	Точность
`single`	4 байта	`[1.5E-45 … 3.4E38]`	7-8 знаков
`double`	8 байт	`[5.0E-324 … 1.7E308]`	15-16 знаков
`extended`	10 байт	`[1.9E-4932 … 1.1E4932]`	19-20 знаков

C++

Знаковые типы

Тип данных	Размер	Диапазон значений
`char`	1 байт	`[-128 … 127]`
`short`	2 байта	`[-32768 … 32767]`
`int`	4 байта	`[-2147483648 … 2147483647]`
`long long`	8 байт	`[-9223372036854775808 … 9223372036854775807]`

Беззнаковые типы

Тип данных	Размер	Диапазон значений
`unsigned char`	1 байт	`[0 … 255]`
`unsigned short`	2 байта	`[0 … 65535]`
`unsigned int`	4 байта	`[0 … 4294967295]`
`unsigned long long`	8 байт	`[0 … 18446744073709551615]`

Вещественные типы

Тип данных	Размер	Диапазон значений	Точность
`float`	4 байта	`[1.5E-45 … 3.4E38]`	7-8 знаков
`double`	8 байт	`[5.0E-324 … 1.7E308]`	15-16 знаков
`long double`	12 байт	`[1.9E-4932 … 1.1E4932]`	19-20 знаков

Java

Тип данных	Размер	Диапазон значений
`byte`	1 байт	`[-128 … 127]`
`short`	2 байта	`[-32768 … 32767]`
`int`	4 байта	`[-2147483648 … 2147483647]`
`long`	8 байт	`[-9223372036854775808 … 9223372036854775807]`

Беззнаковых типов в Java нет.

Вещественные типы

Тип данных	Размер	Диапазон значений	Точность
`float`	4 байта	`[1.5E-45 … 3.4E38]`	7-8 знаков
`double`	8 байт	`[5.0E-324 … 1.7E308]`	15-16 знаков

C#

Знаковые типы

Тип данных	Размер	Диапазон значений
`sbyte`	1 байт	`[-128 … 127]`
`short`	2 байта	`[-32768 … 32767]`
`int`	4 байта	`[-2147483648 … 2147483647]`
`long`	8 байт	`[-9223372036854775808 … 9223372036854775807]`

Беззнаковые типы

Тип данных	Размер	Диапазон значений
`byte`	1 байт	`[0 … 255]`
`ushort`	2 байта	`[0 … 65535]`
`uint`	4 байта	`[0 … 4294967295]`
`ulong`	8 байт	`[0 … 18446744073709551615]`

Вещественные типы

Тип данных	Размер	Диапазон значений	Точность
`float`	4 байта	`[1.5E-45 … 3.4E38]`	7-8 знаков
`double`	8 байт	`[5.0E-324 … 1.7E308]`	15-16 знаков