twarzo's blog

Spoj task
By twarzo, 11 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

misunderstood

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

http://pastebin.com/2jjauTrm

→ Reply