CF1093A Dice Rolling 题解

Content

有\(t\)次询问,每次询问给定一个\(x\),求某一个\(k\)使得\(\sum_{i=1}^ka_i=x(a_i\in[2,7]~\&~a_i\in \text{N}^*)\),并输出这个\(k\)。

数据范围:\(1\leqslant t\leqslant100,2\leqslant x\leqslant 100\)。

Solution

一开始看题我还以为是求最小的\(k\),结果一看样例输出,懵了,这到底是要求什么啊!!但后面看了题解才发现,是输出任何一个\(k\)都可以。那倒不影响,继续求最小的\(k\)。

我们可以发现,掷骰子掷\(7\)的次数越多,\(k\)就越小。

这结论是显摆着的,而关键又因为你可以指定掷到的点数,所以,我们可以通过最大化掷到\(7\)的次数,来最小化\(k\)。

具体是这样子的:

\(x\)如果能被\(7\)整除,那么答案就是\(x\div 7\),因为很容易想到一个方案——每次都掷中\(7\)。

否则,答案就是\(x\div 7+1\),因为很容易想到一个方案——前\(x\div7\)(整除)次都掷到\(7\),那么最后一次就再掷一个恰好能够到\(x\)的点数。

综上:

\[k=\begin{cases}x\div7&x\bmod7=0\\x\div7+1&x\bmod7\ne0\end{cases} \]

总的来说题目还是挺简单的。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

int t, x;

int main() {
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &x);
		if(!(x % 7))	printf("%d\n", x / 7);
		else	printf("%d\n", x / 7 + 1);
	}
	return 0;
}
上一篇:最大二叉树lt-654


下一篇:Yarp 让系统内调度更灵活