Разбор задач муниципального этапа ВсОШ 2016/2017

Ниже приводится разбор муниципального этапа Всероссийской олимпиады школьников по информатике 2016/2017 с примерами реализации.

Перед прочтением разбора рекомендуется ознакомиться с задачами и попробовать их решить на неофициальном зеркале олимпиады.

Клетчатые прямоугольники

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

Решение

Классическая задача нахождения максимальной площади по заданному периметру. Задачу можно решить просто перебором за , однако существует красивое решение за O(1), рассмотрим его ниже.

Достаточно было заметить, что количество закрашенных клеток в точности равно периметру искомого прямоугольника плюс четыре угловых клетки. Разберём решение этой задачи, пусть - стороны искомого прямоугольника, тогда его периметр также будет равен , а площадь .

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

Покажем теперь, что .

Пусть , тогда и .

Тогда .

В то же время .

Получаем , что и требовалось доказать.

Реализация

int N;
cin >> N;
N -= 4;
cout << N*N/16;

Диофантово уравнение

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

Решение

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

Реализация

int n;
cin >> n;
int answer = 0;
int i = 1;
for (; i*i < n+1; ++i)
    if ((n+1)%i == 0)
        answer += 2;
if (i*i == n+1)
    answer++;
cout << answer;

Системы счисления

Учитель предложил ученикам в равенстве определить, в какой системе счисления оно записано. Например, верно для двоичной системы, а равенство будет верным в системе счисления с основанием 17.

Решение

Задачу следует решать перебором по основанию системы счисления, переводя в неё числа , и , и проверяя корректность равенства в этой системе. Сначала по цифрам числел , , определим минимальное основание, с которого будет начинаться перебор. Если в каком-то числе встречается цифра , то основание не может быть меньше . Затем производится перебор от минимального основания до 36.

Реализация

Определение порядкового номера цифры

int get_number(const char c) {
    if ((c >= '0') && (c <= '9'))
        return c - '0';
    else
        return c - 'A' + 10;
}

Чтения чисел и поиск минимально возможного основания

string s;
cin >> s;
int min_ss = 1;
int X[10], Y[10], Z[10];
int X_len(0), Y_len(0), Z_len(0);
int i = 0;
while (s[i] != '+') {
    X[X_len] =  get_number(s[i]);
    min_ss = max(min_ss, X[X_len]);
    i++;
    X_len++;
}
i++;
while (s[i] != '=') {
    Y[Y_len] =  get_number(s[i]);
    min_ss = max(min_ss, Y[Y_len]);
    i++;
    Y_len++;
}
i++;
while (i < s.length()) {
    Z[Z_len] =  get_number(s[i]);
    min_ss = max(min_ss, Z[Z_len]);
    i++;
    Z_len++;
}
min_ss++;

Перебор оснований

long long X_num;
long long Y_num;
long long Z_num;
for (int i = min_ss; i <= 36; ++i) {
    X_num = 0;
    for (int j = 0; j < X_len; ++j)
        X_num = X_num*i + X[j];
    Y_num = 0;
    for (int j = 0; j < Y_len; ++j)
        Y_num = Y_num*i + Y[j];
    Z_num = 0;
    for (int j = 0; j < Z_len; ++j)
        Z_num = Z_num*i + Z[j];
    if (X_num + Y_num == Z_num) {
        cout << i;
        break;
    }
}

Три кучи камней

Имеются три кучи камней (в первой камней, во второй – , в третьей – камней). Два игрока по очереди делают ходы. На каждом ходу игрок выбирает две кучи и из меньшей в большую перекладывает любое число камней. Выигрывает тот, кто первым соберет все камни в одной куче. Определите, кто из игроков победит в игре при данном наборе , если оба игрока играют наилучшим образом.

Решение

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

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

Поэтому для определения победителя достаточно проверить равенство и , и если оно выполняется, то выигрывает второй игрок, в противном случае - первый.

Реализация

int x, y, z;
cin >> x >> y >> z;
if (y < x)
    swap(x, y);
if (z < x)
    swap(x, z);
if (z < y)
    swap(y, z);
if (x < y) 
    cout << 1;
else
    cout << 2;

Фракталы

Кривая, изображенная на рисунке, называется кривой дракона Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку . Далее на каждом шаге из конца, построенной кривой, повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

Один из членов жюри попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил ее рисовать, проделав описанные выше шагов. Требуется написать программу, которая по заданному числу определяет координаты конца кривой после выполнения шагов.

Решение

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

Реализация

int n;
cin >> n;
int x1(0), x2, y1(1), y2;
for (int i = 0; i < n-1; ++i) {
    x2 = x1+y1;
    y2 = y1-x1;
    swap(x1, x2);
    swap(y1, y2);
}
cout << x1 << ' ' << y1;

tutorials vos