ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1044. Lucky Tickets. Easy!

Precalculate is not needed
Posted by Pearl 30 Sep 2018 18:01
#include <iostream>
using namespace std;

int sumDigit(int n) {
int sum = 0;
while (n) {
sum += n % 10;
n /= 10;
}
return sum;
}

int main()
{
int n;
cin >> n;
if (n % 2 == 1) {
cout << 0;
} else {
// We need to choose at most 4 digits, so the largest digit sum is 9*4
int count[9*4 + 1] = {0};
int halfN = n / 2;
int maxNum = 9;
for (int i = 1; i < halfN; ++i) {
maxNum *= 10;
maxNum += 9;
}
// Count the ways to create a particular sum
for (int i = 0; i <= maxNum; ++i)
++count[sumDigit(i)];

// Now, for each number i whose digit sum are s, there are
// count[s] numbers (including i itself) have the sum s.
// So we have count[s] ways to choose the second half.
int result = 0;
for (int i = 0; i <= maxNum; ++i)
result += count[sumDigit(i)];
cout << result;
}
return 0;
}