#P17745. 果实摘取

果实摘取

题目描述

小D的家门口有一片果树林,果树上果实成熟了,小D想要摘下它们。

为了便于描述问题,我们假设小D的家在二维平面上的(0,0)(0,0)点,所有坐标范围的绝对值不超过NN的整点坐标上都种着一棵果树。((0,0)(0,0)这个点没有果树)

小D先站在(0,0)(0,0)处,正对着(1,0)(1,0)的方向。

每次摘果实时,小D会逆时针选择他能看到的第KK棵还未摘取果实的果树,然后向着这个方向走去,在行走的过程中摘下沿路的所有的果树上的果树果实,直到走到果树林的边缘。

接下来,小D回到(0,0)(0,0)处,正对着上一次摘果实的果树的方向。

小D会重复这个过程,直到所有的果实都被摘取,小D感兴趣的是,最后一棵被摘下果实的果树是哪一棵?

注意小D不能看到被任何其他果树遮挡着的果树。

输入格式

从标准输入读入。

一行两个整数,N,KN,K,意义见题面。

输出格式

输出到标准输出。

一行两个整数,表示最后一棵被摘下果实的果树的坐标。

样例1输入

2 2

样例1输出

2 0

样例解释

第一圈后摘下果实的树的情况:(数字表示被摘下的时间)

*  3  *  2  *
4  *  *  *  1
*  *  0  *  *
5  *  *  *  8
*  6  *  7  *

整个果树林被摘下的情况:

12 3  18 2  10
4  11 17 9  1
22 21 0  23 24
5  13 19 15 8
14 6  20 7  16

所以最后一棵被摘下的果树为(2,0)(2,0)

样例2输入

10 4

样例2输出

-8 -6

样例3输入

12345 67890

样例3输出

11299 1509

数据范围和约定

对于10%10\%的数据,N≤8N \leq 8

对于30%30\%的数据,N≤500N \leq 500

对于另外20%20\%的数据,K=2K=2

对于100%100\%的数据,1≤N,K≤1051 \leq N,K \leq 10^5

原题面:day1.pdf,第 7–8 页。