Профиль – специализированный

Задание 1.

Из булевой алгебры известно, что операция логического сложения по модулю 2 (или логического исключаещего ИЛИ – xor) используется в простом шифровании. К неизвестной последовательности HIDDEN применили ключ шифрования KEY: «ключ для шифрования логического сложения по модулю два или сокращенно xor» и получили зашифрованную последовательность CRYPT: «приветствуем участников финального тура интернет-олимпиады по информатике». Символы ‘«’, ‘»’ не входят в приведенные последовательности, и справедливо выражения HIDDEN xor KEY = CRYPT. Подсчитать сколько символов русского алфавита содержится в исходном выражении HIDDEN?

Задание 2.

Дана таблица с числами в i-й системе счисления:

Здесь X – это число, а Y – его основание. Значения оснований минимального (a) и максимального (b) чисел в десятичной системе счисления, а также среднего (с) (округлив до целого) и суммы (d) чисел в десятичной системе счисления равны ______. (Результат запишите через запятую без пробела в следующем порядке: a,b,c,d.)

Задание 3.

В нулевой момент времени мастеру одновременно поступает N работ.

Работы пронумерованы от 1 до N (N<100). Для каждой работы i заранее известно следующее:

1) время выполнения работы ti, кратное суткам,

2) штраф сi за каждые сутки ожидания работы i до момента начала ее выполнения.

Одновременно может выполняться только одна работа, и если мастер приступает к выполнению некоторой работы, то он продолжает выполнять ее, пока не закончит. Таким образом, суммарный штраф, который надо будет уплатить, выражается следующим образом:

Штраф равен сумме сi*(время начала выполнения работы i) по всем i.

Найти такой порядок выполнения работ, чтобы штраф оказался минимальным.

Найти решение для следующего случая:

Результат записать в следующем виде: первое число сумма штрафа, запятая, последовательность работ через запятую.

Задание 4.

На рынок пришли N продавцов арбузов и M покупателей. У каждого продавца ровно один арбуз, и каждый покупатель хочет купить ровно один арбуз. Каждый продавец объявил минимальную цену, по которой он согласен продать свой арбуз, а каждый покупатель назвал максимальную цену, по которой он согласен купить арбуз. Для назначения единой цены был вызван директор рынка. В его интересах назначить такую цену, чтобы суммарная стоимость всех проданных по этой цене арбузов была максимальной. Как это сделать, не принуждая покупателей и продавцов к изменению заданных ими границ? Проверить решение на следующем примере N = 15, M = 10.

Минимальные допустимые цены продавцов: 90; 110; 150; 50; 90; 90; 50; 110; 90; 110; 50; 90; 150; 90; 90;

Максимальные цены, за которые покупатели согласны купить арбуз: 120; 70; 70; 100; 70; 100; 70; 120; 100; 70

Вывод должен содержать два числа через запятую: единую цену, которая принесет максимальную выручку, и размер этой выручки. Если решений несколько, дать наименьшую единую цену.

Задание 5.

В школе Саше задали решить уравнение

.

Он нашел верный ответ при следующих параметрах: A = 0, B = 1, C = 2 и D = 23. Но Саша догадывался, что существуют другие решения, и захотел решить уравнение в общем виде:

,

где A, B, C, D – неотрицательные целые числа.

Помогите юному школьнику найти общее количество решений для . Результат запишите общей суммой.

Задание 6.

В магазине штучных изделий продают флешки, бляшки, чашки и другие товары. В налоговой инспекции оказались два списка: X и Y. В первом указано количество проданных товаров каждого вида, а во втором – цены каждого вида товаров в копейках. Порядок товаров в списках разный. Значения элементов списка указаны в строках таблицы:

Добрый и злой инспекторы для начисления налогов желают определить наименьшую и наибольшую возможную выручку от всех проданных товаров (через запятую). Найдите эти величины и введите через запятую без пробела.

Задание 7.

В некотором районе проводится всеобщая газификация. Для этого прежде всего нужно построить газораспределительную станцию. Она может располагаться только на участке магистрального газопровода, соединяющего по прямой пункты M и N. На карте района известны координаты этих пунктов: (u₁, v₁) и (u₂, v₂) соответственно. От станции протягиваются отдельные прямолинейные трубы ко всем населенным пунктам. Координаты (x_i, y_i) населенных пунктов заданы в следующей таблице:

Известно, что затраты на проведение газовой трубы пропорциональны квадрату длины трубы. Требуется указать минимальную стоимость затрат на проведение труб. Проведите расчет для следующих трех вариантов координат пунктов M и N:

Ответы введите через запятую без пробела, округлив до целого значения.

Задание 8.

Робот действует по инструкции, написанной на специальном языке.

Если инструкция будет не понята (написана не строго по правилам языка), то действия робота непредсказуемы (вплоть до самоуничтожения).

Напишите программу, определяющую количество простых команд (слов) правильной инструкции или номер первого ошибочного слова. Вывод результат организовать следующим образом:

0 и через запятую без пробела количество простых команд (слов) правильной инструкции;

1 и через запятую без пробела номер первого ошибочного слова.

Запятая отделяет каждую группу. Число считать как одно слово.

Правила составления инструкции следующие:

Входные инструкции:

Задание 9.

Поездка

С окраины в центр города каждое утро на работу по одному маршруту едут в троллейбусе N = 4 человек. За долгое время поездок они достаточно хорошо узнали друг друга, да к тому же они работали в одном учреждении. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P = 2.

Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины – a_i и b_i. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется a_i, если же он стоит, то прибавляется b_i.

Всего в троллейбусе M = 4 сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Вычислить значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины a_i и b_i, а также номера остановок (таблица), на которых он садится и выходит из троллейбуса.

Задание 10.

В алфавите племени мумба-юмба только три буквы, которые обозначаются как A, B и D. Юношам в день совершеннолетия принято давать взрослые имена, состоящие ровно из 21 буквы. Повторение букв в имени не ограничивается. Если юноша не может представить вождю скальп врага, то в имени присутствует подстрока BAD (возможно, в нескольких экземплярах), иначе такие имена категорически запрещаются. Сколько разных имен может быть в племени мумба-юмба для юношей, запоздавших в развитии (не представивших скальп)?

Задание 11.

Профессор Психовецкий решил покрасить все числа от 1 до N так, чтобы каждые два числа A и B имели разный цвет, если A делится на B нацело. Каким минимальным количеством цветов можно обойтись? Дайте ответ для N = 60000, N = 200000, N = 500000 и N = 1000000 через запятую без пробела.

Задание 12.

Гомер Симпсон внес 2 миллиарда долларов на распространение дисков с фильмами о себе и потребовал как можно более полного освоения этой суммы. Имеется 3 вида дисков, которые продаются по ценам C₁, C₂ и C₃ долларов. Нужно купить как можно больше дисков так, чтобы осталась неизрасходованной как можно меньшая сумма денег. Требуется указать, сколько долларов осталось неизрасходованными для следующих 5 вариантов значений C₁, C₂ и C₃:

Ответы введите через запятую без пробела.