ТЕШЕНИЯ ПРИНИМАЮТСЯ ДО 00:00 27 ЯНВАРЯ 2018 Г.

Задача Hoard. Пираты спрятали клад в подземном лабиринте, который состоит из бесконечного количества комнат с каменными стенами. Комнаты имеют номера и соединены переходами, так что все подземелья, если смотреть сверху, выглядит как спираль. Комнаты пронумерованы, как на рисунке. После большого землетрясения некоторые стены разрушились, а между смежными комнатами образовались новые проходы. Вход в лабиринт находится в комнате 1 Кладоискатель знает, что сокровище находится в комнате N. Напишите программу, которая, учитывая расположение клада N и список новых переходов, определяет наименьшее количество переходов, через которые должен пройти искатель, пока доберется до сокровища.

Технические условия. Программа Hoard читает с устройства стандартного ввода в первой строке целое число N (1 ≤ N ≤ 10¹⁵) - номер комнаты, в которой расположен сокровище, во второй строке - целое число K (1 ≤ K ≤ 100 000), количество новых переходов . Каждый из следующих K строк содержит одно целое число B (4 ≤ B ≤ 10¹⁵), что означает, что теперь новый переход объединяет смежные помещения A и B, где A<B. Номер А не задано явным образом, но его можно однозначно определить по  B (например, если B равно 20, то A должно быть 7). Кроме того, в некоторые комнаты никогда не могут быть номером В (номера 2, 3, 5, 7, 10, 13 и т.д.). Программа выводит на устройство стандартного вывода единственное целое число - наименьшее количество переходов, через которые искатель должен пройти, прежде чем он может добраться до сокровища.

Примеры

__________________________________________________________________________________________________

Задача Cool2k17. Назовем число «крутым», если в его десятичной записи присутствуют только цифры 0, 1, 2. Перестановка чисел A1, A2, ..., An  лексикографически меньше перестановки   B1, B2, ..., Bn, если существует k такое, что для всех i <k справедливо Ai = Bi и для Ak <Bk. Вам дано число N - длина перестановки (количество цифр в перестановке), а также число K - номер перестановки среди всех перестановок, отсортированных лексикографически. Вам необходимо найти количество «крутых» чисел, стоящих на «крутых» местах, то есть их индексы в перестановке также являются «крутыми» числами. Элементы в перестановке нумерованы с 1.

Технические условия. Программа Cool2k17 считывает с клавиатуры два числа N и K, оба не большем по 10¹⁸. Программа должна вывести единственное число - ответ задачи. В случае, если   K-й перестановки не существует, следует вывести -1.

Примеры:

Комментарий: Всего существует 6 перестановок чисел от 1 до 3. Это  (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) (3, 2, 1). Поэтому на первый пример ответ 1 (двенадцатой перестановки не существует). На второй пример ответ 1 – в перестановке (2, 3, 1) только «крутое» число 2 стоит на «крутом» месте 1.

______________________________________________________

Задача Segtree2k17. В среде крутых олимпиадных  гуру модно помнить наизусть решение такой задачи: Дан массив з N чисел и M запросов вида L R. На каждый такой запрос нужно вывести произведение элементов массива, имеющих индексы от L до R включительно. Так как произведение может быть весьма велико, ответ выводим по модулю  Mod 

Рассмотрим некую модификацию  этой задачи. Условие менять не будем, изменим лишь ограничения:

Поскольку в этом случае входной файл будет достаточно большим, предлагается его генерировать. Код генератора (С++) должен быть  встроен  в решение. (Аналогичный код  на языках Pascal и  Python можно зарузить тут).

const int MAXN = 1000 * 1000;
long long a[MAXN];
long long mod;

unsigned s;
unsigned getNext(){
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}

int main() {
    unsigned n, m, seed ;
    cin >> n >> m >> mod >> seed;
    s = seed;
    for(int i = 0; i < n; i++){
        a[i] = getNext();
    }

    long long ans = 0;
    for(int i = 0; i < m; i++){
        unsigned left = getNext() % n;
        unsigned right = getNext() % n;
        if(left > right) swap(left, right);

        long long result = query(left, right);

        ans = (ans + result) % mod;
    }
}

Таким образом, входными данными будут N, M, Mod, Seed, где Seed – начальное значение для генератора. В ответе нужно вывести сумму для каждого запроса (по модулю)

Технические условия. Программа Segtree2k17  (содержащая встроенный код генератора!)  читает с устройства стандартного ввода натуральные числа N, M, Mod, Seed   seed<=2³²

Программа выводит на устройство стандартного вывода единственное число – сумму результатов (по модулю) на всех запросах.

Примеры

Ввод                                                           Вывод

10 15 1000000007 1                                216091399

Ввод                                                         Вывод

5000 100000 1283189389247 8932   541836623127

Ввод                                                             Вывод

1000 100 100007 7632                           4701

_______________________________________________________________

Задача Viability. Василий  Пупенко  (участникам NetOI с конца 1990-х годов известен как Вася Пупкин) защищает диссертацию по теории чисел. Более того, ввел в эту теорию несколько новых понятий. Сердцем целого положительного числа он назвал произведение всех десятичных цифр этого числа. Например, сердцем числа 2612 будет 2 · 6 · 1 · 2 = 24 А вот жизнеспособность такого числа - это произведение числа на его сердце. Например, жизнеспособность числа 2612 составляет 2612 · 24 = 62688. Темой диссертации на соискание степени Ph.D Василия стало исследование: сколько существует натуральных чисел, жизнеспособность которых лежит в промежутке от А до В? Помогите ученому - напишите программу, которая посчитает это количество, тем самым подтвердит  теорию Василия.

 Технические условия. Программа Viability читает с устройства стандартного ввода два целых числа A и B (1 ≤ A ≤ B <10¹⁸) через пробел к одной строке. Программа выводит на устройство стандартного вывода единственное число - искомую величину.

Комментарий  к второму  примеру. Жизнеспособности чисел 19, 24, 32 і 41 имеют значения 171, 192, 192 и 164.

______________________________________________________________________

Задача Vinsoft.  В г. Винница есть N фирм, занимающихся разработкой программного обеспечения. Известный винницкий олигарх Чайник решил монополизировать отрасль в городе, создав концерн Vinsoft. Для этого он решил приобрести как можно больше фирм. Он разослал соответствующие предложения всем N компаниям и через некоторое время получил от каждой из них согласие или отказ. Но, как опытный бизнесмен, Чайник знает, что в бизнесе очень многое зависит от взаимного доверия партнеров. Путем сбора информации Чайник обнаружил, между которыми фирмами существует взаимное доверие (причем, всегда, если фирма A доверяет фирме B, то фирма B доверяет фирме A).  Теперь Чайник может повторно разослать предложения всем фирмам, включив в письмо список фирм, которые согласились на его проект. При этом каждая фирма, независимо от своей первоначальной позиции, дает согласие, если в списке есть хоть одна фирма, которой она доверяет, и отказывается в противном случае. Таким образом, некоторые фирмы, которые изначально не соглашались, теперь дают согласие «продаться» Чайнику, а некоторые из тех, что сначала дали согласие, отказываются. В результате в Чайника формируется новый список, он снова может разослать фирмам. Такую операцию Чайник может повторять много раз, каждый раз рассылая текущий список. Он может прекратить процесс в любой момент и приобрести те фирмы, которые после последнего рассылки согласились. Какое максимальное число фирм может купить Чайник? Как это ни странно, Чайник - честный олигарх и никогда не «подтасовывает» списки.

Технические условия. Программа Vinsoft читает с устройства стандартного ввода в первой строке число N - количество фирм (1≤N≤2000). Далее в той же строке N чисел, описывающих ответ компании на первое предложение Чайника (1 - согласие 0 - отказ). Далее - число M (0≤M≤200000) - количество пар компаний, между которыми существует доверие. Далее - M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара фирм упоминается в списке не более одного раза. Все числа разделены пробелами. Программа выводит на устройство стандартного вывода  максимальное число фирм, которые сможет купить Чайник.

Примеры

_________________________________________________________________________

Заданиия подготовили В.Бездушный, Г.Непомнящий, Ю.Пасихов, М.Стречень