Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Пятью пять - двадцать пять!

(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Решение №1

В формулировке задачи не случайно присутствует описание метода быстрого возведения в квадрат чисел, оканчивающихся на 5. Дело в том, что здесь имеется "подводный камень", который связан с ограничениями входных данных. Многие, используя 4х байтовый целый тип, пытаются считать A и вывести A*A. Но не все так просто, т.к. при A = 399 995 (максимально возможное значение согласно ограничениям задачи) мы в качестве A*A должны получить значение 159 996 000 025, которое не помещается в вышеописанный тип (максимум там может быть 232-1 = 4 294 967 295). Поэтому в процессе вычислений может происходить переполнение типа, что приведет к неправильному результату. Но используя описанный в задаче метод, мы можем сократить на порядок размер чисел, с которыми работаем. Т.е. сначала мы отбрасываем последнюю цифру, получая B = A div 10, в нашем случае тогда в B получится значение 39 999, далее нам нужно будет умножить его на 40 000, это даст значение 1 599 960 000, которое мы можем вычислить и вывести в файл. После этого остается вывести 25, сразу после ранее выведенного числа. Здесь распространенной ошибкой также является вывод значения в форме 100*B*(B+1)+25. Дело в том, что такая форма так же может вызывать переполнение, т.к. конечным результатом является опять то же самое большое число.

Таким образом, решение задачи может иметь следующий вид:

  int a,b;

  read(a);
  b = a div 10;
  write(b*(b+1),25);

Однако заметим, что такое решение не пройдет первый тест. Надеемся, что с этой проблемой читатель разберется самостоятельно.

Решение №2

Благодаря возможности современных компиляторов возможно использование 8-байтовых целых типов, что дает возможность решить эту задачу очень легко, простым возведением числа в квадрат. В Delphi для этого может использоваться целый тип int64, а в VC аналогичный ему тип __int64 (или long long). Более того, можно обойтись и вещественными типами и решить эту задачу под DOS, скажем на Borland C++ 3.1 и Turbo Pascal 7.0. Для этого можно воспользоваться такими типами как double и extended соответственно, при этом при выводе следует писать printf("%.Lf", a*a) и write(a*a:0:0) соответственно.

В завершении разбора рассмотренных выше решений докажем описанный в задаче метод возведения в квадрат. Пусть некоторое число A оканчивается на 5, тогда A = B*10+5, где B - некоторое целое число. Попробуем теперь выразить A2 через B:

A2= (B*10+5)*(B*10+5) = B*B*10*10+B*10*5+5*B*10+5*5 = 100*B2+100*B+25 = 100*B*(B+1)+25

Что и требовалось доказать.

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru