#P17918. Easy Tetris
Easy Tetris
Easy Tetris
在一个宽度为 、高度无限的棋盘上玩俄罗斯方块,棋盘初始为空。接下来按照给定顺序落下 个方块,只有以下两种形状:
I:高 、宽 的竖直长条。O:高 、宽 的实心正方形。
棋盘的列从左到右编号为 到 。每个方块落下前,你选择它的横向位置:I 可以放在任意一列;O 的左侧列可以是 到 中的任意一列。
方块随后竖直下落,直到碰到棋盘底部或已有方块。不能旋转方块,不能在下落过程中横向移动,也不能拆分方块。落定后,方块覆盖的格子全部被填满。注意,O 落在高度不同的两列上方时,可能在下方留下空洞。
某一行的 个格子全部被填满时,这一行会被消除,其上方的所有格子向下移动一格。同一次落块形成的所有满行会同时消除。
如果一次落块恰好同时消除 行,称为获得一次 tetris,得分加 。消除其他数量的行不增加得分。
求最大可能得分,并输出一种达到最大得分的落块方案。
输入格式
第一行一个整数 ,表示方块数量。
第二行一个长度为 、只包含 I 和 O 的字符串,依次描述方块类型。
输出格式
第一行输出一个整数,表示最大得分。
第二行输出 个整数 :
- 若第 个方块为
I, 为它所在的列,要求 。 - 若第 个方块为
O, 为它的左侧列,要求 。
输出的方案必须实际获得第一行声明的最大得分。有多种最优方案时,可以输出任意一种。
数据范围
。每个输入文件只有一组数据。
样例
10
IIOIOIOOII
1
1 2 3 5 3 6 7 7 9 10
样例输出只是一种最优方案。