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

Ural SU contest. Petrozavodsk training camp. Winter 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Квадратная страна 5

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Первое арифметическое действие, которое учатся выполнять школьники Квадратной страны — это возведение в квадрат целых положительных чисел. На первом уроке школьникам предлагают только «удобные» числа, то есть числа, для возведения в квадрат которых достаточно дописать к ним спереди несколько цифр (например, 76 — удобное число, поскольку 762 = 5776). Конечно, числа не должны содержать ведущих нулей. Задание не должно быть слишком сложным, поэтому исходное число должно состоять не более чем из n цифр. Сколько различных вариантов задания смогут подготовить учителя для первого урока?

Исходные данные

В единственной строке записано целое число n (1 ≤ n ≤ 2000), максимальная длина числа, которое может быть предложено школьникам.

Результат

Выведите количество удобных для возведения в квадрат чисел, состоящих не более чем из n цифр.

Пример

исходные данныерезультат
1
3
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1698. Квадратная страна 5