Score : $500$ points

问题描述

在_ABC Confiserie_担任糕点师的高桥决定制作蛋糕来庆祝AtCoder Beginner Contest 200。

高桥制作的每款蛋糕有三个参数：美观度（beauty）、口感（taste）和受欢迎程度（popularity），每个参数都由一个介于$1$到$N$（包含两端点）之间的整数表示。

对于每组三元组 $(i,j,k)\ (1 \le i,j,k \le N)$，他已经制作了一个美观度为$i$、口感为$j$、受欢迎程度为$k$的蛋糕。然后，他将这$N^3$个蛋糕按照如下规则排列成一排：

• 蛋糕从左至右按美观度、口感和受欢迎程度之和升序排列。
• 对于两个总和相同的蛋糕，美观度较小的蛋糕位于左侧。
• 对于两个总和相同且美观度也相同的蛋糕，口感较小的蛋糕位于左侧。

请找出从左边数第$K$个蛋糕的美观度、口感和受欢迎程度。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi, a pastry chef at ABC Confiserie, has decided to make cakes to celebrate AtCoder Beginner Contest 200.

A cake made by Takahashi has three parameters: beauty, taste, and popularity, each of which is represented by an integer between $1$ and $N$ (inclusive).

He has made a cake of beauty $i$, taste $j$, and popularity $k$ for every triple $(i,j,k)\ (1 \le i,j,k \le N)$.
Then, he has arranged these $N^3$ cakes in a row, as follows:

• The cakes are in ascending order of sum of beauty, taste, and popularity from left to right.
• For two cakes with the same sum of beauty, taste, and popularity, the cake with the smaller beauty is to the left.
• For two cakes with the same sum and the same beauty, the cake with the smaller taste is to the left.

Find the beauty, taste, and popularity of the $K$-th cake from the left.

Constraints

• All values in input are integers.
• $1 \le N \le 10^6$
• $1 \le K \le N^3$

Input

Input is given from Standard Input in the following format:

$N$ $K$

Output

Print three integers representing the cake's beauty, taste, popularity, in this order, with spaces in between.

Sample Input 1

2 5

Sample Output 1

1 2 2

The cakes are in the following order:

$(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)$.

Here, each triple of integers represents the beauty, taste, and popularity of a cake.

Sample Input 2

1000000 1000000000000000000

Sample Output 2

1000000 1000000 1000000

The values in input may be large.

Sample Input 3

9 47

Sample Output 3

3 1 4

update @ 2024/3/10 09:12:09