Tetris
Interview Prep 2018
Time Limit: 10s, Memory Limit: 128MiB
Въпреки (а може би поради) огромната си популярност, малко хора знаят, че играта Тетрис е създадедна от руснаци. Целта в нея е да се нареждат падащи фигури в двуизмерна дъска (наречена "кладенец").

Ели е решила да покаже на своите приятели колко е добра, като постигне невиждани до сега рекорди в играта. Разбира се, да стои и играе по цял ден би било нетипично за нея, затова тя решава да напише изкуствен интелект, който играе вместо нея. Какво по-добро от това да подобряваш рекорди докато си на шопинг? От вас се иска да напишете сходен изкуствен интелект.

Дори никога да не сте играли Тетрис, това не е проблем – това няма да ви навреди по никакъв начин (изкуственият интелект може да бъде много по-умен от който и да е човек). Ако сте играли играта, все пак прочетете правилата, тъй като за удобство ще ползваме по-лесна нейна версия.

Точки

За разлика от оригиналната игра, спечелените точки тук ще бъдат зависими от броя на фигурите, които сте успели да поставите преди да загубите. Ако успеете да поставите всички фигури - печелите (и, съответно, взимате максимален брой точки за дадения тест).

Дъска

Играта се играе на дъска с двадесет реда и десет колони (тоест, кладенецът е два пъти по-дълбок, отколкото широк).

Фигури

Както и в оригиналната игра, ще ползваме седем различни фигури, всяка от които се състои от четири блокчета (от където идва и името на играта – гръцкия числов префикс tetra-, означаващ "четири"). Седемте фигури изглеждат по следния начин:
Tetris Figurines
Видът на фигурите при ротация 0.

Фигурите също така можем да представим и чрез ASCII арт:
Фиг. 1 Фиг. 2 Фиг. 3 Фиг. 4 Фиг. 5 Фиг. 6 Фиг. 7
# # # # ## # # ## # # ## ## # ## # # ## # # ## #

Ротации

Всяка от фигурите може да бъде ротирана нула, един, два или три пъти на 90 градуса по часовниковата стрелка (забележете, че четвърта ротация би дала оригиналната фигура за всяка от тях).

Падане на фигура

Фигурите падат една по една - във всеки момент пада по точно една фигура, а останалите "чакат" в опашка някъде извън дъската. Когато дойде ред на някоя фигура, тя се поставя над кладенеца (тоест извън дъската). Играчът избира как да бъде ротирана тя и над коя колона да бъде поставена най-лявата ѝ част. След това фигурата "пада" вертикално надолу докато някое от четирите ѝ блокчета срещне под себе си дъното на кладенеца или някое друго, вече паднало блокче. Забележете, че позицията на фигурата трябва да бъде избрана по такъв начин, че тя да падне в кладенеца (тоест да не излиза отляво или отдясно на него). Ако след падането и евентуалните последвали изтривания фигурата се "подава" отгоре на кладенеца, играта свършва.

Изтриване на ред

Ако след падането на някоя фигура един или повече реда се "напълнят" – тоест и в десетте им колони има блокче на фигура – блокчетата в тези редове изчезват. Това се прави във всички такива редове едновременно преди да се продължи нататък.

Компоненти

След изтриване на ред е възможно да останат блокчета, висящи "във въздуха" (тоест досегашната им подпора е била изтрита). Те се разделят на свързани компоненти, като две блокчета са в една компонента ако от едното може да се достигне до другото през други блокчета, като се "местим" в съседни блокчета наляво, надясно, нагоре или надолу. Погледнете примера малко по-долу за пояснение.

Падане на компонента

След изтриване на един или няколко реда, всички останали "във въздуха" компоненти започват да падат едновременно надолу по същите правила както и фигурите – докато някое тяхно блокче не срещне под себе си дъното на кладенеца или друга, вече статична компонента.

Край на играта

Играта свършва когато някоя от поставените фигури излиза отгоре на кладеница (не е в двадесетте реда на дъската) след падането си и последвалите изтривания. Играта също така свършва и при невалиден ход на играча или при поставяне на всички фигури.

Информация за фигурите

За разлика от оригиналната игра, тук играчът знае предварително всички фигури (колко и кои са те, а също така в какъв ред падат).

Пример

За пояснение на горните правила нека разгледаме следния пример (показани са само най-долните десет реда от кладенеца):
Стъпка 1 Стъпка 2 Стъпка 3 Стъпка 4
" 2 " " 2 " " 22 " "11 3 " "11 333" "1 33 " "11 33 " "111 33333" "111 333333" "111 3 3333" " " " " " " "11 3 " "11 333" "1 2 33 " "11 2 33 " "1112233333" "111 333333" "111 3 3333" " " " " " " "11 5 " "11 555" "1 4 55 " "11 4 55 " " " "222 333333" "222 3 3333" " " " " " " " " "11 5 " "11 555" "1 55 " "11 55 " "2224333333" "22243 3333"
Блокчетата на различните компоненти в нечетните стъпки са отбелязани с различни цифри. В четните стъпки компонентите са различни, но цифрите са запазени за яснота кое къде се е спряло.
Стъпка 5 Стъпка 6 Стъпка 7 Стъпка 8
" " " " " " " " "11 4 " "11 444" "1 44 " "11 44 " " " "22222 3333" " " " " " " " " " " "11 4 " "11 444" "1 44 " "11 44 " "22222 3333" " 33 " " 33 " " " " " " " "11 2 " "11 222" "1 22 " "11 22 " "11111 2222" " " " " " " " " " " "11 2 " "11 222" "1 33 22 " "1133 22 " "11111 2222"
Забележете, че след падането на компонентите в стъпка 3, в стъпка 4 отново се образува пълен ред, който бива премахнат в стъпка 5. Това продължава докато всички компоненти се наместят без да има нов ред за изтриване. След това играта продължава със следващата фигура, както е показано в стъпка 7.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броят фигури, които ще паднат. На втория ред ще бъдат зададени N цели числа между 1 и 7 включително, разделени с интервали – фигурите, които ще паднат, в реда на тяхното падане.
Изход
На стандартния изход изведете N двойки цели числа. Първото число от всяка двойка трябва да е между 0 и 3, включително, задавайки колко пъти фигурата е ротирана, а второто трябва да е между 0 и 9, включително, задавайки в коя колона се намира най-лявото блокче от ротираната фигура. За ротация 0 считайте фигурите, както са показани по-горе.
Оценяване
Ако вашето решение е поставило
X
фигури преди играта да свърши, а най-добрият резултат за този тест от някой от участниците е
Y
фигури, то вие ще получите
(X / Y)2 * 10.0
точки. Така, например, ако сте поставили 72 фигури, а най-добрият резултат е 97, то вие ще вземете
(72 / 97)2 * 10 = 5.51
точки за съответния тест.
Ограничения
  • 1 ≤ N ≤ 100,000
  • Фигурите ще се падат на случаен принцип.
Примерен Вход Примерен Изход
20 2 7 6 4 7 3 6 6 4 6 3 4 2 1 1 1 5 7 4 2 2 1 0 0 0 0 3 0 2 4 1 7 0 6 1 7 0 6 3 7 2 3 0 2 0 5 1 8 2 4 2 4 2 4 2 4 2 4 2 4
Първите 12 фигури образуват дъската от примера. 14-тата фигура е сложена по такъв начин, че излиза "отдясно" на дъската, което е невалиден ход - следователно играчът е направил 13 хода преди да загуби.

Първите 11 хода:
"   B      "
"   B      "
"   BB     "
"44      A "
"44     AAA"
"3     99  "
"33    99  "
"321  57888"
"221 557786"
"211 5 7666"
Мрън!