Тренировки

2 комментария
Подписаться на комментарии к посту

Важное объявление - в эту субботу личная тренировка, тем кто сможет - быть с ноутбуками.

Разбор задач.

А. Пронумеруем клетки начиная с угла (0,0). Заметим что клетки с номерами вида (3 * к, 3 *л) не могут соседствовать с одной и той же миной, а значит мин должно быть как минимум upper_round(n/3) * upper_round(m/3). Заметим также что ровно столько мин нам и хватит (ставя жадно в клетки с номерами (min(3 к + 1, n), min(3 л +1, m) ) где к бегает в пределах 0..upper_round(n/3)-1, а л в пределах 0.. upper_round(m/3)-1

B. Возьмем в качестве отметок все точки и их противоположные, отсортируем. Для первой точки из списка найдем сумму расстояний, а так же количество тех что находятся на левой полудуге(l) от нее и на правой(r), теперь двигаемся покругу между соседними отметками сумма расстояний изменяется на (r-l) * длину дуги, а точка задающая эту отметку после этого меняет свое состояние (переходит из lв rили наоборот). Пройдя все точки найдем минимум.

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

D. Получаем ответ динамикой пусть c[1,1] = 1 (биномиальный коэффициент), ans[1,1] = 1 (наилучший ответ если мы находимся в данной позиции). Остальные клетки нули. Заполняем c[i][j] = c[i-1][j-1]+c[i-1][j], ans[I,j] = max(ans[i-1,j], ans[i-1,j-1]) + sum_digits(c[i][j]). А потом находим наилучший ответ для максимальной строки.

E. Если угол от центра до точки на окружности до точки вне окружности острый – то пересекает иначе нет. Проверить это можно скалярным произведением.

F. Заметим что одна из сторон прямоугольников должна совпадать со стороной квадрата и это максимальная по длине сторона. Находим прямоугольник с максимальной стороной mесли с такой же макс стороной ещё два прямоугольника то проверяем что сумма оставшихся равна mиначе проверяем что сумма двух тех же сторон равна mа две другие совпадают и в сумме со стороной первого прямоугольника также дают m. (Или можно аккуратно нарисовать на листочке все случаи.

G. Нужно отсортировать все числа по убыванию и посчитать суммы на позициях дающих остаток 1 или 0 по модулю 4 первому игроку, а иначе второму, сравнить суммы и вывести ответ.

H. пусть загаданы числа s*2^kи s*2^(k+1) где S - нечетное. Если игрок не может в начале определить число другого, значит его число как минимум четное (иначе он может сразу сказать). Если теперь второй не может определить – значит его число делиться на 4 (иначе он уже знал что у первого не может быть ни нецелого числа ни нечетного а значит однозначно бы сказал какое у него) и так далее. Соответственно если на i-ом шагу степень вхождения двойки у игрока <iто он отгадывает число. Осталось вычислить ответ.

I. храним массив для каждой команды с длинной наибольшей цепочки в конце которой данная команда и последний матч который приводит к такой цепочке, а также для каждого матча предыдущий матч приводящий к наибольшей цепочке. Поочередно добавляем матчи пытаясь обновить и максимизировать ответ (то есть если ответ для текущей команды меньше чем ответ для ее соперника +1, то мы его обновляем, пишем для его предка текущее значении в ячейке для соперника  и обновляем предка для данной команды). В конце находим максимальную цепочку и по третьему массиву восстанавливаем ответ.

J. если nили m n*m(легкозаполнить все клетки и стрелять вне поля) иначе 2*(n+m) – 4. Так как в каждой строке/столбце не более двух снайперов стреляющих по горизонтали/по вертикале. Плюс для крайних рядов если есть стреляющий в этом ряду вертикально то в столбце где он стоит не может стоять снайпер стреляющий в его направлении.

K. Считаем число крестиков и ноликов xи o, должно выполняться oxo+1. Для каждых 5 соседних клеток смотрим нет ли там ряда крестиков или ноликов и если есть добавляем в эти клетки (в отдельный массив) по 1 а к win_xи win_oединицу соответственно. Далее проверяем что если win_x > 0, то x = o+1, win_o = 0 и существует клетка в отдельном массиве которую мы прибавляли win_xраз. Ну и аналогично если win_o = 1.

L. Посчитаем в скольких различных строка муравьи движутся горизонтально hи в скольких вертикально v. Тогда для двух противоположных граней число посещенных клеток h*n + v*n– h*v, для двух боковых h*nа для двух других v*nосталось просуммировать.

M. В начале для каждой хорошей клетки предпосчитаем сколько от нее вправо (вместе с ней) хороших клеток. Hor[I,j] Теперь динамика если a[I,j] = 1 то ans[I,j]=0 иначе ans[i][j] = ans[i-1][j]+hor[i,j].

N. Если даны три середины то отражениями находим ответ. Иначе запускаем в цикл, если на каком-то ребре есть хотя бы две вершины, то находим третью. Если мы при таких операциях сделали круг и не обновили вершины то их невозможно установить.

O. Каждая цифра от 0 до 9 на j-ой позиции попадет в сумму 10^(n-1) раз, а значит ответ 45*n*10^(n-1)

P. Нужно понять, что если копы на расстоянии 3 они ловят за 1 ход Хуссейна, если же не 3, то в худшем случае они его поймать не могут. Так что оптимальная стратегия разойтись на расстояние 3 а потом поймать его -> нужно 7 – 2*nходов

Q. В конце расстояние между фигурами станет 0, после каждого хода оно меняет четность, таким образом тот после чего хода расстояние становится четным только и может выиграть, осталось заметить что ему всегда это удастся (он может постепенно уменьшать расстояние между собой и соперником.)

R. Заметим что в начале игроки обязаны брать кучки по единичке, после этого тот чей будет ход выигрывает (так как для каждой кучки он может брать все камни кроме одного а второму придется добирать этот камень) – таким образом ответ четность числа единичек, а первых ход это или 1(если минимальная кучка 1) или min-1.

S. Нужно вычесть числа (например можно отдельно считать знаки и числа и реализовать вычитание или сложение в нужном типе)

 

T. Так как все переменные различны достаточно посчитать число запятых в строке +1  и тип строки и просуммировать по типам.