Олимпиада по информатике школьный этап всероссийской олимпиады. Задания школьного этапа олимпиады по информатике
Всероссийская олимпиада школьников по ИНФОРМАТИКЕ
Школьный этап
9 класс
А1.
Сколько значащих нулей в двоичной записи числа 48?
1) 1 2) 2 3) 4 4) 6
А2.
Считая, что каждый символ кодируется 16-ю битами, оцените информационный объем следующей пушкинской фразы в кодировке Unicode :
Привычка свыше нам дана: Замена счастию она.
1) 44 бита 2) 704 бита 3) 44 байта 4) 704 байта
А3.
Вычислите сумму чисел x и y , при x = 271 8 , y = 11110100 2 . Результат представьте в шестнадцатеричной системе счисления.
1) 151 16 2) 1AD 16 3) 412 16 4) 10B 16
А4.
Определите значение переменной c после выполнения следующего фрагмента программы:
a:= 100;
b:= 30;
a:= a – b*3;
if a > b then
C:= a – b
else c:= b – a;
1) 20 2) 70 3) –20 4) 180
А5.
Для какого числа X истинно высказывание X > 1 ((X
1) 1 2) 2 3) 3 4) 4
А6.
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
1) X ¬Y Z 2) X Y Z 3) X Y ¬Z 4 ) ¬X Y ¬Z
А7.
В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
А8.
Учитель работал в каталоге
D:\Материалы к урокам\10 класс\Практические работы.
Затем перешел в дереве каталогов на уровень выше, спустился в подкаталог
Лекции
и удалил из него файл
Введение
. Каково полное имя файла, который удалил преподаватель?
1) D:\Материалы к урокам\10 класс\Введение
2) D:\Материалы к урокам\10 класс\Лекции\Введение
3) D:\Материалы к урокам\Лекции\Введение
4) D:\Материалы к урокам\Введение\Лекции
А9.
Ниже приведены фрагменты таблиц базы данных учеников школы:
Код класса | Класс | |
1-А | ||
3-А | ||
4-А | ||
4-Б | ||
6-А | ||
6-Б | ||
6-В | ||
9-А | ||
10-А | ||
Фамилия | Код класса | Рост |
Иванов | ||
Петров | ||
Сидоров | ||
Кошкин | ||
Ложкин | ||
Ножкин | ||
Тарелкин | ||
Мискин | ||
Чашкин |
В каком классе учится самый высокий ученик?
1) 3-А 2) 4-А 3) 6-А 4) 9-А
А10.
Разрешение экрана монитора – 1024 х 768 точек, глубина цвета – 16 бит. Каков необходимый объем видеопамяти для данного графического режима?
1) 6 Мбайт 2) 256 байт 3) 4 Кбайта 4) 1,5 Мбайт
А11.
В ячейке C2 записана формула =$E$3+D2 . Какой вид приобретет формула, после того как ячейку C2 скопируют в ячейку B1?
1) =$E$3+C1 2) =$D$3+D2 3) =$E$3+E3 4) =$F$4+D2
А12.
Дан фрагмент электронной таблицы:
B1+1 | ||
A1+2 | ||
B2-1 | ||
После выполнения вычислений, была построена диаграмма по значениям диапазона ячеек A1:A4. Укажите получившуюся диаграмму.
А13.
Некий исполнитель умеет выполнять три команды:
FD – движение вперед на указанное число шагов
RT – поворот направо на указанное число градусов
REPEAT – команда повторения
Рассмотрим решение задач школьного этапа Всероссийской олимпиады школьников по информатике на программирование. Скачать задания вы можете по ссылкам:
Рассмотрим следующие задачи:
Задача №1. Шахматная доска.
Шахматная доска состоит из n × m клеток, покрашенных в черный и белый цвет в «шахматном» порядке. При этом клетка в левом нижнем углу доски покрашена в черный
цвет. Определите, сколько всего на доске черных клеток. Программа получает на вход два числа n и m, записанных в отдельных строках. Все числа - натуральные, не превосходящие 30 000. Программа должна вывести одно целое число - количество черных клеток на доске.
Решение.
Рассмотрим частные случаи:
Видим закономерность:
- если количество полей четное (4х4=16), то на каждом ряду одинаково количество черных и белых клеток, т.е. чтобы найти количество черных полей нужно общее количество клеток разделить на 2. Проверим: 16:2=8. Посчитаем. Действительно 8!! Можете поэкспериментировать с досками других размеров, но чтобы общее число клеток было четным.
- если количество полей нечетное (5х5=25) то дело обстоит иначе. Количество черных клеток вычисляется по формуле: (n+1)/2, где n — общее число полей шахматной доски (25+1)/2=13 — верно!!!)
Если применим данную формулу для досок 3х3 или 5х3 — ответ будет верным.
Программа на Паскале будет выглядеть следующим образом:
var n, m, result: longint; begin readln(n); readln(m); if n*m mod 2 =0 then result:=n*m div 2 else result:= (n*m+1) div 2; writeln(result); end.(Оператор div используется из-за того, что в данном шаблоне, в условии задачи, все переменные имеют целочисленный тип. Если div заменить на обычное деление, то переменную result нужно объявлять как real ).
Задача №2. Манхеттен.
Кварталы Манхэттена состоят из авеню, направленных с юга на север и улиц, направленных с запада на восток. Все улицы и авеню пронумерованы числами, начиная с 1
подряд (первая улица, вторая улица, третья улица и т. д.). Передвигаться можно только по улицами или по авеню.
Миша впервые попал на Манхэттен. Сейчас он стоит на пересечении авеню номер x1 и улицы номер y1. Ему нужно попасть на перекресток авеню номер x2 и улицы номер y2.
Определите маршрут, который он должен пройти. Программа получает на вход 4 числа: x1, y1, x2, y2, записанных в отдельных строках. Все числа - натуральные, не превышают 103. Начальное и конечное расположение Миши не совпадают.
Программа должна вывести последовательность из латинских заглавных букв, описывающих маршрут, которому должен следовать Миша. Буква «N» обозначает перемещение на один квартал на север, «S» - на юг, «W» - на запад, «E» - на восток. Программа должна вывести самый короткий из всех возможных маршрутов, если же кратчайших маршрутов существует несколько, то программа должна вывести любой из них (но только один).
Программа может выводить последовательность ходов не в одну строку (как в примере), а каждый символ ответа - в отдельной строке (например, если каждый символ
ответа выводится при помощи отдельной команды вывода внутри цикла).
Решение.
Представим систему улиц и авеню в виде системы координат, где перекрестки — это точки с соответствующими координатами (пересечение второго авеню и первой улицы — точка с координатами (2;1); пересечение четвертого авеню и третей улицы — точка с координатами (4;3) и т.д.)
Чтобы добраться от перекрестка второй авеню и четвертой улицы (точка А) до перекрестка шестой авеню и первой улицы (точка В) нужно пройти вправо на x2 — x1 = dx (6-2 = 4) и вниз на y2 — y1 = dy (4 — 1 = 3) . Если бы точка В была на месте точки А, а точка А на месте точки В, то пришлось бы двигаться влево на dx и вверх на dy. Т.е. от взаимного расположения этих точек (А и В) зависит направление движения.
Напишем программу на языке Паскаль:
var x1,y1,x2,y2,dx,dy,i:integer; begin readln(x1,y1,x2,y2); dx:=abs(x1-x2); // расстояние по оси x dy:=abs(y1-y2); // расстояние по оси y if x2>x1 then // если точка В правее точки А, то... for i:=1 to dx do write("E") else for i:=1 to dx do write("W"); if y1>y2 then // если точка А выше точки В, то... for i:=1 to dy do write("S") else for i:=1 to dy do write("N"); end.Остальные задачи несколько сложнее. В ближайшее время будет разбор. Следите за обновлениями, подписывайтесь!
Рассмотрим таблицу, содержащую n строк и m столбцов, в каждой клетке которой расположен ноль или единица. Назовем такую таблицу симпатичной, если в ней нет ни одного квадрата 2 на 2, заполненного целиком нулями или целиком единицами.
Так, например, таблица 4 на 4, расположенная слева, является симпатичной, а расположенная справа таблица 3 на 3 — не является.
Задано несколько таблиц. Необходимо для каждой из них выяснить, является ли она симпатичной.
Входные данные
Первая строка входного файла INPUT.TXT содержит количество t (1 ≤ t ≤ 10) наборов входных данных. Далее следуют описания этих наборов. Описание каждого набора состоит из строки, содержащей числа n и m (1 ≤ n,m ≤ 100), и n строк, каждая из которых содержит по m чисел, разделенных пробелами. j-ое число в i+1-ой строке описания набора входных данных — элемент a ij соответствующей таблицы. Гарантируется, что все a ij равны либо нулю, либо единице.
Выходные данные
Для каждого набора входных данных выведите в файл OUTPUT.TXT единственную строку, содержащую слово «YES», если соответствующая таблица является симпатичной, и слово «NO» — в противном случае.
Пример
INPUT.TXT | OUTPUT.TXT |
|
| 3 1 1 0 4 4 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 3 3 0 0 1 0 0 1 1 1 1 | YES YES NO |
Задание рассчитано на написание программы на любом языке программирования.
Ввод данных может осуществляться как из входного файла, так и с клавиатуры.
Заданы два числа: N и K. Необходимо найти остаток от деления N на K.
Входные данные
Входной файл INPUT.TXT содержит два целых числа: N и K (1 <= N <= 10 100 , 1 <= K <= 10 9 ).
Выходные данные
В выходной файл OUTPUT.TXT выведите остаток от деления N на K.
Примеры
INPUT.TXT | OUTPUT.TXT |
|
| 239 16 | 15 | |
| 4638746747645731289347483927 6784789 | 1001783 |
Задание рассчитано на написание программы на любом языке программирования.
Ввод данных может осуществляться как из входного файла, так и с клавиатуры.
Ваня наблюдает за лягушкой. Изначально она сидит в точке 0 числовой прямой. Каждую секунду она прыгает на 1 вправо, пока не достигнет точки K .Затем она начинает каждую секунду прыгать на 1 влево, пока не вернется в точку 0,затем – опять вправо и т.д. Требуется определить, где окажется лягушка через T секунд.
Формат входных данных
Во входном файле input.txt в двух строках находятся два числа K и T , разделенные пробелом. Оба
числа натуральные и не превосходят 1 000 000 000.
Формат выходных данных
Вывести в выходной файл output.txt одно число – координату лягушки в момент времени T.
Пример
8 2
Примечание
Программа не должна выводить никаких дополнительных сообщений, а также не может содержать операторов, вызывающих задержку выполнения программы (например, readln в конце программы)
Ключи
к заданиям первого (школьного) этапа Всероссийской предметной олимпиады школьников
по информатике и ИКТ 2016/2017 учебный год
класс ( max – 45 баллов )
Задача 1. “Проверка на симпатичность” – 20 баллов
Тип задачи: Задача по программированию. Двумерные массивы
Задание рассчитано на написание программы на любом языке программирования.
Ввод данных может осуществляться как из входного файла, так и с клавиатуры.
В этой задаче необходимо последовательно считывать в двумерный массив все представленные матрицы и проверять их на симпатичность, результат проверки выводить в выходной файл. Для проверки текущей матрицы на симпатичность можно в двойном цикле перебрать всевозможные подмассивы 2х2 и проверить: существует ли среди них хотя бы один, состоящий из одинаковых элементов. Если — да, то в файл нужно вывести «NO» и «YES» в противном случае. Механизм проверки одной матрицы на симпатичность можно описать следующим образом:
Ok=true;
for i=1..n-1{
for j=1..m-1{
if((a[i][j]+a[i]+a[j]+a) mod 4 == 0) Ok=false;
if(Ok) write(«YES») else write(«NO»);
Следует заметить, что использование двумерного массива вовсе не обязательно. Здесь не обязательно запоминать все элементы матрицы, достаточно помнить предыдущую и текущую строчку и в процессе считывания данных проверять подмассивы 2х2. Такой алгоритм немного сложнее для реализации, но более экономичен по используемой памяти, что иногда не менее важно.
Задача 2. “Деление с остатком” – 10 баллов
Тип задачи: Задача по программированию. Целочисленная арифметика
Задание рассчитано на написание программы на любом языке программирования.
Ввод данных может осуществляться как из входного файла, так и с клавиатуры.
Решение данной задачи похоже на решение задачи « A div B «. Здесь следует учесть, что делимое — достаточно большое число и в процессе вычисления текущее значение может превосходить максимально возможное для 4-байтного целого, поэтому нужно использовать другие типы (например, int64 или __int64 в паскале).
Алгоритм, реализующий данную задачу может быть записан в следующем виде:
const maxsize=101;
int a, b;
int64 x;
readlong(a);
read(b);
x=0; k=0;
for i=a..1{
x = x*10+a[i];
if(x < b and k=0 and i > 1) continue;
k=1;
x = x mod b;
write(x);
Задача 3. “Лягушки” – 15 баллов
Тип задачи: Задача по программированию. Условный оператор
Задание рассчитано на написание программы на любом языке программирования.
Ввод данных может осуществляться как из входного файла, так и с клавиатуры.
program A;
var
k, t: integer;
begin
assign(input, ‘input.txt’); reset(input);
assign(output, ‘output.txt’); rewrite(output);
ReadLn(k, t);
if (t div k mod 2 = 0) then
WriteLn(t mod k)
else
WriteLn(k — t mod k);
close(input); close(output);
end.
Вконтакте
Задания школьного этапа олимпиады по информатике с 7-11 классы
«7-8 класс_И»
Всероссийская олимпиада школьников по информатике. 2017 -2018 год.
Муниципальный этап, 7-8 класс
Задача А. Автобусы
N детей и M K
Формат входного файла
N, M и K
Формат выходного файла
| Входные данные | Выходные данные |
Задача В. Лавочки
Формат входного файла
L - длина лавочки и K
Во второй строке следуют K
Формат выходного файла
| Входные данные | Выходные данные |
| 13 4 | |
| 14 6 |
Задача С. Выборы
N N символов - плюсов и минусов.
действительных бюллетеней.
Формат входного файла
N - количество партий и M N M
В следующих M N
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| +-- | |
| + |
Формат входного файла
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Задача E . Камни
На столе лежат N
1 или 2 камня, если N делится на 3;
1 или 3, если N
1, 2 или 3, если N
Формат входного файла
Вводится целое число 0 N
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Страница 6 из 6
Просмотр содержимого документа
«9-11 класс_И»
Всероссийская олимпиада школьников по информатике. 2017 -2018 год.
Муниципальный тур, 9-11 класс
Задача А. Ставки
A придет раньше, чем таракан №B ".
Формат входного файла
K N K . Каждая из следующих N A , B , C , D , не превосходящих K A придет раньше, чем таракан №B " и "Таракан №C придет раньше, чем таракан №D ".
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 3 2 | |
| 3 4 |
Задача В. Гонки на машинках
n
n xi vi
Формат входных данных
n n xi и vi i xi vi 1000).
Формат выходных данных
Примеры
| Входные данные | Выходные данные |
Задача С. Тестирование
Формат входного файла
n (1 ≤ n a 1 , a 2 , . . . , a n n целых чисел b 1 , b 2 , . . . , b n a i и b i верны неравенства 1 ≤ a i , b i ≤ 10.
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Задача D . Соревнования картингистов
n m
Требуется
Формат входного файла
n и m (1n m 100). Последующие 2n
Вторая строка содержит m m
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| Sumaher Barikelo |
Задача E . Дипломы
n w - в ширину и h - в высоту.
w на h
Требуется
Формат входного файла
w , h , n (1w h n 109).
Формат выходного файла
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
И
ллюстрация к примеру:
Страница 5 из 5
Просмотр содержимого документа
«Методические рекомендации по разбору олимпиадных задач»
Муниципального этапа Всероссийской олимпиады школьников по информатике в 2017-2018 учебном году
7- 8 класс
Задача А. Автобусы.
Для заезда в детский оздоровительный лагерь организаторы решили заказать автобусы. Известно, что в лагерь собираются поехать N детей и M взрослых. Каждый автобус вмещает K человек. В каждом автобусе, в котором поедут дети, должно быть не менее двух взрослых.
Определите, удастся ли отправить в лагерь всех детей и взрослых, и если да, то какое минимальное количество автобусов требуется для этого заказать.
Формат входного файла
На вход программы поступают 3 натуральных числа, записанных через пробел - N, M и K , каждое из них не превосходит 10 000.
Формат выходного файла
Выведите количество автобусов, которые нужно заказать. Если же отправить всех в лагерь невозможно, выведите 0 (ноль).
Пример входного и выходного файлов
| Входные данные | Выходные данные |
Решение.
Алгоритм:
Во первых: нужно учесть, что К может принимать значение меньше или равное 2. В этом случае следует выводить 0, потому, что в каждый автобус мы будем вынуждены посадить взрослых (а дети так и не уедут). Теперь рассмотрим случай когда К больше двух: в том случае нужно будет ровно n/(k-2) автобусов для перевозки детей. Заметим, что если n не делится нацело на k-2, то автобусов понадобиться на один больше. Так же мы не сможем уехать если количество взрослых делённое на два меньше количества нужных автобусов для перевозки детей. Во всех остальных случаях ответом будет (m+n)/k, но если (m+n) не делится нацело на k то на один автобус больше.
Программа:
var a,b,c,k,n,p: integer;
k:=a div (c-2); //2
if a mod (c-2) 0 then inc(k);
if (a+b) mod c 0 then inc(k);
ЗадачаВ. Лавочки
Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).
Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.
Формат входного файла
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.
Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка - это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).
Формат выходного файла
Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 13 4 | |
| 14 6 |
Второй пример соответствует лавочке на рисунке.
Решение.
Алгоритм:
Обозначим координату (положение) i -й ножки как d i . Найдём числа left и right - номера самой правой ножки, хотя бы часть которой находится левее середины лавочки, и самой левой ножки, хотя бы часть которой находится правее середины лавочки, соответственно: left = max i 2 d i L , right = min i 2 (d i +1) L . Если в итоге left = right (то есть L нечётно и i d i = 2 L ), то вывести нужно одно число d left , в противном случае - сначала d left , затем d right .
Программа:
var L,k,n,i: longint;//0..10 000
a: array of boolean;
for i:=1 to k do begin
if (L mod 2 0) and (a) then begin
for i:=(L-1) div 2 downto 0 do
if a[i] then begin
for i:=l div 2 to L-1 do
if a[i] then begin
ЗадачаС. Выборы
На выборах в Государственную думу в избирательные бюллетени внесено N партий. Электронный сканер для считывания информации с бюллетеней передает информацию о каждом бюллетене в следующем формате: если в соответствующей клетке бюллетеня стоит пометка, то сканер передает + (плюс), в противном случае он передает - (минус). Таким образом, он передает последовательность из N символов - плюсов и минусов.
Бюллетень считается действительным, если пометка есть ровно в одной клетке. Недействительные бюллетени в подсчете результатов выборов не участвуют.
Партия проходит в Государственную Думу, только если она набирает не менее 7% от общего числа действительных бюллетеней.
Требуется вывести номера (в порядке их перечисления в бюллетене) всех партий, которые проходят в Государственную Думу.
Формат входного файла
В первой строке входных данных содержатся два числа, разделенные пробелом: N - количество партий и M - количество бюллетеней. Оба числа натуральные, N M
В следующих M строках записана информация, полученная из бюллетеней. Каждая строка - последовательность из N символов + или - (без пробелов).
Гарантируется, что есть хотя бы один действительный бюллетень.
Формат выходного файла
Выведите через пробел номера партий, прошедших в Думу, в порядке возрастания. Если ни одна из партий не проходит в Думу, выводить ничего не нужно.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| +-- | |
| + |
Решение.
Алгоритм:
Напишем специальную функцию who, по данной строчке-бюллетеню возвращающую номер выбранного в данном бюллетене кандидата или 0 для недействительного бюллетеня (для этого достаточно один раз пройти циклом по строчке-бюллетеню, помня текущий ответ). Теперь для каждого бюллетеня вызовем функцию who от него и, если результат не равен нулю, увеличим на 1 числа K (количество действительных бюллетеней) и gwho (количество действительных голосов, отданных за партию с номером, равным результату функции who). Осталось вывести все i такие, что 100 gi 7 K .
Программа:
{$h +}
flag :boolean ;
a:array of longint;
n,m,max,k,i,j:longint;
for i:=1 to m do
for j:=1 to length(s) do
if s[j]="+" then
if not flag then
for j:=1 to length(s) do
if s[j]="+" then
for i:=1 to n do
if a[i]=max*0.07 then
Задача D . Билет на электричку
В новых элитных электричках каждому пассажиру положено сидячее место. Естественно, количество сидячих мест ограничено и на всех их может не хватить. Маршрут электрички проходит через N станций, занумерованных от 0 до N-1. Когда человек хочет купить билет, он называет два числа x и y – номера станций, откуда и куда он хочет ехать. При наличии хотя бы одного сидячего места на этом участке на момент покупки ему продается билет, иначе выдается сообщение «билетов нет» и билет не продается. Ваша задача – написать программу, обслуживающую такого рода запросы в порядке их прихода.
Формат входного файла
В первой строке содержаться три числа N – количество станций (1 ≤ N ≤ 10 000), K – количество мест в электричке (1 ≤ K ≤ 1000) и M – количество запросов (1 ≤ M ≤ 50 000). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел x и y (0 ≤ x
Формат выходного файла
На каждый запрос ваша программа должна выдавать результат в виде числа 0 если билет не продается и 1 если билет был продан. Каждый результат должен быть на отдельной строке
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Решение.
Алгоритм:
Представим массив длины N в i-той ячейке которого будем хранить количество пассажиров уже купивших билет и едущих от станции i к (i+1).
Будем поддерживать для такого массива RMQ (дерево максимумов) с возможностью быстрой модификации (прибавления) на отрезке.
Теперь при обработке каждого запроса мы сначала узнаём максимум на отрезке , и, если он меньше К (т.е. между каждой парой станций на маршруте существует хотя бы одно свободное место), продаём билет и выполняем update(x, y-1, +1). Иначе отказываем в продаже билета.
Программа :
mas: array of longint;
n, m ,k, i, a, b, j, z:longint;
readln(n, k, m);
for i:= 0 to n-1 do
for i:=1 to m do
for j:= a to b-1 do
if mas[j]=0 then z:=5;
if z=5 then writeln("0")
Задача E . Камни
На столе лежат N камней. За ход игрок может взять
1 или 2 камня, если N делится на 3;
1 или 3, если N при делении на 3 дает остаток один;
1, 2 или 3, если N при делении на 3 дает остаток два.
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
Формат входного файла
Вводится целое число 0 N
Формат выходного файла
Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Решение.
Алгоритм:
Пусть (F[i] = 1) если выигрывает первый и (F[i] = 2) если второй. Тогда заметим, что F=1,F=1 F = 2. Теперь мы просто заполним наш массив F. Будем считать, что 1 это выигрышная позиция 2 проигрышная. Тогда если мы можем из теперешней позиции попасть в проигрышную, то она выигрышная, а если мы попадаем только в выигрышные, то наша позиция проигрышная. Осталось пробежаться циклом от 4 до n. И выписать условия для разной кратности 3. На самом деле, потом можно заметить, что позиции кратные 3ём проигрышные, а все остальные выигрышные.
Программа:
if(n mod 3 = 0) then
if(n mod 3 0) then
end .
9 -11 класс
Задача А. Ставки
Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B ".
Организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). Считается, что никакие два таракана не могут прийти к финишу одновременно.
Формат входного файла
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K , не превосходящее 10, - количество тараканов и числоN , не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K . Каждая из следующих N строк содержит 4 натуральных числа A , B , C , D , не превосходящих K , разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B " и "Таракан №C придет раньше, чем таракан №D ".
Формат выходного файла
Если завершить бега так, чтобы у каждого из болельщиков сыграла ровно одна из двух ставок, можно, то следует вывести номера тараканов в том порядке, в котором они окажутся в итоговой таблице результатов (сначала номер таракана, пришедшего первым, затем номер таракана, пришедшего вторым и т. д.) в одну строку через пробел. Если таких вариантов несколько, выведите любой из них.
Если требуемого результата добиться нельзя, выведите одно число 0.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Решение.
Алгоритм:
Переберём все перестановки чисел от 1 до K - все возможные исходы бегов (порядок прихода тараканов). Для каждой перестановки за O (N ) проверим, правда ли, что у каждого болельщика в таком случае сыграет ровно одна ставка. Если это действительно так, выводим текущую перестановку и завершаем работу программы. В конце программы выводим 0 (программа не завершилась раньше, следовательно, ответ не найден).
Программа :
Tstavka = record
a1, a2, b1, b2: longint;
i, n, k, e, s, p, w: int64;
a: array of int64;
st: array of Tstavka;
procedure change(x: longint);
for i1:= x + 1 to x + ((k - x) div 2) do
a := a;
a := t;
need, ch, t, i1: longint;
for i1:= k - 1 downto 1 do
if need = 0 then
for i1:= k downto 1 do
if a a then
a := a;
// assign(input,"input.txt"); reset(input);
for i:= 1 to n do
read(st[i].a1, st[i].a2, st[i].b1);
readln(st[i].b2);
if (k=1) and (st[i].a1=1) and (st[i].a2=1) and (st[i].b1=1) and (st[i].b2=1) then
for i:= 1 to k do a[i] := i; s:= 1;
for i:= 1 to k do s:= s * i;
for e:= 1 to s do
for w:= 1 to n do
if ((a.a1] a.a2]) and (a.b1] a.b2])) then
if go = true then
for i:= 1 to k do
if a[i] = p then
for i:= 1 to k do
if a[i] = k then
Задача В. Гонки на машинах
Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику - все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.
Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта - имеет фору xi метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью vi метров в секунду. Все машинки движутся в одном направлении - удаляются от старта.
Недавно Феде подарили видеокамеру, и он хочет заснять яркие моменты гонки. Прежде всего Федя хочет запечатлеть первый обгон гонки, то есть первый момент времени, в который две машины находятся на одном расстоянии от старта.
Так как этого события можно ждать очень долго, Федя хочет настроить камеру на автоматическое включение во время обгона. Однако, Федя самостоятельно не может найти время, которое пройдет со времени начала гонки до времени первого обгона. Помогите Феде - напишите программу, находящую искомую величину.
Формат входных данных
В первой строке входного файла содержится единственное число n - количество машинок на трассе (2 n 100). Каждая из следующих n строк содержит по два целых числа xi и vi - расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1 xi vi 1000).
Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.
Формат выходных данных
В выходной файл выведите количество секунд, которое пройдет с момента старта до момента первого обгона, с точностью не менее 5 знаков после десятичной точки.
Примеры
| Входные данные | Выходные данные |
Пояснение для первого примера:
На рисунке точкой A обозначено место обгона.
Решение.
Алгоритм:
1)Машинка а когда-нибудь догонит машинку б, если её скорость больше, а координата меньше
2)Переберём каждую машинку с каждой и если одна машинка когда-нибудь обгонит другую(пункт 1), то посчитаем это время. Среди всех таких значений выберем минимальное. Это и будет ответом
Программа:
var a,b:arrayof longint;
c:arrayof real;
j,n,i,k,l:longint;
for i:=1 to n do
read(a[i],b[i]);
for i:=1 to n do
for j:=1 to n do
if(ij)and(a[i]b[j])then begin
c[k]:=(a[j]-a[i])/(b[i]-b[j]);
for i:=2 to k do
writeln(min:1:5);
Задача С. Тестирование
Одним из способов контроля знаний учащихся является проведение тестирований. На тестировании обычно предлагается несколько вопросов, для каждого из которых необходимо выбрать один из вариантов ответа. Для этого тестируемому выдается специальный бланк с вопросами и вариантами ответов.
Тестирования можно проводить одновременно для достаточно большого количества людей, поэтому возникает вопрос об эффективной обработке заполненных тестируемыми бланков. Во Флатландии эту проблему пытаются решить с помощью применения информационных технологий для автоматической обработки результатов тестирования.
Первым этапом является написание программы, которая бы вычисляла баллы за тест по известной информации о правильных ответах на вопросы и ответах, данных тестируемым. Ваша задача состоит в написании такой программы.
Формат входного файла
Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) вопросов в тесте. Вторая строка входного файла содержит n целых чисел a 1 , a 2 , . . . , a n - номера правильных вариантов ответов на каждый из вопросов. Третья строка входного файла содержит n целых чисел b 1 , b 2 , . . . , b n - номера вариантов, выбранных тестируемым. Для чисел a i и b i верны неравенства 1 ≤ a i , b i ≤ 10.
Формат выходного файла
В выходной файл выведите число вопросов, на которые тестируемый дал правильный ответ.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
Решение.
Алгоритм:
Очень легкая задача. Считываем данные в два массива. Затем запускаем цикл до n и проверяем: если i-й элемент 1-го массива равен i-му элементу 2-го массива, то мы увеличиваем счетчик на 1.
Программа :
a,b:array of byte;
assign(input, "input.txt");
assign(output, "output.txt");
rewrite(output);
for i:=1 to n do
for i:=1 to n do begin
if a[i]=b[i] then
end .
Задача D. Соревнования картингистов
После очередного этапа чемпионата мира по кольцевым автогонкам на автомобилях с открытыми колёсами Формула-А гонщики собрались вместе в кафе, чтобы обсудить полученные результаты. Они вспомнили, что в молодости соревновались не на больших болидах, а на картах - спортивных автомобилях меньших размеров.
Друзья решили выяснить победителя в одной из гонок на картах. Победителем гонки являлся тот гонщик, у которого суммарное время прохождения всех кругов трассы было минимальным.
Поскольку окончательные результаты не сохранились, то каждый из n участников той гонки вспомнил и выписал результаты прохождения каждого из m кругов трассы. К сожалению, по этой информации гонщикам было сложно вычислить победителя той гонки. В связи с этим они попросили сделать это вас.
Требуется написать программу, которая вычислит победителя гонки на картах, о которой говорили гонщики.
Формат входного файла
Первая строка входного файла содержит два целых числа n и m (1n m 100). Последующие 2n строк описывают прохождение трассы каждым из участников. Описание прохождения трассы участником состоит из двух строк. Первая строка содержит имя участника с использованием только латинских букв (строчных и заглавных). Имена всех участников различны, строчные и заглавные буквы в именах различаются.
Вторая строка содержит m положительных целых чисел, где каждое число - это время прохождения данным участником каждого из m кругов трассы (каждое из этих чисел не превосходит 1000). Длина имени каждого участника не превышает 255.
Формат выходного файла
В выходной файл необходимо вывести имя победителя гонки на картах. Если победителей несколько, требуется вывести имя любого из них.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| Sumaher Barikelo |
Обращаем внимание на пробел в конце последней строки входных данных.
Решение.
Алгоритм:
Заведем отдельную строку для хранения фамилии игрока с лучшим результатом, и отдельную переменную для хранения этого результата. Затем присваиваем им результаты и фамилию 1-го гонщика, а затем считываем оставшиеся результаты и сравниваем с максимумом на данном шаге и, если требуется изменяем последний.
Программа :
var n,m,i,j,x,sum,min:longint;
min:=maxlongint;
for i:=1 to n do
for j:=1 to m do
end;
Задача Е. Дипломы
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w - в ширину и h - в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней - дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h . Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Формат входного файла
Входной файл содержит три целых числа: w , h , n (1w h n 109).
Формат выходного файла
В выходной файл необходимо вывести ответ на поставленную задачу.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
И
ллюстрация к примеру:
Решение.
Алгоритм:
Из-за больших ограничений на n,w,h линейный перебор возможной длины стороны квадрата не проходит по времени, поэтому данную задачу следует решать, используя бинарный поиск по ответу. Очевидно, что размеры доски лежат в пределах от min(w,h) до n * max(w,h). За O(1) легко проверить, поместятся ли все грамоты в квадрат со стороной a (n
Программа:
function maxwh (w2, h2:int64) :int64;
if w2h2 then maxwh:=w2 else maxwh:=h2;
function maxd (w1, h1, mid1: int64) : int64;
maxd:=(mid1 div w1)*(mid1 div h1);
hi, lo, mid: int64;
readln(w, h, n);
hi:=maxwh(w, h)*n;
mid:=(hi+lo) div 2;
if maxd(w, h, mid)
Просмотр содержимого документа
«Требования к проведению олимпиады по Информатике»
Требования к проведению и оцениванию муниципального этапа олимпиады
по информатике 2017 – 2018 уч. года.
Настоящие требования разработаны региональной предметно-методической комиссией по информатике и являются частью нормативно-правового обеспечения Всероссийской олимпиады школьников.
В соответствие с Порядком проведения всероссийской олимпиады школьников (далее порядок), утвержденным приказом Минобрнауки России от 18 ноября 2013 г. №1252 (зарегистрирован Минюстом России 21 января 2014 г., регистрационный № 31060) с изменениями, внесенными приказом Минобрнауки России от 17 марта 2015 г. №249 (зарегистрирован Минюстом России 7 апреля 2015 г., регистрационный № 36743) и приказом Минобрнауки России от 17 декабря 2015 г. №1488 (зарегистрирован Минюстом России 20 января 2016 г., регистрационный № 40659) предоставлен следующий комплект материалов для проведения Муниципального этапа Всероссийской олимпиады школьников по информатике в 2017-2018 учебном году:
тексты олимпиадных задач;
требования к проведению и оцениванию муниципального этапа олимпиады ;
специализированная системы проведения олимпиады, расположенная на сайте http://informatics.mccme.ru ;
инструкция по работе в специализированной системе проведения олимпиады;
Олимпиада проводится среди учащихся 7,8,9,10,11 классов. Представлены два комплекта заданий по информатике: для 7-8 классов и 9-11 классов.
Победители и призеры муниципального этапа Олимпиады определяются по параллелям.
Муниципальный этап олимпиады будет проходить с использованием специализированной системы проведения олимпиад, расположенной на сайте http://informatics.mccme.ru в разделе ЛИЧНЫЕ ОЛИМПИАДЫ/РЕСПУБЛИКА КОМИ. ОЛИМПИАДЫ. Время проведения олимпиады на этом сайте 22 ноября 2017 г. с 12.00 до 18.00 (доступ будет закрыт в 18.15).
В случае использования бумажного варианта олимпиады время определяется муниципальным органом управления образованием.
Для муниципального этапа олимпиады используются следующие языки и среды программирования:
основная: FreePascal, C, С++, GNU C/C++4/6/1, Delphi 7.0; дополнительная: Borland C++3.1, Visual Basic, Mono 2.0, Python 3.3.
Следует отметить, что на все программное обеспечение, используемое при проведении муниципального этапа, организаторы этого этапа должны иметь необходимые лицензии. Большинство рекомендуемых программных систем являются свободно распространяемыми и их можно загрузить с соответствующих сайтов. Примерами таких сайтов являются:
FreePascal – сайтhttp://freepascal.org ;
MinGW – сайтhttp://mingw.org ;
Eclipse – сайтhttp://eclipse.org ;
Code::Blocks – сайтhttp://www.codeblocks.org ;
Far manager– сайтhttp://farmanager.com/index.php?l=ru
Длительность тура может составлять от трех до четырех астрономических часов для 7-8 класса и от четырех до пяти астрономических часов – для 9–11 классов.
Во время тура участникам Олимпиады запрещается пользоваться Интернетом, любыми электронными устройствами, в том числе личными компьютерами, калькуляторами, электронными записными книжками, средствами связи (пейджерами, мобильными телефонами и т.п.), электронными носителями информации (дискетами, CD- и DVD-дисками, модулями флэш-памяти и т.п.), а также учебной литературой и заготовленными личными записями.
Выход в Интернет возможен только в случае использования во время тура Интернет-системы автоматической проверки решений участников, но тогда доступ к другим сайтам, кроме сайта проведения олимпиады, должен быть заблокирован.
В случае возникновения во время тура не по вине участника сбоев в работе компьютера или используемого программного обеспечения по решению жюри время, затраченное на восстановление работоспособности компьютера, может быть компенсировано.
Описание системы оценивания решений задач
Оценивание решений задач будет проходить автоматически на специализированной системе проведения олимпиады.
Таблица бальной оценки задач:
| задачи | 7 - 8 класс | 9 - 11 класс |
| max кол-во баллов | max кол-во баллов |
|
| Итого: |
В случае ручной проверки решения задач используются тесты из примеров, приведенных в условии задачи. Если на этих тестах решение участника выдает правильный ответ, то участник получает за 1 тест - 10 баллов, за 2 теста -20 баллов.