|
Пятью пять - двадцать пять!
(Время: 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
Что и требовалось доказать.
| |
