题目描述

茨韦蒂（Цвети）花了大量时间制作播放列表。凭借这么多经验，她觉得只听到自己某个播放列表中的几首任意歌曲，就能够认出这个播放列表。为了测试这一能力，她玩如下一个游戏：

起初，茨韦蒂会得到以下参数：

• $N$：需要创建的播放列表数量。播放列表编号为 $0$ 到 $N-1$；
• $K$：每个播放列表中必须包含的歌曲数；
• $S$：可用的不同歌曲总数。歌曲编号为 $0$ 到 $S-1$；
• $P$：一个介于 $0.1$ 到 $0.95$ 之间的小数，表示要求达到的识别准确率。

之后，茨韦蒂需要使用这 $S$ 首歌曲，创建 $N$ 个播放列表，每个播放列表恰好包含 $K$ 首歌曲。同一首歌在一个播放列表中可以出现多次。

创建好播放列表后，会进行许多轮游戏。每一轮按如下形式进行：

1. 随机选择一个播放列表，并将其中的歌曲顺序随机打乱。茨韦蒂既不知道被选中的是哪个播放列表，也不知道打乱后的歌曲顺序；
2. 茨韦蒂开始试听该播放列表。她可以试听从 $0$ 首到全部 $K$ 首歌曲中的任意数量。在任意时刻，她都可以结束本轮，并猜测当前隐藏播放列表的编号。

游戏总共进行恰好 20 000 轮（因为她真的有很多空闲时间）。

若被正确识别的播放列表所占比例至少为 $P$，则认为茨韦蒂赢得了游戏。也就是说，至少要正确识别 $\lceil 20000 \times P \rceil$ 轮。

但这对茨韦蒂来说太容易了，所以她不只想赢，还想尽可能快地赢。一局游戏的得分定义为：在猜对播放列表的那些轮次中，平均试听歌曲的数量。
猜错的轮次不计入这一平均值。

请你帮助茨韦蒂，编写程序 playlists.cpp 代替她进行游戏。该程序将与评测程序一起编译。

实现细节

这是一个提交函数题 / 通信题。

你需要实现两个函数。

第一个函数 makePlaylists 的原型为：

std::vector<std::vector<int>> makePlaylists(int n, int k, int s, double p);

该函数只会在任何对另一个函数的调用开始之前被调用一次。传入参数即为题目中的 $N,K,S,P$。
函数需要返回你设计的播放列表，返回值应为一个长度为 $N$ 的列表，其中每个元素又是一个长度为 $K$ 的列表，且内部所有值都必须是 $0$ 到 $S-1$ 之间的整数。

第二个函数 guessPlaylist 的原型为：

int guessPlaylist();

评测程序每调用一次该函数，就表示一轮新游戏开始。
该函数应返回一个 $0$ 到 $N-1$ 之间的整数，表示你对当前隐藏播放列表编号的猜测。
播放列表的编号，按照 makePlaylists 返回时的顺序确定。
对每个测试，guessPlaylist 都会被调用恰好 20 000 次。

在每一轮中，你还可以调用评测程序提供的函数 nextSong：

int nextSong();

该函数返回当前轮次中、被随机打乱后的隐藏播放列表的下一首歌。
在一轮之内，你的程序最多只能调用该函数 $K$ 次。若在同一轮中调用超过 $K$ 次，将被视为错误。
该函数时间复杂度为 $O(1)$。

你的程序必须实现 makePlaylists 和 guessPlaylist，但不能包含 main 函数；同时不能从标准输入读取数据，也不能向标准输出打印内容。
程序还必须通过预处理指令包含头文件：

#include "playlists.h"

只要满足以上条件，你的程序可以包含任意辅助函数、变量、常量等。

数据范围

• $1 \le N, K \le 100$
• $2 \le S \le N$
• $0.1 \le P \le 0.95$

保证给定的 $N,K,S,P$ 总是存在可行策略，使游戏能够获胜。

评分规则

每个测试点单独评分。

要获得该测试点的分数，正确识别的播放列表比例必须至少为 $P$，也就是说，在全部 20 000 轮中，至少要有 $\lceil 20000 \times P \rceil$ 轮识别正确。

设：

• $Q$ 为你的程序在识别正确的轮次中平均试听歌曲数；
• $T$ 为作者程序在该测试点中的同一指标。

则：

• 如果 $Q \le T$，你将获得该测试点的满分；
• 否则，你将获得该测试点分数的 $\dfrac{Q}{T}$。

注：以上评分规则按原题面表述保留。

注意： 你在本题中的最终得分，等于你所有提交中成绩最好的一次。

本地测试

题目提供 playlists.h 和 Lgrader.cpp，可以与你的程序一起编译进行本地测试。
运行程序时，需要输入 $N,K,S,P$。随后你的程序会执行，并输出得分，或在发生错误时输出错误说明。

样例通信

序号	playlists 的行为	评测程序的行为与返回	说明
1	{{0, 1}, {1, 1}, {2, 2}}	makePlaylists(3, 2, 3, 0.5)
2		guessPlaylist()	评测程序选择播放列表 0，并打乱为 {1, 0}
3	nextSong()	return 1
4		return 0
5	return 0		在试听 2 首歌后，正确识别该播放列表
6		guessPlaylist()	评测程序选择播放列表 2，并打乱为 {2, 2}
7	nextSong()	return 2
8	return 2		在试听 1 首歌后，正确识别该播放列表
9		guessPlaylist()	评测程序选择播放列表 0，并打乱为 {0, 1}
10	nextSong()	return 1
11	return 1

样例通信说明

样例中总共进行了 3 轮，而真实测试中固定为 20 000 轮。
在这 3 轮中，有 2 轮正确识别了播放列表，因此成功率为 $\dfrac{2}{3} \approx 0.67$，高于要求的 $P=0.5$，因此该测试被成功通过。

由于只统计识别正确轮次中的试听次数，因此这个方案在成功轮次中平均试听歌曲数为：

$$\frac{1+2}{2} = 1.5$$

如果作者程序在该测试中的平均试听歌曲数为 $1$，则该方案将获得：

$$\frac{1}{1.5} \approx 67\%$$

的测试点分数。