Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 63 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1342
Стековый калькулятор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В кабинете информатики есть старый стековый калькулятор. Он содержит K ячеек памяти, организованных в виде стека. Первая ячейка называется вершиной стека. На индикаторе калькулятора отображается содержимое вершины стека, если стек непуст.

Над стеком может выполняться операция проталкивания. Применение этой операции приводит к записи числа на вершину стека. Перед этим, если в стеке уже были числа, то каждое из них перемещается в ячейку с номером на единицу больше. Если в стеке уже находится K чисел, то выполнение операции проталкивания невозможно.

Калькулятор позволяет выполнять арифметические операции. Они применяются к числам, хранящимся во второй и первой ячейках стека. Результат операции записывается в первую ячейку стека, а число из второй ячейки удаляется. После этого, если третья ячейка непуста, то число из неё переписывается во вторую, если есть число в четвертой ячейке — оно переписывается в третью и так далее до последней занятой ячейки, которая становится пустой. Для выполнения арифметической операции в стеке должно быть хотя бы два числа. Например, при выполнении операций сложения или умножения, значения соответственно суммы или произведения чисел из первой и второй ячеек помещаются на вершину стека. Операция вычитания выполняется так: из содержимого второй ячейки стека вычитается содержимое первой ячейки.

Известно, что калькулятор неисправен. Из цифровых клавиш работает только клавиша «1». Нажатие этой клавиши приводит к проталкиванию в стек числа 1. Например, попытка набрать число 11, два раза нажав клавишу «1», приводит к тому, что в стек два раза проталкивается число 1. Из операций работают только сложение (клавиша «+»), умножение (клавиша «*») и вычитание (клавиша «-»). Если в результате вычитания получено отрицательное число, то калькулятор зависает.

Легко заметить, что на индикаторе возможно получить произвольное натуральное число. Например, чтобы получить число 3, необходимо дважды нажать клавишу «1», затем клавишу «+» (на индикаторе после этого появится число 2), затем один раз нажать клавишу «1» и один раз — клавишу «+». При K > 2 того же результата можно достичь иначе, трижды нажав клавишу «1», а затем два раза клавишу «+». Дополнительно используя операции умножения и вычитания, в некоторых случаях число N можно получить быстрее, чем сложив N единиц.

Требуется написать программу, которая определяет, каким образом можно получить на индикаторе калькулятора заданное число N, выполнив минимальное количество нажатий клавиш. Стек изначально пуст.

Входные данные

В единственной строке входного файла записаны два натуральных числа — N и K (1 ≤ N ≤ 109, 2 ≤ K ≤ 100).

Выходные данные

В первой строке выходного файла выведите минимальное количество нажатий клавиш, необходимых для получения числа N. Если число нажатий не превосходит 200, то дополнительно выведите во второй строке оптимальную последовательность нажатий, приводящих к появлению данного числа на индикаторе.

Последовательность необходимо выводить без пробелов. Клавиши обозначаются символами «1» — протолкнуть число 1 в стек, «+» — выполнить операцию сложения, «*» — выполнить операцию умножения, «-» — вычесть из значения второй ячейки стека значение первой ячейки.

В результате выполнения выведенной последовательности нажатий на индикаторе должно отображаться число N. Если оптимальных последовательностей нажатий несколько, разрешается выводить любую из них.

Примечания

Решения, корректно работающие при N ≤ 100 и K ≤ 10, будут оцениваться из 40 баллов.

Решения, корректно работающие при N ≤ 106 и K ≤ 100, будут оцениваться из 80 баллов.

Примеры
Входные данные
1 2
Выходные данные
1
1
Входные данные
9 3
Выходные данные
11
11+1+11+1+*
#1346
ВТО
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Территория Великой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть территории области квадратными плитами размером 11 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.

Согласно межгосударственным соглашениям, правительство ВТО не имеет права покрыть частью своей плиты чужую территорию. Производитель поставляет плиты только контейнерными партиями — по P плит. Правительство заказывает столько контейнеров, сколько необходимо для реализации проекта.

Заведующий центральным складом, узнав про проект, решил, что его интересует коли­чество плит, которые останутся на складе из последнего контейнера после покрытия территории ВТО.

Напишите программу, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.

Входные данные

Единственная строка входного файла содержит три целых числа: M, N (2≤M, N≤2 000 000 000) и P (100≤P≤10 000).

Выходные данные

Единственная строка выходного файла должна содержать целое число — количество неиспользованных плит из последнего контейнера.

Примеры
Входные данные
4 3 100
Выходные данные
97
#1389
Верное равенство
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Возвращаясь из школы домой, Петя каждый раз обращал внимание на надпись на заборе «1 + 1 = 10» и удивлялся очевидной его неправоте. Но однажды его осенило, что это равенство верное, если рассматривать его в двоичной системе счисления. Его настолько поразила эта идея, что он решил непременно придумать свои три числа так, чтобы сумма первых двух была равна третьему в некоторой системе счисления.

Теперь он перебирает тройки чисел, которые, на его взгляд, достойны находиться на заборе. Петя выбирает числа A, B, C, записывающиеся десятичными цифрами, и дальше пытается найти основание системы счисления K, в которой равенство A + B = C оказалось бы верным. Петя рассматривает системы счисления с основанием от 2 до бесконечности.

Поскольку проверка каждой тройки — занятие трудоемкое, в помощь Пете необходимо написать программу, облегчающую расчеты.

Входные данные

В первой строке содержится число A, состоящее из цифр от 0 до 9 длины не более 200. В следующих двух строках в таком же формате записаны числа B и C.

Все числа неотрицательные и без ведущих нулей.

Выходные данные

Выведите минимальное основание системы счисления, в которой выполняется равенство A + B = C. Если такого не существует, то выведите 0.

Частичные ограничения

Первая группа состоит из тестов, в которых у всех трех чисел количество цифр не превышает 5, а при сложении их «столбиком» в искомой системе счисления не происходит переноса в следующий разряд.

Вторая группа состоит из чисел, при переводе которых из искомой системы счисления в десятичную они не будут превышать 109.

Примеры
Входные данные
9
8
17
Выходные данные
10
Входные данные
9
8
11
Выходные данные
16
Входные данные
5
5
1010
Выходные данные
0
Входные данные
0
0
0
Выходные данные
2
#1391
Шестеренки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке n зубцов, на второй — m, на третьей — k. На каждом зубце первой, второй и третьей шестеренок по часовой стрелке написаны в порядке возрастания числа от 1 до n, от 1 до m и от 1 до k соответственно. Стрелки зафиксировали таким образом, что когда стрелка первой оси указывает на число, стрелки двух других осей также указывают на числа. Витя записывает три числа (a1,a2,a3), на которые указывают стрелки. После этого он поворачивает первую шестеренку на угол 360°/n против часовой стрелки, чтобы напротив стрелки на первой оси оказался следующий (по часовой стрелке) зубец. При этом вторая шестеренка поворачивается на угол 360°/m по часовой стрелке (размеры зубцов у шестеренок одинаковые, поэтому размеры самих шестеренок разные, чтобы на границе шестеренок равномерно уложилось разное число одинаковых по размеру зубцов), а третья шестеренка поворачивается на угол 360°/k против часовой стрелки. Витя опять записывает три числа, на которые указывают стрелки.

Поступая и далее таким образом, Витя заметил, что после некоторого количества таких действий стрелки показывают на три первоначальных числа.

Теперь его очень интересует, как по двум данным тройкам чисел определить, принадлежат ли они к одной последовательности, то есть можно ли некоторым количеством поворотов перейти от первой тройки ко второй. Он попросил вас написать программу, которая отвечает на этот вопрос.

Входные данные

В первой строке содержатся четыре числа T, n, m, k (1 ≤ T ≤ 10, 1 ≤ n, m, k ≤ 1018) — количество пар троек, которые хочет проверить Витя и количества зубцов соответственно на первой, второй и третьей шестеренках.

В следующих T строках записаны шесть натуральных чисел a1, a2, a3, b1, b2, b3 (1 ≤ a1, b1 ≤ n, 1 ≤ a2, b2 ≤ m, 1 ≤ a3, b3 ≤ k).

Выходные данные

Для каждой пары троек в выходной файл выведите YES, если обе тройки принадлежат одной последовательности, и NO иначе. Каждое слово должно быть в отдельной строке, в порядке, соответствующем входному файлу.

Комментарии к примерам тестов

1. В первой и второй парах вторая тройка получается из первой за один поворот первой шестеренки против часовой стрелки.
В третьем случае из второй конфигурации просто получить первую опять же одним поворотом первой шестеренки против часовой стрелки.
Очевидно, что тогда из первой можно каким-то образом получить вторую.

2. В первой паре тройки нельзя перевести друг в друга.
Во второй тройки переходят друг в друга при одном повороте.

3. (1, 1, 1) — (семь поворотов первой против часовой стрелки шестеренки) — (1, 4, 2) — (еще семь таких же поворотов) — (1, 2, 3) — (один поворот) — (2, 1, 1)

Частичные ограничения

Первая группа состоит из тестов, в которых произведение nmk ≤ 106.

Вторая группа состоит из тестов, в которых n, m, k ≤ 109.

Примечание

Не гарантируется, что описанную в условии задачи систему шестеренок и стрелок можно реально построить.

Примеры
Входные данные
3
11 13 15
5 5 5
6 4 6
11 13 15
1 12 1
2 13 2
1 1 1
Выходные данные
YES
YES
YES
Входные данные
2
2 2 2
1 1 1
1 1 2
1 1 1
2 2 2
Выходные данные
NO
YES
Входные данные
1
7 5 3
1 1 1
2 1 1
Выходные данные
YES
#1396
Эволюция
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

>Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

  1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
  2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
  3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
  4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.

Входные данные

Первая строка входного файла содержит целое число N (1≤N≤100) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки файла содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

Выходные данные

Единственная строка выходного файла должна содержать натуральное число – номер ближайшего предка для двух видов.

Примеры
Входные данные
4
15
12
Выходные данные
3
Входные данные
18
233016
233008
Выходные данные
14563
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест