Системы счисления Автоматизированная система генерации тестов

Твитнуть

Плюсануть

Класснуть

Запинить

Олимпиадный тренинг

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

XOR

Системы счисления Разные системы счисления

Исключающим "или" (XOR) называется булева функция, а также логическая и битовая операция от двух аргументов, результат которой истинен тогда и только тогда, когда один из аргументов истинен, а второй - ложен.
Циклический побитовый сдвиг вправо - операция, при которой младший разряд переносится в начало числа и становится старшим, а все остальные сдвигаются вправо на одну позицию.
К двум 16-битовым числам A и B, записанным в 16-ричной системе счисления, была применена операция исключающего "или", а затем к результату - операция побитового циклического сдвига вправо на K разрядов. Одно из двух исходных чисел было забыто, требуется его восстановить.
Входные данные
в строку через пробел записаны числа A, K и результат X. Числа A и X заданы в 16-ричной системе счисления, K - в десятичной.
Выходные данные
число B.

Примеры

№	Входные данные	Выходные данные
1	1A2B 4 4E5D	FFFF
2	AB00 1 5C9A	1234

В троичную систему счисления

Перевод из 10СС Системы счисления

Задано натуральное число N, не превышающее 10⁸ . Требуется определить, сколько чётных цифр входит в его запись в троичной системе счисления.
Входные данные
число N, записанное в десятичной системе счисления.
Выходные данные
количество чётных цифр, входящих в запись числа N в троичной системе счисления.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4	0	4₁₀=11₃
2	15	2	15₁₀=120₃

489

Системы счисления

Вычислите значение суммы 10₂+ 10₈ +10₁₆ в двоичной системе счисления.

Ответ: 1) 10100010(2) 2)11110(2) 3)11010(2) 4)10100(2)

It's All About the Base

Системы счисления

Беси пошла компьютерные курсы и восхищена темой «Системы
счисления». Напомним, что число, записанное в системе счисления
B имеет цифровые места, представляющие 1, B, B^2, B^3 … справа
налево. Например, для 10-ой системы счисления мы имеем цифры,
представляющие 1, 10, 100, 1000, … Последовательность цифр 1234
в 10-й системе означает
1(1000) + 2(100) + 3(10) + 4(1).
Та же последовательность в 5-ой системе означает
1(125) + 2(25) + 3(5) + 4(1)
И даёт число 194 в 10-й системе.
Беси заметила, что если основание системы счисления B возрастает,
возрастает и число, им представляемое. Например, 1234 в 7-ой системе
счисления представляет большее число, чем 1234 в 6-ой системе
счисления.

Когда мы записываем число в системе счисления с основанием B,
каждая цифра может быт в диапазоне от 0 до B-1. Поэтому, например,
в 10-й систем счисления, цифры находятся в диапазоне 0..9,
а в 5-ой систем счисления, цифры находятся в диапазоне 0..4.

Можно рассматривать системы счисления с основанием больше чем 10.
Например, компьютерные специалисты часто используют в качестве
основания системы счисления основание 16, и используют буквы A..F
для обозначения величин 10..15. Например, BEEF в 16-ой системе соответствует
11(4096) +14(256) + 14(16) + 15,
что после сложения даёт 48879 в 10-ой системе счисления.
Беси заинтригована концепцией использования оснований больше 10.
Она берёт число N и выписывает его в двух различных системах счисления X и Y,
каждое из которых в диапазоне 10..15,000. Интересно, что в обоих случаях
она получает последовательность из 3 цифр, каждое из которых в диапазоне 1..9.
К сожалению, из-за плохой памяти Беси забыла N X Y. Пожалуйста, помогите
ей по двум 3-цифровым последовательностям, которые она выписала,
определить системы счисления X и Y, которые она использовала.
Заметим, что программа, которая просто будет перебирать все возможные
сочетания X и Y (примерно 15,000^2 вариантов) не пройдёт по времени,
и не получит полный балл.

Формат входных данных

Входной файл начинается с целого числа K, затем оно содержит K строк,
каждая из которых отдельный тест. Каждый тест состоит из двух
3-значных чисел. Первое - число N, записанное в системе счисления с
основанием X, второе - число N, записанное в системе счисления с
основанием Y. N X Y могут различаться для каждого теста.

Формат выходных данных

Ваш вывод должен содержать K строк, по одной для каждого теста.
На каждой строке выведите два числа X и Y для соответствующего теста,
разделённые одиночными пробелами. Гарантируется существование и
единственность решения.

Примечание
Число 8892, записанное в системе счисления с основанием 47 есть 419,
и это же число, записанное в системе счисления с основанием 35 есть 792.

Awkward Digits

Системы счисления

Problem 2: Awkward Digits [Brian Dean]
Бесси учиться конвертировать числа между системами счисления, с различными основаниями, но она делает ошибки, поскольку тяжело держать ручку между копытами.
Когда Бесси записывает результат конвертирования, она всегда записывает одну цифру с ошибкой. Например, если она конвертирует число 14 в двоичную систему, корректный результат будет 1110, но она может написать вместо него «0110» или «1111». Бесси никогда не добавляет и не удаляет цифры, но у нее может получится число с ведущим нулем в результате ее ошибки.
Вам дается ответ, записанный Бесси при конвертировании числа N К основаниям 2 и 3. Определите исходное значение числа N в десятичной системе счисления. Вы можете полагать, что N не превосходит 1 миллиард, и что всегда существует уникальное значение N.
PROBLEM NAME: digits
Формат входных данных
* Строка 1: представление числа N в двоичной системе счисления, одна цифра записана некорректно. (основание=2)
* Строка 2: представление числа N в троичной системе счисления, одна цифра записана некорректно (основание=3).
Формат выходных данных
* Строка 1: корректное значение числа N.
Примечание
Корректное значение числа 14 ("1110" в двоичной системе, "112" в троичной).

B. Красные и синие шарики

Системы счисления

У пользователя ainta есть стек, в котором содержатся n красных и синих шариков. Он умеет выполнять со стеком операцию, которая изменяет цвета шаров в стеке. Операция описывается алгоритмом:

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

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

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

В первой строке записано целое число n (1 ≤ n ≤ 50) — количество шариков в стеке.

Во второй строке записана последовательность s (|s| = n), описывающая изначальное состояние стека: i-й символ в строке s обозначает цвет i-го шарика (считайте, что шарики в стеке пронумерованы, начиная от вершины стека). Если символ равняется "R", то шарик красный. Если символ равняется "B", то шарик синий.

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

Выведите максимальное количество операций, которые ainta может последовательно выполнить.

Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примечание

Описание первого тестового примера.

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

$\text{[math]}$

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

$\text{[math]}$

Теперь ainta больше не может применить ни одной операции, поскольку в стеке не осталось синих шаров. ainta выполнил две операции, так что ответ равняется 2.

Описание второго примера приведено ниже. Синяя стрелка обозначает применение одной операции.

$\text{[math]}$

Степенные числа

Системы счисления

Если вас интересует математика, то эта задача для вас.

Будем называть целое число $n$ $k$-степенным, если его можно разложить в сумму различных степеней числа $k$, то есть если $n$ представимо в виде $n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}$, где все $a_i$ целые и $a_i \ne a_j$ для всех $i \ne j$.

Ответьте на множество запросов: какое минимальное целое число, большее либо равное $n_i$, является $k_i$-степенным?

Формат входных данных
Первая строка ввода содержит целое число $q$ — количество запросов, на которые вам предстоит ответить ($1 \le q \le 10^5$).

Каждая из следующих $q$ строк содержит два целых числа $n_i$ и $k_i$, описывающие $i$-й запрос ($1 \le n_i \le 10^9$; $2 \le k_i \le 10^9$).

Формат выходных данных
Выведите $q$ строк, в $i$-й из которых выведите минимальное $k_i$-хорошее число, большее либо равное $n_i$.

Операции с числом

Динамическое программирование: один параметр Системы счисления

Дима работает на складе чисел. Он входит на склад с двоичным числом $x=0$. Ему необходимо превратить свое число $x$ в число $s$. Для этого на складе есть два автомата для увеличения чисел.

Первый автомат увеличивает двоичное число $x$ на $1$ за $a$ секунд. Он расположен слева от входа на склад, в $p$ секундах ходьбы от входа.

Второй автомат умножает двоичное число $x$ на $2$ за $b$ секунд. Он расположен справа от входа на склад, в $q$ секундах ходьбы от входа.

Таким образом, если Диме понадобится дойти от одного автомата до другого, он потратит $p+q$ секунд. Исходно он находится у входа на склад.

Помогите Диме узнать, за какое наименьшее количество секунд можно получить число $x=s$ и вернуться ко входу на склад.
Число в двоичной системе счисления из $n$ цифр, представимое в виде: $\overline{a_1 a_2 \ldots a_n}$ $(a_i \in \{0, 1\})$, равно $2^{n-1} \cdot a_1 + 2^{n-2} \cdot a_2 + \ldots + 2 \cdot a_{n-1} + a_n$. ($a_1 = 1$ при $n > 1$, то есть число не имеет ведущих нулей).

Формат входных данных
В первой строке даны два целых числа $a$ и $b$ в десятичной записи $(1 \le a, b \le 10^9)$ — время, которое потребуется автоматам для увеличения числа.

Во второй строке даны целые числа $p$ и $q$ в десятичной записи $(0 \le p, q \le 10^9)$ — расстояние от входа на склад до первого и второго автоматов.

В третьей строке дано число $s$ в двоичной системе счисления без ведущих нулей (кроме случая $s = 0$). Длина числа $s$ не превышает $100\,000$ цифр.

Формат выходных данных
Выведите минимальное количество секунд, которое потребуется, чтобы из $x=0$ получить $x=s$, пользуясь автоматами, и вернуться ко входу на склад.

Примечание

В первом тесте необходимо получить число $s=32 + 8 + 2 + 1 = 43$ в десятичной записи.

Оптимальная последовательность действий: Дима идет к первому автомату (2 секунды), прибавляет к числу единицу 5 раз (5 секунд), потом идет ко второму автомату ($2+3=5$ секунд), умножает число 3 раза ($3 \cdot 2 = 6$ секунд) и получает число 40, возвращается к первому автомату ($3+2=5$ секунд), прибавляет единицу 3 раза (3 секунды), и идет ко входу на склад (2 секунды). Всего потрачено 28 секунд.

Во втором тесте у Димы с самого начала есть число $x=0$.

При каком наименьшем х?

Системы счисления Задача на реализацию

Значение выражения $ 27^7 - 3^{11} + 36 - x$ записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100). Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Перестановки

Системы счисления Перебор

Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно выполняться следующие три условия:

1. Шестнадцатеричные цифры в записи числа упорядочены по невозрастанию.

2. Если перевести это число в двоичную систему счсиления, то запись будет содержать не менее 5-ти идущих подряд единиц.

3. Любое шестнадцатеричное число, образованное перестановкой цифр этого числа и переведенное в двоичную систему счисления, также будет содержать в двоичной записи не менее 5-ти единиц подряд.

Огромное число

Системы счисления Задача на реализацию

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

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