Информатика

В файле содержится последовательность натуральных чисел.
Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых хотя бы одно число делится на минимальный элемент последовательности, кратный 21. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар через пробел. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

Скачать файл

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2 при n < 3;
F(n) = F(n − 2) + F(n − 1) – n, если n > 2 и при этом n чётно;
F(n) = F(n − 1) − F(n − 2) + 2 × n, если n > 2 и при этом n нечётно.
Чему равно значение функции F(32)?

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?

Значение арифметического выражения  записали в системе счисления с основанием 8. Определите количество цифр 7 в записи этого числа.

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 234 символов и содержащий только десятичные цифры и символы из 1350-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 65 536 идентификаторов. В ответе запишите только целое число – количество Кбайт.

Текст романа Льва Николаевича Толстого «Анна Каренина» представлен в виде файлов нескольких форматов. Откройте один из файлов и определите, сколько раз встречается в тексте отдельное слово «душа» со строчной буквы.
В ответе запишите только число.

Скачать файл

Откройте файл электронной таблицы, содержащей в каждой строке пять натуральных чисел. Определите количество строк таблицы, в которых квадрат суммы максимального и минимального чисел в строке больше суммы квадратов трёх оставшихся.

Скачать файл

Все пятибуквенные слова, в составе которых могут быть только буквы Б, А, Т, Ы, Р, записаны в алфавитном порядке и пронумерованы начиная с 1.
Ниже приведено начало списка.
1. ААААА
2. ААААБ
3. ААААР
4. ААААТ
5. ААААЫ
6. АААБА
…
Под каким номером в списке идёт первое слово, которое не содержит ни одной буквы Ы и не содержит букв А, стоящих рядом?

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 4₁₀ = 100₂ результатом будет являться число 20₁₀ = 10100₂, а для исходного числа 5₁₀ = 101₂ результатом будет являться число 53₁₀ = 110101₂.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее, чем 441. В ответе запишите это число в десятичной системе счисления.

По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 01, Р – 001. Для трёх оставшихся букв Б, Н и А кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова БАРАБАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Миша заполнял таблицу истинности логической функции F но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт B и из пункта A в пункт E.
В ответе запишите целое число.

Дочь короля Флатландии собирается выйти за прекрасного принца. 
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. 
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе. 
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:
 

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел ai,j, где j-й элемент i-й строки равен ai,j (0 <= a_i,j <= 10¹⁸).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

На вход программы поступает строка s.  Используя обращения к символам по индексу и срезы строк выведите следующие подстроки:

1. все символы, начиная с индекса 3, до середины строки включительно (при нечетной длине строки, средний символ не брать);
2. последний символ;
3. все символа с четными индексами (0, 2, ...);
4. все символы с нечетнымы индексами (1, 3, ...);
5. все символы, кроме последнего;
6. все символы, кроме первого;
7. все символы в обратном порядке;
8. все символы в обратном порядке, начиная с 3 с конца, и кроме первых двух;
9. все символы первой половины в обратном порядке, кроме первого (при нечетной длине строки, средний символ не брать);
10. скопировать срезом всю строку s в строку s2.

Допишите строчки в программе.
 

Примеры

№	Входные данные	Выходные данные
1	Hallo, World!	lo, ! Hlo ol! al,Wrd Hallo, World allo, World! !dlroW ,ollaH lroW ,oll ,olla Hallo, World!

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Среди натуральных чисел, не превышающих 10⁹, найдите все числа, соответствующие маске 12345?6?8 и делящиеся на 17 без остатка.
В ответе запишите все найденные числа в порядке возрастания, и через пробел от найденного числа - соответствующее ему частное от деления на 17.

В одной строке должно быть записано только одна пара чисел: само число и через пробел - соответствующее ему частное от деления на 17.
Каждая пара чисел выводится в отдельной строке. 

Строки выводятся в порядке возрастания найденных чисел.

Текстовый файл состоит не более, чем из 10⁶ символов из набора A, B, C.
Найдите максимальное количество подряд идущих пар символов АС или АВ. Искомая подстрока может включать только пары АВ, только пары АС или содержать одновременно как пары АС, так и пары АВ.

Файл к заданию

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

1. Прибавить 2
2. Умножить на 2

Первая команда увеличивает число на экране на 2, вторая – вдвое.
Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 52 и при этом траектория вычислений программы содержит число 16?

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) 1 камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (10, 6), (20, 10) и (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 223. В начальный момент в первой куче было 17 камней, во второй куче – S камней, 1 <= S <= 205.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
 

Вопрос 1

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. При каком минимальном значении S такое возможно?
 

Вопрос 2

Известно, что Петя имеет выигрышную стратегию. Укажите два значения при которых:

• Петя не может победить первым ходом;
• при любом ходе Вани Петя побеждает своим вторым ходом.

В ответе укажите два числа в порядке возрастания их значений.
 

Вопрос 3

Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
 

Формат ввода ответов 

На каждое задание ответы пишите с новой строки. Если вы не знаете ответ на какое-либо задание, напишите в ответе любое число.

Например, если ответ на вопрос  1 - 1, на вопрос 2 - 2 и 3, на вопрос 3 - 4, то ответы надо записать так:

1
2 3
4

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. 
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стены Робот пройти не может. 
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Оба числа указываются в одной строке через один пробел.

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