分析
首先考虑相邻柱子之间没有浮台。
记前 (m-1) 个盘子为 x, 第 (m) 个盘子为 y，有如下过程：(x ightarrow C, y ightarrow B, x ightarrow A, y ightarrow C, x ightarrow C) 。
写出递推式：(f(m)=f(m-1)+1+f(m-1)+1+f(m-1)) 。
将递推式展开，容易得到：(f(m-1)=3^{m-1}-1) 。
发现如果第 (X) 步要取 (m) 的话就只有两个位置，分别是 (X=3^{m-1}) 和 (X=2 imes 3^{m-1}) 。
什么时候可以取到 (m-1) ？考虑将递推式中的 (f(m-1)) 展开一层，容易发现当且仅当 (3^{m-2}|X) 且 (3^{m-1} mid X) 时，答案是 (m-1) 。所以可以直接用 (X) 不断整除三直到有余数，答案就是合法整除的次数+1。
实际有浮台可以转化成没有浮台，令两段为 L, R, 因为我们操作的序列一定形如 LRLRLRLR ，所以可以根据给定的 (X) 对 (n-1) 作除法得到的商和余数得到没有浮台模型下的步数。
复杂度 (O(q*len*30))，(len) 是大整数长度。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 1e3 + 7;
int n, m, k, q;
char s[N];
struct num {
int x[N], l;
num(){memset(x, 0, sizeof x); l = 0;}
num(int a){x[0] = a, l = 1;}
void read() {
scanf("%s", s);
l = strlen(s);
for(int i = 0; i < l; ++i) x[i] = s[l - i - 1] - '0';
}
pair<num, LL> operator /(LL f) {
num res;
LL rest = 0;
for(int i = l - 1; ~i; --i) {
rest = rest * 10 + x[i];
res.x[i] = rest / f;
if(!res.l && res.x[i])
res.l = i + 1;
rest %= f;
}
if(!res.l) res.l = 1;
return make_pair(res, rest);
}
num operator +(num rhs) {
num res;
for(int i = 0; i < min(rhs.l, l); ++i) res.x[i] = x[i] + rhs.x[i];
for(int i = min(rhs.l, l); i < max(rhs.l, l); ++i) {
if(l > i) res.x[i] += x[i];
if(rhs.l > i) res.x[i] += rhs.x[i];
}
res.l = max(rhs.l, l);
for(int i = 0; i < res.l; ++i) res.x[i + 1] += res.x[i] / 10, res.x[i] %= 10;
for(; res.x[res.l]; ++res.l) {
res.x[res.l + 1] += res.x[res.l] / 10;
res.x[res.l] %= 10;
}
return res;
}
}A, B;
int main() {
n = gi(), m = gi(), k = gi(), q = gi();
while(q--) {
A.read();
pair<num, LL> f = A / (n - 1);
B = f.first;
B = B + B;
if(f.second == 0);
else if(f.second < k) B = B + num(1);
else B = B + num(2);
int cnt = 1;
while(1) {
f = B / 3;
if(f.second == 0) ++cnt;
else break;
B = f.first;
}
printf("%d
", cnt);
}
return 0;
}