← 返回题目列表

AtCoder · rco_contest_2019_final_a

A. 翻转并对齐

中文机器翻译题面 查看原题

問題文

这个问题采用互动形式。

X 是 我喜欢参加神経衰弱和跑马拉松。 有一天,X决定玩一种结合神经崩溃和长跑的新游戏。

\(1\) \( \lfloor N/2 \rfloor \) 准备大量写有整数的牌,经过Shiyafuru后,会将牌堆叠朝向后方,形成一叠。

牌组等间隔水平排列,从左开始是牌组\(0, 1, \cdots, N-1\)。

X 在牌堆中移动,当他看到两张连续的具有相同值的牌时,他将它们成对地移除以得分。

游戏开始时,X 位于牌组顶部 \(0\),他的初始得分为 \(0\)。

X可以在不超过它可以移动的总距离\(T\)的范围内重复执行以下一系列操作。

  • 设 \(p\) 为运算开始时包含 X 的牌组的编号。
  • 如果牌组顶牌 \(p\) 面朝上,则其整数为 \(a_p\)。
  • (这副牌\(p\)的顶牌在第一次操作期间以及在被下述对子移除后立即移动时面朝下。)
  • 从牌组 \(q ( 0 \leq q \leq N-1) \) 中选择一张牌,并将其从牌组 \(p\) 移动到牌组顶部 \(q\)。 (\(q = p\) 也是可以接受的。)在这种情况下行驶的距离是 \(|p - q|\)。
  • 将这副牌最上面的一张牌 \(q\) 面朝上,并让该牌上写的整数为 \(a_q\)。
  • 如果两张正面朝上的牌具有相同的值,则成对地取出牌,并获得等于牌上写的整数的分数。换句话说,如果 \(p \neq q\) 和 \( a_p = a_q \),则从牌堆顶部 \(p, q\) 一张一张地移走牌,并将 \(a_p\) 添加到你的分数中。取出一张牌后,每副牌的顶部总会有一张面朝下的新牌。
  • 如果一对无法移除,并且有两张面朝上的牌,则第一张面朝上的牌将面朝下。换句话说,当 \(p \neq q\) 时,这副牌 \(p\) 的顶牌面朝下。

移动X,使X得到的分数尽可能大。

每个测试用例和该问题的分数计算如下:

  • 在一个测试用例中,X得到的总分就是分数。
  • 所有测试用例都是 有 50 件。每个测试用例的总分就是该题的得分。

入出力

首先,输入是从标准输入按以下格式给出的:

\(N\) \(T\)
  • N 是一个整数,表示这副牌中的牌数,N = 50 满意。
  • T 是一个整数,表示可以行驶的总距离,T = 10000 满意。
  • 为了方便程序判断,请务必阅读标准输入的内容。

从现在开始,重复以下与判断程序的交流。

1. 将整数输出到标准输出。

\(q\)
  • 移动 X 时,输出表示 X 移动到的牌组编号的整数 \((0 \leq q \leq N-1)\)。
  • 退出游戏 输出-1并退出程序。
  • 如果您移动的距离超过了您可以移动的总距离,这将是一个错误答案。
  • 请务必在输出后添加换行符并刷新。

2. 对于 \(q \neq -1\),从标准输入给出一个整数。

\(a_q\)
  • a_q 表示写在这副牌 \(q\) 顶牌上的整数 \((1 \leq a_q \leq N/2)\)。
  • 为了方便程序判断,请务必阅读标准输入的内容。

关于测试用例生成

每张卡上写入的整数是根据统一的随机数生成的。


入出力例

程序的输入 程序输出 説明 股票信息 移動
総距離
分数
4 6
表示牌组中有4张牌,总可移动距离为6。
此样本不满足约束 \(N=50\) 和 \(T=10000\)。
? ? ? ? 0 0
0
移至牌组 0 并将顶牌翻面朝上。
最初,X 位于甲板 0 的顶部,因此行进的距离为 0。
? ? ? ? 0 0
1
在牌组顶部 0 有一张卡片写着1。 1 ? ? ? 0 0
2
移动到卡座 2。从卡座 0 移动到卡座 2 的距离为 2。 1 ? ? ? 2 0
2
在甲板 2 的顶部是 有一张卡片写着2。 \(a_0 \neq a_2\) 因此,之前牌面朝上的牌组 0 的顶牌将面朝下。 1 ? 2 ?
↓
? ? 2 ?
2 0
1
移动到甲板 1。从甲板 2 到甲板 1 的移动距离为 1。 ? ? 2 ? 3 0
2
第 1 副牌的顶部有一张标记为 2 的牌。
\(a_1 = a_2 = 2\) 因此,从牌组 1 和牌组 2 中取出牌并获得 2 分。
通过从牌组 1 和牌组 2 中移除牌,您将无法辨别每组牌的顶部是哪张牌,除非您再次将其正面朝上。
? 2 2 ?
↓
? ? ? ?
3 2
1
将当前牌组 1 的顶牌翻为正面朝上。 ? ? ? ? 3 2
2
第 1 副牌的顶部有一张标记为 2 的牌。
您可能会得到与之前相同的整数。
? 2 ? ? 3 2
2
从卡座 1 移动到卡座 2。 ? 2 ? ? 4 2
1
在牌 2 的顶部有一张标记为 1 的牌。 ? 2 1 ?
↓
? ? 1 ?
4 2
0
从卡座 2 移动到卡座 0。 ? ? 1 ? 6 2
1
在这副牌的最上面 0 是一张写有数字 1 的牌(我们已经从它被翻过一次的事实知道),并且由于满足条件,我们将它成对地移走并得到 1 分。 1 ? 1 ?
↓
? ? ? ?
6 3
-1
退出游戏。如果您尝试进一步移动,则会超出您可以移动的总距离,并将被视为错误答案。 ? ? ? ? 6 3

测试仪

可从以下链接获取。

测试仪