вторник, 29 октября 2019 г.

Решения задач школьного этапа олимпиады по информатике (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 ) )

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

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

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

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

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

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

Вводятся три целых числа A, B, L (2<=A,B<=

10^{6}

, 1<=L<=

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)

Задача 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 􏰀

10^{9}

, 1 􏰀 K 􏰀 2

\cdot 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) ))

четверг, 17 октября 2019 г.

ЕГЭ. Реализация алгоритмических задач на Python

Реализация алгоритмических задач из ЕГЭ на Python

Возможные алгоритмические задачи для подраздела 1.1 перечня требований к уровню подготовки выпускников, достижение которых проверяется на ЕГЭ (согласно документу ФИПИ - "Кодификатор элементов содержания и требований к уровню подготовки выпускников образовательных организаций для проведения единого государственного экзамена по информатике и ИКТ")¶

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

В стили Python (не используем на ЕГЭ!):

In [14]:

print(min(map(int,input().split())))

6 4 5 3 8
3

Подходит для любого количества чисел.

Для ЕГЭ в классическом стиле :

Один из возможных вариантов для четырех чисел:

In [7]:

a,b,c,d=map(int,input().split())
m=a
if m>b: m=b
if m>c: m=c
if m>d: m=d
print(m)

5 4 3 6
3

2. Нахождение всех корней заданного квадратного уравнения.

In [16]:

from math import sqrt
a,b,c = map(int,input().split())
d = b*b - 4*a*c
if d==0:
    print('Один корень x=', -b/(2*a))
elif d>0:
    print('Два корня: x1=',(-b-sqrt(d))/(2*a),', x2=',(-b+sqrt(d))/(2*a))
else:
    print('Нет корней в области действительных чисел.')

1 3 2
Два корня: x1= -2.0 , x2= -1.0

In [ ]:

1 2 1
Один корень x= -1.0
2 2 2
Нет корней в области действительных чисел.

3. Запись натурального числа в позиционной системе с основанием, меньшим или равным 10. Обработка и преобразование такой записи числа.

В качестве ответа получаем строку y из символов-цифр в системе счисления q:

In [4]:

x,q = map(int,input().split())
t = x
y = ''
while t:
    y = str(t%q) + y
    t //= q
print(y)

18 4
102

В качестве ответа получаем список y из цифр в системе счисления q:

In [7]:

x,q = map(int,input().split())
t = x
y = []
while t:
    y.append(t%q)
    t //= q
print(y)

18 4
[2, 0, 1]

4. Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива).

В стили Python (не используем на ЕГЭ!):

In [1]:

print(sum(map(int,input().split())))

Для ЕГЭ в классическом стиле :

сумма последовательности:

In [3]:

s=0
for a in input().split():
    s += int(a)
print(s)

произведение последовательности:

In [4]:

p=1
for a in input().split():
    p *= int(a)
print(p)

сумма элементов имеющегося списка x (вместо массива):

In [5]:

x=[2,4,3,5,1]
s=0
for a in x:
    s += a
print(s)

5. Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т.д.).

наименьшей делитель r данного натурального числа n:

In [ ]:

n=int(input())
r=2
while n%r and r*r<=n: r +=1
if  r*r<=n: print(r)
else: print (n)

проверка числа n на простоту

In [9]:

n=int(input())
r=2
while n%r and r*r<=n: r +=1
if  r*r<=n: print('Составное')
else: print ('Простое')

35
Составное

In [ ]:

37
Простое

наименьшей простой делитель r

данного натурального числа n:

In [36]:

n=int(input())
r=2
prostoe=True
while n%r and r*r<=n: r +=1
if  r*r<=n:
    print(r)
    prostoe=False
if prostoe: print ('Число является простым')

Число является простым

наибольший общий делитель a и b:

In [38]:

a,b = map(int,input().split())
while a^b:
    if a>b: a -= b
    else: b -= a
print(a)

наименьшее общее кратное a и b- $Н О К (a, b) = \frac{a * b}{Н О Д (a, b)}$ :

In [10]:

a,b = map(int,input().split())
x,y = a,b
while a^b:
    if a>b: a-=b
    else: b -=a
print(x*y//a)

14 35
70

6. Заполнение элементов одномерного и двумерного массивов по заданным правилам.

Ввод элементов одномерного массива (списка) a с клавиатуры

Все элементы в одной строке:

In [22]:

a=list(map(int,input().split()))
print(a)

3 2 5 4
[3, 2, 5, 4]

N элементов, каждый с новой строки

In [25]:

N=int(input())
a=[]
for __ in range(N):
    a.append(int(input()))
print(a)

4
3
2
5
4
[3, 2, 5, 4]

Ввод элементов двумерного NxN массива (списка) a с клавиатуры

In [26]:

a=[]
N=int(input())
for __ in range(N):
    a.append(list(map(int,input().split())))
print(a)

3
1 2 3
2 3 4
3 4 5
[[1, 2, 3], [2, 3, 4], [3, 4, 5]]

Заполнение массива a 10-ю одинаковыми значениями (0)

In [27]:

a=[0]*10
print(a)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Заполнение массива a значениями последовательности. Например, геометрическая прогрессия с $a_{0} = 4$ и $q = 1.5$ до an

In [28]:

N=int(input())
a=[4*1.5**i for i in range(N)]
print(a)

10
[4.0, 6.0, 9.0, 13.5, 20.25, 30.375, 45.5625, 68.34375, 102.515625, 153.7734375]

7. Операции с элементами массива.

Линейный поиск элемента

Наличие элемента с заданными свойствами. Например, нечетного и заканчивающегося на 3

In [81]:

a=[7, 31, 53, 34]
print(sum(1 for i in a if i&1 and i%10==3)>0)

True

In [82]:

a=[7, 31, 35, 34]
print(sum(1 for i in a if i&1 and i%10==3)>0)

False

Положение первого элемента со значением x

In [62]:

a=[7, 31, 35, 34]
x=10
print(x in a and a.index(x))

False

In [64]:

a=[7, 31, 35, 34]
x=31
print(x in a and a.index(x))

Вставка и удаление элементов в массиве.

Вставка в позицию k1 значения x и удаление из элемента позиции k2

In [67]:

a=[7, 31, 35, 34]
print(a)
k1,x = 2,50
a.insert(k1,x)
print(a)
k2=1
a.pop(k2)
print(a)

[7, 31, 35, 34]
[7, 31, 50, 35, 34]

Out[67]:

[7, 50, 35, 34]

Перестановка элементов данного массива в обратном порядке.

In [68]:

a=[7, 31, 35, 34]
a=a[::-1]
print(a)

[34, 35, 31, 7]

Суммирование элементов массива.

В стиле Python

In [69]:

a=[7, 31, 35, 34]
print(sum(a))

По некоторому уловию. Например, cумма четных

In [76]:

a=[8, 31, 35, 34]
print(sum(i for i in a if i&1^1))

В классическом стиле

In [70]:

a=[7, 31, 35, 34]
s=0
for i in a:
    # if ... могут быть условия:
    s += i
print(s)

Проверка соответствия элементов массива некоторому условию.

Все элементы с заданными свойствами. Например, нечетные и положительные

In [84]:

a=[7, 31, 53, 34]
print(sum(1 for i in a if i&1 and i>0)==len(a))

False

In [83]:

a=[7, 31, 53, 35]
print(sum(1 for i in a if i&1 and i>0)==len(a))

True

Более рационально:

In [92]:

a=[7, 31, 53, 35]
L=len(a)
i=0
while i<L and a[i]&1 and a[i]>0:
    i +=1
print(i==L)

True

Является ли массив упорядоченным по возрастанию:

In [93]:

a=[7, 31, 53, 35]
L=len(a)
i=1
while i<L and a[i-1]<=a[i]>0:
    i +=1
print(i==L)

False

In [94]:

a=[7, 31, 35, 53]
L=len(a)
i=1
while i<L and a[i-1]<=a[i]>0:
    i +=1
print(i==L)

True

8. Нахождение второго по величине (второго минимального) значения в данном массиве за однократный просмотр массива

In [97]:

a=[47, 31, 9, 35, 53, 7]
m1=a[0]
m2=a[1]
if m2<m1: m1,m2 = m2,m1
for x in a[2:]:
    if x<m1:
        m2,m1 = m1,x
    elif x<m2:
        m2 = x
print(m2)

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

In [103]:

a=[17, 17, 11, 19, 35, 11, 27]
m,k = a[0],1
for x in a[1:]:
    if x<m:
        m,k = x,1
    elif x==m:
        k += 1
print(m,k)

11 2

10. Операции с элементами массива, отобранных по некоторому условию

нахождение минимального четного элемента в массиве

In [107]:

a=[17, 18, 11, 12, 35, 11, 27]
m=False
for i in range(len(a)):
    if a[i]&1^1:
        if not m : m=a[i]
        elif i and a[i]<m: m=a[i]
print(m)

In [108]:

a=[17, 17, 11, 19, 35, 11, 27]
m=False
for i in range(len(a)):
    if a[i]&1^1:
        if not m : m=a[i]
        elif i and a[i]<m: m=a[i]
print(m)

False

нахождение количества и суммы всех четных элементов в массиве

In [110]:

a=[17, 18, 11, 12, 35, 11, 27]
k=0; s=0
for x in a:
    if x&1^1:
        k,s = k+1,s+x
print(k,s)

2 30

11. Сортировка массива.

В стиле Python:

In [111]:

a=[17, 18, 11, 12, 35, 11, 27]
a.sort()
print(a)

[11, 11, 12, 17, 18, 27, 35]

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

Простые виды сортировки

Сортировку обменом (пузырьковая) - не эффективна со всех сторон (проверок - $N^{2}$ перестановок - $N^{2}$ ) - рассматривать не будем

Сортировка выбором, по крайней мере, перестановок - $N$

In [112]:

a=[17, 18, 11, 12, 35, 11, 27]
L=len(a)
for i in range(L-1):
    m=i
    for j in range(i,L):
        if a[j]<a[m]: m=j
    if m>i:
        a[m],a[i] = a[i],a[m]
print(a)

[11, 11, 12, 17, 18, 27, 35]

Сортировка вставками - хорошо работает на частично упорядоченных массивах

In [120]:

a=[17, 18, 11, 12, 35, 11, 27]
L=len(a)
for i in range(1,L):
    j=i
    while j and a[j]<a[j-1]:
        a[j],a[j-1] = a[j-1],a[j]
        j -= 1
print(a)

[11, 11, 12, 17, 18, 27, 35]

Сортировка подсчетом - хорошо работает, если диапазон значений значительно меньше количества элентов $N$

In [1]:

a=[3, 5, 4, 3, 5, 4, 5, 4, 4]
k=[0]*6
for i in a:
    k[i] += 1
for i in range(6):
    for j in range(k[i]):
        print(i, end=' ')

3 3 4 4 4 4 5 5 5

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

In [2]:

a=[11, 12, 17, 18, 27]
b=[9, 15, 23, 25, 41, 50]
c=[]
ia=ib=0
while ia<len(a) and ib<len(b):
 if a[ia]<=b[ib]:
  c.append(a[ia])
  ia += 1
 else:
  c.append(b[ib])
  ib += 1
if ia<len(a):
 c.extend(a[ia:])
else:
 c.extend(b[ib:])
print(c)

[9, 11, 12, 15, 17, 18, 23, 25, 27, 41, 50]

12. Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке.

Сколько раз в строке $a$ встречается символ (строка) $b$

In [6]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(a.count(b))

введите строку: abracadabra
введите символ: ra
2

Определить в строке $a$ позицию первого вхождения символа (строки) $b$ (или -1)

In [4]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(a.find(b))

введите строку: abracadabra
введите символ: r
2

Есть ли в строке $a$ символ (строка) $b$

In [7]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(b in a)

введите строку: abracadabra
введите символ: ad
True

13. Работа с подстроками данной строки с разбиением на слова попробельным символами. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку.

Разбиение на слова попробельным символами.

In [9]:

print(input().split())

Разбиение на слова попробельным символами
['Разбиение', 'на', 'слова', 'попробельным', 'символами']

Удаление из строки $a$ подстроки $b$

In [15]:

a='abracadabra'
b='br'
print(''.join(a.split(b)))

aacadaa

Змена в строке $a$ подстроки $b$ на строку $c$

In [16]:

a='abracadabra'
b='br'
c='dub'
print(a.replace(b,c))

adubacadaduba

Страницы

вторник, 29 октября 2019 г.

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

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

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

Решение

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

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

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

Примеры

Решение

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

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

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

Примеры

Решение

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

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

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

Примеры

Решение

четверг, 17 октября 2019 г.

ЕГЭ. Реализация алгоритмических задач на Python

Реализация алгоритмических задач из ЕГЭ на Python

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

В стили Python (не используем на ЕГЭ!):

Для ЕГЭ в классическом стиле :

2. Нахождение всех корней заданного квадратного уравнения.

3. Запись натурального числа в позиционной системе с основанием, меньшим или равным 10. Обработка и преобразование такой записи числа.

4. Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива).

В стили Python (не используем на ЕГЭ!):

Для ЕГЭ в классическом стиле :

5. Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т.д.).

наименьшей делитель r данного натурального числа n:

проверка числа n на простоту

наименьшей простой делитель r

данного натурального числа n:

наибольший общий делитель a и b:

наименьшее общее кратное a и b- НОК(𝑎,𝑏)=𝑎∗𝑏НОД(𝑎,𝑏)НОК(a,b)=a∗bНОД(a,b):

6. Заполнение элементов одномерного и двумерного массивов по заданным правилам.

Ввод элементов одномерного массива (списка) a с клавиатуры

Ввод элементов двумерного NxN массива (списка) a с клавиатуры

Заполнение массива a 10-ю одинаковыми значениями (0)

Заполнение массива a значениями последовательности. Например, геометрическая прогрессия с 𝑎0a0=4 и 𝑞q=1.5 до an

7. Операции с элементами массива.

Линейный поиск элемента

Вставка и удаление элементов в массиве.

Перестановка элементов данного массива в обратном порядке.

Суммирование элементов массива.

Проверка соответствия элементов массива некоторому условию.

8. Нахождение второго по величине (второго минимального) значения в данном массиве за однократный просмотр массива

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

10. Операции с элементами массива, отобранных по некоторому условию

нахождение минимального четного элемента в массиве

нахождение количества и суммы всех четных элементов в массиве

11. Сортировка массива.

Простые виды сортировки

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

12. Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке.

AI

Общее·количество·просмотров·страницы

вторник, 29 октября 2019 г.

четверг, 17 октября 2019 г.

наименьшее общее кратное a и b- $Н О К (a, b) = \frac{a * b}{Н О Д (a, b)}$ :

Заполнение массива a значениями последовательности. Например, геометрическая прогрессия с $a_{0} = 4$ и $q = 1.5$ до an