Презентация A. Another Game онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему A. Another Game абсолютно бесплатно. Урок-презентация на эту тему содержит всего 36 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:36 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:805.32 kB
- Просмотров:61
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: A. Another game
№2 слайд
Содержание слайда: A. Another Game
Аккуратно прочитать входные данные и выделить значимую часть, т.е. содержание тайлов без рамок
Выбрать из 4-х поворотов тайла Васи уникальные
Перебрать все позиции всех уникальных поворотов тайла внутри и на границе карты
Проверить выполнение требований условия
№3 слайд
Содержание слайда: B. BOMB HAS BEEN PLANTED
№4 слайд
Содержание слайда: B. Bomb Has Been Planted
Каким-либо алгоритмом (алгоритм Дейкстры, алгоритм Флойда, поиск в ширину) найти расстояния между вершинами (A,B), (A,C), (B,C)
Для разминирования над либо сначала пройти из C в A, затем из A в B, либо наоборот
Ответ на задачу:
№5 слайд
Содержание слайда: C. CSS IS AWESOME
№6 слайд
Содержание слайда: C. CSS is Awesome
Площадь исходного прямоугольника (без скругленных углов) равна
Посчитаем площадь недостающих частей прямоугольника:
№7 слайд
Содержание слайда: C. CSS is Awesome
Площадь каждого такого «куска» квадрата для скругления радиуса равна:
№8 слайд
Содержание слайда: D. Decompressing
№9 слайд
Содержание слайда: D. Decompressing
По «общему правилу» и «исключениям» построить таблицу – значение красоты для каждой пары яркостей
Сначала посчитаем значения С[i][j][k] –максимальное значение красоты растянутого отрезка, если исходный пиксель имел яркость i, отрезок начинается с пикселя яркости j и заканчивается пикселем яркости k
№10 слайд
Содержание слайда: D. Decompressing
Значения таблицы d1 не зависят от исходной картинки
Эти значения можно посчитать при помощи динамического программирования: для каждого значения k независимо заполним таблицу d1[m][sum][p] – максимальная возможная красота, если у нас осталось m (m <= K) позиций отрезка, суммарная яркость должна быть sum (sum <= K * 9) и последний пиксель имеет яркость p (p <= 9)
№11 слайд
Содержание слайда: D. Decompressing
Каждое значение таблицы можно пересчитать за 10 итераций, выбирая яркость следующего пикселя:
d1[m][sum][p] = max(d1[m-1][sum-p1][p1] +
bonus[p][p1])
Где p1 – яркость нового пикселя, а bonus[p][p1] – бонус красоты за соседние пиксели p и p1
№12 слайд
Содержание слайда: D. Decompressing
Получаем C[i][j][k] = d1[K-1][m*K-j][j] независимо для каждого k (не путать с K)
Общая сложность вычисления таблицы d1 – K*K*10*10*10 = K^2*1000
Теперь можно легко посчитать максимальный бонус красоты для данной текстуры
Бонусы красоты для строк считаются независимо
№13 слайд
Содержание слайда: D. Decompressing
Заведем другую таблицу: d2[m][p] – максимальный бонус, если осталось «растянуть» m пикселей и последний пиксель в растянутой текстуре имеет яркость p
Для каждой строки посчитаем эту таблицу независимо при помощи динамического программирования
№14 слайд
Содержание слайда: D. Decompressing
d2[m][p] = max(d2[m+1][p1] +
bonus[p][p2] +
C[S[m]][p2][p1])
по всем p1 и p2 от 0 до 9
S[m] – яркость пикселя, стоящего на месте m текущего ряда
№15 слайд
Содержание слайда: D. Decompressing
Тогда бонус красоты для текущей строки будет равен
max(d2[1][p1] + C[S[0]][p2][p1])
по всем p1, p2 от 0 до 9
Сложность вычисления этой таблицы для всех строк в сумме – N*M*10*10*10
№16 слайд
Содержание слайда: E. Equation
№17 слайд
Содержание слайда: E. Equation
Если , то решения не существует
В противном случае можно сделать так, чтобы и сумма, и произведение чисел равнялись 0
Например:
Все целые числа от 0 до
Число
№18 слайд
Содержание слайда: F. Formula 8
№19 слайд
Содержание слайда: F. Formula 8
Столкновение возникает, если за одно и то же время один участник проехал целое число восьмерок, а второй – целое и еще одну половину
№20 слайд
Содержание слайда: F. Formula 8
Моменты столкновений – решения уравнений:
№21 слайд
Содержание слайда: F. Formula 8
Рассмотрим одно из уравнений. Немного преобразуем его:
Столкновение возникает тогда и только тогда:
№22 слайд
Содержание слайда: G. Grab your seat!
№23 слайд
Содержание слайда: G. Grab your seat!
№24 слайд
Содержание слайда: G. Grab your seat!
Отсортируем за позиции в которых изначально находятся участники.
Будем перебирать позицию в которой в начинается группа занятых кресел, и позицию в которой заканчивается группа кресел. Если величина , то двигаем , в противном случае можем увеличить .
№25 слайд
Содержание слайда: G. Grab your seat!
№26 слайд
Содержание слайда: H. Heal
№27 слайд
Содержание слайда: H. Heal
Очевидно, битва закончится не позднее чем через:
Просто промоделируем течение времени
Обратите внимание: каждый персонаж выполнит действие в первую же секунду боя
№28 слайд
Содержание слайда: I. Is It Tetris
№29 слайд
Содержание слайда: I. Is It Tetris
Любая фигурка из четырех элементов – фигурка Тетриса
Достаточно посчитать количество связных фигурок размера четыре
Например, отмечать фигурки поиском в глубину
№30 слайд
Содержание слайда: J. Jump!
№31 слайд
Содержание слайда: J. Jump!
Рассмотрим граф, каждая вершина графа соответствует кувшинке в один из моментов времени t от 0 до 1000. Всего вершин.
Ребра в графе – допустимые прыжки между кувшинками
Необходимо написать алгоритм нахождения кратчайшего расстояния в невзвешенном графе. Например, с помощью поиска в ширину или Дейкстры.
№32 слайд
Содержание слайда: J. Jump!
Подводные камни:
Иногда надо подождать на берегу и прыгнуть первый раз на кувшинку после того как она всплывет не первый, а второй, третий и т.д. раз.
Необходимо нескольких секунд стоять на кувшинке.
Необходимо сделать шаг влево.
№33 слайд
Содержание слайда: K. Key number
№34 слайд
Содержание слайда: K. Key Number
Считать число как строку и вывести ее задом наперед.
См. задачу “B” пробного тура.
№35 слайд
Содержание слайда: L. Looking for Next String
№36 слайд
Содержание слайда: L. Looking for Next String
Следующей строки нет только для строки вида
zzzzz...zz
Найти самый правый не-Z, заменить его на следующий в алфавите, все, что правее заменить на A
Скачать все slide презентации A. Another Game одним архивом:
