A. Another Game

Содержание

Слайд 2

A. Another Game Аккуратно прочитать входные данные и выделить значимую часть,

A. Another Game

Аккуратно прочитать входные данные и выделить значимую часть, т.е.

содержание тайлов без рамок
Выбрать из 4-х поворотов тайла Васи уникальные
Перебрать все позиции всех уникальных поворотов тайла внутри и на границе карты
Проверить выполнение требований условия
Слайд 3

B. BOMB HAS BEEN PLANTED

B. BOMB HAS BEEN PLANTED

Слайд 4

B. Bomb Has Been Planted

B. Bomb Has Been Planted

 

Слайд 5

C. CSS IS AWESOME

C. CSS IS AWESOME

Слайд 6

C. CSS is Awesome

C. CSS is Awesome

 

Слайд 7

C. CSS is Awesome

C. CSS is Awesome

 

Слайд 8

D. DECOMPRESSING

D. DECOMPRESSING

Слайд 9

D. Decompressing По «общему правилу» и «исключениям» построить таблицу – значение

D. Decompressing

По «общему правилу» и «исключениям» построить таблицу – значение красоты

для каждой пары яркостей
Сначала посчитаем значения С[i][j][k] –максимальное значение красоты растянутого отрезка, если исходный пиксель имел яркость i, отрезок начинается с пикселя яркости j и заканчивается пикселем яркости k
Слайд 10

D. Decompressing Значения таблицы d1 не зависят от исходной картинки Эти

D. Decompressing

Значения таблицы d1 не зависят от исходной картинки
Эти значения можно

посчитать при помощи динамического программирования: для каждого значения k независимо заполним таблицу d1[m][sum][p] – максимальная возможная красота, если у нас осталось m (m <= K) позиций отрезка, суммарная яркость должна быть sum (sum <= K * 9) и последний пиксель имеет яркость p (p <= 9)
Слайд 11

D. Decompressing Каждое значение таблицы можно пересчитать за 10 итераций, выбирая

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 (не

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] – максимальный бонус, если осталось

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]) по всем

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]

D. Decompressing

Тогда бонус красоты для текущей строки будет равен
max(d2[1][p1] + C[S[0]][p2][p1])


по всем p1, p2 от 0 до 9
Сложность вычисления этой таблицы для всех строк в сумме – N*M*10*10*10
Слайд 16

E. EQUATION

E. EQUATION

Слайд 17

E. Equation

E. Equation

 

Слайд 18

F. FORMULA 8

F. FORMULA 8

Слайд 19

F. Formula 8 Столкновение возникает, если за одно и то же

F. Formula 8

Столкновение возникает, если за одно и то же время

один участник проехал целое число восьмерок, а второй – целое и еще одну половину
Слайд 20

F. Formula 8

F. Formula 8

 

Слайд 21

F. Formula 8

F. Formula 8

 

Слайд 22

G. GRAB YOUR SEAT!

G. GRAB YOUR SEAT!

Слайд 23

G. Grab your seat!

G. Grab your seat!

 

Слайд 24

G. Grab your seat!

G. Grab your seat!

 

Слайд 25

G. Grab your seat! Корректно! Корректно! Не корректно! Не корректно! Корректно! Не корректно! Корректно!

G. Grab your seat!

Корректно!

Корректно!

Не корректно!

Не корректно!

Корректно!

Не корректно!

Корректно!

Слайд 26

H. HEAL

H. HEAL

Слайд 27

H. Heal

H. Heal

 

Слайд 28

I. IS IT TETRIS

I. IS IT TETRIS

Слайд 29

I. Is It Tetris Любая фигурка из четырех элементов – фигурка

I. Is It Tetris

Любая фигурка из четырех элементов – фигурка Тетриса
Достаточно

посчитать количество связных фигурок размера четыре
Например, отмечать фигурки поиском в глубину
Слайд 30

J. JUMP!

J. JUMP!

Слайд 31

J. Jump!

J. Jump!

 

Слайд 32

J. Jump! Подводные камни: Иногда надо подождать на берегу и прыгнуть

J. Jump!

Подводные камни:
Иногда надо подождать на берегу и прыгнуть первый раз

на кувшинку после того как она всплывет не первый, а второй, третий и т.д. раз.
Необходимо нескольких секунд стоять на кувшинке.
Необходимо сделать шаг влево.
Слайд 33

K. KEY NUMBER

K. KEY NUMBER

Слайд 34

K. Key Number Считать число как строку и вывести ее задом

K. Key Number

Считать число как строку и вывести ее задом наперед.


См. задачу “B” пробного тура.
Слайд 35

L. LOOKING FOR NEXT STRING

L. LOOKING FOR NEXT STRING