Блог пользователя twarzo

Автор twarzo, 12 лет назад, По-английски

Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.

Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.

Majid did finally find the solution. Now it is your turn, can you find a solution? Input

Two space-separated integers 0 <= a <= b <= 109.

Program terminates if a and b are -1. Output

The sum of the digits of numbers a through b. Example

Input: 1 10 100 777 -1 -1 Output: 46 8655

can anyone help me with this ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's dp problem. Let F(x) is the sum of digits of numbers 0 through x. answer = F(B) — F(A — 1). x = a[n — 1] * 10 ^ (n — 1) + ... + a[1] * 10 + a[0]. i.e. a[i] is i-th digit of number x. Let D(pos, digSum, constructedPrefixIsEqualToPrefixX) is answer to question "in how many ways we can put digits on positions 0, 1, ... pos, so the sum of digits is equal to digSum.

int dp[10][100][2];

int D(int pos, digSum, constructedPrefixIsEqualToPrefixX) {
	if (digSum < 0)
		return 0;
	if (pos == -1)
		return digSum == 0;
	int &res = dp[pos][digsum][constructedPrefixIsEqualToPrefixX];
	if (res != -1)
		return res;
	res = 0;
	int maxDigit = 9;
	if (constructedPrefixIsEqualToPrefixX)
	    maxDigit = a[pos];
	for (int digit = 0; digit <= maxDigit; ++digit)
		res += D(pos - 1, digSum - digit, constructedPrefixIsEqualToPrefixX && digit == a[pos]);
	return res;
}
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

misunderstood

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится