Задача A. Кинотеатр
Условие
Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид,
Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо,
затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна
и сказала, что ребята сели неправильно - надо пересесть. Она предложила сначала заполнить все первые
места от первого ряда к последнему, затем все вторые места и т. д.
Определите, сколько школьников после такой пересадки останется на своем месте.
Например, если n = 3 и m = 3, то в первом случае дети сядут так:
а во втором - так:
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.
Формат входного файла
Входной файл содержит два целых числа
n и
m.
Формат выходного файла
Выведите количество школьников, которые останутся на своих местах.
Ограничения
1 ≤ n, m ≤ 109
Примеры тестов
| № |
Входной файл (cinema.in) |
Выходной файл (cinema.out) |
|---|
| 1 |
3 3
|
3
|
| 2 |
2 4
|
2
|
Задача B. НОД и числа Фибоначчи
Условие
k-тым числом Фибоначчи называется k-тый член последовательности Fk = Fk−1 + Fk−2 , F0 = 0 , F1 = 1
Формат входного файла
Во входном файле находятся два числа
n и
k
Формат выходного файла
В выходном файле должно содержаться единственное число — наибольший общий делитель Fn и Fk.
Ограничения
1 ≤ n, k ≤ 100
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1 2
|
1
|
Задача C. Место у прохода, пожалуйста
Условие
Те, кто часто путешествуют самолетами, любят просить место у прохода. Ведь если сидеть у
прохода, можно встать и прогуляться, не тревожа своих соседей.
Компания "Аэротрам" готовит к производству новый самолет "T-239-n". Перед инженерами
встала задача спланировать организацию салона, чтобы как можно больше мест было у прохода.
Будем использовать следующую упрощенную математическую модель салона самолета. В горизонтальном
сечении салон представляет собой прямоугольник длиной
l и шириной
w сантиметров.
Кресло представляет собой прямоугольник размером
x на
y сантиметров и должно быть расположено
в салоне так, чтобы его сторона длиной
x была параллельна стороне салона длиной
l. Проход
представляет собой полосу шириной
a, параллельную стороне салона длиной
l. Проход идет вдоль
всего салона.
В салоне требуется разместить n кресел. Помогите инженерам компании выяснить, как организовать
салон, чтобы максимальное количество кресел было расположено у прохода. В салоне
необходимо сделать хотя бы один проход. Кресло считается расположенным у прохода, если оно
имеет хотя бы одну общую сторону с проходом.
В первом примере оптимально расположить кресла, например, следующим образом:
Формат входного файла
Формат входного файла
Входной файл содержит шесть целых чисел:
n,
l,
w,
x,
y и
a.
Формат выходного файла
Формат выходного файла
Если разместить n кресел в салоне так, чтобы был хотя бы один проход, невозможно, выведите в
выходной файл единственное число
−1. Иначе выведите максимальное количество кресел, которое
можно разместить у прохода.
Ограничения
1 ≤ n, l, w, x, y, a ≤ 104
Примеры тестов
| № |
Входной файл (aisle.in) |
Выходной файл (aisle.out) |
|---|
| 1 |
400 3250 750 80 60 70
|
160
|
| 2 |
450 3250 750 80 60 70
|
-1
|
Задача D. Интересные числа
Условие
Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает
интересными положительные числа, запись которых в системе счисления с основанием k заканчивается
нечетным числом нулей. Например, при k=2 такими числами являются 210=102,
2410=110002.
Для того, чтобы пополнить свою коллекцию, Роман хочет найти
n-ое в порядке возрастания
такое число. Поскольку
n он взял достаточно большим, то вручную у него это сделать
не получается.
Помогите Роману — напишите программу, которая найдет число, которое нужно ему для
пополнения коллекции.
Формат входного файла
Первая строка входного файла содержит два целых числа.
Формат выходного файла
В выходной файл выведите
n-ое в порядке возрастания число, запись которого
в системе счисления с основанием
k заканчивается на нечетное число нулей.
Это число необходимо вывести в десятичной системе счисления.
Ограничения
1 ≤ n ≤ 1015
2 ≤ k ≤ 10
Примеры тестов
| № |
Входной файл (numbers.in) |
Выходной файл (numbers.out) |
|---|
| 1 |
1 2
|
2
|
| 2 |
10 10
|
110
|
