自动搬运

查看原文

来自洛谷，原作者为

	Alarm5854 Stop Smoking!

搬运于2025-08-24 21:25:00，当前版本为作者最后更新于2020-01-31 21:23:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题目是一道数论题。需要分类讨论。

当 $p\neq0$ 时，显然答案是 $\lceil\log_3n\rceil$，这是比较容易的，每一次想办法把它平均分成3份，若无法平均分成3份，就将其分为 $\lceil n/3\rceil,\lceil n/3\rceil,n-2\lceil n/3\rceil$，最坏情况下称量次数为$\lceil\log_3n\rceil$。

但是别想当然，当 $p=0$ 时，答案可不是 $\lceil\log_3n\rceil+1$ （我曾经这样想过，结果就听取WA声一片了），而是 $\lceil\log_3(2n+3)\rceil$，具体怎么证明如下（我参考了一位大佬写的博客）：
假如称一次就要找到有问题的那枚硬币，显然不可能，因为硬币要大等于3枚才可以称量。
假如称两次，只能3枚（左1，右1，余1），4枚硬币就不行了（左1，右1，余2，若左右两端平衡，则用左右两端的硬币和剩下的两枚硬币比较，先比较出轻重，接下来还要一次比较哪枚硬币出问题，要3次）。
假如称3次，左右两端最多可以各放4枚而不是3枚，因为只要有3枚标准硬币，就可以2次找到4枚硬币的问题所在，方法如下：左边放3枚标准硬币，右边放3枚可能存在问题的硬币，剩下一枚可能存在问题的硬币，若天平平衡，则问题显然出在那一枚硬币中，和标准硬币比较轻重即可，否则，可先知道轻重，问题转为知道轻重。所以3次最多可称12枚。
类似的，12枚标准硬币可以3次找到13枚硬币的问题，方法如上，所以称4次可称39枚硬币。以此类推，称 $x$ 次可找到 $\sum_{i=1}^{x-1}3^i=(3^x-1)/2-1=(3^x-3)/2$ 枚硬币，解 $3^x-3=2n$，可得 $x=\log_3(2n+3)$，由于要称整数次，所以要称 $\lceil\log_3(2n+3)\rceil$ 次。

然而，知道方法了，也不一定能 A（Python 党请无视），因为它还卡高精，暴力地运算的单次时间复杂度为 $O(k^2)$，看上去可以卡过 $(10000^2=10^8)$，但是这个毒瘤的出题人还设置了多组数据，总时间复杂度为 $O(Tk^2)$，就是这个可恶的 $T$，导致暴力地运算只能得 40~60 分（虽然 $T\le40$），只能另外想办法。我不会其他办法，就用压位高精，每一个压 9 位，这样优化了常数，时间复杂度为 $O(Tk^2/81)$，别小看这个 $81$，它可将速度提升了 $81$ 倍，使得这样做可以通过本题，当然，未吸氧时最慢的点跑了0.9s。上代码（有点压行）。

#include<bits/stdc++.h>
#define int long long//压9位，不开LL见祖宗
using namespace std;
const int base = 1000000000LL; int T;//每一位都小于10^9
const int pow18 = 387420489LL;//进一步优化常数，预处理出最接近10^9的3的n次幂的数，即3^18
FILE *fin, *fout;
struct bigint {
	int a[1122];//ceil(10000.0/9)=1112，所以数组稍微开大一点即可，a[0]储存位数
	bigint(){memset(a, 0, sizeof(a));}
	inline int& operator [](int n) {//重载[]运算符，之后方便写
		return a[n];
	}
	inline friend bool operator <(bigint a, int x) {//比较bigint和int的大小
		if (a[0] > 2) return 0; int y = 0;//由于这里出现的最大整数不超过10^18，所以可以这样做节省时间
		for (int i = a[0]; i; --i) y = y * base + a[i];//最多两位
		return y < x;
	}
	inline friend bigint operator +(bigint a, int x) {//高精加低精
		int i; a[i = 1] += x;//相当于i = 1, a[i] += x;
		while (a[i] >= base) ++a[i + 1], a[i] -= base, ++i;//处理进位
		if (i > a[0]) a[0] = i; return a;
	}
	inline friend bigint operator *(bigint a, int x) {//高精乘低精
		for (int i = 1; i <= a[0]; ++i) a[i] *= x;//先暂时不管进位，乘完以后再处理进位
		for (int i = 1; i <= a[0]; ++i) a[i + 1] += a[i] / base, a[i] %= base;//处理进位
		while (a[a[0] + 1]) ++a[0], a[a[0] + 1] += a[a[0]] / base, a[a[0]] %= base;//可能出现新的一位
		while (!a[a[0]]) --a[0]; return a;
	}
	inline friend bigint operator /(bigint a, int x) {//高精除低精
		for (int i = a[0]; i; --i) {
			if (i > 1) a[i - 1] += a[i] % x * base;
			a[i] /= x;//这一位除以x，下一位加上余数的10^9倍
		}while (!a[a[0]]) --a[0]; return a;
	}
	inline friend int operator %(bigint a, int x) {//高精对低精取余，返回值int即可
		int res = 0;
		for (int i = a[0]; i; --i) res = (res * base + a[i]) % x;
		return res;
	}
};
inline int read(int &x) {//快读和快写
	char c = 0; int f = x = 0;
	while (c < 48 || c > 57) {
		if (!~c) return 0;
		if (c == '-') f = 1; c = fgetc(fin);
	}
	while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
	if (f) x = -x; return 1;
}
inline int read(string &s) {
	s = "";
	char c = 0;
	while (c == 32 || c == 10 || c == 13 || c == 0) c = fgetc(fin);
	if (c == -1) return 0;
	while (!(c == 32 || c == 10 || c == 13 || c == 0 || c == -1)) s += c, c = fgetc(fin);
	return 1;
}
inline int read(bigint &x) {//压位高精最困难的地方就是读入，一定要小心，我有一次WA过
	string s; read(s);
	int len = s.length();if (s == "") return 0; x[0] = len / 9;
	if (len % 9) {//如果有多出来的一位，还要单独处理
		for (int i = 0; i < len % 9; ++i) x[x[0] + 1] = x[x[0] + 1] * 10 + s[i] - 48;
		s.erase(0, len % 9);//删掉前len%9位
	}
	for (int i = 0; i < x[0]; ++i)
		for (int j = 0; j < 9; ++j)
			x[x[0] - i] = x[x[0] - i] * 10 + s[i * 9 + j] - 48;//注意这里的下标是x[x[0]-i]，而不是x[i]
	if (len % 9) ++x[0]; return 1;//多出来的一位也要加上
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
	return read(x) + read(args...);
}
inline void write(int x) {
	if (x < 0) return putchar(45), (void)write(-x);
	if (x > 9) write(x / 10);
	fputc((x % 10) | 48, fout);
}
inline void write(char c) {
	fputc(c, fout);
}
inline int solve() {
	int k, p, flag = 0, res = 0;
	bigint n; read(k, p, n);
	if (!p) n = n * 2 + 3;//若p=0，则n=2n+3
	while (!(n < pow18)) res += 18, flag |= n % pow18, n = n / pow18;//先18个18个加，这里没有定义过>=，只能用!(n<pow18)
	while (!(n < 3)) ++res, flag |= n % 3, n = n / 3;//剩余部分一个一个加
	if (!(n < 2)) ++res; else if (flag) ++res; return res;//三行压成一行，其实也很容易理解，若最终结果大于1或有出现余数的，答案要加一
}
signed main() {
	#ifdef ONLINE_JUDGE//在评测机上使用标准输入输出，在本机上使用文件输入输出，方便读入
	fin = stdin;
	fout = stdout;
	#else
	fin = fopen("P1431.in", "rb");
	fout = fopen("P1431.out", "wb");
	#endif
	read(T); while (T--) write(solve()), write('\n');//这里再次压行，对于每组数据都要处理
	return 0;
}