Вариант 7

Дано N = 10101011₂, М = AD₁₆. Найдите целое значение числа К, которое отвечает условию N < К < М. Ответ запишите в десятичной системе счисления.

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.

Дан фрагмента таблицы истинности выражения F7

Каким выражением может быть F?

1) ¬(x1 ∧ ¬x2 ∧ x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7 ∧ ¬x8)

2) ¬(x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ ¬x5 ∧ x6 ∧ x7 ∧ ¬x8)

3) ¬(¬x1 v x2 v ¬x3 v x4 v x5 v ¬x6 v ¬x7 v x8)

4) ¬(¬x1 v ¬x2 v ¬x3 v x4 v x5 v x6 v x7 v x8)

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

Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

В каталоге находятся шесть файлов:

pig.doc tiger.doc dog.dll haghog.dat goat.docx dig.dat

Ниже представлено восемь масок. Сколько из них таких, которым соответствуют ровно пять файлов из данного каталога?

Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, затем вторая и третья, а далее третья и четвёртая цифры исходного числа.

2. Полученные три числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 7531. Суммы: 7 + 5 = 12; 5 + 3 = 8; 3 + 1 = 4. Результат: 1284.

Укажите наименьшее число, в результате обработки которого автомат выдаст число 1262.

Дан фрагмент электронной таблицы.

Формулу из ячейки D3 скопировали в ячейку С2 так, что числовое значение ячейки С2 стало отличаться от числового значения ячейки D3. Каково стало числовое значение ячейки С2?

У Тани есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2¹⁹ бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Тани по телефонному каналу со средней скоростью 2¹⁵ бит в секунду. Сергей договорился с Таней, что та будет скачивать для него данные объёмом 10 Мбайт по высокоскоростному каналу и ретранслировать их Сергею по низкоскоростному каналу.

Компьютер Тани может начать ретрансляцию данных, не раньше чем им будут получены первые 512 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Таней данных до полного их получения Сергеем?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

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

Бейсик

DIM k, s AS INTEGER
s = 1024
k = 0
WHILE s < 2000
	s = s + 32
	к = к + 1
WEND
PRINT к

Паскаль

var k, s : integer;
begin
	s := 1024;
	k := 0;
	while s < 2000 do
	begin
		s : = s + 32;
		k := k + 1; 
	end;
	write(k); 
end.

Си

{
	int к, s;
	s = 1024;
	k = 0;
	while (s < 2000) {
		s = s + 32;
		k = k + 1;
	}
	printf("%d", k);
}

Алгоритмический язык

нач
	цел k, s
	s := 1024
	k := 0
	нц пока s < 2000
		s := s + 32
		k := k + 1
	кц
вывод k
кон

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А — 0; Б — 111; В — 11001; Г — 11000; Д — 10.

Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Сколько существует различных символьных последовательностей длины 7 в четырёхбуквенном алфавите {А, В, С, D}, которые содержат ровно пять букв А?

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 1

F(2) = 1

F(n) = F(n-1) + F(n-2), при n > 2

Чему равно значение функции F(7)?

В ответе запишите только натуральное число.

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и 1Р-адрес, — в виде четырёх байтов, причем каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 207.123.255.131, а маска равна 255.240.0.0, то адрес подсети равен 207.112.0.0.

По заданным IP-адресу узла и маске определите второй слева байт адреса сети. IP-адрес узла: 14.8.192.131. Маска: 255.255.192.0. Ответ запишите в виде десятичного числа.

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля — ровно 13 символов. В качестве символов используются десятичные цифры и 15 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!).

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

Определите объём памяти (в байтах), который занимает хранение 25 паролей. В ответе укажите только число.

Ниже приведён фрагмент программы, записанный на разных языках программирования. При каком наибольшем введённом числе а после выполнения программы значение переменной с будет равно 45?

Бейсик

INPUT а
b = 15
а = b - 5 * а
IF а * b < 0 THEN
	с = b + 4
ELSE
	с = 3 * b
END IF

Паскаль

readln(а);
b := 15;
а : = b - 5 * а;
if а * b < 0 then
	с : = b + 4
else
	с := 3 * b;

Си

scanf("%d", &a);
b = 15;
a = b - 5 * a;
if (a * b < 0)
	c = b + 4;
else
	c = 3 * b;

Алгоритмический язык

ввод а
b := 15
a := b - 5 * a
если a * b < 0
	то c := b + 4
	иначе c := 3 * b
все

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных способов добраться из населённого пункта А в населённый пункт К?

Известно, что для натурального числа х справедливо равенство:

332_{2x + 1} - 312_{2x + 2} + 89₁₀ = 0

Определите значение х. Ответ запишите в десятичной системе счисления.

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

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

олимпиада & задание

Укажите целое число, которое напечатает компьютер.

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

На числовой прямой даны два отрезка: Р = [44, 48] и Q = [23, 35].

Укажите наибольшую возможную длину промежутка А, для которого формула ((x ∈ P) → (x ∈ Q)) ∧ (x ∈ A)

тождественно ложна, то есть принимает значение 0 при любом значении переменной х.

В программе описан одномерный целочисленный массив с индексами от 0 до 10. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив.

Бейсик

	s = 0 n — 10
FOR 1 = 0 ТО n - 1
	s = s + 2 * A(i) + A(i+1) 
NEXT i

Паскаль

s : = 0;
n := 10;
for i := 0 to n - 1 do begin 
	s := s + 2 * A[i] + A[i+1] 
end;

Си

s = 0; 
n = 10;
for (i = 0; i <= n - 1; i++) 
	s = s + 2 * A [i] + A [i +1];

Алгоритмический язык

s : = 0 
n := 10
нц для i от 0 до n - 1
	s := s + 2 * A[i] + A[i +1]
кц

В начале выполнения этого фрагмента в массиве находились двухзначные нечётные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?

Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает два числа: L и М. Укажите наибольшее из таких чисел х, при вводе которых алгоритм печатает сначала 2, а потом 5.

Бейсик

DIM X, L, M AS INTEGER
INPUT X
L = 0: M = 9
WHILE X > 0
	L = L + 1
	IF M > (X MOD 10) THEN
		M = X MOD 10
	END IF
	X = X \ 10
WEND
PRINT L
PRINT M

Паскаль

var x, L, M: integer;
begin
	readln (x);
	L := 0; M := 9;
	while x > 0 do
	begin
		L := L + 1;
		if M > (x mod 10) then
			M := x mod 10;
		x := x div 10;
	end;
writeln(L); write(M);
end.

Си

#include<stdio.h>
void main()
{
	int x, L, M;
	scanf("%d", &x);
	L = 0; M = 9;
	while (x > 0) {
		L = L + 1;
		if M > x % 10 {
			M = x % 10
		}
		x = x /10;
	}
	printf("%d\n%d", L, M);
}

Алгоритмический язык

алг
нач
	цел х, L, М
	ввод X
	L := 0; М := 9
	нц пока х > 0
		L : = L + 1
		если М > mod(х,10) то
			М := mod (х,10)
		все
		х := div(х,10)
	кц
	вывод L, нс, М
кон

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

Бейсик

DIM А, В, Т, М, R AS INTEGER
А = -20: В - 20
М = A: R = F (А)
FOR Т = А ТО В
	IF F(Т) < R THEN
		М = Т
		R = F (Т)
	END IF
NEXT Т
PRINT М

FUNCTION F (x)
	F = -3 * (x + 2) * (x - 6)
END FUNCTION

Паскаль

var a, b, t, M, R: integer;
function F(x: integer): integer;
begin
	F := -3 * (x + 2) * (x - 6);
end;

begin
	a := -20; b := 20;
	M : = a; R : = F (a) ;
	for t := a to b do
	begin
		if (F(t) < R) then begin
			M := t;
			R := F(t);
		end;
	end;
write(M);
end.

Си

int F(int х)
{
	return -3 * (х + 2) * (х - 6);
}
void main()
{
	int a, b, t, M, R;
	a = -20; b = 20;
	M = a; R = F (a) ;
	for (t = a; t <= b; t++){
		if (F (t) < R) {
			M = t; R = F (t) ;
		}
	}
printf("%d", M) ;
}

Алгоритмический язык

нач
	цел а, b, t, М, R
	а := -20; b := 20
	М := a; R := F(a)
	нц для t от а до b
		если F(t) < R то
			М := t; R := F(t)
		все
	кц
	вывод М
кон

алг цел F(цел х)
нач
	знач := -3 * (х + 2) * (х - 6)
кон

У исполнителя Увеличитель две команды, которым присвоены номера:

Первая из них увеличивает число на экране на 2, вторая увеличивает его на 5. Программа для Увеличителя — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 21?

Сколько существует различных наборов значений логических переменных x₁, х₂, ...x₉, x₁₀, которые удовлетворяют всем перечисленным ниже условиям?

((x₁ ~ x₂) v (x₃ ~ x₄)) ∧ (¬((x₁ ~ x₂) → (x₃ ~ x₄))) = 1

((x₅ ~ x₆) v (x₇ ~ x₈)) ∧ (¬((x₅ ~ x₆) → (x₇ ~ x₈))) = 1

((x₁ ~ x₂) v (x₇ ~ x₈)) ∧ (¬((x₁ ~ x₂) → (x₇ ~ x₈))) = 1

((x₆ ~ x₈) v (x₃ ~ x₄)) ∧ (¬((x₅ ~ x₆) → (x₃ ~ x₄))) = 1

x₉ ~ x₁₀ = 1

В ответе не нужно перечислять все различные наборы значений x₁, х₂, ... x₉, х₁₀, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превосходящее 109, и выводится максимальная цифра этого числа. Программист торопился и написал программу неправильно. (Ниже для Вашего удобства программа представлена на четырёх языках программирования.)

Бейсик

DIM N AS LONG
INPUT N
max digit = 9
WHILE N > 0
	digit = N MOD 10
	IF digit > max digit THEN
		digit = max digit
	END IF
	N = N \ 10
WEND
PRINT max_digit
END

Паскаль

var N: longint;
	digit, max digit: integer;
begin
	readln(N);
	max digit := 9;
	while N > 0 do
	begin
		digit := N mod 10;
		if digit > max digit then
			digit := max digit;
		N := N div 10;
	end;
	writeln(max digit); 
end.

Си

#include <stdio.h>
int main()
{
	long int N;
	int digit, max digit;
	scant("%ld", &N);
	max digit = 9;
	while (N > 0)
	{
		digit = N % 10;
		if (digit > max digit)
			digit = max digit;
		N = N / 10;
	}
	printf(M%d", max digit);
}

Алгоритмический язык

алг
нач
	цел N, digit, max digit
	ввод N
	max digit := 9
	нц пока N > 0
		digit := mod(N, 10)
		если digit > max digit to
			digit := max digit
		все
		N := div(N, 10)
	кц
вывод max_digit
кон

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 384.

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

1) выпишите строку, в которой сделана ошибка;

2) укажите, как исправить ошибку, — приведите правильный вариант строки. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от —1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди положительных элементов массива, оканчивающихся на 5. Если в исходном массиве нет элемента, значение которого положительно и оканчивается цифрой 5, то вывести сообщение «Не найдено». Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Бейсик

N = 30
DIM A(N) AS INTEGER
DIM I, J, MIN AS INTEGER
FOR I = 1 TO N
	INPUT A(I)
NEXT I
. . .
END

Паскаль

const
	N = 30;
var
	a: array [1..N] of integer;
	i, j, min: integer;
begin
	for i := 1 to N do
		readln(a[i]);
end.

Си

#include <stdio.h>
# define N 30
void main() {
	int a[N];
	int i, j, min;
	for (i = 0; i < N; i++)
		scanf("%d", &a[i]);
	...
}

Алгоритмический язык

алг
нач
	цел N = 30
	целтаб а[1:N]
	цел i, j, min
	нц для i от 1 до N
		ввод a[i]
	кц
	...
кон

Естественный язык

Объявляем массив А из 30 элементов. 
Объявляем целочисленные переменные I, J, MIN.
В цикле от 1 до 30 вводим элементы массива А с 1-го по 30-й.

В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 9 камней, за один ход можно получить кучу из 10, 11 или 27 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней.

В начальный момент в куче было S камней, 1 ⩽ S ⩽ 32.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1

а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 2

Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение S, при котором:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в куче.

В лаборатории для большого количества частиц производятся замеры электрического заряда каждой из них. Заряд частицы измеряется как целое число (положительное, отрицательное или 0). Частиц, заряд которых измерен, может быть очень много, но не может быть меньше трёх. Заряды всех частиц различны.

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

Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.

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

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

Нумерация частиц ведётся с единицы.

Пример выходных данных для приведённого выше примера входных данных: 1 3 4.