QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB Total points: 100

#13112. 哲学家漫步

Statistics

在编程之地,有几条被称为“哲学家漫步”(Philosopher’s Walk)的路径,供哲学家们休憩。哲学家漫步是一条位于正方形区域内的路径,区域内绿意盎然。这些树林有助于哲学家思考,但他们种得太密,以至于哲学家在树林中迷了路。

幸运的是,所有哲学家漫步的结构都很相似;哲学家漫步的结构是根据 $2^k$ 米边长的正方形区域内的相同规则设计和建造的。设计该路径的规则是:当 $k=1$ 时,每走 1 米后向右转 90 度;对于大于 1 的整数 $k$,则以分形方式由 4 个子路径构成。图 F.1 展示了 $k$ 分别为 1、2 和 3 时的三条哲学家漫步路径。哲学家漫步 $W_2$ 由 4 个 $W_1$ 结构组成,其中左下角和右下角的结构分别顺时针和逆时针旋转了 90 度;上方的结构与 $W_1$ 具有相同的结构。对于任何大于 1 的整数 $k$,其对应的 $W_k$ 也是如此。这一规则由数学家大卫·希尔伯特(David Hilbert,1862–1943)提出,由此产生的路径通常以他的名字命名为希尔伯特曲线(HILBERT CURVE)。他曾谈到使用这种曲线填充 $2^k$ 边长的正方形的空间填充方法,每一条哲学家漫步路径都是根据这种方法设计的。

图 F.1:大小分别为 $2^1=2$,$2^2=4$ 和 $2^3=8$ 的三条哲学家漫步路径。

泰川(Tae-Cheon)负责营救在哲学家漫步路径中迷路的哲学家,他使用热气球进行搜救。幸运的是,每位迷路的哲学家都可以向泰川报告他所走的米数,泰川知道哲学家漫步路径的边长。他必须确定迷路哲学家的位置,即假设哲学家漫步路径放置在笛卡尔平面的第一象限,且每个单位长度为一个方格,求出其 $(x, y)$ 坐标。假设左下角方格的坐标为 $(1, 1)$。哲学家漫步的入口始终在 $(1, 1)$,出口始终在 $(n, 1)$,其中 $n$ 是边长。同时假设哲学家在入口处时已经走了一米,并且他总是向前走向出口,不会后退。

例如,如果迷路哲学家在图 F.1(b) 所示的 $W_2$ 路径中走的米数为 10,则你的程序应报告 $(3, 4)$。

你的任务是编写一个程序,帮助泰川根据迷路哲学家所走的米数和哲学家漫步路径的边长,报告该哲学家的位置。快点!哲学家急需你的帮助。

输入格式

程序从标准输入读取数据。输入包含一行,包含两个正整数 $n$ 和 $m$,分别表示哲学家漫步路径的边长和迷路哲学家所走的米数,其中 $n = 2^k$,且 $m \le 2^{2k}$,其中 $k$ 为满足 $0 < k \le 15$ 的整数。

输出格式

程序将结果写入标准输出。输出应包含两个整数 $x$ 和 $y$,中间用空格分隔,其中 $(x, y)$ 是该哲学家在给定哲学家漫步路径中的位置。

样例

样例输入 1

4 10

样例输出 1

3 4

样例输入 2

8 19

样例输出 2

2 6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.