Чемпионат ИТ-сферы Ульяновской области по программированию среди школьников

Расскажи мне — и я забуду, покажи мне — и я запомню, позволь мне действовать самому — и я научусь. (Конфуций)


О чемпионате
    Смысл участия
    Спонсоры
    Рейтинги
    Регистрация
    Проекты в турнирах

Уроки
    Первые шаги
    Советы начинающим
    Этика
    Полезные материалы

Информатика и вычислительная техника — Computer Science (CS)
    ИВТ в УлГТУ
    Дисциплины ИВТ
    CS → ИВТ

Решение задач по программированию в системе 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».

 

Теперь вы можете перейти к решению турнирных задач.