Bolek 和 Lolek 正在玩一个名字听起来很本土的游戏,叫作 misie-patysie。要玩 misie-patysie,只需要有一些 misiów(小熊)以及同样数量不确定的 patysiów(小棍),它们一起构成游戏的池子。还需要选择一个任意的自然数,根据传统,这个数被称为 MP-限制。
第一步由 Bolek 执行,他可以从池子里拿走某个正数数量的 misiów 或 patysiów。他也可以同时拿小熊和小棍,但只有在两者数量相同且都大于零时才可以。当然,不能拿超过池子里现有数量的小熊——小棍也同理。此外,小熊和小棍都不能拿超过 MP-限制的数量。
接下来的行动依次轮流进行,并遵循相同的规则。胜利者是那个在他行动之后使池子变空的玩家。你的目标是帮助 Bolek 战胜 Lolek。
任务是编写一个模块,它在与适当的对局程序一起编译后,将作为 Bolek 进行对局。为完成此任务,你会得到一个简化的对局程序,它将允许你测试解法。你的模块应包含以下两个过程(函数):
• procedure poczatek (m, p, mpo : LongInt) 或 void poczatek (int m, int p, int mpo) 此过程(函数)在对局开始时只会被调用一次。你可以用它来初始化在对局期间需要的变量或数据结构。参数 m、p 和 mpo 分别包含池子中小熊的数量、小棍的数量,以及 MP-限制。池子中的小熊和小棍的数量总是正数且不超过 10⁷。MP-限制将是正数且不超过 10⁶。
• procedure ruch_bolka (m, p : LongInt; var bm, bp : LongInt) 或 void ruch_bolka (int m, int p, int bm, int bp) 此过程(函数)应确定 Bolek 的下一步行动。传递给它的参数 m 和 p 分别包含在 Lolek 最后一步行动后,池子里剩余的小熊和小棍数量。第一次调用 ruch_bolka 时传递的参数值与传给 poczatek 的对应参数值相同。在过程结束前,变量 bm、bp(或 C/C++ 中的 bm、bp)应分别包含 Bolek 从池子中拿走的小熊和小棍的数量。
你的模块不能打开任何文件,也不能使用标准输入/输出。如果你的程序执行了不允许的操作,例如 ruch_bolka 过程返回了一个不符合游戏规则的行动,它的运行将被终止。在这种情况下,你会在该测试中得到 0 分。
如果你的程序输掉对局,你将在该测试中得到 0 分。如果赢了,你将得到该测试的最高分。对于每个运行你程序的测试,Bolek 都可以获胜,而不依赖于 Lolek 的行动。
可用文件
Pascal
在目录 mis_pas 中你会找到以下文件:
- mis.pas —— 包含空的 poczatek 和 ruch_bolka 过程的对局模块框架。你应该编写这些过程的代码。
- graj.pas —— 简化的生成对局的程序。Lolek 的行动依据非常简单的策略进行,而 Bolek 的行动则通过调用对局模块 mis.pas 中的过程来确定。你可以使用此程序来测试你的对局模块。
C/C++
在目录 mis_c/mis_cpp 中你会找到以下文件:
- mis.h —— 包含 poczatek 和 ruch_bolka 函数声明的头文件。
- mis.c/mis.cpp —— 对局模块的框架,包含在头文件 mis.h 中声明的函数的空定义。你应该编写这些函数的代码。
- graj.c/graj.cpp —— 简化的生成对局的程序。Lolek 的行动依据非常简单的策略进行,而 Bolek 的行动则通过调用对局模块 mis.c/mis.cpp 中的过程来确定。你可以使用此程序来测试你的对局模块。
示例对局
对局可能按以下方式进行:
| 调用 | 说明 |
|---|---|
| poczatek(7, 2, 3) | 初始:7 小熊,2 小棍,MP-限制 = 3 |
| ruch_bolka(7, 2, bm, bp) | Bolek 拿 1 小熊 + 1 小棍 → 剩 6 小熊 1 小棍 |
| ruch_bolka(3, 1, bm, bp) | Lolek 拿走 3 小熊 → 剩 3 小熊 1 小棍 |
| ruch_bolka(3, 1, bm, bp) | Bolek 拿 1 小熊 → 剩 2 小熊 1 小棍 |
| ruch_bolka(1, 0, bm, bp) | Lolek 拿 1 小熊 + 1 小棍 → 剩 1 小熊 0 小棍 |
| ruch_bolka(1, 0, bm, bp) | Bolek 拿 1 小熊 → 游戏结束,Bolek 获胜 |