Волшебные числа.
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по памяти: 64 мб
Ограничение по времени: 0.5 секунд
Назовем натуральное число «волшебным», если оно имеет вид ab+ba (где a и b – натуральные числа). Например, число 57 – волшебное, т.к. 57=25+52. Дано число N (N<=10100), необходимо определить является ли оно волшебным. А также вывести a и b.
Входные данные.
В файле содержится единственное число N.
Выходные данные.
Вывести два числа a и b, каждое в отдельной строке, причем меньшее вывести первым.
В случае если он таковыми не являются вывести -1.
| input.txt | output.txt |
Занимательная игра.
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по памяти: 64 мб
Ограничение по времени: 1 секунда
Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик - он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
...
и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28.
Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.
Входные данные.
Входной файл содержит одно целое число N (0 <= N <= 32767).
Выходные данные.
Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.
| input.txt | output.txt |
Занимательная игра
В решении этой задачи нам пригодиться знание о представлении числа в памяти компьютера. Как известно, оно представлено в виде последовательности нулей и единиц и полностью соответствует тем правилам перевода и записи, какими пользуется Юрий Петрович.
В переменную best, которая будет хранить максимальную перестановку, изначально инициализируем данным числом. Сначала определим некоторое число, которое назовем max. Посчитаем его таким образом: сначала приравняем его 1, а затем будем сдвигать бит с единичкой на 1 позицию влево (то же самое, что операция умножения на 2), до тех пор, пока число max не станет больше данного числа. Никакая перестановка цифр данного числа не может быть больше, чем max, т.к. содержит на 1 быть меньше. Запомним, какое количество операций сдвига мы произвели.
Теперь запустим цикл до количества операций сдвига для получения max. Булем осуществлять сдвиг двоичных цифр данного числа по следующему правилу: сдвигаем число на 1 бит влево, если оно больше max, то отнимаем от него max и прибавляем 1 - циклический перенос единицы. Если это число больше, чем best - заменяем best на это число.
Осталось только вывести ответ - best.
Квадраты.
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по памяти: 64 мб
Ограничение по времени: 1 секунда
В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной а метров, покупатель платил а2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это, безусловно, можно было сделать, приобретя участки размером 1*1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. "Так мне будет легче общаться с Квадратной Налоговой Инспекцией", - сказал он. Сделка состоялась.
Задание:
Напишите программу, которая находит количество свидетельств, полученных жителем.
Входные данные.
Единственная строка входного файла содержит целое положительное число N <= 60000 - число квадриков, которое было у жителя.
Выходные данные.
Единственная строка выходного файла содержит число свидетельств, полученных в результате сделки.
| input.txt | output.txt |
Квадраты
Эта задача решается с помощью динамического программирования.
Сначала проверим, не является ли число полным квадратом. Если так, то сразу выводим "1" и заканчиваем. Если же не является, то придется потрудиться.
Заведем массив размером в 60000 элементов - в нем мы будем хранить количество участков для каждой площади. Пройдем его с 1 до N, если текущее число (i) - квадрат целого числа, то в соответствующий элемент массива записываем 1 и переходим к следующему. Если же это не так, то тут понадобиться еще один цикл (j) от 1, до тех пор, пока разность между i и j2 не станет меньше 1. Итак, мы можем узнать, сколько участков необходимо, чтобы скупить территорию i - j2; для того, чтобы скупить территорию площадью i, необходимо на один участок больше (этот участок со стороной j). Среди всех возможных j выберем минимальное количество участков для площади i и перейдем к следующему i. Этим мы полностью рассматриваем все варианты и выбираем наилучший (в этом несложно убедиться).
