← 返回题目列表

Codeforces · 679/A

A. 熊和 Prime 100

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

这是一个交互问题。在下面的输出部分中,您将看到有关刷新输出的信息。

Bear Limak 想到了一些隐藏的数字——区间 [2, 100] 中的一个整数。你的任务是判断隐藏的数字是质数还是合数。

如果整数 x > 1 恰好有两个不同的约数 1 和 x,则该整数称为素数。如果整数 x > 1 不是质数,则称为合数。

您最多可以询问 20 个有关隐藏数字除数的查询。在每个查询中,您应该打印区间 [2, 100] 中的一个整数。如果您的整数是隐藏数字的除数,系统将回答“是”。否则,答案将是“不”。

例如,如果隐藏数字是 14,则仅当您打印 2、7 或 14 时系统才会回答“是”。

完成查询后,打印“prime”或“composite”并终止程序。

如果您询问超过 20 个查询,或者打印不在 [2, 100] 范围内的整数,您将得到错误答案判决。此外,如果打印的答案不正确,您将得到错误答案的判决。

如果您不打印任何内容(但您应该)或者忘记刷新输出(更多信息如下),您将得到空闲限制超出的判决。

输入

每次查询后,您应该从输入中读取一个字符串。如果打印的整数是隐藏数字的除数,则为“是”,否则为“否”。

输出

您最多可以询问 20 次 - 在一行中打印区间 [2, 100] 中的一个整数。您必须打印行尾字符并刷新输出。刷新后,您应该从输入中读取响应。

您可以随时打印答案“质数”或“复合数”(不带引号)。之后,刷新输出并终止程序。

要刷新,您可以使用(在打印整数和行尾之后):

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

黑客攻击。要破解某人,您应该打印隐藏的数字作为输入 - 区间 [2, 100] 中的一个整数。当然,他/她的解决方案将无法从输入中读取隐藏的数字。

示例

输入 #1

yes
no
yes

输出 #1

2
80
5
composite

输入 #2

no
yes
no
no
no

输出 #2

58
59
78
78
2
prime

注意

第一个查询中的隐藏数字是 30。在下表中,您可以看到所提供的通信过程示例的更好形式。

$$\begin{数组}{|c|c|}
\hline
\text{解决方案} & \text{系统} \\
\hline
2 & \text{是} \\
80 & \text{否} \\
5 & \text{是} \\
\hline
\text{复合} & \\
\hline
\end{数组}$$

隐藏数字可以被 2 和 5 整除。因此,它必须是合数。请注意,无需知道隐藏数字的确切值。在本次测试中,隐藏数字为 30。

$$\begin{数组}{|c|c|}
\hline
\text{解决方案} & \text{系统} \\
\hline
58 & \text{否} \\
\hline
59 & \text{是} \\
\hline
78 & \text{否} \\
\hline
78 & \text{否} \\
\hline
2 & \text{否} \\
\hline
\text{prime} & \\
\hline
\end{数组}$$

59 是隐藏数字的除数。在区间 [2, 100] 中只有一个数字具有该除数。隐藏的数字必须是 59,它是质数。请注意,即使在第二个查询之后答案也是已知的,您可以打印它并终止。不过,并不禁止提出不必要的查询(除非您超过 20 个查询的限制)。