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

Обсуждение задачи 1608. Счастливые билеты 2008

How to solve this? I get TLE10 (-)
Послано rohit 30 мар 2008 21:23
Re: How to solve this? I get TLE10 (-)
Послано Denis Koshman 10 авг 2008 00:08
Count F(n) - number of lucky tickets in range 1..n, the answer is F(b) - F(a-1). If n=4567, then F(4567) is number of 1-digit lucky numbers + number of 2-digit lucky numbers + number of 3-digit lucky numbers. With 4 digit numbers it's a bit harder - if first digit is 1..3, then remainder can be anything sustaining luckiness (i.e. there is no effect from upper border). Also first digit can't be 5,6,7. If first digit is 4, the last one can be anything except 4 - so you have multiplier 9 for the next step. This is not everything, but the basic idea.