основы_программирования_на_языке_python. Министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего
 Скачать 208.8 Kb.
|
|
| ввод | вывод |
| 2 3 7 | NO |
| 0.1 0.2 0.3 | YES |
РЕШЕНИЕ
Для сравнения двух действительных чисел нужно посчитать модуль разности этих чисел и сравнить их с некоторой константой эпсилон. Входные данные заданы с точностью 10−7 (два разных входных числа отличаются как минимум на 10−7, поэтому значение эпсилон нужно взять меньшим, чем 10−7. Возьмем значение эпсилон равное 10−8
a = float(input())
b = float(input())
c = float(input())
if abs(a + b - c) < 1e-8:
print("YES")
else:
print("NO")
Задача 57: Утренняя пробежка
Ограничение по времени работы программы: 1 секунда
В первый день спортсмен пробежал x километров, а затем он каждый день увеличивал пробег на 70% от предыдущего значения. По данному числу y определите номер дня, на который пробег спортсмена составит не менее y километров.
ВХОДНЫЕ ДАННЫЕ
На вход программа получает два числа x и y, записанные в одной строке. Числа положительные, действительные, не превосходят 1000, заданы с точностью до шести знаков после запятой.
ВЫХОДНЫЕ ДАННЫЕ
Программа должна вывести одно натуральное число — номер дня в который спортсмен пробежал не менее y километров.
ПРИМЕР
| ввод | вывод |
| 10.0 30.0 | 4 |
| 1 2.89 | 3 |
РЕШЕНИЕ
В цикле домножайте значение x на 1.7, пока оно меньше y. При сравнении действительных чисел нужно использовать эпсилон, можно взять значение эпсилон равное 10−9.
EPS = 1e-9
x, y = map(float, input().split())
n = 1
while x < y - EPS:
x *= 1.7
n += 1
print(n)
Задача 58: Объединение отрезков
Ограничение по времени работы программы: 2 секунды
Решая задачу из контрольной по математике, Вася получил ответ в виде объединения N отрезков [Li,Ri] на числовой прямой. Однако, некоторые из этих отрезков могут пересекаться друг с другом, что не слишком нравится Васе. От вас требуется представить Васин ответ в виде объединения минимального количества непересекающихся отрезков.
ВХОДНЫЕ ДАННЫЕ
В первой строке входных данных дано число N (1≤N≤30000). В следующих N строках перечислены пары целых чисел Li и Ri (−50000≤Li≤Ri≤50000). Обратите внимание, что концы отрезков могут совпадать, в этом случае отрезок вырождается в точку.
ВЫХОДНЫЕ ДАННЫЕ
В первой строке выведите число M — количество отрезков в искомом объединении. В следующих M-строках выведите сами эти отрезки в том же формате, что и во входном файле. Список отрезков необходимо упорядочить по возрастанию левого конца.
ПРИМЕР
| ввод | вывод |
| 4 0 2 4 5 1 3 5 6 | 2 0 3 4 6 |
РЕШЕНИЕ
Создадим список событий, добавив туда начала и концы всех данных отрезков. Отсортируем список событий по возрастанию координаты, при равном значении координаты сначала должны идти начала отрезков, потом - концы.
Пройдем по списку событий, считая количество отрезков, которые пересекаются с текущим положением, при появлении начала отрезка этот счетчик увеличивается на 1, при появлении конца отрезка - уменьшается на 1. Обнаружив место, в котором начинается новый отрезок общего объединения или заканчивается отрезок общего объединения. добавим к ответу координату текущей точки.
Конец отрезка в объединении соответствует ситуации, когда счетчик числа пересекающихся отрезков стал равен 0. Начало отрезка в объединении соответствует ситуации, когда счетчик числа отрезков стал равен 1, при этом тип текущего события - начало отрезка.
n = int(input())
Events = []
for i in range(n):
l, r = map(int, input().split())
Events.append((l, -1))
Events.append((r, 1))
Ans = []
count = 0
for x, type in sorted(Events):
count -= type
if count == 0 or count == 1 and type == -1:
Ans.append(x)
print(len(Ans) // 2)
for i in range(0, len(Ans), 2):
print(Ans[i], Ans[i + 1])
Задача 59: Кассы
Ограничение по времени работы программы: 1 секунда
На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
ВХОДНЫЕ ДАННЫЕ
Сначала вводится одно целое число N (0
В каждой из следующих N строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает-— на следующий день.
ВЫХОДНЫЕ ДАННЫЕ
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все N касс.
ПРИМЕР
| ввод | вывод |
| 3 1 0 0 23 0 0 12 0 0 12 0 0 22 0 0 2 0 0 | 7200 |
| 2 9 30 0 14 0 0 14 15 0 21 0 0 | 0 |
| 2 14 00 00 18 00 00 10 00 00 14 00 01 | 1 |
РЕШЕНИЕ
Задача решается стандартным методом с сортировкой всех событий (начало и конец работы кассы) и проходом по отсортированному списку событий с подсчетом того, сколько касс работает в настоящий момент. Удобно все времена сразу же перевести в секунды от начала суток.
Если в какой-то момент количество работающих касс стало равно n, нужно запомнить этот момент в отдельной переменной. Если в какой-то момент количество работающих касс стало n−1 и текущее событие - окончание работы какой-то кассы, то к ответу нужно добавить текущее время минут запомненный момент, когда открылись все кассы.
Необходимо также понять, как обрабатывать кассы, которые открыты в полночь, то есть время начала их работы больше или равно времени окончания. Для этого просто посчитаем количество таких касс, и проинициализируем счетчик числа работающих касс этим количеством, далее будем решать задачу обычном образом (тогда касса, которая работает в полночь, была открыта, потом она закрывается, что уменьшает значение счетчика, а потом открывается, что увеличивает счетчик).
Также нужно учесть, что если в конце обработки всех событий счетчик числа работающих касс равен n, то это означает, что в полночь следующих суток все n касс открыты и к ответу нужно добавить время, прошедшее с момента, когда открылись все n касс в последний раз до полуночи.
n = int(input())
Events = []
count = 0
for i in range(n):
h1, m1, s1, h2, m2, s2 = map(int, input().split())
t1 = 3600 * h1 + 60 * m1 + s1
t2 = 3600 * h2 + 60 * m2 + s2
Events.append((t1, 1))
Events.append((t2, -1))
if t1 >= t2:
count += 1
ans = 0
start = 0
for x, type in sorted(Events):
count += type
if count == n:
start = x
if count == n - 1 and type == -1:
ans += x - start
if count == n:
ans += 24 * 3600 - start
print(ans)
Заключение
Во время выполнения работы был создан учебно - методический комплекс по изучению языка программирования Python и размещен на labs.tspu.ru.
В данной работе были рассмотрены такие темы как: комментарии, числа, строки, переменные, типы данных, операторы, функции, модули, структуры данных, списки, словари, множества, кортежи. Также были рассмотрены программное (Python) и методическое (алгоритмы) обеспечение и решен ряд задач:
• изучены алгоритмы для решения олимпиадных задач;
• решены олимпиадные задачи с использованием языка программирования Python;
• разобраны олимпиадные задачи;
• рассмотрено 59 задач с подробным разбором.
Материалы учебно - методического комплекса по изучению языка программирования Python можно использовать в кружках по олимпиадному программированию. В перспективе планируется рабочая программа для проведения занятий в таком кружке на основе представленных материалов.
Список литературы
CITATION htt \l 1033 : , (1),
CITATION Рус \l 1049 : , (2),
CITATION Вом16 \l 1049 : , (3),
CITATION Pyt16 \l 1033 : , (4),
CITATION Хаб16 \l 1049 : , (5),
CITATION Вгл16 \l 1049 : , (6),
CITATION Кир \l 1049 : , (7),
