查看原文
其他

[C++] Lucky Tickets

2016-12-14 Y叔 biobabble

幸运票被定为前半部分数字总和等于后半部分,比如数字1172344493278

1 + 1 + 7 = 2 + 3 + 4 = 9 4 + 4 + 9 = 2 + 7 + 8 = 17   (3 is ignored)

如果个数是奇数的,中间的数字被忽略。


数字不一定是10进制的,可以是各种各样的B进制,题目给定数字的位数N和进制B,求解所有的幸运票,比如N是6,而B是10,那么要求出区间[000000, 999999]所有幸运票的数目。


实例如下:

input data: 4 1 5 4 3 5 2 6 10 answer: 5 19 12 55252


像最后一个,答案已经超过5万个,显然遍历是很耗时的,特别当我们需要求解很多个不同的NB组合时。


#include <iostream>
#include <fstream>
#include <sstream>
#include <string>


unsigned long long int count_lucky(int N, int B);
int plus1_sum(int* digits, int N, int B, int sum);

int main() {
  std::ifstream infile("data/id109.txt");
  std::string line;
  getline(infile, line);
  std::stringstream ss(line);
  int n;
  ss >> n;

  int N, B;
  for (int i=0; i<n; i++) {
    getline(infile, line);
    std::stringstream NB(line);
    NB >> N;
    NB >> B;
    std::cout << count_lucky(N, B) << " ";
  }
  std::cout << std::endl;
}


主程序很简单,读了N和B,用count_lucky求解,并打印结果。


这个问题的重点在于,要求前后两部分,我们知道,其实取值的各种组合是一样的,所以只要求解前半部分就可以了。


所以呢,我定义了:

int plus1_sum(int* digits, int N, int B, int sum) {
  digits[N-1]++;
  sum++;
  for (int i=N-1; i>0; i--) {
    if (digits[i] >= B) {
      digits[i] -= B;
      digits[i-1]++;
      sum = sum - B + 1;
    } else {
      break;
    }
  }
  return sum;
}

这里digits是长度为N的向量,而这里的N是要求解的NB的N/2,也就是我们只看前半部分,函数很简单,通过每次加1来遍历所有数字,每一次都记录数字的总和sum。


然后count_luck可以登场了:


unsigned long long int count_lucky(int N, int B) {
  int n = N/2;
  if (n == 0)
    n = 1;
  int* digits = new int[n];
  int size = 1;
  for (int i=0; i<n; i++) {
    digits[i] = 0;
    size *= B;
  }

  int max = n*(B-1) +1 ;
  int* sum_cnt = new int[max];
  for (int i=1; i<max; i++) {
    sum_cnt[i] = 0;
  }
  sum_cnt[0] = 1;

  int i=0;
  int sum = 0;
  while(++i < size) {
    sum = plus1_sum(digits, n, B, sum);
    sum_cnt[sum]++;
  }

  unsigned long long int cnt = 0;
  for (i=0; i<max; i++) {
    cnt += sum_cnt[i] * sum_cnt[i];
  }
  if (N % 2 == 1 && N > 1)
    cnt *= B;
  return cnt;
}

遍历了前半部分,记录下了所有数字加和的个数,比如说前半部分有和为X的组合Y个,那么后半部分也会有和为X的组合Y个,所以前半部分和为X以及后半部分和也为X的组合就应该是Y^2,所以呢cnt += sum_cnt[i] * sum_cnt[i];就算出来总数。但这里还有一个问题,如果是数字位数是奇数,那么中间可以是0:(B-1)的任意数,所以还需要cnt*B.


这里我们只遍历了前半部分,次数是B^(N/2),试想一下,如果遍历所有,次数是B^N次方,B^N/B^(N/2) = exp(N/2 * log(B)),这时间差距可是指数增长。

https://v.qq.com/txp/iframe/player.html?vid=f13114lvr7z&width=500&height=375&auto=0
程序员的日常生活就是各种试错,这视频让无数人躺枪有没有!👻

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存