ФГБОУ ВПО «БГПУ» им. М. Акмуллы
Центр развития одаренности школьников
ЗАДАНИЯ
2 тура дистанционной олимпиады по программированию
для 10-11 классов
г. Кумертау, Республика Башкортостан, МБОУ СОШ №12.
E-mail: *****@***com
Интерпретатор: Python 3.4.3
Исходники:
Yandex: https://yadi.sk/d/jBknbqginq6zf
Задание 1
Разработайте программу, которая формирует таблицу 10 на 10, заполняет ее случайными числами и сортирует по строкам.
Code:
# coding=utf-8
#!/usr/bin/python3
import random
arr = [sorted([str(random. randint(-1000, 1000)) for x in range(10)]) for k in range(10)]
# Список из 10 списков, заполненных случайными отсортированными числами от - 1000 до 1000
[print(', '.join(x)) for x in arr]
Out:
-211, -281, -303, -590, 343, 578, 749, 767, 963, 980
-369, -442, -553, 176, 433, 572, 6, 775, 896, 958
-149, -392, -525, -544, -551, -80, -973, 310, 368, 876
-368, -399, -772, -89, -890, 1, 126, 720, 830, 886
-632, -891, -95, 193, 303, 364, 412, 516, 858, 994
-286, -603, -773, -789, -95, 17, 450, 724, 786, 860
-583, -642, -691, 191, 239, 330, 357, 42, 425, 916
-275, -700, -94, 118, 295, 359, 38, 500, 509, 547
-159, -233, -503, -996, 240, 396, 475, 788, 854, 855
-27, -358, -383, -456, -707, -991, 26, 39, 592, 856
Screen:
Run:
Задание 2
Разработайте программу, которая формирует таблицу 10 на 10, заполняет ее случайными числами и сортирует по столбцам.
Code:
# coding=utf-8
# !/usr/bin/python3
import random
arr = [sorted([str(random. randint(-1000, 1000)) for x in range(10)]) for k in range(10)]
# Список из 10 списков, заролненных случайными отсортированными числами от - 1000 до 1000
[print(', '.join(x)) for x in list(reversed(list(zip(*arr))))]
# *a расспаковывает список, как аргумент функции zip, которая возвращает с n-ный элемент с каждого итерируемого в аргументах
Out:
829, 812, 993, 765, 996, 58, 318, 854, 342, 899
572, 537, 882, 606, 425, 464, 12, 760, -852, 896
53, 480, 790, 577, 383, 101, -841, 500, -831, 643
450, 19, 523, 280, 342, -987, -829, 434, -829, 275
434, 131, 518, -947, -794, -833, -817, 310, -77, -983
-829, -925, 376, -879, -676, -474, -540, -920, -699, -979
-682, -884, 317, -630, -649, -377, -462, -87, -695, -76
-461, -571, 293, -486, -524, -359, -297, -583, -556, -488
-358, -259, -536, -316, -4, -327, -249, -533, -407, -180
-103, -137, -405, -107, -196, -228, -239, -291, -113, -12
Screen:
Run:
Задание 3
Разработайте программу, которая формирует таблицу 10 на 10, заполняет ее случайными числами и находит наибольшие четные значения в каждом столбце.
Code:
# coding=utf-8
#!/usr/bin/python3
import random
a = [[str(random. randint(-1000, 1000)) for x in range(10)] for k in range(10)]
# Список из 10 списков, заролненных случайными числами от - 1000 до 1000
for i in a:
max_even = 'Нет четных'
for k in i:
k = int(k)
if k % 2 == 0 and k!= 0: # четное и не 0
if max_even == 'Нет четных':
max_even = k
else:
if max_even < k:
max_even = k
i. append('Максимальное четное: {}'.format(max_even))
[print(', '.join(x)) for x in a]
Out:
650, 216, 824, -273, 305, -634, -5, -541, 386, -329, Максимальное четное: 824
-516, -511, 139, -65, -463, -332, -364, -15, -173, 674, Максимальное четное: 674
-572, -228, 914, 15, 454, 368, 598, -77, -603, -708, Максимальное четное: 914
899, -59, 236, -101, -110, -267, -189, -875, -44, -192, Максимальное четное: 236
376, 129, 270, 183, 455, 217, -385, -316, -621, -908, Максимальное четное: 376
-339, -858, 200, -208, 970, -593, 272, 411, -463, 658, Максимальное четное: 970
110, -831, -184, -816, 922, -989, -988, -45, -703, 189, Максимальное четное: 922
170, 12, 862, -812, -764, -999, 811, -214, -25, -911, Максимальное четное: 862
-926, 11, -944, -758, 53, 980, -789, 980, -93, 755, Максимальное четное: 980
-375, -819, -497, 647, -176, 286, -465, 934, -260, -770, Максимальное четное: 934
Screen:
Run:
Задание 4
Разработайте программу для кодирования последовательности из N символов, которая использует неравномерный минимальный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Code:
# coding=utf-8
# !/usr/bin/python3
import math
import sys
def generate(end):
"""
:param end: Генерировать двоичный код до 2**end
:return:список с возможными вариантами двоичного кода
"""
counter = 0
alpha = [['0', '1']]
while True:
if counter == end:
break
buf = []
for i in alpha[counter]:
buf. append(i + '0')
buf. append(i + '1')
alpha. append(buf)
counter += 1
return alpha[-1]
def make_primal_alpha(word):
"""
Составляет словарь с первичными НЕ минимальным "алфавитом"
"""
unique = set(word)
end = math. ceil(math. log2(len(unique))) - 1 # найти в какой радиус степени двойки попадают символы слова
alpha = generate(end)
result = {}
for letter, cipher in zip(unique, alpha):
result[letter] = cipher
return result
def test_seq(seq):
"""
Проверка последовательности на условаие Фано
"""
for i in range(len(seq)):
_seq = seq. copy()
_seq. pop(i)
for k in _seq:
if seq[i].startswith(k) or k == seq[i]:
return False
return True
def minimize(word):
"""
Составляет алфавит и минимизирует его для слов word
"""
unique = set(word)
primal_two = math. ceil(math. log2(len(unique))) - 1
alphabet = make_primal_alpha(word)
structured = [[x, word. count(x), alphabet[x]] for x in unique]
structured. sort(key=lambda x: x[1], reverse=True) # чтобы уменьшать сначало код букв, которых больше в слове
variables = [] # тут будут все возможные варианты уменьшения
for key, count, cipher in structured:
for z in range(primal_two): # чтобы еребрать все возможные варианты спускаясь вниз
reduced = alphabet. copy()
test = generate(primal_two - z)
for i in test:
reduced[key] = i
if test_seq(list(reduced. values())):
variables. append(reduced)
alphabet = reduced. copy() # чтобы дальше работать с уже уменьшеным кодом
break
minimum_alphabet = variables[-1] # последним элементом идет минимальный из возможных
cipher = ''.join([minimum_alphabet[x] for x in word])
return (word, cipher, minimum_alphabet)
for i in sys. stdin:
result = minimize(i. strip())
print('Слово: ', result[0])
print('Зашифрованное слово: ', result[1])
print('Алфавит: ', end='')
for i in result[2].items():
print(i[0], ':', i[1], end=' | ')
print('\n', '-'*30)
In:
приветпривет
she sells sea shells on the seashore
Карл у Клары украл кораллы, а Клара у Карла украла кларнет
word
test
vegetables
potato
*/+-дщдкек
Out:
Слово: приветпривет
Зашифрованное слово: 01011001001010110101100100101011
Алфавит: и : 00 | р : 11 | п : 010 | в : 100 | т : 011 | е : 101 |
------------------------------
Слово: she sells sea shells on the seashore
Зашифрованное слово: 1101111010001111010010011100011110101010001110111101001001110001100011000010000011110100011110101011101111000100101
Алфавит: t : 0000 | s : 11 | : 0001 | l : 001 | a : 0101 | r : 0100 | n : 0110 | e : 101 | o : 100 | h : 0111 |
------------------------------
Слово: Карл у Клары украл кораллы, а Клара у Карла украла кларнет
Зашифрованное слово: 01001110011001000000001000001000010111001101010000000110100111110010000010111000111110010001001011001000011100000100001011100111110000000100000100111001100101110000000110100111110010111000010100101110011100001110110
Алфавит: у : 0001 | л : 0010 | ы : 0101 | т : 0110 | е : 0111 | н : 1000 | а : 111 | , : 1001 | К : 0100 | р : 0011 | : 0000 | к : 101 | о : 110 |
------------------------------
Слово: word
Зашифрованное слово: 10000111
Алфавит: o : 00 | r : 01 | w : 10 | d : 11 |
------------------------------
Слово: test
Зашифрованное слово: 00011000
Алфавит: t : 00 | e : 01 | s : 10 |
------------------------------
Слово: vegetables
Зашифрованное слово: 101111011111000110010100111001
Алфавит: t : 000 | s : 001 | b : 010 | g
: 011 | v : 101 | e : 111 | a : 110 | l : 100 |
------------------------------
Слово: potato
Зашифрованное слово: 111000010010
Алфавит: t : 00 | a : 01 | o : 10 | p : 11 |
------------------------------
Слово: */+-дщдкек
Зашифрованное слово: 001011101100000110000111010111
Алфавит: д : 000 | * : 001 | е : 010 | / : 011 | - : 100 | + : 101 | щ : 110 | к : 111 |
------------------------------
Screen:
Run:
Задание 5
Разработайте программу, которая по четырехбайтовому IP-адресу узла и IP-адресу маски подсети вычисляет сетевой адрес.
Code:
# coding=utf-8
#!/usr/bin/python3
import sys
def generate(ip_or_mask):
"""
Заполняет нулями до 8 символов, переводя в двоичную систему
:param ip_or_mask: ip или маска
"""
ip_or_mask = [int(x) for x in ip_or_mask. split('.')]
res = []
for i in ip_or_mask:
st = '{0:b}'.format(i)
if len(st) < 8:
st = ('0' * (8 - len(st))) + st
res. append(st)
return res
def compare(ip_bin, netmask_bin):
"""
Поразрядно сравнивает двоичные значения ip и маски
:param ip_bin: ip в двоичной форме
:param netmask_bin: маска в двоичной форме
"""
result = []
for i, k in zip(ip_bin, netmask_bin):
temp = []
for x, y in zip(i, k):
x, y = int(x), int(y)
temp. append(str(x and y)) # по тому что bool(0) == False; bool(1) == True
result. append(temp)
return [''.join(x) for x in result]
def generate_subnet(ip, net_mask):
"""
Вычисляет сетевой адрес
"""
ip = generate(ip)
net_mask = generate(net_mask)
bin_subnet = compare(ip, net_mask)
subnet_result = '.'.join([str(eval('0b{}'.format(x))) for x in bin_subnet]) # выполняем строку в качестве кода
return subnet_result
input()
for i in sys. stdin:
tmp = i. split('\t\t')
ip = tmp[0]
mask = tmp[1]
print('IP: ', ip)
print('MASK: ', mask)
print('Сетевой адрес:', generate_subnet(ip, mask))
print('-'*30)
In:
IP MASK
192.168.192.168 255.254.6.4
165.250.120.99 254.64.128.216
265.250.230.209 254.44.158.216
16.25.100.89 16.74.128.216
185.283.121.14 51.64.86.190
Out:
IP: 192.168.192.168
MASK: 255.254.6.4
Сетевой адрес: 192.168.0.0
------------------------------
IP: 165.250.120.99
MASK: 254.64.128.216
Сетевой адрес: 164.64.0.64
------------------------------
IP: 265.250.230.209
MASK: 254.44.158.216
Сетевой адрес: 132.40.134.208
------------------------------
IP: 16.25.100.89
MASK: 16.74.128.216
Сетевой адрес: 16.8.0.88
------------------------------
IP: 185.283.121.14
MASK: 51.64.86.190
Сетевой адрес: 49.0.80.14
Screen: 
Run:
Задание 6
Разработайте программу для выдачи денег банкоматом по заданной клиентом сумме денег M кратной 50 рублям и наличию в банкомате X1 купюр по 50 рублей, X2 купюр по 100 рублей, X3 купюр по 1000 рублей, X4 купюр по 5000 рублей. Известно, что максимальная сумма для выдачи M не превышает 50000 рублей, минимальная сумма выдачи денег 50 рублей. После каждой выдачи денег, программа подсчитывает минимально возможные количества купюр X1, X2, X3, X4 и выдает сообщение "Банкомат временно не работает" в случае нехватки купюр для следующей выдачи денег по указанным условиям. Программа выполняет сначала учет ввода денег в банкомат для выдачи, а затем выдачу произвольных сумм клиентам банка.
Code:
# coding=utf-8
# !/usr/bin/python3
import random
import sys
class OutOfMoney(Exception): pass
def expand(bills, money):
_money = money
_bills = bills. copy()
pos_bills = [5000, 1000, 100, 50]
for i in pos_bills:
col = money // i
if col >= 1:
for k in range(col, 0, -1): # чтобы подобрать максимальное количество купуюр большего ноинала
if bills[i] - k >= 0 and money - k * i >= 0:
money -= k * i # вычитаем деньги которые можно выдать купюрами
bills[i] -= k
if money!= 0:
print('-' * 50)
print('Банкомат временно не работает')
raise OutOfMoney
print('Купюры: ', _bills)
print('Нужно снять: ', _money)
print('Осталось купюр: ', bills)
print('-' * 50)
return bills
bls = {j: random. randint(1, 100) for j in [5000, 1000, 100, 50]} # пусть изначальное кол-во купюр будет случайным
print('Купюры в банкомате: ', bls)
for i in sys. stdin:
try:
cash = int(i)
if cash < 50 or cash > 50000:
raise ValueError
except ValueError:
print('Неправильное Ввод ', i)
print('-' * 50)
continue
try:
bls = expand(bls, cash)
except OutOfMoney:
break
In:
7
500
50
6150
1650
6150
5000
1000
10000
45000
41250
42650
47850
950
50
150
47850
50000
700
600
Out:
Купюры в банкомате: {5000: 83, 1000: 41, 50: 98, 100: 51}
Неправильное Ввод 7
--------------------------------------------------
Купюры: {5000: 83, 1000: 41, 50: 98, 100: 51}
Нужно снять: 500
Осталось купюр: {5000: 83, 1000: 41, 50: 98, 100: 46}
--------------------------------------------------
Купюры: {5000: 83, 1000: 41, 50: 98, 100: 46}
Нужно снять: 50
Осталось купюр: {5000: 83, 1000: 41, 50: 97, 100: 46}
--------------------------------------------------
Купюры: {5000: 83, 1000: 41, 50: 97, 100: 46}
Нужно снять: 6150
Осталось купюр: {5000: 82, 1000: 40, 50: 96, 100: 45}
--------------------------------------------------
Купюры: {5000: 82, 1000: 40, 50: 96, 100: 45}
Нужно снять: 1650
Осталось купюр: {5000: 82, 1000: 39, 50: 95, 100: 39}
--------------------------------------------------
Купюры: {5000: 82, 1000: 39, 50: 95, 100: 39}
Нужно снять: 6150
Осталось купюр: {5000: 81, 1000: 38, 50: 94, 100: 38}
--------------------------------------------------
Купюры: {5000: 81, 1000: 38, 50: 94, 100: 38}
Нужно снять: 5000
Осталось купюр: {5000: 80, 1000: 38, 50: 94, 100: 38}
--------------------------------------------------
Купюры: {5000: 80, 1000: 38, 50: 94, 100: 38}
Нужно снять: 1000
Осталось купюр: {5000: 80, 1000: 37, 50: 94, 100: 38}
--------------------------------------------------
Купюры: {5000: 80, 1000: 37, 50: 94, 100: 38}
Нужно снять: 10000
Осталось купюр: {5000: 78, 1000: 37, 50: 94, 100: 38}
--------------------------------------------------
Купюры: {5000: 78, 1000: 37, 50: 94, 100: 38}
Нужно снять: 45000
Осталось купюр: {5000: 69, 1000: 37, 50: 94, 100: 38}
--------------------------------------------------
Купюры: {5000: 69, 1000: 37, 50: 94, 100: 38}
Нужно снять: 41250
Осталось купюр: {5000: 61, 1000: 36, 50: 93, 100: 36}
--------------------------------------------------
Купюры: {5000: 61, 1000: 36, 50: 93, 100: 36}
Нужно снять: 42650
Осталось купюр: {5000: 53, 1000: 34, 50: 92, 100: 30}
--------------------------------------------------
Купюры: {5000: 53, 1000: 34, 50: 92, 100: 30}
Нужно снять: 47850
Осталось купюр: {5000: 44, 1000: 32, 50: 91, 100: 22}
--------------------------------------------------
Купюры: {5000: 44, 1000: 32, 50: 91, 100: 22}
Нужно снять: 950
Осталось купюр: {5000: 44, 1000: 32, 50: 90, 100: 13}
--------------------------------------------------
Купюры: {5000: 44, 1000: 32, 50: 90, 100: 13}
Нужно снять: 50
Осталось купюр: {5000: 44, 1000: 32, 50: 89, 100: 13}
--------------------------------------------------
Купюры: {5000: 44, 1000: 32, 50: 89, 100: 13}
Нужно снять: 150
Осталось купюр: {5000: 44, 1000: 32, 50: 88, 100: 12}
--------------------------------------------------
Купюры: {5000: 44, 1000: 32, 50: 88, 100: 12}
Нужно снять: 47850
Осталось купюр: {5000: 35, 1000: 30, 50: 87, 100: 4}
--------------------------------------------------
Купюры: {5000: 35, 1000: 30, 50: 87, 100: 4}
Нужно снять: 50000
Осталось купюр: {5000: 25, 1000: 30, 50: 87, 100: 4}
--------------------------------------------------
Купюры: {5000: 25, 1000: 30, 50: 87, 100: 4}
Нужно снять: 700
Осталось купюр: {5000: 25, 1000: 30, 50: 81, 100: 0}
--------------------------------------------------
Купюры: {5000: 25, 1000: 30, 50: 81, 100: 0}
Нужно снять: 600
Осталось купюр: {5000: 25, 1000: 30, 50: 69, 100: 0}
Screen:
Run:
Задание 7
Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
Пример
исходные данные | результат |
4 3 14 7 6 | 0 0 1 0 |
Code:
#!/usr/bin/python3
# coding=utf-8
import sys
def make_lazy_seq(k_max):
"""
Позиция каждой n-ной единички вычисляется по формуле (n*(n+1)) * 1/2 + 1
Эта функция генерирует список положений единички до k_max
"""
def infinity_generator():
i = 0
while True:
yield i
i += 1
lazy_caterers_sequence = []
for n in infinity_generator():
x = (0.5 * n * (n + 1)) + 1
lazy_caterers_sequence. append(x)
if x > k_max:
break
return lazy_caterers_sequence
seq = make_lazy_seq(2 ** 31 - 1)
for i in sys. stdin:
try:
position = int(i)
if position < 0 or position > 2 ** 31 - 1:
raise ValueError
except ValueError:
print('Неправильное число')
continue
if position in seq:
print('1', end=' ')
else:
print('0', end=' ')
print()
In:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
14
7
6
16
21
22
23
65535
5424
34
64
35
78
98
Out:
1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0
Screen:
Run:
Задание 8
Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня, одиноко стоящего на шахматной доске. На всякий случай напомним, что конь ходит буквой «Г» — на две клетки по горизонтали или вертикали в любом направлении, и потом на одну клетку в направлении, перпендикулярном первоначальному.
Исходные данные
В первой строке находится единственное число N, 1 ≤ N ≤ 100 — количество тестов. В каждой из последующих Nстрок содержится очередной тест: два символа (маленькая латинская буква от 'a' до 'h' и цифра от 1 до 8) — стандартное шахматное обозначение клетки, на которой стоит конь. При этом буква обозначает вертикаль, а цифра — горизонталь.
Результат
Выведите N строк: в каждой из них должно находиться единственное число — количество клеток шахматной доски, находящихся под боем коня.
Пример
исходные данные | результат |
3 a1 d4 g6 | 2 8 6 |
Code:
# coding=utf-8
#!/usr/bin/python3
import string
def killer_horse(horse):
board = [[0 for x in range(8)] for k in range(8)] # составляем пустую доску
numerated_alphabet = {i:j for i, j in zip(string. ascii_lowercase, range(len(string. ascii_lowercase)))} # нумеруем английский алфавит
horse = (int(numerated_alphabet[horse[0]]), int(horse[1]) - 1) # заменяем букву на её положение в алфавите, чтобы получить координату
# (ver, hor)
turns = [(2, -1), (2, 1), (-1, -2), (1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2)] # Возможные ходы коня в разные стороны
possible_turns = 0
for i in turns:
go = horse[0] + i[0], horse[1] + i[1] # Пробует сходить
if False not in [x in range(0, 7) for x in go]: # из за индексов в python тк. индекс от отр. числа будет брать элементы с конца
try:
board[go[0]][go[1]]
except IndexError:
pass
else:
possible_turns += 1 # если небыло исключения
return possible_turns
input()
while True:
try:
cell = input()
except EOFError:
break
print(killer_horse(cell))
In:
10
a1
d4
g6
f8
a4
c3
c6
h1
f4
e2
Out:
2
8
6
4
4
8
8
2
8
6
Screen:
Run:
