ТЕШЕНИЯ ПРИНИМАЮТСЯ ДО 00:00 27 ЯНВАРЯ 2018 Г.
Задача Hoard. Пираты спрятали клад в подземном лабиринте, который состоит из бесконечного количества комнат с каменными стенами. Комнаты имеют номера и соединены переходами, так что все подземелья, если смотреть сверху, выглядит как спираль. Комнаты пронумерованы, как на рисунке. После большого землетрясения некоторые стены разрушились, а между смежными комнатами образовались новые проходы. Вход в лабиринт находится в комнате 1 Кладоискатель знает, что сокровище находится в комнате N. Напишите программу, которая, учитывая расположение клада N и список новых переходов, определяет наименьшее количество переходов, через которые должен пройти искатель, пока доберется до сокровища.
Технические условия. Программа Hoard читает с устройства стандартного ввода в первой строке целое число N (1 ≤ N ≤ 1015) - номер комнаты, в которой расположен сокровище, во второй строке - целое число K (1 ≤ K ≤ 100 000), количество новых переходов . Каждый из следующих K строк содержит одно целое число B (4 ≤ B ≤ 1015), что означает, что теперь новый переход объединяет смежные помещения A и B, где A<B. Номер А не задано явным образом, но его можно однозначно определить по B (например, если B равно 20, то A должно быть 7). Кроме того, в некоторые комнаты никогда не могут быть номером В (номера 2, 3, 5, 7, 10, 13 и т.д.). Программа выводит на устройство стандартного вывода единственное целое число - наименьшее количество переходов, через которые искатель должен пройти, прежде чем он может добраться до сокровища.
Примеры
|
Ввод 31 9 15 25 30 6 9 19 24 27 4
|
Вывод 6 |
Ввод 10000 5 52 4 9 25 27
|
Вывод 9953 |
Пояснение к первому примеру: 1-4-15-14-13-30-31 К сокровищу можно добраться, пройдя 6 проходов |
__________________________________________________________________________________________________
Задача Cool2k17. Назовем число «крутым», если в его десятичной записи присутствуют только цифры 0, 1, 2. Перестановка чисел A1, A2, ..., An лексикографически меньше перестановки B1, B2, ..., Bn, если существует k такое, что для всех i <k справедливо Ai = Bi и для Ak <Bk. Вам дано число N - длина перестановки (количество цифр в перестановке), а также число K - номер перестановки среди всех перестановок, отсортированных лексикографически. Вам необходимо найти количество «крутых» чисел, стоящих на «крутых» местах, то есть их индексы в перестановке также являются «крутыми» числами. Элементы в перестановке нумерованы с 1.
Технические условия. Программа Cool2k17 считывает с клавиатуры два числа N и K, оба не большем по 1018. Программа должна вывести единственное число - ответ задачи. В случае, если K-й перестановки не существует, следует вывести -1.
Примеры:
|
Ввод |
Вывод |
|
3 12 |
-1 |
|
3 4 |
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<=232
Программа выводит на устройство стандартного вывода единственное число – сумму результатов (по модулю) на всех запросах.
Примеры
Ввод Вывод
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 <1018) через пробел к одной строке. Программа выводит на устройство стандартного вывода единственное число - искомую величину.
|
Ввод 20 30 |
Вывод 2 |
|
145 192 |
4 |
|
2224222 2224222
|
1 |
Комментарий к второму примеру. Жизнеспособности чисел 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 пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара фирм упоминается в списке не более одного раза. Все числа разделены пробелами. Программа выводит на устройство стандартного вывода максимальное число фирм, которые сможет купить Чайник.
Примеры
|
Ввод |
|
7 1 0 0 0 0 0 1 6 1 2 1 3 1 4 4 5 5 6 2 5 Вывод 4 |
|
Ввод 3 0 0 0 0 Вывод 0 |
_________________________________________________________________________
Заданиия подготовили В.Бездушный, Г.Непомнящий, Ю.Пасихов, М.Стречень