Решение задач по программированию в системе Contester: первые шаги
Вход в проверяющую систему
Откройте главную страницу проверяющей системы. В левой части страницы вы увидите форму «Вход». Выберите имя своей учётной записи из выпадающего списка, введите пароль и нажмите кнопку «ОК». (Если у вас нет учётной записи, вам необходимо зарегистрироваться.)
Знакомство с задачами
Ссылки на задачи текущих олимпиад находятся на вкладке «Турниры», однако мы предлагаем вначале решить несколько пробных задач.
Самой распространённой пробной задачей является «А + B». Эту задачу часто используют для ознакомления с проверяющей системой и проверки работоспособности окружения.
Для тренировки по программированию целесообразно использовать сборники задач, доступные в системе Contester.
Откройте вкладку «Сборники», далее ссылку «Пробные задачи», затем ссылку «Одного ли цвета?». Вы увидите условие задачи, а также примеры входных и выходных данных.
Для решения задачи нужно написать программу, считывающую входные данные и выводящую правильный ответ. В данном случае программа должна определять, одного ли цвета два поля шахматной доски.
Как показано в примерах, если в программу ввести числа «1 1 2 2», программа должна вывести «YES» и завершить работу, если ввести «1 1 1 4» — вывести «NO» и завершить работу. Кроме тех тестов, которые даны в условии, программа должна будет правильно обработать определённое количество секретных тестов. Решение будет засчитано как верное только в том случае, если выведет корректный ответ на все тесты.
Составление решения
Вы можете писать решения на языках Pascal, C/C++, C# или Java. Для составления решения вам потребуется одна из сред программирования для выбранного языка (например, PascalABC или Lazarus для Pascal или CodeBlocks для C++). Мы воспользуемся онлайн-компилятором, который не требует установки, — ideone.com.
Перейдите на страницу онлайн-компилятора, нажмите нижнюю левую кнопку и выберите язык программирования, на котором будете составлять решение. В нашем случае это будет Pascal с компилятором fpc.
Ввод данных
Программирование решения можно начать с организации ввода данных. Перечитайте условие задачи: на вход поступают две пары целых чисел, каждое из которых находится в диапазоне от 1 до 8, — координаты клеток шахматной доски. Заметьте, что в задачах по программированию входные данные всегда будут соответствовать указанному в условии формату, если явно не указано обратное; таким образом, проверять введённые числа на принадлежность отрезку [1; 8] не нужно.
Определим в программе две пары целочисленных переменных: aX и aY для координат первой клетки и bX и bY — для координат второй. Для указанного диапазона подойдёт любой целочисленный тип.
Прочитаем все числа при помощи функции read(), как если бы они вводились с клавиатуры.
var aX, aY, bX, bY : integer;
begin
read(aX, aY, bX, bY);
end.
Программирование алгоритма
Теперь подумаем, каким образом вычислять ответ. Можно, например, явно определить цвета обеих клеток и потом сравнить их.
Чёрный цвет имеют такие клетки, как (1; 1), (1; 3), (1; 5), (2; 2), (2; 4), (3; 1), (3; 3), (4; 6), а белый — такие клетки, как (1; 2), (1; 4), (1; 6), (2; 1), (2; 3), (3; 2), (3; 4), (4; 7).
Можно заметить, что чёрный цвет имеют клетки, находящиеся в нечётных строках и нечётных столбцах или в чётных строках и чётных столбцах. Для белых клеток всё наоборот: они находятся в нечётных строках и чётных столбцах либо в чётных строках и нечётных столбцах. Другими словами, если чётность строки и столбца совпадает, то клетка чёрная, иначе — белая. Можно придумать и более простое условие: если сумма координат строки и столбца чётная, то клетка чёрная, иначе — белая.
Добавим в программу две переменные — aColor и bColor, обозначающие соответственно цвет первой и второй клетки. Примем, что если клетка чёрная, то значение переменной равно 0, а если белая, то 1. Чтобы записать в переменные нужные значения, добавим в программу условия, проверяющие суммы координат клеток на чётность.
var aX, aY, aCol, bX, bY, bCol : integer;
begin
read(aX, aY, bX, bY);
if (aX + aY) mod 2 = 0 then {если число чётное, значит остаток от деления на 2 равен 0}
aColor = 0
else
aColor = 1;
if (bX + bY) mod 2 = 0 then
bColor = 0
else
bColor = 1;
end.
Осталось лишь сравнить цвета клеток и вывести нужный ответ при помощи функции write().
var aX, aY, aCol, bX, bY, bCol : integer;
begin
read(aX, aY, bX, bY);
if (aX + aY) mod 2 = 0 then {если число чётное, значит остаток от деления на 2 равен 0}
aColor = 0
else
aColor = 1;
if (bX + bY) mod 2 = 0 then
bColor = 0
else
bColor = 1;
if aColor = bColor then
write('YES')
else
write('NO');
end.
Вообще говоря, отдельные переменные aColor и bColor оказываются не нужными, так как требуется только сравнить соответствующие значения. Поэтому от данных переменных можно отказаться, сократив код программы.
var aX, aY, bX, bY : integer;
begin
read(aX, aY, bX, bY);
if (aX + aY) mod 2 = (bX + bY) mod 2 then
write('YES')
else
write('NO');
end.
Тестирование решения
Теперь нужно проверить, что решение компилируется без ошибок и выводит корректные ответы.
Скопируйте код решения в окно онлайн-компилятора. Чтобы указать входные данные, нажмите расположенную внизу кнопку «stdin» и в появившееся поле скопируйте содержание первого примера из условия задачи («1 1 2 2»).
Нажмите зелёную кнопку «Run».
Вы увидите результат компиляции программы (в данном случае «Успешно»), а также вывод программы («YES»).
Нажмите расположенную сверху ссылку «Редактировать», введите данные второго примера из условия и запустите решение на нём. Придумайте ещё несколько тестов и проверьте корректность работы решения.
Отправка решения на проверку
Когда вы уверены в правильности решения, вы можете отвравить его в проверяющую систему. Форма отправки решения находится в нижней части окна с условием задачи.
В поле «Текст попытки» скопируйте код решения, в выпадающем списке «Компилятор» выберите Pascal. Нажмите кнопку «Отправить».
Страница обновится, и в её нижней части вы сможете увидеть результат проверки решения. В данном случае это «Accepted» — решение принято.
Решения на других языках и ошибки
Откройте в сборнике «Пробные задачи» задачу «Симметричная матрица». Составим её решение на языке C++ (в ideone нужно выбрать компилятор C++ 5.1).
На вход программе поступает целочисленная матрица размером не более 100 × 100, поэтому в программе можно объявить и заполнить массив matrix[110][110]. Для считывания элементов матрицы потребуется два вложенных цикла for.
#include <iostream> //подключается библиотека с функциями ввода-вывода
using namespace std; //используется стандартное пространство имён
int main() {
int size, matrix[110][110]; //размер матрицы и собственно матрица
cin >> size; //считывание размера с клавиатуры
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
cin >> matrix[i][j]; //считывание элементов матрицы
}
Для проверки симметричности матрицы требуется удостовериться, что все пары симметричных элементов равны. Для элемента matrix[i][j] симметричным является элемент matrix[j][i].
#include <iostream> //подключается библиотека с функциями ввода-вывода
using namespace std; //используется стандартное пространство имён
int main() {
int size, matrix[110][110]; //размер матрицы и собственно матрица
cin >> size; //считывание размера с клавиатуры
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
cin >> matrix[i][j]; //считывание элементов матрицы
bool isSymmetrical = true; //изначально считаем, что матрица симметрична
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
if (matrix[i][j] != matrix[j][i]) //если парные элементы оказались не равны,
isSymmetrical = false; //матрица не является симметричной
if (isSymmetrical)
cout << "YES";
else
cout << "NO";
}
Отправьте решение на проверку в тестирующую систему, но не копируйте первые две строки («#include <iostream>» и «using namespace std;»). Вы получите вердикт «Compilation Error» — ошибка компиляции.
В данном случае вы можете посмотреть отчёт компилятора, чтобы установить причину ошибки. Для этого нажмите ссылку «Инфо» в правой части строки с вердиктом проверки и выберите «Лог». В данном случае можно видеть, что компилятор не распознал стандарные потоки ввода-вывода cin и cout, так как мы не добавили библиотеку iostream и пространство имён std, где они определены.
Скопируйте решение полностью, но теперь при определении симметричности поменяйте верхние границы циклов с size на 3:
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (matrix[i][j] != matrix[j][i]) //если парные элементы оказались не равны,
isSymmetrical = false; //матрица не является симметричной
Таким образом, на симметричность будет проверяться не вся матрица, а только левый верхний квадрат 3 × 3. Этого достаточно, чтобы пройти первый тест, но в целом такое решение, безусловно, является неверным.
Отправьте его на проверку. Вы получите вердикт «Wrong Answer on test 2» — неверный ответ на втором тесте. При получении такого вердикта у вас не будет возможности увидеть содержание теста, поэтому тщательно проверяйте свои решения самостоятельно перед отправкой на проверку.
Решение может получить и другие вердикты проверки, которые подробно описаны на странице помощи.
Отправьте на проверку полное решение и получите вердикт «Accepted».
Теперь вы можете перейти к решению турнирных задач.