1, Д1, 3, 5, 6, 7, Д7, Д7, Д7, 8, Д8, Д9, 11, Д11, 12, Д12, Д12, 13, 14, Д14, 16, Д18, Д19, Д19 C4, Д23, Д24 C1, Д25 C2, Д26 C3
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 1 | |||||
| B | 1 | 10 | 7 | 10 | ||
| C | 10 | 8 | ||||
| D | 7 | 2 | ||||
| E | 10 | 8 | 2 | 5 | ||
| F | 5 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Укажите наибольшее десятичное число, которое в двоичной системе счисления можно записать с помощью трёх цифр.
На городской тур олимпиады по математике отбираются те учащиеся, кто набрал на районном туре не менее 12 баллов или полностью решил хотя бы одну из двух самых сложных задач (№ 6 или № 7). За полное решение задач 1–4 даётся 2 балла; задач 5, 6 — 3 балла; задачи 7 — 4 балла. Дан фрагмент таблицы результатов районного тура.
| Фамилия | Пол | Задача № 1 | Задача № 2 | Задача № 3 | Задача № 4 | Задача № 5 | Задача № 6 | Задача № 7 |
|---|---|---|---|---|---|---|---|---|
| Айвазян | ж | 1 | 0 | 2 | 1 | 0 | 3 | 3 |
| Житомирский | м | 2 | 2 | 2 | 2 | 2 | 3 | 3 |
| Иваненко | ж | 2 | 1 | 1 | 0 | 1 | 2 | 3 |
| Лимонов | м | 2 | 1 | 1 | 1 | 2 | 2 | 3 |
| Петраков | м | 2 | 0 | 0 | 1 | 0 | 2 | 0 |
| Рахимов | м | 2 | 2 | 2 | 0 | 2 | 0 | 1 |
| Суликашвили | ж | 1 | 1 | 1 | 1 | 1 | 2 | 3 |
| Толкачёва | ж | 2 | 2 | 2 | 1 | 2 | 2 | 0 |
Сколько девочек из этой таблицы прошли на городской тур?
У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его.
Например, 2121 — это программа
умножь на 2
прибавь 1
умножь на 2
прибавь 1,
которая преобразует число 1 в число 7.
Запишите порядок команд в программе преобразования числа 4 в число 79, содержащей не более 8 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Определите число, которое будет напечатано в результате выполнения программы.
Для Вашего удобства программа представлена на четырёх языках программирования.
| Бейсик | Паскаль |
|---|---|
DIM I, S AS INTEGER I = 0 S = 64 WHILE S > 8 S = S – 8 I = I + 1 WEND PRINT(I)
| var i, s: integer; begin i := 0; s := 64; while s > 8 do begin s := s – 8; i := i + 1 end; writeln(i) end.
|
| Си++ | Алгоритмический язык |
#include <iostream> using namespace std; int main() { int i, s; i = 0; s = 64; while (s > 8) { s = s – 8; i++; } cout << i << endl; }
| алг нач цел i, s i := 0 s := 64 нц пока s > 8 s := s - 8 i := i + 1 кц вывод i кон |
| Python | |
i = 0 s = 64 while s > 8: s -= 8 i += 1 print(i)
| |
Документ объёмом 40 Мбайт можно передать с одного компьютера на другой двумя способами.
А) Сжать архиватором, передать архив по каналу связи, распаковать.
Б) Передать по каналу связи без использования архиватора.
Какой способ быстрее и насколько, если:
· средняя скорость передачи данных по каналу связи составляет 223 бит в секунду;
· объём сжатого архиватором документа равен 30% исходного;
· время, требуемое на сжатие документа, – 10 секунд; на распаковку — 1 секунда?
В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите количество секунд, на сколько этот способ быстрее другого, без указания размерности.
Например, запись ответа Б23 означает, что способ Б быстрее на 23 секунды.
Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которой также могут встречаться следующие символы.
Символ «?» (вопросительный знак) означает ровно один произвольный символ.
Символ «*» (звёздочка) означает любую последовательность символов
произвольной длины, в том числе «*» может задавать и пустую последовательность.
Определите, какое из указанных имён файлов удовлетворяет маске:
b?ar*.?xt
1) baara.xt
2) blar.xt
3) bar.ext
4) blar.txt
В электронной таблице значение формулы =СРЗНАЧ(B5:E5) равно 80. Чему равно значение формулы =СУММ(B5:D5), если значение ячейки E5 равно 20? Пустых ячеек в таблице нет.
Дан фрагмент электронной таблицы.
| A | B | C | |
| 1 | 1 | 6 | |
| 2 | =A1+B1/2 | =(1+A1+B1)/4 | =(C1–1)*2 |
Какое целое число должно быть записано в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:С2 соответствовала рисунку?
Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.
Все 4-буквенные слова, составленные из букв В, Н, Р, Т, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. ВВВВ
2. ВВВН
3. ВВВР
4. ВВВТ
5. ВВНВ
……
Запишите слово, которое стоит под номером 251.
Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А — 0; Б — 10; В — 110. Каким кодовым словом нужно кодировать символ Г, чтобы длина его была минимальной, а код при этом допускал однозначное разбиение кодированного сообщения на символы?
1) 1
2) 1110
3) 111
4) 11
Рассмотрим алгоритм, преобразующий одно целое число в другое.
A. Умножить текущее число на 2.
B. Прибавить к результату 3.
C. Если получившееся число больше или равно 19, вычесть из него 19.
Какое получится число, если повторить этот алгоритм 7 раз для исходного числа 4?
1) 0
2) 8
3) 3
4) 9
Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 7 символов. В качестве символов используются десятичные цифры и 26 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!).
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который занимает хранение 65 паролей. (Ответ дайте в байтах.)
Производится одноканальная (моно) цифровая звукозапись. Значение сигнала фиксируется 16 000 раз в секунду, для записи каждого значения используется 32 бит. Результаты записываются в файл, сжатие данных не производится.
Размер файла с записью не может превышать 3 Мбайт. Какое из приведённых ниже чисел наиболее близко к максимально возможной продолжительности записи, выраженной в секундах?
1) 37
2) 49
3) 74
4) 98
Система команд исполнителя РОБОТ, «живущего» в клетках прямоугольного лабиринта на плоскости:
вверх, вниз, влево, вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево←, вправо →.
Четыре условия позволяют проверить отсутствие преград у каждой из сторон той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно.
В цикле
ПОКА <условие> команда
команда выполняется, пока условие истинно, иначе происходит переход на следующую строку программы.
Если РОБОТ начнёт движение в сторону стены рядом с которой он стоит, то робот разрушится, и выполнение программы прервётся. Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < слева свободно > вниз
ПОКА < снизу свободно > вправо
ПОКА < справа свободно > вверх
ПОКА < сверху свободно > влево
КОНЕЦ
Дан фрагмент таблицы истинности выражения F.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Каким выражением может быть F?
1) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ x7
2) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7
3) x1 ∧ ¬x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7
4) x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 16.8.192.181
Маска: 255.255.192.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы, без использования точек.
| A | B | C | D | E | F | G | H |
| 0 | 255 | 16 | 181 | 192 | 64 | 128 | 8 |
Пример.
Пусть искомый IP-адрес — 192.168.128.0 и дана таблица.
| A | B | C | D | E | F | G | H |
| 128 | 168 | 255 | 8 | 127 | 0 | 17 | 192 |
В этом случае правильный ответ будет записан в виде: HBAF.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Л?
Запишите число 128 в пятеричной системе счисления. В ответе укажите только цифры, основание системы счисления писать не нужно.
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» — символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в тысячах) |
|---|---|
| Крейсер | Линкор | 3700 |
| Крейсер & Линкор | 400 |
| Линкор | 1800 |
Какое количество страниц (в тысячах) будет найдено по запросу Крейсер?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими рекуррентными соотношениями:
F(n) = 1 при n = 1;
F(n) = F(n − 1) · n при n ≥ 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Определите значение переменной c после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования). Ответ запишите в виде целого числа.
| Бейсик | Паскаль |
|---|---|
a = 27 b = 3 b = 2 * a / 3 * b IF a > b THEN c = a - b ELSE c = b + 2 * a ENDIF | a := 27; b := 3; b := 2 * a / 3 * b; if a > b then c := a - b else c := b + 2 * a; |
| Си++ | Алгоритмический язык |
a = 27; b = 3; b = 2 * a / 3 * b; if (a > b) c = a - b; else c = b + 2 * a; | a := 27 b := 3 b := 2 * a / 3 * b если a > b то c := a - b иначе c := b + 2 * a все |
| Python | |
a = 27 b = 3 b = 2 * a / 3 * b if a > b: c = a - b else: c = b + 2 * a;
| |
Ниже приведён фрагмент программы, записанный на четырёх языках программирования.
Массив A двумерный; в программе рассматривается его фрагмент, соответствующий значениям каждого индекса от 1 до 9.
| Бейсик | Паскаль |
|---|---|
FOR n=1 TO 9 FOR k=1 TO 9 A(n,k)=2*n+k NEXT k NEXT n | for n:=1 to 9 do for k:=1 to 9 do A[n,k]:=2*n+k
|
| Си++ | Алгоритмический язык |
for (n=1;n<=9;n++) { for (k=1;k<=9;k++) A[n][k]=2*n+k; } }
| нц для n от 1 до 9 нц для k от 1 до 9 A[n,k]=2*n+k кц кц |
| Python | |
for n in range(1, 10): for k in range(1, 10): A[n,k] = 2*n+k | |
Сколько элементов указанного фрагмента массива A будут принимать нечётные значения после выполнения данного фрагмента программы?
Региональный этап олимпиады по информатике проводился для учеников 9–11-х классов. Все ученики участвовали в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 600 баллов. По положению об олимпиаде победители определяются следующим образом.
1. Определяются все участники, набравшие наибольшее среди всех участников количество баллов. Они объявляются кандидатами в победители.
2. Если число кандидатов составляет не более 25% всех участников олимпиады, все кандидаты считаются победителями.
3. Если кандидатов в победители более 25%, то рассматривается количество баллов, набранное кандидатами в победители. Если кандидаты набрали более 300 баллов, все они объявляются победителями. Если балл, набранный кандидатами, не превышает 300 баллов, победителем не признаётся никто.
Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет определять фамилию и имя лучшего участника, не ставшего победителем олимпиады. Если следующий за баллом победителей один и тот же балл набрали несколько человек или если победителей нет, а лучших участников несколько (в этом случае они же являются искомыми), то выдаётся только число искомых участников. Гарантируется, что искомые участники (участник) имеются.
На вход программе сначала подаётся число участников олимпиады N
(N<10000).
В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>,
где <Фамилия> — строка, состоящая не более чем из 20 непробельных символов; <Имя> — строка, состоящая не более чем из 15 непробельных символов; <класс> — число от 9 до 11; <баллы> — целое число от 0 до 600 набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом.
Пример входной строки:
Иванов Пётр 10 275
Программа должна выводить через пробел Фамилию и Имя искомого участника или их число. Пример выходных данных:
Кузнецов Иван
Второй вариант выходных данных:
4
Сколько различных решений имеет система уравнений
x1 ∨ ¬x2 = 1
x2 ∨ ¬x3 = 1
…
x9 ∨ ¬x10 = 1,
где x1, x2, … x10 — логические переменные?
В ответе не нужно перечислять все различные наборы значений x1, x2, … x10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x — действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно. (Ниже для Вашего удобства программа представлена на четырёх языках программирования.)
| Бейсик | Паскаль |
|---|---|
INPUT x IF x<12 THEN IF x>=0 THEN IF x<=6 THEN PRINT "принадлежит" ELSE PRINT "не принадлежит" ENDIF ENDIF ENDIF END | var x: real; begin readln(x); if x<12 then if x>=0 then if x<=6 then write('принадлежит') else write('не принадлежит') end. |
| Си++ | Алгоритмический |
int main(void) { float x; cin >> x; if(x<12) if(x>=0) if(x<=6) cout << "принадлежит"; else cout << "не принадлежит"; } | алг нач вещ x ввод x если x<12 то если x>=0 то если x<=6 то вывод 'принадлежит' иначе вывод 'не принадлежит' все все все кон |
| Python | |
x = int(input()) if x < 12: if x >= 0: if x <= 6: print("принадлежит") else: print("не принадлежит")
| |
Последовательно выполните следующее.
1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки 0, 6, 12 и 18) принадлежат заштрихованным областям (B и D соответственно).
| Область | Условие 1 (x<12) | Условие 2 (x>=0) | Условие 3 (x<= 6) | Программа выведет | Область обрабатывается верно |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
В столбцах условий укажите «да», если условие выполнится; «нет», если условие не выполнится; «—» (прочерк), если условие не будет проверяться; «не изв.», если программа ведёт себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, поставьте «—» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет».
2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от 1 до 5 и содержат годовые оценки по информатике учащихся выпускного класса. Опишите на русском языке или на одном из языков программирования алгоритм, который позволяет подсчитать и вывести средний балл среди «хорошистов» и «отличников» (тех, кто получил итоговую отметку «4» или «5»). Гарантируется, что в классе есть хотя бы один «хорошист» или «отличник». Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Бейсик | Паскаль |
|---|---|
N=30 DIM A(N) AS INTEGER DIM I, X, Y AS INTEGER DIM S AS SINGLE FOR I = 1 TO N INPUT A(I) NEXT I … END | const N=30; var a: array [1..N] of integer; i, x, y: integer; s: real; begin for i:=1 to N do read (a[i]); … end. |
| Си++ | Алгоритмический язык |
#include <iostream> using namespace std; #define N 30 int main(void) {int a[N]; int i, x, y; float s; for (i=0; i < N; i++) cin >> a[i]; … } | алг нач цел N = 30 целтаб a[1:N] цел i, x, y вещ s нц для i от 1 до N ввод a[i] кц ... кон |
| Естественный язык | |
Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, X, Y. Объявляем вещественную переменную S. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. | |
| Python | |
# допускается также # использовать две # целочисленные переменные x, y # и вещественную переменную s a = [] n = 30 for i in range(0, n): a.append(int(input())) ... | |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке
программирования (укажите название и используемую версию языка программирования, например Borland Pascal 7.0) или в виде блок-схемы. В этом случае Вы должны использовать переменные, аналогичные переменным, используемым в алгоритме, записанном на естественном языке, с учётом синтаксиса и особенностей используемого Вами языка программирования.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 106. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 106 или больше камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 105.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.