Задачи:
Буду очень благодарен соточкой на киви)
В одной из версий очень цивилизованной стратегической игры количество денег выражается целым знаковым 32-битным числом.
После поражения от сильного противника игрок Вася потерял все деньги и получил следующий ультиматум: он должен отдать ещё 1 золотой на первом ходу. Если он не отдаст, то на втором ходу он должен дополнительно будет отдать N золотых (то есть общий долг станет равным N+1), на каждом следующем ходу начисляемая дополнительно сумма также увеличивается в N раз, то есть в начале третьего хода Вася будет должен N2+N+1 и так далее.
Вася уже собрался было продать какую-нибудь постройку и заплатить один золотой, но его сестра Катя заметила, что если Вася подождёт какое-то время, то на очередном ходу долг станет отрицательным и управляемая Васей цивилизация даже заработает на этом инциденте.
Какое наименьшее количество ходов должен подождать Вася, чтобы прогноз Кати сбылся.
Формат ввода
Входные данные содержат одно целое число N (2≤N≤1000) — коэффициент роста долга. Гарантируется, что входные данные подобраны так, что ответ всегда существует.
Формат вывода
Выведите одно целое число — минимальное количество ходов, после которых прогноз Кати сбудется.
Пример 1
Ввод
2
Вывод
32
Пример 2
Ввод
3
Вывод
22
После поражения от сильного противника игрок Вася потерял все деньги и получил следующий ультиматум: он должен отдать ещё 1 золотой на первом ходу. Если он не отдаст, то на втором ходу он должен дополнительно будет отдать N золотых (то есть общий долг станет равным N+1), на каждом следующем ходу начисляемая дополнительно сумма также увеличивается в N раз, то есть в начале третьего хода Вася будет должен N2+N+1 и так далее.
Вася уже собрался было продать какую-нибудь постройку и заплатить один золотой, но его сестра Катя заметила, что если Вася подождёт какое-то время, то на очередном ходу долг станет отрицательным и управляемая Васей цивилизация даже заработает на этом инциденте.
Какое наименьшее количество ходов должен подождать Вася, чтобы прогноз Кати сбылся.
Формат ввода
Входные данные содержат одно целое число N (2≤N≤1000) — коэффициент роста долга. Гарантируется, что входные данные подобраны так, что ответ всегда существует.
Формат вывода
Выведите одно целое число — минимальное количество ходов, после которых прогноз Кати сбудется.
Пример 1
Ввод
2
Вывод
32
Пример 2
Ввод
3
Вывод
22
На одной планете в далёкой-далёкой галактике живут два вида организмов. Обозначим их за A и B. Организмы вида A питаются организмами типа B, однако A может съесть B, только если размер хищника (A) строго больше размера жертвы (B).
Например, пусть популяция A состоит из организмов с размерами {8,1,7,3,1}, а популяция организмов B — с размерами {3,6,1}, тогда существуют 7 пар A,B таких, что A>B: (8,3), (8,6), (8,1), (7,3), (7,6), (7,1), (3,1).
Вам даны размеры организмов в каждой из популяций. Напишите программу, которая подсчитывает количество таких пар A,B, что A строго больше B.
Формат ввода
Первая строка входных данных содержит одно целое число T (1≤T≤30) — количество тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N (1≤N≤2⋅104) и M (1≤M≤2⋅104), задающие количество организмов типа A и типа B соответственно. Следующая строка содержит N целых положительных чисел — размеры организмов типа A. Третья строка содержит M целых положительных чисел — размеры организмов типа B. Размер одного организма не превосходит 109.
Формат вывода
Для каждого тестового примера выведите одно число — количество таких пар A,B, что Aстрого больше B.
Пример
Ввод
2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215
Вывод
7
1
Например, пусть популяция A состоит из организмов с размерами {8,1,7,3,1}, а популяция организмов B — с размерами {3,6,1}, тогда существуют 7 пар A,B таких, что A>B: (8,3), (8,6), (8,1), (7,3), (7,6), (7,1), (3,1).
Вам даны размеры организмов в каждой из популяций. Напишите программу, которая подсчитывает количество таких пар A,B, что A строго больше B.
Формат ввода
Первая строка входных данных содержит одно целое число T (1≤T≤30) — количество тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N (1≤N≤2⋅104) и M (1≤M≤2⋅104), задающие количество организмов типа A и типа B соответственно. Следующая строка содержит N целых положительных чисел — размеры организмов типа A. Третья строка содержит M целых положительных чисел — размеры организмов типа B. Размер одного организма не превосходит 109.
Формат вывода
Для каждого тестового примера выведите одно число — количество таких пар A,B, что Aстрого больше B.
Пример
Ввод
2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215
Вывод
7
1
Дима — системный администратор в университете. Сейчас он разбирается с крупной проблемой — некоторые из компьютеров в дисплейных классах дружественной университету школы заражены компьютерным вирусом. Антивирусное ПО не помогает — вирус слишком свежий...
Дима нашёл компьютер, с которого началось заражение, после чего собрал лог по всем переданным по локальной сети пакетам. Выяснилось, что в случае, если компьютер получил данные от компьютера, зараженного вирусом, компьютер заражается (при этом если компьютер только отправлял данные на зараженный компьютер, заражения не происходит).
Так как размер лога очень большой, Дима предлагает распараллелить усилия и просит Вас написать программу, которая определит список заражённых компьютеров (а сам он будет разбираться с тем, как обезвредить вирус на конкретном компьютере).
Формат ввода
Входные данные состоят из нескольких (не более 30) тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N и M (0 < N ≤ 2 ⋅ 104, 0 ≤ M ≤ 2 ⋅ 104), где N — количество компьютеров в школьной сети и M — количество записей в логе о переданных пакетах данных.
В последующих M строках задаются пакеты, по одному на строку. Каждый пакет задаётся тремя целыми числами ti, si и di — временем отправки пакета, номером компьютера, с которого был отправлен пакет и номером компьютера, на который был отправлен пакет, соответственно (0 ≤ ti ≤ 109, 1 ≤ si, di ≤ N, si ≠ di, все ti попарно различны).
Компьютер, зараженный первым, имеет id 1.
Входные данные завершаются строкой с двумя нулями. Обрабатывать эту строку как тестовый пример не требуется.
Гарантируется, что объём входных данных не превосходит 5 мебибайт.
Формат вывода
Для каждого тестового примера выведите одно число — количество компьютеров, заражённых вирусом.
Пример
Ввод
3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0
Вывод
3
1
Дима нашёл компьютер, с которого началось заражение, после чего собрал лог по всем переданным по локальной сети пакетам. Выяснилось, что в случае, если компьютер получил данные от компьютера, зараженного вирусом, компьютер заражается (при этом если компьютер только отправлял данные на зараженный компьютер, заражения не происходит).
Так как размер лога очень большой, Дима предлагает распараллелить усилия и просит Вас написать программу, которая определит список заражённых компьютеров (а сам он будет разбираться с тем, как обезвредить вирус на конкретном компьютере).
Формат ввода
Входные данные состоят из нескольких (не более 30) тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N и M (0 < N ≤ 2 ⋅ 104, 0 ≤ M ≤ 2 ⋅ 104), где N — количество компьютеров в школьной сети и M — количество записей в логе о переданных пакетах данных.
В последующих M строках задаются пакеты, по одному на строку. Каждый пакет задаётся тремя целыми числами ti, si и di — временем отправки пакета, номером компьютера, с которого был отправлен пакет и номером компьютера, на который был отправлен пакет, соответственно (0 ≤ ti ≤ 109, 1 ≤ si, di ≤ N, si ≠ di, все ti попарно различны).
Компьютер, зараженный первым, имеет id 1.
Входные данные завершаются строкой с двумя нулями. Обрабатывать эту строку как тестовый пример не требуется.
Гарантируется, что объём входных данных не превосходит 5 мебибайт.
Формат вывода
Для каждого тестового примера выведите одно число — количество компьютеров, заражённых вирусом.
Пример
Ввод
3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0
Вывод
3
1
Пусть задано шестнадцатеричное число. Рассмотрим все шестнадцатеричные числа, которые можно получить из заданного перестановками цифр (при этом перестановки, в которых на первом месте оказывается 0, из рассмотрения исключаются, а исходное число, наоборот, включается). Для каждого такого числа считаем остаток от его деления на 5.
Требуется найти среднее арифметическое таких остатков всех рассматриваемых чисел.
Формат ввода
Входные данные содержат одно шестнадцатеричное число, состоящее из не более чем 20 знаков. Цифры, большие 9, обозначаются строчными латинскими буквами от ‘a’ до ‘z’. Гарантируется, что первой цифрой числа не является 0.
Формат вывода
Выведите среднее арифметическое остатков от деления всех корректных (то есть не имеющих ведущих нулей) чисел, образованных перестановками цифр в данном числе, от деления на 5, с точностью не хуже 10−9.
Пример 1
Ввод
222
Вывод
1
Пример 2
Ввод
aaa
Вывод
0
Требуется найти среднее арифметическое таких остатков всех рассматриваемых чисел.
Формат ввода
Входные данные содержат одно шестнадцатеричное число, состоящее из не более чем 20 знаков. Цифры, большие 9, обозначаются строчными латинскими буквами от ‘a’ до ‘z’. Гарантируется, что первой цифрой числа не является 0.
Формат вывода
Выведите среднее арифметическое остатков от деления всех корректных (то есть не имеющих ведущих нулей) чисел, образованных перестановками цифр в данном числе, от деления на 5, с точностью не хуже 10−9.
Пример 1
Ввод
222
Вывод
1
Пример 2
Ввод
aaa
Вывод
0
Напомним, что палиндромом называется строка, которая читается одниаково как слева направо, так и справа налево. Например, “А роза упала на лапу Азора". Можно ввести также понятие палиндромичного массива.
Будем считать, что массив a длины n является палиндромом, если для каждого i от 0 до n−1 элементы a и a[n−1−i] равны.
Вам дан массив, вы должны вставить ровно один элемент так, чтобы массив после вставки оказался палиндромом, или сообщить, что таким образом элемент вставить не получится.
Формат ввода
Первая строка входа содержит одно целое число n — длину массив (1≤n≤105).
Вторая строка содержит n целых чисел — элементов массива. i-е число задаёт элемент массива ai−1 с индексом i−1, −109≤ai≤109.
Формат вывода
Если невозможно вставить ровно одно целое число в массив так, чтобы он стал палиндромом, выведите −1. Иначе выведите два целых числа — номер k вставляемого элемента и значение этого элемента v (−109≤v≤109).
Например, если элемент вставляется в начало, то k=0, если элемент вставляется между a[i−1] и a, то k=i, если элемент вставляется в конце, то k=n.
Если ответов несколько, разрешается вывести любой.
Пример
Ввод
2
19 84
Вывод
2 19
Будем считать, что массив a длины n является палиндромом, если для каждого i от 0 до n−1 элементы a и a[n−1−i] равны.
Вам дан массив, вы должны вставить ровно один элемент так, чтобы массив после вставки оказался палиндромом, или сообщить, что таким образом элемент вставить не получится.
Формат ввода
Первая строка входа содержит одно целое число n — длину массив (1≤n≤105).
Вторая строка содержит n целых чисел — элементов массива. i-е число задаёт элемент массива ai−1 с индексом i−1, −109≤ai≤109.
Формат вывода
Если невозможно вставить ровно одно целое число в массив так, чтобы он стал палиндромом, выведите −1. Иначе выведите два целых числа — номер k вставляемого элемента и значение этого элемента v (−109≤v≤109).
Например, если элемент вставляется в начало, то k=0, если элемент вставляется между a[i−1] и a, то k=i, если элемент вставляется в конце, то k=n.
Если ответов несколько, разрешается вывести любой.
Пример
Ввод
2
19 84
Вывод
2 19
PascalABC.NET 3.1
Free Basic 1.04
GNU bash 4.2.24
Delphi 2.4.4
Free Pascal 2.4.4
GNU c 4.9
GNU c x32 4.9
GNU c11 4.9
GNU c11 x32 4.9
GNU c++ 4.9
GNU c++ x32 4.9
GNU c++ 11 4.9
GNU c++ 11 x32 4.9
Clang c11 3.8
Clang cxx11 3.8
Mono C# 5.2
GDC 4.9
Oracle Java 7
Oracle Java x32 7
Oracle Java 8
Haskell 7.10.2
Perl 5.14
PHP 5.3.10
Python 2.7
Python 3.4
pypy 4
Ruby 1.9.3
Scala 2.9.1
GC go
GCC go
Node JS 0.10.28
R
Ocaml 4.02.3
Ruby 2.2.3
Rust 1.2
Kotlin 1.1.50
Free Basic 1.04
GNU bash 4.2.24
Delphi 2.4.4
Free Pascal 2.4.4
GNU c 4.9
GNU c x32 4.9
GNU c11 4.9
GNU c11 x32 4.9
GNU c++ 4.9
GNU c++ x32 4.9
GNU c++ 11 4.9
GNU c++ 11 x32 4.9
Clang c11 3.8
Clang cxx11 3.8
Mono C# 5.2
GDC 4.9
Oracle Java 7
Oracle Java x32 7
Oracle Java 8
Haskell 7.10.2
Perl 5.14
PHP 5.3.10
Python 2.7
Python 3.4
pypy 4
Ruby 1.9.3
Scala 2.9.1
GC go
GCC go
Node JS 0.10.28
R
Ocaml 4.02.3
Ruby 2.2.3
Rust 1.2
Kotlin 1.1.50
Буду очень благодарен соточкой на киви)
Последнее редактирование модератором:
