Решения задач школьного этапа олимпиады по информатике (9-11 кл)

Решения задач школьного этапа Всероссийской олимпиады школьников по информатике (9-11 классы)

Московская область, 21-22 октября 2019 г. На YuoTobe: https://youtu.be/hd_BMb6aanU

Задача A. Системы счисления

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

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

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

• Тест №1: N=123
• Тест №2: N=796
• Тест №3: N = 60452
• Тест №4: N = 101001
• Тест №5: N = 32674
• Тест №6: N = 306973
• Тест №7: N = 123042
• Тест №8: N = 202122
• Тест №9: N = 871856
• Тест №10: N = 125341

Решение

Для получения ответов удобно воспользовать программой, в которой будет определяться минимально возможное основание системы счисления:

• int( max(n) ) + 1 - максимальный символ в строке n переводим в целое число + 1
• преводим строковое представление числа n с найденным основанием в целое десятичное число: int( строка, основание) (если основание не указано - сторка в десятичном представлении)

In [1]:

for i in range(10):
    n = input()
    print ( int( n, int( max(n) ) + 1 ) )

123
27
796
796
60452
14639
101001
41
32674
13756
306973
306973
123042
4772
202122
557
871856
519747
125341
11581

Задача B. Улиточные бега

• Имя входного файла: стандартный ввод
• Имя выходного файла: стандартный вывод
• Ограничение по времени: 1 секунда
• Ограничение по памяти: 256 мегабайт

Каждые 100 лет в Стране Улиток проводятся улиточные бега на дистанции L сантиметров. Это станет для вас неожиданностью, но в этом столетии они проводятся именно сегодня!

В этом году организаторы приняли решение провести бега на новой трассе — прямоугольнике размера A × B сантиметров. Согласно правилам, участники начнут бежать из нижнего левого угла прямоугольника против часовой стрелки в соответствии со схемой ниже:

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

Формат входных данных

Вводятся три целых числа A, B, L (2<=A,B<=106${10}^6$, 1<=L<=1018${10}^{18}$) — длина и ширина прямоугольника и длина пути соответственно. Гарантируется, что улитка не останавливается в углу прямоугольника.

Формат выходных данных

Выведите TOP, если улитка остановится на верхней стороне прямоугольника, BOTTOM — на нижней, LEFT — на левой, RIGHT — на правой стороне прямоугольника.

Примеры

In:	Out:
2 4 11	LEFT
2 4 13	BOTTOM

Решение

После преодаления дистанции равной периметру прямоугольника 2(a+b) - история со сторонами повтаряется. Поэтому достаточно взять не всю дистанцию l, а ее остаток на длину периметра l = l % 2(a+b). Далее, сравниваем l с длиной сторон в рамках одного периметра: до a - нижняя, иначе до a+b - правая, иначе до 2a+b - верхняя и иначе - левая

In [2]:

a,b,l=int(input()), int(input()), int(input())
l %= 2*(a+b)
print (l<=a and 'BOTTOM' or l<=(a+b) and 'RIGHT' or l<=(a+a+b) and 'TOP' or 'LEFT')

2
4
13
BOTTOM

Задача C. Треугольник

• Имя входного файла: стандартный ввод
• Имя выходного файла: стандартный вывод
• Ограничение по времени: 1 секунда
• Ограничение по памяти: 256 мегабайт

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A(0, 0), B(d, 0), C(0, d). Требуется написать программу, которая определяет взаимное расположение точки X и треугольника. Если точка X расположена внутри или на сторонах треугольника, выведите 1. Если же точка находится вне треугольника, выведите 0.

Формат входных данных

В первой строчке вводится натуральное число d (не превосходящее 1000), во второй — координата точки X по оси OX (целое число из диапазона от −1000 до 1000), в третьей координата точки X по оси OY (целое число из диапазона от −1000 до 1000).

Формат выходных данных

Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выве- дите число 1. Если точка лежит вне треугольника, то выведите 0.

Примеры

In:	Out:
5 1 1	1
4 4 4	0
4 2 2	1

Решение

Прямая проходящая через B и C имеет уравнение y=d-x. Для точек лежащих на и под ней: y<=d-x или x+y<=d. Точка X с координатами x0 и y0 будет принадлежать ABC, если x0>=0 and y0>=0 and (x0+y0)<=d - тогда ответ 1, иначе - 0. Интерактивная модель к задаче №3

In [6]:

d,x0,y0= int(input()),int(input()),int(input())
print(x0>=0 and y0>=0 and (x0+y0)<=d and 1 or 0)

4
2
2
1

Задача D. Цветные клетки

• Имя входного файла: стандартный ввод
• Имя выходного файла: стандартный вывод
• Ограничение по времени: 1 секунда
• Ограничение по памяти: 256 мегабайт

Чемпион по межгалактическим шахматам Гарик Проспалов очень любит коллекционировать шахматные доски.
Сегодня он купил себе очередную шахматную доску размера N × M , состоящую из клеток K цветов от 0 до K − 1. Клетка, стоящая в i-й строке и j-м столбце имеет цвет (i + j) mod K (в данном случае mod — остаток от деления). Строки и столбцы нумеруются с 0. Для того, чтобы внести эту доску в коллекцию, Гарик должен составить её статистику. А именно, он должен для каждого цвета от 0 до K − 1 записать, какое количество клеток покрашено в этот цвет. Так как размер доски может быть очень большой, то он попросил вас составить статистику данной доски.
Напишите программу, которая позволит ему решить эту весьма непростую задачу.

Формат входных данных

Вводятся три целых числа N, M, K (1 􏰀 N,M 􏰀 109${10}^9$, 1 􏰀 K 􏰀 2·105$·{10}^5$) — размеры доски и количество цветов соответственно.

Формат выходных данных

Выведите через пробел K целых чисел, где i-е число обозначает количество клеток, покрашенных в i-й цвет (i от 0 до K − 1).

Примеры

In:	Out:
8 8 2	32 32
5 5 4	7 6 6 6

Решение

Если число клеток nm кратно k, то каждый цвет будет повторятся nm/k раз. Иначе - цвета имееющие номера меньше остатка от этого деления n*m % k будут повторяться на 1 раз больше

In [3]:

n,m,k = int(input()), int(input()), int(input())
print(' '.join(str ( n*m//k + int(i<n*m%k) ) for i in range(k) ))

5
5
4
7 6 6 6