彩票球问题

Question

一名妇女在一家彩票工厂工作。她被指示打开一个彩票球创作工具包，由1个红色橡皮球和n条数字组成，从0到9。

她奉命做以下事情：

1. 从1开始，使用n条上可用的数字在球上写入当前数字。
2. 将未使用的数字放入碗中，在步骤1中，当她用完可用的数字时，可以使用这些数字。
3. 打开另一个彩票球创建工具包，并继续第1步为下一个号码。

问题是，在她没有数位来写数字之前，她会以什么数字来写数字？编辑:给定n是在每个彩票创建工具包中提供的从0到9的数字条带数，编写一个程序可以在最少的时间内解决这个问题(不是微不足道的)。

编辑:附加注释-6和9是不同的数字。假设可以粘贴在球上的数字数没有限制。

提示:如果她计算的是基数2而不是基数10，这将如何改变结果，这会更容易计算吗？你能从基2中的解中得到什么？

Answer 1

C

这里有一个C中的非高尔夫蛮力解决方案，它似乎给出了正确的答案1条，但我还没有耐心让它运行足够长的时间，看看它是否得到了一个解决方案2条(事实上，如果我外推进度输出，我不确定它是否会在我的生命周期内完成!)

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    const int MAX_DIGITS = 24;
    char buff[MAX_DIGITS + 1];
    int num_strips = 1;
    int64_t digits[10] = { 0 };
    int64_t i;

    if (argc > 1)
    {
        num_strips = atoi(argv[1]);
        if (num_strips < 1 || num_strips > 2)
        {
            fprintf(stderr, "num_strips must be 1 or 2\n");
            exit(1);
        }
    }

    memset(buff, ' ', MAX_DIGITS - 1);
    buff[MAX_DIGITS - 1] = '1';
    buff[MAX_DIGITS] = '\0';

    for (i = 1 ; ; ++i)
    {
        int d;

        // add 2 to each remaining digit count

        for (d = 0; d < 10; ++d)
        {
            digits[d] += num_strips;
        }

        // update counts of remaining digits based on current i

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            if (ch != ' ')
            {
                int digit = ch - '0';
                digits[digit]--;
            }
            else
            {
                break;
            }
        }

        // check to see whether we found solution

        for (d = 0; d < 10; ++d)
        {
            if (digits[d] < 0)
            {
                printf("Found solution at i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
                goto done;
            }
        }

        // log progress when i == 2^n

        if ((i & (i - 1)) == 0)
        {
            printf("i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
        }

        // increment "i"

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            switch (ch)
            {
                case ' ':
                    buff[d] = '1';
                    break;
                case '9':
                    buff[d] = '0';
                    continue;
                    break;
                default:
                    buff[d] = ch + 1;
                    break;
            }
            break;
        }
    }
done:
    return 0;
}