I Областная олимпиада школьников по информатике
2016-2017 учебный год
9-10 классы
Заключительный тур
Разбор задач
Задача 1. Игра на вылет (10 баллов)
Ответ для каждого входного значения N равен log2(N) c округлением вверх. Или, другими словами, это максимальная степень числа 2, больше или равная N. Обоснуем это.
Вначале рассмотрим частный случай, когда N − это степень двойки. Для удобства будем считать, что все матчи разбиты на туры. В первом туре все команды делятся на пары и играют друг с другом, в результате половина команд выбывает. Во втором туре повторяется то же самое, и так до тех пор, пока не останется одна команда. Количество туров равно количеству раз, которое N нужно поделить на 2, чтобы получить 1 − то есть log2(N). Понятно, что количество туров − это и есть максимальное количество матчей, в которых может сыграть одна команда.
Если N не равняется степени двойки, то схема разбиения на туры несколько меняется. Если N − нечётное, то одна команда в текущем туре не играет, а сразу переходит в следующий тур, в котором она сыграет в первом же матче. То есть, если в предыдущем туре было N команд, то в следующем туре их будет N/2 с округлением вверх. Чтобы сосчитать количество туров, можно просто промоделировать этот процесс. Нетрудно также заметить (и при желании доказать), что количество туров будет равно log2(N) с округлением вверх.
Осталось еще показать, что для любого N всегда найдётся такое расписание, что хотя бы одна команда поучаствует в матче в каждом туре. Пусть это будет команда №1. Будем считать, что если какая-то команда не участвовала в предыдущем туре, то в следующем она обязательно проигрывает. Тогда в каждом следующем туре будут участвовать команды, которые уже сыграли одинаковое число матчей, за исключением, возможно, одной команды, которая сыграла на один матч меньше. Отсюда следует, что расписание матчей в каждом туре всегда можно назначить так, чтобы команда №1 с кем-то играла.
Заметим, что здесь нужно быть аккуратным с вещественными вычислениями. Например, log2(1073741825)≈30.000000001, и округление вверх даёт 31, а не 30.
Задача 2. Сумма (10 баллов)
Возможным ответом на эту задачу является следующая формула:
(A/2*2 + (B-1)/2*2 + 2) / 2 * ((B-1)/2 - A/2 + 1)
Для её вывода воспользуемся формулой суммы арифметической прогрессии:
S = (x1+xn)/2*n, где x1 и xn − первый и последний член последовательности, n − количество членов.
Однако, напрямую применить эту формулу затруднительно, поскольку значения A и B могут быть как нечётными, так и чётными.
Получим из A нечётное число − первый член последовательности. Несложно убедиться, что выражение x1 = A/2*2+1 даёт требуемый результат. Например, 4/2*2+1=5, 5/2*2+1=5.
Теперь получим из B нечётное число − последний член последовательности. Требуемый результат даёт выражение xn = (B−1)/2*2+1. Например, (7−1)/2*2+1=7, (8−1)/2*2+1=7.
Количество нечётных чисел между двумя нечётными числами x1 и xn найдётся как n = (xn − x1 + 2) / 2. Подставим выражения для x1 и xn и сократив, получим n = (B-1)/2−A/2+1.
Подставив в формулу для суммы арифметической прогрессии выражения для x1, xn и n и сократив, получаем, что сумма равна:
(A/2*2 + (B-1)/2*2+2) / 2 * ((B-1)/2-A/2+1)
Заметим ещё, что поскольку сумма двух нечётных чисел всегда является чётным числом, то деление этой суммы на 2 можно выполнять как перед последующим умножением (как в вышенаписанной формуле), так и после него:
(A/2*2 + (B-1)/2*2+2) * ((B-1)/2-A/2+1) / 2
Разумеется, верная формула может быть записана разными способами, поэтому проверка решений этой задачи выполняется путём подстановки ряда значений A и B в решение участника и сравнением результата с правильным. Например, вот ещё один верный ответ:
((A+1-A%2) + (B-1+B%2)) * (((B-1+B%2) - (A+1-A%2)) / 2 + 1) / 2
Задача 3. Пилообразные числа (10 баллов)
Данную задачу можно решить методом динамического программирования. Создадим две матрицы g и l размерности 1..N по вертикали и 0..9 по горизонтали, где:
· g[i][j] − это количество пилообразных последовательностей длины i,которые кончаются цифрой j, а предыдущая цифра больше j.
· l[i][j] − это количество пилообразных последовательностей длины i,которые кончаются цифрой j, а предыдущая цифра меньше j.
Теперь несложно написать правила перехода от i к (i+1).
Для всех пар цифр k и j, где k > j:
l[i + 1][k] := l[i + 1][k] + g[i][j]
Для всех пар цифр k и j, где k < j:
l[i + 1][k] := l[i + 1][k] + g[i][j]
В первой формуле мы говорим, что можно добавить цифру k в конец всех i-разрядных чисел, которые кончались цифрой j, а предыдущая цифра была больше j. Поскольку теперь предыдущая цифра станет меньше k, то результат добавляется к элементу матрицы l. Вторая формула объясняется аналогично.
Заметим, что ответ может диапазон значений 32-битного целого типа, поэтому нужно использовать 64-битный тип.
Пример решения на Free Pascal:
const NMAX = 18;
var
g, l: array[1..NMAX, 0..9] of Int64;
n, i, j, k: integer;
ans: int64;
begin
fillchar(g, sizeof(g), 0);
fillchar(l, sizeof(l), 0);
read(n);
for i := 1 to 9 do begin
g[1][i] := 1;
l[1][i] := 1;
end;
for i := 1 to n - 1 do
for j := 0 to 9 do begin
for k := j + 1 to 9 do
l[i + 1][k] := l[i + 1][k] + g[i][j];
for k := 0 to j - 1 do
g[i + 1][k] := g[i + 1][k] + l[i][j];
end;
ans := 0;
for j := 0 to 9 do
ans := ans + l[n][j] + g[n][j];
writeln(ans);
end.
Подзадача 1 может быть решена простым перебором всех N-разрядных чисел и проверкой каждого из них на пилообразность.
Подзадача 2 может быть решена преподсчётом. Например, меньше, чем за минуту (на Intel Core i5) можно перебрать все 12-разрядные пилообразные числа с помощью перебора с возвратом:
const
UP = 1; DOWN = 2;
var
n, i: integer;
ans: int64;
procedure backtrack(prev, n, dir: integer);
var
d: integer;
begin
if dir = UP then begin
for d := prev + 1 to 9 do
if n > 1 then
backtrack(d, n - 1, DOWN)
else inc (ans);
end else begin
for d := 0 to prev - 1 do
if n > 1 then
backtrack(d, n - 1, UP)
else
inc(ans);
end;
end;
begin
assign(input, 'input. txt');
reset(input);
assign(output, 'output. txt');
rewrite(output);
read(n);
ans := 0;
for i := 1 to 9 do begin
backtrack(i, n - 1, UP);
backtrack(i, n - 1, DOWN);
end;
writeln(ans);
end.
На проверку посылается программа с набором if, в которых выводятся заранее сосчитанные ответы.
Задача 4. Лабиринт (10 баллов)
Задача решается методом поиска в ширину (bfs). Создадим следующие структуры данных:
· матрица field для хранения входного игрового поля;
· очередь queue, в которую будут помещаться записи со следующими четырьмя полями: координаты клетки x и y, номер игрока player, длина кратчайшего пути до этой клетки pathLength;
· трёхмерный массив visited, в котором для каждой клетки и каждого игрока будет отмечаться, что он её уже посетил;
· матрица playersCount, в которой для каждой клетки будет записано количество игроков, которые её уже посетили.
Вначале занесём в очередь начальные координаты всех игроков. В массиве visited отметим, что эти клетки ими уже посещены. В матрице playersCount поставим в эти клетки по единичке.
Далее повторяем в цикле следующие действия. Извлекаем из очереди очередной элемент. Пытаемся сходить влево, вправо, вверх и вниз. Если в соответствующей клетке нет стены, и мы там ещё не бывали (смотрим в visited), то делаем следующее:
· заносим её координаты в очередь (при этом поле pathLength увеличится на 1),
· отмечаем посещённость клетки в массиве visited,
· в матрице playersCount увеличиваем число игроков для этой клетки на 1.
Процесс заканчивается либо когда очередь опустеет, либо когда в матрице playersCount впервые появится значение, больше или равное K − требуемому числу игроков.
Количество итераций цикла будет равно количеству элементов, добавляемых в очередь. Поскольку каждая тройка <y, x, игрок> может быть добавлена в очередь только один раз, то количество итераций не превышает M∙N∙U (где U − количество игроков на поле). При максимальных ограничениях задачи это будет 200∙200∙100= 4 000 000.
Оценим ещё требования к памяти (хотя на олимпиаде она существенно и не ограничивалась). Если для целых чисел использовать 2-байтный тип, то под очередь нужно выделить 200∙200∙100∙8≈32 мегабайта. Под массив visited нужно 200∙200∙100≈4 мегабайта, плюс ещё один-два мегабайта под всё остальное. Таким образом, потребление памяти составит около 40 мегабайт.
Пример решения на Free Pascal
const
NMAX = 200; PMAX = 100;
type
Point = record
x, y, player, pathLength: smallint;
end;
var
field: array[1..NMAX] of String[NMAX];
queue: array[1..NMAX * NMAX * PMAX] of Point;
qLeft, qRight, nY, nX, player, needPlayers, x,y, dx, dy: longint;
playersCount: array[1..NMAX, 1..NMAX] of smallint;
visited: array[1..PMAX, 1..NMAX, 1..NMAX] of boolean;
p, pNext: Point;
begin
fillchar(visited, sizeof(visited), false);
fillchar(playersCount, sizeof(playersCount), 0);
readln(nY, nX, needPlayers);
for y := 1 to nY do
readln(field[y]);
player := 0; qRight := 0;
for y := 1 to nY do
for x := 1 to nX do
if field[y][x] = '*' then begin
inc(player);
p. x := x;
p. y := y;
p. player := player;
p. pathLength := 0;
inc(qRight);
queue[qRight] := p;
playersCount[y][x] := 1;
visited[player][y][x] := true;
end;
qLeft := 1;
while (qLeft <= qRight) do begin
p := queue[qLeft];
inc(qLeft);
for dy := -1 to 1 do
for dx := -1 to 1 do
if ((dy<>0)xor(dx<>0)) and (p. y+dy>=1)
and (p. x+dx>=1) and (p. y+dy<=nY)
and (p. x+dx<=nX) then
if (field[p. y+dy][p. x+dx] <> '#') and
(not visited[p. player][p. y+dy][p. x+dx]) then
begin
pNext. y := p. y + dy;
pNext. x := p. x + dx;
pNext. player := p. player;
pNext. pathLength := p. pathLength + 1;
inc(playersCount[pNext. y][pNext. x]);
if (playersCount[pNext. y][pNext. x]>=needPlayers)
then begin
writeln(pNext. pathLength);
exit;
end;
visited[pNext. player][pNext. y][pNext. x] := true;
inc(qRight);
queue[qRight] := pNext;
end;
end;
writeln(-1);
end.
Задача 5. Олимпиады (10 баллов)
Занесём информацию об олимпиадах в логические массивы t1, ta и tb, где:
· t1[i] = true, если имеется однотуровая олимпиада, идущая в день i,
· ta[i] = true, если имеется двухтуровая олимпиада без промежутка между турами, у которой второй тур идёт в день i,
· tb[i] = true, если имеется двухтуровая олимпиада с промежутком между турами, у которой второй тур идёт в день i.
Вначале заметим следующий факт. Пусть в оптимальное решение входит какая-то двухтуровая олимпиада, и она пересекается с какой-то однотуровой, которая в решение не входит. Тогда их можно поменять местами, и решение от этого не ухудшится.
Тогда первый шаг решения будет такой: добавим к ответу количество различных дней, в которые проводятся однотуровые олимпиады (то есть количество значений true в массиве t1). Также выбросим из дальнейшего рассмотрения все двухтуровые олимпиады, у которых хотя бы один тур приходится на эти дни.
Теперь у нас осталась задача только с двухтуровыми олимпиадами. Воспользуемся методом динамического программирования. Создадим два массива ca и cb, где:
· ca[i] − это максимальное количество двухтуровых олимпиад, в которых можно поучаствовать в дни 1..i,
· cb[i] − это максимальное количество двухтуровых олимпиад, в которых можно поучаствовать в дни 1..i при условии, что в день (i−1) мы в олимпиадах не участвуем
Осталось определиться, каким образом вычислять ca[i] и cb[i], зная их значения при всех меньших i. Для этого рассмотрим несколько случаев:
1. Можно в i-й день вообще ни в какой олимпиаде не участвовать. Тогда:
ca[i] := ca[i - 1];
cb[i] := ca[i - 2];
2. Можно в i-й день поучаствовать во втором дне олимпиады без промежуточного дня между турами (если такая, конечно, в этот день проводится). Для этого нужно, чтобы предыдущий день был свободен:
if ta[i] and (ca[i - 2] + 1 > ca[i]) then
ca[i] := ca[i - 2] + 1;
3. Можно в i-й день поучаствовать во втором дне олимпиады с промежуточным днём между турами (если такая, конечно, в этот день проводится). Для этого нужно, чтобы день (i−2) был свободен:
if tb[i] then begin
ca[i] := max(ca[i], ca[i - 3] + 1);
ca[i] := max(ca[i], cb[i - 1] + 1);
cb[i] := max(cb[i], ca[i - 3] + 1);
end;
Пример решения на Free Pascal
uses math;
const
NMAX = 1000; DMAX = 300;
var
n, i, t, d1, d2, ans: integer;
t1, ta, tb: array[0..DMAX + 2] of boolean;
ca, cb: array[0..DMAX + 2] of Integer;
begin
read(n);
for i := 0 to DMAX + 2 do begin
t1[i] := false; ta[i] := false; tb[i] := false;
ca[i] := 0; cb[i] := 0;
end;
for i := 1 to n do begin
read(t, d1);
if t = 1 then
t1[d1] := true
else begin
read(d2);
if d1 + 1 = d2 then
ta[d2] := true
else
tb[d2] := true
end;
end;
ans := 0;
for i := 1 to DMAX do
if t1[i] then begin
inc(ans);
ta[i] := false;
ta[i + 1] := false;
tb[i] := false;
tb[i + 2] := false;
end;
if ta[2] then ca[2] := 1;
for i := 3 to DMAX + 2 do begin
// если этот день пропустить
ca[i] := ca[i - 1];
cb[i] := ca[i - 2];
// если поучаствовать в олимпиаде без промежуточного дня
if ta[i] and (ca[i - 2] + 1 > ca[i]) then
ca[i] := ca[i - 2] + 1;
// если поучаствовать в олимпиаде со свободным днём
if tb[i] then begin
ca[i] := max(ca[i], ca[i - 3] + 1);
ca[i] := max(ca[i], cb[i - 1] + 1);
cb[i] := max(cb[i], ca[i - 3] + 1);
end;
end;
ans := ans + max(ca[DMAX + 2], cb[DMAX + 2]);
writeln(ans);
end.
Подзадачу 1 можно решить полным перебором подмножеств.
Подзадачу 2 можно решить простым жадным алгоритмом: двухтуровые олимпиады, которые не пересекаются с однотуровыми, сортируем по дню проведения. Берём первую олимпиаду и отбрасываем все пересекающиеся с ней. Далее берём следующую по-порядку и отбрасываем пересекающиеся с ней, и т. д.
Дорешивание задач будет доступно по адресу
http://atpp. vstu. edu. ru/acm
(в разделе "Задачи с соревнований" - "Школьные олимпиады Вологодской области).
