ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1044. Счастливые билеты. Easy!

Precalculate is not needed
Послано Pearl 30 сен 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;
}