A. Another Game - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему A. Another Game. Доклад-сообщение содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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

Слайд 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

Теги Another Game

Похожие презентации