从编程竞赛的问题......数字求和 [英] A problem from a programming competition... Digit Sums
问题描述
我需要帮助,从这个早期的竞争解决问题N:
I need help solving problem N from this earlier competition:
问题N:数字求和
由于3个正整数A,B和C, 发现有多少正整数少 大于或等于A,当EX pressed在 基地B,有位该笔款项为C。
Given 3 positive integers A, B and C, find how many positive integers less than or equal to A, when expressed in base B, have digits which sum to C.
输入将包括一系列 线,各含三个整数, A,B和C,2≤乙≤100,1≤A,C≤ 10亿。数字A,B和C 列于基座10和分离 由一个或多个空格。输入是 由线包含三个终止 零。
Input will consist of a series of lines, each containing three integers, A, B and C, 2 ≤ B ≤ 100, 1 ≤ A, C ≤ 1,000,000,000. The numbers A, B and C are given in base 10 and are separated by one or more blanks. The input is terminated by a line containing three zeros.
输出将是数字的数, 对于每个输入线路(它必须被给予 在基数为10)。
Output will be the number of numbers, for each input line (it must be given in base 10).
样品输入
100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0
示例输出
10
3
189
45433800
666303
有关的规则:
-
从键盘读取所有输入,即使用
标准输入
,System.in
,CIN
或同等学历。将输入从文件重定向到形成输入到您所提交。
Read all input from the keyboard, i.e. use
stdin
,System.in
,cin
or equivalent. Input will be redirected from a file to form the input to your submission.
写入所有输出到屏幕上,即使用标准输出
,的System.out
, COUT
或同等学历。不要写标准错误
。不要使用,甚至包括所有的模块,可以直接操控屏幕,如 conio
, CRT
或类似的话。从你的程序输出重定向到一个文件中供以后查看。使用直接I / O是指这样的输出不能重定向,因此不能进行检查。这可能意味着一个正确的程序被拒绝!
Write all output to the screen, i.e. use stdout
, System.out
, cout
or equivalent. Do not write to stderr
. Do NOT use, or even include, any module that allows direct manipulation of the screen, such as conio
, Crt
or anything similar. Output from your program is redirected to a file for later checking. Use of direct I/O means that such output is not redirected and hence cannot be checked. This could mean that a correct program is rejected!
除非另有说明,在输入的所有整数将适用于一个标准的32位计算机字。上的线相邻整数将被一个或多个空格分隔。
Unless otherwise stated, all integers in the input will fit into a standard 32-bit computer word. Adjacent integers on a line will be separated by one or more spaces.
当然,这是公平地说,我应该学会更试图解决过,但我真的AP preciate,如果有人在这里告诉我如何做。
Of course, it's fair to say that I should learn more before trying to solve this, but i'd really appreciate it if someone here told me how it's done.
在此先感谢,约翰。
推荐答案
其他人指出平凡解:遍历1的所有号码 A
。但这个问题,实际上,可以在几乎恒定的时间解决: 0(A的长度)
,这是 O(日志(A))
。
Other people pointed out trivial solution: iterate over all numbers from 1 to A
. But this problem, actually, can be solved in nearly constant time: O(length of A)
, which is O(log(A))
.
-
提供
- code是基地10适应它的任意基地实在是微不足道。
- 要达到上述估计的时候,你需要添加记忆以递归。让我知道,如果您有任何关于这部分的问题。
- Code provided is for base 10. Adapting it for arbitrary base is trivial.
- To reach above estimate for time, you need to add memorization to recursion. Let me know if you have questions about that part.
现在,递归函数本身。 Java编写的,但一切都应该在C#/ C ++,没有任何变化。这是很大的,但意见在那里我试图澄清算法,主要是因为。
Now, recursive function itself. Written in Java, but everything should work in C#/C++ without any changes. It's big, but mostly because of comments where I try to clarify algorithm.
// returns amount of numbers strictly less than 'num' with sum of digits 'sum'
// pay attention to word 'strictly'
int count(int num, int sum) {
// no numbers with negative sum of digits
if (sum < 0) {
return 0;
}
int result = 0;
// imagine, 'num' == 1234
// let's check numbers 1233, 1232, 1231, 1230 manually
while (num % 10 > 0) {
--num;
// check if current number is good
if (sumOfDigits(num) == sum) {
// one more result
++result;
}
}
if (num == 0) {
// zero reached, no more numbers to check
return result;
}
num /= 10;
// Using example above (1234), now we're left with numbers
// strictly less than 1230 to check (1..1229)
// It means, any number less than 123 with arbitrary digit appended to the right
// E.g., if this digit in the right (last digit) is 3,
// then sum of the other digits must be "sum - 3"
// and we need to add to result 'count(123, sum - 3)'
// let's iterate over all possible values of last digit
for (int digit = 0; digit < 10; ++digit) {
result += count(num, sum - digit);
}
return result;
}
辅助功能
// returns sum of digits, plain and simple
int sumOfDigits(int x) {
int result = 0;
while (x > 0) {
result += x % 10;
x /= 10;
}
return result;
}
现在,让我们写一个小测试
Now, let's write a little tester
int A = 12345;
int C = 13;
// recursive solution
System.out.println(count(A + 1, C));
// brute-force solution
int total = 0;
for (int i = 1; i <= A; ++i) {
if (sumOfDigits(i) == C) {
++total;
}
}
System.out.println(total);
您可以编写多个COM prehensive测试仪检查A的所有值,但整体解决方案似乎是正确的。 (我试了随机A的和C的。)
You can write more comprehensive tester checking all values of A, but overall solution seems to be correct. (I tried several random A's and C's.)
不要忘了,你不能为测试解决方案A == 10亿
无记忆:它会运行过久。但随着记忆,你可以测试它甚至 A == 10 ^ 1000
。
Don't forget, you can't test solution for A == 1000000000
without memorization: it'll run too long. But with memorization, you can test it even for A == 10^1000
.
修改
只是为了证明一个概念,穷人的记忆。 (在Java中,在其他语言哈希表的声明有所不同),但是如果你想学习的东西,它可能是更好的尝试自己做。
edit
Just to prove a concept, poor man's memorization. (in Java, in other languages hashtables are declared differently) But if you want to learn something, it might be better to try to do it yourself.
// hold values here
private Map<String, Integer> mem;
int count(int num, int sum) {
// no numbers with negative sum of digits
if (sum < 0) {
return 0;
}
String key = num + " " + sum;
if (mem.containsKey(key)) {
return mem.get(key);
}
// ...
// continue as above...
// ...
mem.put(key, result);
return result;
}
这篇关于从编程竞赛的问题......数字求和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!