Фестиваль по информатике. Разбор задач 31 марта – 1 апреля 2013 года филиал МГУ им. М.В.Ломоносова в г. Ташкент

2 Квалификационный раунд. (31 марта)

3 Задача A. Счастливый год. Автор: Мирсаид Миролимжонов

4 Постановка задачи Необходимо найти количество целых чисел из отрезка [n, m], которые: 1) не делятся на 13 2) делятся на 3

5 Решение Переберем все целые числа из отрезка [n, m] Для каждого числа проверим делимость на 3 и 13 Примечание. Можно было, не перебирая числа, найти количество чисел, делящихся на 3 и делящихся на 39

6 Задача B. Опасные числа. Автор: Бехзод Солиев

7 Постановка задачи Необходимо найти количество пар целых чисел (x, y) из отрезка [n, m], для которых: НОД (x, y) = 1

8 Решение Переберем все пары целых чисел из отрезка [n, m] Для каждой пары проверим, что НОД чисел равен 1 (перебирая все возможные делители). Примечание. Для нахождения НОД можно было использовать алгоритм Евклида

9 Задача C. Необычный отрезок. Автор: Анастасия Быстрыгова

10 Постановка задачи На плоскости даны n точек A 1, … A n, m точек B 1, … B m, точка X и число е Найти количество способов выбрать точку A i и точку B k так, чтобы: Длины отрезков XA i и XB k были не больше e

11 Решение

12 Задача D. Секретная строка. Автор: Бехзод Солиев

13 Постановка задачи Изначально дана строка S Каждый символ a-z в строке заменяется на число 0-25 К каждому числу, двигаясь слева направо, прибавляется значение предыдущего по модулю 26 Каждое число 0-25 обратно заменяется на a-z Дана конечная строка C. Найти исходную строку S

14 Решение Выполним действия в обратном порядке: Заменим символы на числа От каждого числа, д вигаясь справа налево, отнимем значение предыдущего по модулю 26 Заменим числа на символы

15 Задача E. Зеркальный массив. Автор: Баходир Аширматов

16 Постановка задачи Дано N чисел a 1, … a N Поменяв порядок чисел a 1, … a N, получить N чисел b 1, … b N, чтобы: a k != b k для каждого k

17 Решение Разобьем числа на группы по их значениям Отсортируем группы по размеру, сохраняя индексы Сдвинем индексы на maxK, где maxK – размер максимальной группы Восстановим по индексам числа b 1, … b N

18 Более простое решение Будем генерировать случайную перестановку чисел, пока не найдем подходящую Примечание. Поскольку чисел всего не так много (N = 75), это будет работать

19 Финальный раунд. (1 апреля)

20 Задача A. Простая сумма. Автор: Бехзод Солиев

21 Постановка задачи Найти 1 + (1 + 2) + … + ( … + n) для заданного n

22 Решение Переберем целые числа от 1 до n, для каждого числа прибавим к сумме количество его вхождений

23 Задача B. Таинственные окружности. Автор: Бехзод Солиев

24 Постановка задачи Дано 2N окружностей с радиусами r 1, R 1 …, r N, R N Найти целую часть суммы площадей колец с радиусами (r k, R k )

25 Решение

26 Задача C. Неутомимый путешественник. Автор: Тимур Сытдыков

27 Постановка задачи Дана строка С перемещений путешественника Изначально путешественник находится в точке (0, 0) На каждом шаге k путешественник, находясь в точке (x, y) перемещается: 1) в точку (x, y + 1) если k-ый символ равен U 2) в точку (x + 1, y) если k-ый символ равен R Найти сумму x + y для всех точек (x, y), в которых путешественник побывал

28 Решение Заметим, что на каждом шаге сумма x + y увеличивается на 1 (арифметическая прогрессия) Тогда найдем длину len строки S Ответом будет len (len + 1)

29 Задача D. Виртуальные треугольники. Автор: Анастасия Быстрыгова

30 Постановка задачи Изначально дано N треугольников A 1 B 1 C 1, …, A N B N C N На середине каждой из сторон A k B k, B k C k и C k A k отмечены точки D k, E k и F k Необходимо по точкам D k, E k и F k найти точки A k, B k и C k

31 Решение

32 Задача E. Красивое число. Автор: Анастасия Быстрыгова

33 Постановка задачи Дано число N Найти количество способов вставить цифру в число N, чтобы оно делилось хотя бы на одно из чисел 3, 7, 11

34 Решение Переберем возможную позицию в числе N и цифру C для вставки Проверим делимость нового числа на 3, 7, 11

35 Задача F. Угадай число. Автор: Мирсаид Миролимжонов

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

37 Решение Единственная задача, в которой необходимо было сделать гарантированно 9 штрафных попыток Используем бинарный поиск: Каждый раз проверяем середину отрезка После ответа системы сжимаем отрезок в 2 раза (берем левую или правую часть)

38 Задача G. Волшебный треугольник. Автор: Бехзод Солиев

39 Постановка задачи Дан треугольник, состоящий из N строк, заполненный числами 1, 2, … сверху вниз: 1) если заполняется строка с нечетным номером, она заполняется слева направо 2) если заполняется строка с четным номером, она заполняется справа налево Найти сумму чисел, находящихся в i-ом столбце

40 Решение Последовательно заполним треугольник числами Найдем сумму чисел в i-ом столбце

41 Задача H. Пузырьковое перемешивание. Автор: Баходир Аширматов

42 Постановка задачи Даны N чисел a 1, …, a N Используя числа a 1, …, a N (числа должны остаться те же), получить числа b 1, …, b N, что: Сумма S = 1 * b * b 1 + …+ N * b N будет минимальной Найти это минимальное значение

43 Решение Отсортируем числа a 1, …, a N по убыванию Найдем сумму S Примечание. Данная сумма будет минимальной, так как любой обмен в расположении чисел будет давать сумму, которая больше либо равна данной

44 Задача I. Черно-белая матрица. Автор: Баходир Аширматов

45 Постановка задачи

46 Решение

47 Задача J. Хитрое вычеркивание. Автор: Анастасия Быстрыгова

48 Постановка задачи Даны N чисел a 1, …, a N и N чисел b 1, …, b N и число r Для каждого i (1

49 Решение Переберем все возможные 2 N вычеркиваний Для каждого вычеркивания найдем сумму и сравним ее с r

50 Более быстрое решение Решаем задачу при помощи задачи динамического программирования D[0][0] = 1, D[0][i] = 0 (i >= 0) D[i][k] = D[i - 1][k - a i ] + D[i - 1][k - b i ] Тогда ответом будет сумма значений D[N][j] (j >= 0)

51 Спасибо за внимание! Вопросы?