Матч 431, Мегахолодные числа, простая (MegaCoolNumbersEasy)

Дивизион 2, Уровень 1

Положительное число называется мегахолодным, если его цифры образуют арифметическую прогрессию. Найти количество мегахолодных чисел от 1 до n включительно.

Класс: MegaCoolNumbersEasy

Метод: int count(int n)

Ограничения: 1 £ n £ 1000.

Вход. Натуральное число n.

Выход. Количество мегахолодных чисел от 1 до n.

Пример входа

n

1

110

500

Пример выхода

1

99

119

РЕШЕНИЕ

перебор

Сгенерируем все мегахолодные числа, не большие 1000, после чего подсчитаем, сколько их не больше n. Все одно- и двузначные числа являются мегахолодными. Единственное четырехзначное число 1000 не является мегахолодным. Остается найти все трехзначные мегахолодные числа. Число является мегахолодным, если b – a = c – b.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

vector<int> v;

class MegaCoolNumbersEasy

{

public:

int count(int n)

{

int i, a, b, c;

for(i = 1; i < 100; i++) v.push_back(i);

for(a = 1; a <= 9; a++)

for(b = 0; b <= 9; b++)

for(c = 0; c <= 9; c++)

if (b - a == c - b) v.push_back(100 * a + 10 * b + c);

v.push_back(1111);

for(i = 0; i < v.size(); i++)

if (v[i] > n) return i;

}

};