← 返回题目列表

AtCoder · kupc2014_g

G. 暗室

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

这个问题是一个反应型问题。 换句话说,你用响应程序玩游戏。

您的程序最初采用两个整数作为输入。 给出了 N 和 在 D 。 相比之下,长度 输出 N 的0/1列。 然后,响应程序将两个小矮人 Kyoko 和 Yui 放置在这一排上方的某个位置。京子此时的位置 i 并将 Yui 的位置设置为j。 而且,这个时候,杏子和唯也肯定会 距离为 D 。 (|i-j| = D )。 您始终可以知道哪些角色处于这两个位置。

在这些条件下,您将玩一个游戏来识别响应程序与 Kyoko 和 Yui 之间的位置关系。你对程序做出回应 通过命令,你可以将Kyoko或Yui一一向左或向右移动。由于两个人的初始位置都设置得距离队尾足够远,所以不需要考虑两个人中的一个人因为指令而从队尾跳出的情况。最后确定两个人的位置关系。 i < j 或 给出 j < i 输入响应程序。您只能输入一次位置关系。该命令总共最多可以执行 50 次,包括位置关系的输入。

尽可能少的动作 i < j 是吗? j < i。

入出力形式

首先,按以下格式给出输入。

N D

N是您将输出的 0/1 列的长度。 D是初始状态下两个人之间的距离。

在这些输入之后,首先输入长度 必须输出N的0/1列。 如果你的程序打印0/1列,那么两个人的初始位置将在响应程序中打印。 字符由系统确定,您可以输入 Kyoko 位置和 Yui 位置的字符。 我可以收到。例如,要在C/C++中输出长度为3的0/1列“011”, 如果

printf("011\n"); fflush(stdout);

。下一步

scanf("%d %d", &a, &b);

则变量a和b包含Kyoko初始位置的字符和Yui初始位置的字符。

此后,您可以将 Kyoko 或 Yui 向左或向右移动一步,次数不限,最多 50 次。 移动两个人后,您可以接收他们所在位置的字符作为输入。 例如,如果你想把 Kyoko 移到右边,

printf(“Move(A,1)\n”); fflush(stdout);
。接下来,
scanf(“%d %d”, &a, &b);
会将两个人位置上的人物放入变量a和b中。 另外,当将 Yui 向左移动时,
printf(“Move(B,-1)\n”); fflush(stdout);
。接下来,
scanf(“%d %d”, &a, &b);
两个人所在位置的字符将被存储在变量a和b中。

您可以发送六种类型的命令:

命令意味
移动(A,1)Kyoko 向右移动一位
移动(A,-1)将 Kyoko 向左移动一位。
移动(B,1)将 Yui 向右移动一位。
移动(B,-1)将 Yui 向左移动一位。
i<j确定 i < j
i>j确定 i > j
命令不得包含空格。

制約

  • 10000 \leq N \leq 100000
  • 1 \leq D \leq N-1
  • 所有输入值都是整数。
  • 包括位置关系输入在内,该命令总共最多可以执行 50 次。
  • 两个人的初始位置都设置得离队尾足够远,所以不需要考虑两个人中的一个人因为指令而从队尾跳出的情况。
  • 此问题的时限为6秒,但最大2秒度被响应程序用来确定两个人的初始位置。

採点方式

此问题的分数基于您对测试数据的最大指令数。C什么时候
  • C \leq 5 然后900点
  • C \gt 5 如果 900 / (C - 4) 点。

入出力例

説明プログラムの出力プログラムへの入力
あなたが出力する0/1列の長さと2人の間隔が与えられる10000 100
長さ10000の 0/1 列を出力する010101 … 010101
京子さんと結衣さんの位置の文字が返される0 1
京子さんを1つ右に動かすMove(A,1)
京子さんと結衣さんの位置の文字が返される1 1
結衣さんを1つ左に動かすMove(B,-1)
京子さんと結衣さんの位置の文字が返される1 0
京子さんの初期位置が結衣さんの初期位置より左にあったと確定するi<j