Дома у Наташи живёт несколько котов. Известно, что за ночь один кот роняет от $$$A$$$ до $$$B$$$ плохо закреплённых предметов (а таких предметов у Наташи бесконечно много).

Однажды ночью Наташа сквозь сон $$$N$$$ раз услышала, как что-то упало. Определите, какое наименьшее число котов может у неё жить.

В ряд лежат 2*N+1 пустых карточек. Петя на каждой чётной карточке пишет по своему усмотрению знак ">" или "<". Сможет ли Вася вписать на нечётные карточки числа от 1 до (N+1) так, чтобы все неравенства были верными? Каждое число должно быть написано ровно один раз.

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

1. Цифры от 0 до 9
2. Круглые скобки
3. Символ '*', означающий любое количество повторений символа или подвыражения в скобках, которое записано перед ним. Например, выражение '345*6' означает, что после подстроки '34' идёт ноль или более цифр '5', затем цифра '6'. Выражение '3(45)*6' означает, что после символа '3' может идти ноль или более повторений подстроки '45', затем цифра '6'.
4. Символ '|', означающий операцию 'ИЛИ'. Приоритет данной операции меньше, чем приоритет неявной операции склеивания. Например, выражение '12|345' означает строку '12' или строку '345'. Выражение '(12|34)5' означает, что вначале идёт либо '12', либо '34', а затем '5'.

Одно из применений регулярных выражений — проверка, соответствует ли строка заданному шаблону. Например, чтобы проверить, является ли введённое целое неотрицательное число чётным, можно написать такое выражение (для простоты разрешим ведущие нули): (0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)

От вас требуется решить более сложную задачу. Нужно определить, можно ли в целом неотрицательном числе переставить цифры так, чтобы число стало делиться на 6. Например, в числе 123 цифры нужным образом переставить можно, а в числе 31 — нельзя. Составьте регулярное выражение для выполнения такой проверки.

Маленькая девочка Кристина приехала в гости к бабушке и увидела старинные механические часы, на циферблате которых было две стрелки — часовая и минутная. Часы исправно ходили, при этом перемещение стрелок у таких часов непрерывное (а не дискретное), то есть, например, за 1 минуту минутная стрелка равномерно перемещается на 6 градусов, а часовая — на 0.5 градуса. В момент наблюдения часы показывали ровно h часов, m минут, 0 секунд (то есть минутная стрелка указывала ровно на отметку m минут на циферблате). Например, часы на рисунке ниже показывают 8 часов 23 минуты и 0 секунд времени.

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

Некоторая тропическая республика представляет собой архипелаг, состоящий из нескольких (не менее двух) островов. Карта архипелага представляет собой матрицу $$$n \times m$$$, в которой символ '1' означает землю, а цифра '0' — воду. Любые две соседние по стороне клетки с символом '1' принадлежат одному острову.

Свежеизбранный президент республики в ходе предвыборной гонки обещал соединить все острова мостами. Теперь обещание нужно выполнять, но денег в стране немного. Поэтому он решил начать с возведения самого маленького моста. Определите, какое наименьшее число клеток нужно изменить с '0' на '1', чтобы какие-нибудь два острова (или более) соединились.

Вася считает сумму 2+22+202+2002+...20...02 и среди подряд идущих цифр получившегося результата хочет увидеть своё счастливое четырёхзначное число $$$N$$$. Помогите Васе определить, какое наименьшее количество слагаемых ему нужно взять, чтобы в десятичной записи такой суммы встретился фрагмент, совпадающий с его счастливым числом $$$N$$$.

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

1. из (m, n) получить (m - n, n)
2. из (m, n) получить (m + n, n)
3. из (m, n) получить (n, m)

Определите последовательность команд, чтобы получить из пары чисел (a, b) пару (c, d).

На доске прикреплены $$$N$$$ карточек, на каждой из которых записаны два целых числа — одно слева, другое справа. На обратной стороне одной из карточек написано слово "Приз".

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

Как-то раз на одной из игр между игроками случился следующий диалог:

• Игрок 1: Я знаю, что ты не знаешь призовую карточку. И я её тоже не знаю.
• Игрок 2: Спасибо, теперь я знаю призовую карточку.
• Игрок 1: Спасибо, теперь и я тоже знаю.

После этого один из зрителей в зале воскликнул: "Я тоже знаю!". А вы сможете определить призовую карточку?

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

Решение у этой задачи следующее. Оказывается, достаточно разрезать всего одно кольцо — третье. Тогда у путешественника будет три куска цепочки — из двух, одного и четырёх колец. В первый день он отдаст хозяину одно кольцо. Во второй день он отдаст кусок из двух колец и заберёт обратно кольцо, которое отдал в первый день, и так далее.

Вам предлагается решить эту задачу в общем виде. Пусть цепочка состоит из $$$N$$$ колец, и путешественник хочет жить в гостинице $$$N$$$ дней. Определите, какое наименьшее количество разрезов потребуется сделать, а также какие именно кольца разрезать.

Вам дан исходный код некоторой программы, для удобства он приведён на нескольких популярных языках программирования. Данная программа читает два целых числа $$$a$$$ и $$$n$$$ и затем выводит одно целое число — ответ.

При больших входных данных эта программа может работать довольно долго. Ваша задача — написать альтернативную программу, которая будет выдавать точно такие же ответы, но работать не более одной секунды при любых входных $$$a$$$ и $$$n$$$ в диапазоне от $$$0$$$ до $$$10^{18}$$$.

Текст на C++:

#include <iostream>

int main() {
    long long a, n;
    std::cin >> a >> n;
    long long b = 0;
    for (long long i = 0; i < n; i++) {
        b = (b - a) & a;
    }
    std::cout << b << std::endl;
}

a = int(input())
n = int(input())
b = 0
for _ in range(n):
    b = (b - a) & a
print(b)

Текст на Java:

import java.util.Scanner;

public class Solution {  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong();
        long n = in.nextLong();
        long b = 0;
        for (long i = 0; i < n; i++) {
            b = (b - a) & a;
        }
        System.out.println(b);
    }  
}

Текст на C#:

using System;

public class Solution {
    static void Main() {
        long a = long.Parse(Console.ReadLine());
        long n = long.Parse(Console.ReadLine());
        long b = 0;
        for (long i = 0; i < n; i++) {
            b = (b - a) & a;
        }
        Console.WriteLine(b);
    }
}

Текст на Pascal:

var
    a, b, n, i: int64;
begin
    read(a, n);
    b := 0;
    i := 0;
    while i < n do begin
        b := (b - a) and a;
        inc(i);
    end;
    writeln(b);
end.