Матч 403, Счастливые числа (TheLuckyNumbers)

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

Цифры 4 и 7 являются счастливыми, а остальные – нет. Число называется счастливым, если оно содержит только счастливые цифры. Определить количество счастливых чисел в интервале от a до b включительно.

Класс: TheLuckyNumbers

Метод: int count(int a, int b)

Ограничения: 1 £ a, b £ 10⁹.

Вход. Целые числа a и b.

Выход. Количество счастливых чисел в интервале от a до b включительно.

Пример входа

a	b
1	10
11	20
1000000	5000000

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

2

0

64

РЕШЕНИЕ

рекурсия + перебор

Будем генерировать все числа, состоящие только из 4 и 7, при помощи рекурсии. Если очередное сгенерированное число x лежит в промежутке [a .. b], то добавляется 1 к общей сумме. Если x > b, то приписыванием к x справа 4 и 7 уже нельзя получить счастливых чисел в промежутке [a .. b]. Если счастливое число x £ b, то числа 10 * x + 4 и 10 * x + 7 являются также счастливыми.

ПРОГРАММА

#include <stdio.h>

int solve(int a, int b, long long x)

{

return (x <= b) ? (a <= x && x <= b) + solve(a, b, 10 * x + 4) +

solve(a, b, 10 * x + 7) : 0;

}

class TheLuckyNumbers

{

public:

int count(int a, int b)

{

return solve(a,b,0);

}

};