Уроки информатики
<<  Методическая разработка урока информатики в 1 классе Уроки информатики  >>
Фестиваль по информатике
Фестиваль по информатике
Квалификационный раунд
Квалификационный раунд
Задача A. Счастливый год
Задача A. Счастливый год
Постановка задачи
Постановка задачи
Решение
Решение
Задача B. Опасные числа
Задача B. Опасные числа
Постановка задачи
Постановка задачи
Решение
Решение
Задача C. Необычный отрезок
Задача C. Необычный отрезок
Постановка задачи
Постановка задачи
Решение
Решение
Задача D. Секретная строка
Задача D. Секретная строка
Постановка задачи
Постановка задачи
Решение
Решение
Задача E. Зеркальный массив
Задача E. Зеркальный массив
Постановка задачи
Постановка задачи
Решение
Решение
Более простое решение
Более простое решение
Финальный раунд
Финальный раунд
Задача A. Простая сумма
Задача A. Простая сумма
Постановка задачи
Постановка задачи
Решение
Решение
Задача B. Таинственные окружности
Задача B. Таинственные окружности
Постановка задачи
Постановка задачи
Решение
Решение
Задача C. Неутомимый путешественник
Задача C. Неутомимый путешественник
Постановка задачи
Постановка задачи
Решение
Решение
Задача D. Виртуальные треугольники
Задача D. Виртуальные треугольники
Постановка задачи
Постановка задачи
Решение
Решение
Задача E. Красивое число
Задача E. Красивое число
Постановка задачи
Постановка задачи
Решение
Решение
Задача F. Угадай число
Задача F. Угадай число
Постановка задачи
Постановка задачи
Решение
Решение
Задача G. Волшебный треугольник
Задача G. Волшебный треугольник
Постановка задачи
Постановка задачи
Решение
Решение
Задача H. Пузырьковое перемешивание
Задача H. Пузырьковое перемешивание
Постановка задачи
Постановка задачи
Решение
Решение
Задача I. Черно-белая матрица
Задача I. Черно-белая матрица
Постановка задачи
Постановка задачи
Решение
Решение
Задача J. Хитрое вычеркивание
Задача J. Хитрое вычеркивание
Постановка задачи
Постановка задачи
Решение
Решение
Более быстрое решение
Более быстрое решение
Спасибо за внимание
Спасибо за внимание

Презентация: «Фестиваль по информатике». Автор: Fedor Tsarev. Файл: «Фестиваль по информатике.ppt». Размер zip-архива: 796 КБ.

Фестиваль по информатике

содержание презентации «Фестиваль по информатике.ppt»
СлайдТекст
1 Фестиваль по информатике

Фестиваль по информатике

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

2 Квалификационный раунд

Квалификационный раунд

(31 марта)

2

3 Задача A. Счастливый год

Задача A. Счастливый год

Автор: Мирсаид Миролимжонов

3

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

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

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

4

5 Решение

Решение

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

5

6 Задача B. Опасные числа

Задача B. Опасные числа

Автор: Бехзод Солиев

6

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

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

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

7

8 Решение

Решение

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

8

9 Задача C. Необычный отрезок

Задача C. Необычный отрезок

Автор: Анастасия Быстрыгова

9

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

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

На плоскости даны n точек A1, … An, m точек B1, … Bm, точка X и число е Найти количество способов выбрать точку Ai и точку Bk так, чтобы: Длины отрезков XAi и XBk были не больше e

10

11 Решение

Решение

11

12 Задача D. Секретная строка

Задача D. Секретная строка

Автор: Бехзод Солиев

12

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

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

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

13

14 Решение

Решение

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

14

15 Задача E. Зеркальный массив

Задача E. Зеркальный массив

Автор: Баходир Аширматов

15

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

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

Дано N чисел a1, … aN Поменяв порядок чисел a1, … aN, получить N чисел b1, … bN , чтобы: ak != bk для каждого k

16

17 Решение

Решение

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

17

18 Более простое решение

Более простое решение

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

18

19 Финальный раунд

Финальный раунд

(1 апреля)

19

20 Задача A. Простая сумма

Задача A. Простая сумма

Автор: Бехзод Солиев

20

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

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

Найти 1 + (1 + 2) + … + (1 + 2 + … + n) для заданного n

21

22 Решение

Решение

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

22

23 Задача B. Таинственные окружности

Задача B. Таинственные окружности

Автор: Бехзод Солиев

23

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

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

Дано 2N окружностей с радиусами r1, R1 …, rN, RN Найти целую часть суммы площадей колец с радиусами (rk, Rk)

24

25 Решение

Решение

25

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

Задача C. Неутомимый путешественник

Автор: Тимур Сытдыков

26

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

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

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

27

28 Решение

Решение

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

28

29 Задача D. Виртуальные треугольники

Задача D. Виртуальные треугольники

Автор: Анастасия Быстрыгова

29

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

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

Изначально дано N треугольников A1B1C1, …, ANBNCN На середине каждой из сторон AkBk, BkCk и CkAk отмечены точки Dk, Ek и Fk Необходимо по точкам Dk, Ek и Fk найти точки Ak, Bk и Ck

30

31 Решение

Решение

31

32 Задача E. Красивое число

Задача E. Красивое число

Автор: Анастасия Быстрыгова

32

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

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

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

33

34 Решение

Решение

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

34

35 Задача F. Угадай число

Задача F. Угадай число

Автор: Мирсаид Миролимжонов

35

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

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

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

36

37 Решение

Решение

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

37

38 Задача G. Волшебный треугольник

Задача G. Волшебный треугольник

Автор: Бехзод Солиев

38

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

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

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

39

40 Решение

Решение

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

40

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

Задача H. Пузырьковое перемешивание

Автор: Баходир Аширматов

41

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

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

Даны N чисел a1, …, aN Используя числа a1, …, aN (числа должны остаться те же), получить числа b1, …, bN, что: Сумма S = 1 * b1+ 2 * b1 + …+ N * bN будет минимальной Найти это минимальное значение

42

43 Решение

Решение

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

43

44 Задача I. Черно-белая матрица

Задача I. Черно-белая матрица

Автор: Баходир Аширматов

44

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

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

45

46 Решение

Решение

46

47 Задача J. Хитрое вычеркивание

Задача J. Хитрое вычеркивание

Автор: Анастасия Быстрыгова

47

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

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

Даны N чисел a1, …, aN и N чисел b1, …, bN и число r Для каждого i (1 <= i <= N) можно вычеркнуть либо ai, либо bi После этого все не вычеркнутые числа сложили вместе Найти количество способов получить сумму, которая не больше r

48

49 Решение

Решение

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

49

50 Более быстрое решение

Более быстрое решение

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

50

51 Спасибо за внимание

Спасибо за внимание

Вопросы?

51

«Фестиваль по информатике»
http://900igr.net/prezentacija/informatika/festival-po-informatike-234168.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды