A. Counting Sheep

题意为对于给定的数N，找到最小的正整数i，使得N, 2N, 3N, ... , iN这i个数的各个数位里出现了0~9。

这是一道考察构造的题目，我们不妨设数N有M位，这M位是什么并不重要，就用XX...X进行表示。

现在关注第M+1位，由于倍数每次+1就相当于对当前数加上一个N，在加法中，进位只可能是1，也就是说在这个过程中，每加上一个N，第M+1位最多+1。

同时由于第M位大于0，所以在最坏情况下，每加上10个N，就必然发生进位，也就是说第M+1位就至少+1。

因此，每当对于当前数+N这个操作发生1~10次，第M+1位就必然+1，也就是说，在100次内，第M+1位就会从0变成9再变成0（进位至M+2位）。

因此我们可以得出结论：除了输入为0的情况，均有解，而且答案不超过输入的100倍（实际中一般10+倍就够了）

由于N最大10^6，所以我们可以用一个复杂度为O(N)，常数不超过100的算法进行求解。

B. Revenge of the Pancakes

题意为对于一叠有正反面的馅饼，每次可以选取从顶端开始的一定数量馅饼，并将他们作为一个整体翻转过来，问至少需要多少次操作才能够将所有馅饼翻至正面。

这同样是一道考察构造的题目，首先我们不妨看这些馅饼里连续的同面段（即一个区间内均为正面朝上或者反面朝上），不难发现如果将这些馅饼看作一张馅饼的话，得到的解不会差于其他解（简单证明：对任意最优解，将对于这个“同面段”里第一张馅饼的操作同时作用于整个同面段，所需要采用的步骤不会变多），也就是说一旦连续的一段馅饼在操作中变成同样的面向，那么在接下来的操作中就可以将它们看做一个整体进行处理。

所以所有的局面都变成了...-+-+-+...，因此我们可以用段数（即有多少段）和第一段的面向（正面朝上/反面朝上）来描述所有局面。

不妨用f(i, j)表示一共有i段，第1段面向为j（0为正，1为负）。

每次操作即为选择从头开始的若干段进行翻转，不难发现如果翻转的最后一段和第一段面向相同，那么对局面没有发生改变。

而翻转的最后一段和第一段面向不同，则段数减少1，第一段面向不变。

因此有f(i, j) = f(i - 1, j)

由于f(1, 0) = 0, f(1, 1) = 1，我们可以知道f(i, j) = i + j - 1。

从而我们只需要对于输入的状态，计算总段数和第一段的面向，就可以直接求解出需要进行多少次翻转了。

C. Coin Jam

题意为在N位字符串（字符集仅为{0, 1}，并要求首尾均为1）中，找出L个在任意2~N进制中均为合数的字符串。

这道题目主要考察数论、位运算和剪枝。

我们不妨首先来看看朴素算法，首先枚举这个N位字符串（O(2^(N-2))），然后在每种进制中（10的常数）中判断其是否为合数（O(2^(N/2-1)），是一个显然会超时的做法。

于是我们分阶段进行优化，首先，由于无论输入是16位还是32位，总共字符串的可能性都是相当多的，同时L最大为500，也就是说我们不需要严格判断每个数是否为合数，我们只需要能够大致判断一下（当然能判断出的合数需要一定是合数，但是不能将质数判断为合数）。

即我们用筛选法求出10000以内的质数，然后对于目标数字依次试除，如果成功了就能判断出这个数字是合数（同时也能提供最后需要的因数），这会在一定程度上漏掉一些合数，但是无关紧要，肯定可以凑齐L个。

其次，我们的目标是求L个解，那么一旦找到L个解了，就没有必要进行接下来的运算了。

最后，由于10^32是一个非常大的数字（64位整数也无能为力），我们可以在计算过程中进行取模运算（即利用取模运算的交换律和分配率），即需要判断字符串str在K进制中是否能够被质数P整除时，我们可以用如下方法进行计算：

s = 0, t = 1
for i = 字符串最后一位 to 1
    s = (s + t * str[i]) % p
    t = (t * k) % p
end

这样我们最后只需要判断s是否为0就能够知道是否能被P整除。

由于题目的输入是固定的，我们可以直接对N=16和N=32的情况，输出50/500个满足条件的字符串，然后直接提交即可。

D. Fractiles

题意为对于从原串（字符集为{L, G}）按照特定规则（K、C为参数）生成的字符串str，至少需要知道多少个位置的字符，才能够判断出原串中是否含有至少一个G。

这题主要考察对问题的分析以及多进制的技巧。

首先，我们令f(k1, k2, ... kc)表示在生成过程中，第i次拓展（G和L分别拓展，共C次）中由原串中第ki个字符串拓展，最后生成的字符，这将唯一的对应str中的一个字符，不难发现即为str[k1*k^(c-1)+k2*k^(c-2)+...+kc+1]。（形象一点看就是，在生成最后字符串str的树（就是题目里解释用的那个树），第i层选择第ki条边往下，最后走到的字符）

根据生成的拓展方式，不难发现，一旦由一个G字符进行拓展之后，最后的结果一定是G字符，即对于f(k1, k2, ..., kc)，如果原串中第k1, k2, ..., kc个字符中有一个字符G，那么f(k1, k2, ..., kc)=G。（即在树中经过一个G节点之后永远都是G了）

反之亦然，如果f(k1, k2, ..., kc)=G，那么说明原串中第k1, k2, ..., kc个字符中至少存在一个字符G。

因为，我们只需要查看f(0, 1, 2, ..., c - 1), f(c, c + 1, ..., 2c - 1), …… 一共K/C个位置的取值，就可以知道原串的第0, 1, 2, ... k-1个位置是否存在至少一个字符C。

综上所述，我们只需要判断K/C和S的大小关系，就可以至少是否有解，并在有解情况下，我们可以用f(0, 1, 2, ..., c - 1), f(c, c + 1, ..., 2c - 1), ……来构造出所有的解。