Буває так, що задача нескладна, але умова не відразу є зрозумілою. І тоді звичайний графічний аналіз дуже допомогає розв’язанню. Пропоную розібрати задачу «Гра з перемикачами»
https://www.e-olymp.com/uk/problems/335
Умова:
Є нескінченна кількість ламп, що знаходяться у вимкненому стані. На кожному етапі гри вмикаються (якщо вони були вимкнені) або вимикаються (якщо вони були увімкнені) всі ті лампи, номери яких кратні номеру етапу гри.
Задача:
Визначити стан n-ої лампи після n-го етапу гри.
Вхідні дані
У першому рядку задано кількість тестів t (1 ≤ t ≤ 10). Далі йде t рядків з номером n (0 < n ≤ 105) етапу гри.
Вихідні дані
Вивести t рядків зі станами відповідних ламп: 0 - лампу вимкнено, 1 - увімкнуто.
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Приклад вхідних даних:
2
1
5
Приклад вихідних даних:
1
0
Розв’яжемо задачу графічно. Візьмемо, наприклад, деяку кількість ламп і проаналізуємо їх стан під час проходження етапів гри. На старті гри всі лампи вимкнені, згідно умови.
Після першого етапу всі лампи ввімкнуться, тому що будь-яке число кратне одиниці, тобто націло ділиться на одиницю.
Після другого етапу гри всі лампи, номери яких кратні двом, змінять свій стан. Оскільки після першого етапу всі лампи увімкнені, то лампи з парними номерами вимкнуться.
Ось як можна графічно показати стан ламп після другого етапу гри, жовтий колір – це лампи, що світяться, чорні - вимкнені:

Далі можна аналогічно розписати стан наших 17 ламп після проходження етапів гри і окремо проаналізувати, який стан матиме кожна лампа після чергового етапу:

З нашого прикладу бачимо, що відповідні лампи залишаються увімкненими після 1, 4, 9 і 16 етапів гри, відповідно, в тих випадках, коли квадратний корінь з номера етапу (відповідно, і номера лампи) – ціле число.
Код – питання другорядне, ось один з варіантів на Python:
from math import sqrt
t = int(input())
for _ in range(t):
n = int(input())
if sqrt(n) == int(sqrt(n)):
print(1)
else:
print(0)
У даному випадку графічний аналіз значно допоміг нам знайти логіку і розв'язок.
Два масива
(https://www.e-olymp.com/uk/problems/2099)
Умова:
Задано два масиви чисел. Потрібно вивести ті елементи першого масиву (у том ж порядку, у якому вони йдуть у першому масиві), яких немає у другому масиві.
Вхідні дані:
Спочатку на вхід подається кількість елементів n у першому масиві, потім n чисел - елементи масиву. Далі записано кількість елементів m у другому масиві. Потім записано елементи другого масиву. Кількість елементів кожного масиву не перевищує 100. Усі елементи - цілі числа.
Вихідні дані:
У першому рядку виведіть кількість шуканих елементів, а у другому виведіть ті елементи першого масиву, яких немає у другому, у том у ж порядку, у якому вони йдуть у першому масиві.
Ліміт часу: 1 секунда
Ліміт використання пам'яті: 128 MiB
Джерело: Китеня 2011 м.Ковров
Приклад вхідних даних:
7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
Приклад вихідних даних:
4
3 3 2 12
Задача нескладна, має на сайті e-olymp.com рейтинг cкладності всього 8%.
Проте під час розв’язку варто звернути увагу на одну цікаву особливість роботи зі списками.
Для початку пропоную створити третій список, в який будемо накопичувати значення елементів першого списку, що відповідають умові задачі. Наприклад:
input()
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
third = []
for x in first:
if x not in second:
third.append(x)
print(len(third))
print(' '.join(map(str, third)))
Хоча для оптимального розв’язку буде логічним мінімальне використання пам’яті, тому спробуємо розв’язати дану задачу без додаткового списку. Наприклад:
Перебрати всі елементи першого списку. Якщо елемент з таким значенням є в другому списку, то видалити цей елемент з першого списку. Після перебору кожного елементу першого списку таким способом, у ньому залишаться тільки такі елементи, яких немає в другому списку, що нам і потрібно.
Приклад коду:
input()
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
for x in first:
if x in second:
first.remove(x)
print(len(first))
print(' '.join(map(str, first)))
Це виглядає значно оптимальніше, програма відпрацьовує тестовий приклад, але не проходить всі тести на сайті e-olymp.com Що ж не так?
Справа в тому, що ми змінюємо список, який перебираємо. І отримуємо проблему.
Поясню на прикладі.
Нехай наш перший список: [1,2,3,4,5]
Другий список: [2,3]
Який ми повинні отримати результат? [1,4,5].
Але програма видає [1,3,4,5].
Звідки взялася трійка, програма ж повинна була її видалити!
Ось тут і є особливість. Як цикл for буде перебирати числа? По черзі. Перший елемент, другий елемент, третій елемент і т.д.
А тепер давайте послідовно проаналізуємо значення елементів першого списку: [1,2,3,4,5]
Перший елемент – одиниця, якої немає в другому списку. Отже, одиниця – унікальна, ми її не чіпаємо.
Другий елемент в прикладі – двійка. Вона є в другому списку. Тому ми її видаляємо.
Який список залишається? [1,3,4,5]. Отже, який елемент списку ми відпрацювали? Другий?
Правильно. Беремо третій. Це четвірка. А чому четвірка?
А тому що при видаленні двійки, всі елементи зсунулися і місце видаленої двійки зайняла трійка. Саме трійка стала другим елементом після видалення двійки.
Але цикл, який вже відпрацював другий елемент при наступній ітерації бере собі в роботу третій елемент, таким чином пропускаючи трійку. Виходить, наш підхід неправильний.
Аналізуючи даний приклад можна зробити очевидний висновок: якщо циклом перебираються елементи списку, то змінювати кількість елементів цього списку в циклі треба обережно, бо видалення або додавання елементів може стати причиною неправильного розв'язку.
Цю задачу, звичайно, можна розв'язати без використання третього списку. Але треба враховувати, що при видаленні, наприклад, другого елемента, список змінюється і далі потрібно знову аналізувати другий елемент. Наприклад:
count = int(input())
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
x = 0
while count > x:
if first[x] in second:
first.remove(first[x])
count -= 1
else:
x += 1
print(len(first))
print(' '.join(map(str, first)))
Який шлях краще обрати для розв’язку? Якщо у програміста цейтнот і немає обмежень по пам’яті, то, можливо, варто скористатися простим і логічним варіантом з третім списком. А якщо ви прийшли на співбесіду щодо працевлаштування, то, мабуть… також. Як це не дивно. Але ж ми ж використовуємо менше пам’яті! Це правда, але давайте уважно перечитаємо умову: «Потрібно вивести ті елементи першого масиву…». Хто ж нам дозволяв змінювати цей масив? :)
В 2020 році обласна олімпіада Житомирської області проходила під прапором змін. Змінився університет проведення — аудиторії Житомирського Державного Університету змінили аудиторії університету «Житомирська Політехніка». Змінилась платформа проведення — цього року це був не e-olymp.com, розроблений в ЖДУ, змагання проводились на платформі Ejudge, яку дуже швидко розгорнули і настроїли. Змінилось і журі олімпіади.
Приємно, що не змінився гарний дух змагання. Ті самі лідери-програмісти так само показали шикарні результати. Топ-список найкращих вчителів з програмування залишився практично таким самим. Технічно і організаційно ні у мене ні у моїх учнів претензій не було, як все добре працювало всі попередні роки, так все добре працювало і цього року. В сюжеті «Суспільного телебачення» можна побачити учасників, аудиторії, організаторів:
Пропоную розглянути гарний, як на мене, розв’язок однієї з задач. Це найпростіша задача, організатори, мабуть, вирішили таким чином підняти дух всіх учасників. Задачу розв’язали майже всі учні, отже немає чого мені хвалитися, питання лише стильності розв’язку.
Задача «Змішана послідовність»
https://www.e-olymp.com/uk/problems/9610
Задано послідовність символів, розділених пробілами. Кожний символ послідовності представляє собою велику або маленьку літеру латинського алфавіту або цифру від 0 до 9.
Знайдіть суму цифр, які входять до цієї послідовності. Кількість символів, які входять до послідовності – не більше 10 000.
Вхідні дані.
Послідовність символів, розділених пробілами.
Вихідні дані.
Сума цифр, які входять до послідовності або значення 0, якщо у послідовності немає цифр.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
A 1 2 B C D A B C 1 9 B 3
Вихідні дані #1
16
Вхідні дані #2
A B C
Вихідні дані #2
0
В Python існує величезна купа зручних інструментів, знання яких значно спрощує життя програмісту. Звичайно, Python-програмісти, що працюють з текстом, знають, що для розв’язку можна не порівнювати кожний по циклу вирізаний символ на предмет відповідності його числу, а скористатися функцією isdigit(), що відповідає на запитання «Чи складається рядок з цифр».
Відповідно, використавши цю функцію, задача здається в один рядок:
print(sum([int(x) for x in input().split() if x.isdigit()]))
Хочу звернути увагу програмістів-початківців на величезну купу вже існуючих в Python функцій для роботи з текстом:
Таблиця: «Функції і методи рядків»
x = 'Микола'
y = 'Оленка'
Функція чи метод
|
Призначення
|
Приклад
|
Результат
|
result = x + y
|
Конкатенація (склеювання рядків)
|
result = x + y
|
'МиколаОленка'
|
result = x * 3
|
Повтор рядка
|
result = x * 2
|
'МиколаМикола'
|
result = x[i]
|
Звернення по індексу
|
result = x[0]
|
'М'
|
result = x[[start]:[end]:[step]]
|
Отримання зрізу
|
result = x[1:3]
|
'ик'
|
result = len(x)
|
Визначення довжини рядка
|
result = len(x)
|
6
|
x.lstrip([chars])
|
Видалення символів пропуску (або символів chars) на початку рядка
|
' Коля'.lstrip()
|
'Коля'
|
x.rstrip([chars])
|
Видалення символів пропуску (або символів chars) в кінці рядка
|
'Коля '.lstrip()
|
'Коля'
|
x.strip([chars])
|
Видалення символів пропуску (або символів chars) на початку і в кінці рядка
|
' Коля '.lstrip()
|
'Коля'
|
x.find(str, [start],[end])
|
Пошук підрядка в рядку. Повертає номер першого входження або -1
|
result = x.find('я')
|
-1
|
x.rfind(str, [start],[end])
|
Пошук підрядка в рядку. Повертає номер останнього входження або -1
|
result = x.find('л')
|
4
|
x.replace(шаблон, заміна)
|
Заміна шаблону
|
result = x.replace('икол', 'урк')
|
'Мурка'
|
x.isdigit()
|
Чи складається рядок з цифр
|
result = x.isdigit()
|
False
|
x.isalpha()
|
Чи складається рядок з букв
|
result = x.isalpha()
|
True
|
x.isalnum()
|
Чи складається рядок з букв або цифр
|
result = x.isalnum()
|
True
|
x.islower()
|
Чи складається рядок виключно з символів в нижньому регістрі
|
result = x.islower()
|
False
|
x.isupper()
|
Чи складається рядок виключно з символів в верхньому регістрі
|
result = x.isupper()
|
False
|
x.isspace()
|
Чи включає рядок символи, що не відображаються (пробіл, символи '\f' '\n' '\r' '\t '\v')
|
result = x.isspace()
|
False
|
x.istitle()
|
Чи починаються слова в рядку з великої літери (навіть якщо їх декілька)
|
result = x.istitle()
|
True
|
x.upper()
|
Перетворення рядка до верхнього регістру
|
result = x.upper()
|
'СТЕПАН'
|
x.lower()
|
Перетворення рядка до нижнього регістру
|
result = x.lower()
|
'степан'
|
x.startswith(шаблон)
|
Чи починається рядок з шаблону
|
result = x.startswith('Ст')
|
True
|
x.endswith(шаблон)
|
Чи закінчюється рядок шаблоном
|
result = x.endswith('ан')
|
True
|
z.join(список)
|
Збирання рядка зі списку з розділювачем z
|
result = '+'.join(x)
|
'С+т+е+п+а+н'
|
ord(символ)
|
Символ в його код Unicode
|
ord('Я')
|
1071
|
chr(число)
|
Код Unicode в символ
|
chr(1071)
|
'Я'
|
x.capitalize()
|
Переводить перший символ рядка в верхній регістр, а всі інші в нижній
|
result = 'вАсЯ'.capitalize()
|
'Вася'
|
x.center(width, [fill])
|
Повертає відцентрований рядок, по краях якого стоїть символ fill (пробіл за замовчуванням)
|
'Оленка'.center(10, '+')
|
'++Оленка++'
|
x.ljust(width, [fill])
|
Повертає рядок, довжиною не меншою width, в разі потреби заповнюючи останні символи символом fill (пробіл за замовчуванням)
|
'Оленка'.ljust(10, '+')
|
'Оленка++++'
|
x.rjust(width, [fill])
|
Повертає рядок, довжиною не меншою width, в разі потреби заповнюючи перші символи символом fill (пробіл за замовчуванням)
|
'Оленка'.rjust(10, '+')
|
'++++Оленка'
|
x.title()
|
Першу букву кожного слова переводить в верхній регістр, а всі інші в нижній
|
'доБрИй дЕнь'.title()
|
'Добрий День'
|
x.swapcase()
|
Переводить символи нижнього регістру в верхній, а верхнього - в нижній
|
x.swapcase()
|
'сТЕПАН'
|
І це ще не все :)
Скільки зручних інструментів є в Python. Якщо вам сподобалась саме моє табличне представлення функцій і методи рядків, то все це давно і вільно лежить і оновлюється на «Плетиві» в розділі «Довідники мови Python». Звичайно, більша частина матеріалів там для початківців, бо писав ці довідники для своїх учнів, для уроків. При цьому щось намагався включити і авторське, наприклад, казку «Два зоопарки», що пояснює роботу з даними у списку, придумав сам.
Хочу привітати всіх учасників обласних етапів олімпіади з програмування, – справжнього свята інтелекту. Успіхів вам в наступних змаганнях – учні і вчителі!
Шановні учні!
Даний довідник може стати вам у пригоді для розв'язку задач
Введення цілих чисел:
Якщо вам треба ввести ціле число від користувача в вашу програму, то використовуйте конструкцію:
x = int(input())
Якщо вам треба ввести два цілих числа, кожне з яких записане в окремому рядку, то це можна зробити так:
x = int(input())
y = int(input())
Якщо вам треба ввести в вашу програму кілька цілих чисел, що записані через пропуск, то це можна зробити так:
a, b, c = map(int, input().split())
Я підібрав для вас задачі таким чином, що в перших змаганнях вам для введення даних більше ніякі конструкції не потрібні.
Введення тексту:
Якщо вам треба ввести текст від користувача в вашу програму то використовуйте таку конструкцію:
x = input()
Якщо вам треба ввести текст від користувача в вашу програму, при цьому обрізати пропуски на початку тексту і в кінці, то використовуйте таку конструкцію:
x = input().strip()
Пам'ятайте, що з текстом не можна проводити математичні операції. З тексту ви можете вирізати один або кілька символів, але вирізана частина буде також текстом. Якщо ж вам треба виконати математичні дії з цими даними, то треба конвертувати текст в число. Якщо це стосується цілих чисел, то конструкція така:
y = int(x)
Задача для прикладу. Ваша програма повинна зчитати трицифрове натуральне число і вивести суму першої і останньої цифри.
Ось як може виглядати ваша програма:
x = input().strip()
a = int(x[0])
b = int(x[2])
print(a+b)
Виведення даних:
Для виведення даних використовується оператор print()
Приклад:
a = 5
b = 3
print(a-b)
Розгалуження:
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести -1, 0 або 1, якщо введене значення від’ємне, нульове і додатне, відповідно.
Приклад коду:
n = int(input())
if n < 0:
print(-1)
elif n == 0:
print(0)
else:
print(1)
Цикл FOR:
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести числа від одиниці до цього числа включно. Кожне число - в окремому рядку.
Приклад коду:
n = int(input())
for x in range(1, n + 1):
print(x)
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести числа від цього числа до нуля в порядку зменшення. Кожне число - в окремому рядку.
Приклад коду:
n = int(input())
for x in range(n, - 1, -1):
print(x)
Якщо це саме треба зробити так, щоб всі числа були в одному рядку, ось приклад:
n = int(input())
for x in range(n, - 1, -1):
print(x, end = ' ')
Розбираємо задачу з 8545 з e-olimp під назвою «Таблиця множення».
https://www.e-olymp.com/uk/problems/8545
Проста задача, в принципі. Знову таки, з дивно високим коефіцієнтом складності, 21%. Треба побудувати квадратну матрицю, як на обкладинках зошитів з математики. Вхідні дані - розмірність матриці, від 1 до 9 включно. Результат відповідним чином відформатувати:
n = 5
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
n = 7
1 2 3 4 5 6 7
2 4 6 8 10 12 14
3 6 9 12 15 18 21
4 8 12 16 20 24 28
5 10 15 20 25 30 35
6 12 18 24 30 36 42
7 14 21 28 35 42 49
Запропонував Саша цю задачу. З приміткою «неробіт». Проходить 70% тестів. E-olimp, на відміну від codeforces, тести не відкриває, шукаємо помилку аналітично.
Показав Саша код:
a = int(input())
if a == 1:
print( '1')
elif a == 2:
print(' 1 2\n 2 4')
elif a == 3:
print(' 1 2 3 \n 2 4 6 \n 3 6 9')
elif a == 4:
print(' 1 2 3 4 \n 2 4 6 8 \n 3 6 9 12 \n 4 8 12 16')
elif a == 5:
print(' 1 2 3 4 5 \n 2 4 6 8 10 \n 3 6 9 12 15 \n 4 8 12 16 20 \n 5 10 15 20 25')
elif a == 6:
print(' 1 2 3 4 5 6 \n 2 4 6 8 10 12 \n 3 6 9 12 15 18 \n 4 8 12 16 20 24 \n 5 10 15 20 25 30 \n 6 12 18 24 30 36')
elif a == 7:
print(' 1 2 3 4 5 6 7 \n 2 4 6 8 10 12 14 \n 3 6 9 12 15 18 21 \n 4 8 12 16 20 24 28 \n 5 10 15 20 25 30 35 \n 6 12 18 24 30 36 42 \n 7 14 21 28 35 42 49')
elif a == 8:
print(' 1 2 3 4 5 6 7 8 \n 2 4 6 8 10 12 14 16 \n 3 6 9 12 15 18 21 24 \n 4 8 12 16 20 24 28 32 \n 5 10 15 20 25 30 35 40 \n 6 12 18 24 30 36 42 48 \n 7 14 21 28 35 42 49 56 \n 8 16 24 32 40 48 56 64')
else:
print(' 1 2 3 4 5 6 7 8 9 \n 2 4 6 8 10 12 14 16 18 \n 3 6 9 12 15 18 21 24 27 \n 4 8 12 16 20 24 28 32 36 \n 5 10 15 20 25 30 35 40 45 \n 6 12 18 24 30 36 42 48 54 \n 7 14 21 28 35 42 49 56 63 \n 8 16 24 32 40 48 56 64 72 \n 9 18 27 36 45 54 63 72 81 ')
Звичайно, Саша дізнався про себе багато цікавого після оприлюднення такого щастя :)
Колегі-програмісти нагадали, що так робити не під час олімпіади – гріх. Навіть запропонували з таким підходом приєднатися до написання прекрасного AceLewis-калькулятора. До речі, хто не в курсі, що це таке, дуже раджу ознайомитися, скоріше за все ви, як це побачите, то не забудете ніколи.
Чудовий в своєму різноманітті інструментарію Python дозволяє чудово форматувати текст при виводі. Нам треба вирівняти текст вправо в межах двох символів? Не проблема. Як просто і елегантно, правда?
n = int(input())
for x in range(1, n+1):
for y in range(1, n+1):
print(str(x*y).rjust(2), end = ' ')
print()
Округлення, як відомо, це математична операція, яка полягає в заміні числа α наближеним числом α1 із меншою кількістю значущих цифр. Число α1 вибирають так, щоб похибка округлення була якомога меншою.
У різних галузях застосовують різні методи округлення.
На уроках математики в школі традиційно округлюють методом «Округлення до найближчого цілого» (англ. rounding) — це найбільш часто вживаний метод округлення, при якому число округлюється до цілого, модуль різниці з яким у цього числа мінімальний. У загальному випадку, коли число в десятковій системі округляють до N-ого знаку, правило може бути сформульовано таким чином:
якщо N+1 знак < 5, тоді N-ий знак зберігають, а N+1 та всі наступні обнуляють;
якщо N+1 знак ≥ 5, тоді N-ий знак збільшують на одиницю, а N+1 та всі наступні обнуляють;
Наприклад: 11,9 → 12; −0,9 → −1; −1,1 → −1; 2,5 → 3.
Давайте напишемо ще кілька прикладів на даний тип округлення:
Округлюємо до цілого:
1,5 → 2
2,5 → 3
3,5 → 4
4,5 → 5
5,5 → 6
6,5 → 7
Такий метод округлення використовує Python версії 2 і старі програмні компілятори, наприклад Turbo Pascal.
Але це не єдиний метод округлення. Відповідно до стандарту IEEE 754 (і 1985, і 2008 року), основним для комп'ютерних обчислень є інший метод. Він зветься округленням до найближчого парного, банківським, статистичним, данським, Гаусовим округленням. Вважається, що банківське округлення дозволяє зменшити похибки при роботі з великими масивами даних. Подробиці можна дізнатися, завітавши на кілька років на правильну спеціальність гарного університету. Даний метод на сьогодні популярний: наприклад, .NET Math.Round так робить по замовчуванню, цей метод використовує для функції стандартного округлення round() PascalABC.Net і Python 3.
Синтаксично округлення в Python 3 здійснюється функцією round(number, ndigits), де number – число що округлюється, а ndigits - кількість знаків після коми. Наприклад:
>>>round(2.137, 2)
2.14
>>>round(1.5)
2
Ось результат такого округлення:
1,5 → 2
2,5 → 2
3,5 → 4
4,5 → 4
5,5 → 6
6,5 → 6
Саме так округлює функція round() в Python 3.
Але є і великі підводні камені, пов’язані з представленням в пам’яті комп’ютера дійсних чисел. Ось приклад:
>>>round(2.15, 1)
З точки зору округлення до найближчого парного, результат повинен бути 2.2
Python 3 вважає інакше:
>>>round(2.15, 1)
2.1
Це пов’язано з тим, як представлено число 2.15 в машинному поданні, давайте переглянемо, як воно виглядає для, наприклад, 30 знаків після коми:
>>> '%0.30f' % 2.15
'2.149999999999999911182158029987'
Тепер все зрозуміло, в такому випадку логіка округлення Python 3 цілком зрозуміла.
Але сюрпризи при округленні дійсних чисел можуть з’являтися цілком несподівано, наприклад:
>>> round(2.15, 1)
2.1
>>> round(2.1500000000000001, 1)
2.1
>>> round(2.150000000000001, 1)
2.2
Як бачимо, камінців вистачає. Але round() – не єдина функція округлення.
В Python 3, в модулі math реалізовано ще декілька методів округлення:
math.ceil(x) – округлення до найближчого більшого числа
math.floor(x) - округлення до найближчого меншого числа
math.trunc(x) - усікає значення X до цілого.
Ось приклади, що ілюструють роботу даних функцій:
>>> import math
>>> math.ceil(1.4)
2
>>> math.floor(1.4)
1
>>> math.trunc(1.4)
1
>>> math.trunc(1.9)
1
>>> math.floor(-1.9)
-2
>>> math.trunc(-1.9)
-1
Усікти значення до цілого можна і без використання модуля math:
>>> int(1.1)
1
>>> int(1.9)
1
>>> int(-1.1)
-1
>>> int(-1.9)
-1
А для естетів, перфекціоністів, тих, хто хоче забезпечити абсолютну точність, контролювати стратегію округлення і системно керувати золотою рибкою, Python 3 має модуль decimal
Цей неймовірний інструмент має аж вісім варіантів округлення:
ROUND_CEILING - Округлення в сторону позитивної нескінченності. Наприклад, число 2.52 буде округлено до 2.6, а число -2.58 до -2.5
ROUND_DOWN - Округлення в сторону нуля. Наприклад, число 2.58 буде округлено до 2.5, а число -2.58 - до -2.5
ROUND_FLOOR - Округлення в бік негативної нескінченності. Наприклад, число 2.52 буде округлено до 2.5, а число -2.58 до -2.6
ROUND_HALF_DOWN - Округлення в сторону від нуля, якщо частина, що округлюється, більше половини останнього значущого розряду, в іншому випадку округлення буде виконано в сторону нуля. Наприклад, число 2.58 буде округлено до 2.6, число 2.55 буде округлено до 2.5, а число -2.58 до -2.6
ROUND_HALF_EVEN - Те ж, що і ROUND_HALF_DOWN, тільки якщо частина, що округлюється дорівнює точно половині останнього значущого розряду, результат округлюється вниз, якщо попередня цифра парна, і вгору - якщо попередня цифра непарна. Наприклад, число 2.65 буде округлено до 2.6, число 2.55 також буде округлено до 2.6
ROUND_HALF_UP - Те ж, що і ROUND_HALF_DOWN, тільки якщо частина, що округлюється, дорівнює точно половині останнього значущого розряду, результат округлюється в бік від нуля. Наприклад, число 2.55 буде округлено до 2.6, а число -2.55 до -2.6
ROUND_UP - Округлення в бік від нуля. Наприклад, число 2.52 буде округлено до 2.6, а число -2.52 - до -2.6
ROUND_05UP - Округлення в бік від нуля, якщо останній значущий розряд містить цифру 0 або 5, в іншому випадку округлення виконується в сторону нуля. Наприклад, число 2.54 буде округлено до 2.6, число 2.64 також буде округлено до 2.6
Звичайно, всі ці варіанти з’явилися в decimal не просто так - вони мають цілком прикладний сенс. З таким інструментарієм можна реалізувати багато чого, в тому числі і популярне шкільне округлення методом «Округлення до найближчого цілого»:
import decimal as decimal
print(decimal.Decimal('2.5').quantize(decimal.Decimal('1'), rounding=decimal.ROUND_HALF_UP))
print(decimal.Decimal('3.5').quantize(decimal.Decimal('1'), rounding=decimal.ROUND_HALF_UP))
out:
3
4
Ну і можна, звичайно, написати і власну функцію округлення, якщо на то є причини. В будь-якому варіанті тема округлення дійсних чисел в Python 3 має чимало непростих аспектів. І програмістам необхідно уважно враховувати дані особливості як на етапі проектування інформаційних систем, так і при розробці стратегій їх тестування.
Розберемо задачу 8358 з e-olymp. Джерело задачі — 2018 Azerbaijan School Competition, II Stage, April 8, Problem K. На e-olimp на дату написання статті задача опублікована лише російською, тому перекладаю сам:
Середнє значення – 1
(https://www.e-olymp.com/uk/problems/8358)
Проект "Середня вага школяра школи" вирішили виконати Мамед з Самедом. Що вони будуть робити з цим числом, вони не розкривають. Вони попросили зважитися всіх учнів школи і занесли результати в таблицю. Допоможіть їм підрахувати середню вагу учнів. Але вони просять, щоб учнів з найбільшою і з найменшим вагою не враховувати. Єдине їх упущення, вони не підрахували загальну кількість учнів, але це, звичайно, не завадить вам підрахувати то, що вони просять.
Вхідні дані
У кількох рядках задані ваги учнів в кілограмах, розділених пропусками (одним або кількома) або символом кінця рядка. Читати ваги учнів до кінця введення.
Вихідні дані
Середня вага учнів школи без урахування учнів з найбільшою і найменшою вагою. Відповідь виводити з точністю до кілограм.
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MB
Вхідні дані # 1
40 23 27
59 68 23 84 27
53 46
Вихідні дані # 1
46
В першу чергу треба врахувати, що через невідому кількість рядків вхідних даних, єдиним способом отримати вхідні дані – це використати введення з файлу. Будемо читати рядки з файлу до тих пір, поки не закінчиться файл. Пропоную кожний рядок вхідних даних записувати в тимчасовий список, а далі елементи цього тимчасового списку додавати до основного списку. Код цієї частини програми:
inputfile = open('input.txt', 'r')
outputfile = open('output.txt', 'w')
weights = []
for line in inputfile:
lst = [int(x) for x in line.split()]
weights.extend(lst)
Далі ми можемо використати list comprehension з умовою, наприклад, так ефектно:
weights = [x for x in weights if x != max(weights) and x != min(weights)]
В результаті в новому списку weights будуть лише потрібні дані, всі максимальні і мінімальні ваги в новий список weights не попадуть. Але так робити не треба, тому що це неоптимально по часу і непрофесійно на співбесіді на роботу. Річ в тому, що при кожній ітерації циклу, проходить порівняння значення елементу списку з максимальним і мінімальним елементом списку. І кожного разу python буде обраховувати максимальне і мінімальне значення. Так як список у нас протягом обробки циклом не змінюється, то буде правильним визничити максимальне і мінімальне значення списку до циклічного перебору:
max_weights = max(weights)
min_weights = min(weights)
weights = [x for x in weights if x != max_weights and x != min_weights]
Зверніть увагу на інформативність змінних. В олімпіадному програмуванні часто поспішають і так змінні не називають, а дарма. Рекомендую назви змінним давати розумно, у професійному програмуванню так і роблять.
Ну і на останок, в умові задачі є округлення, це в Python дуже дискутивна тема. Як мінімум, нагадаю, що Python версії 2 виконує так зване «арифметичне округлення», як Pascal, C++ і як на уроках математики, а Python версії 3 при використанні функції round() виконує так зване «банківське округлення» або «округлення до парного». В даній задачі тести обрані таким чином, що при здачі в Python версії 3 ніяких проблем немає, про округлення в Python 3 на «Плетиві» буде окрема стаття, а тим, хто про дива округлення чує вперше, банківське округлення в Python 3 (і не лише там) виглядає так:
>>> round(1.5)
2
>>> round(2.5)
2
>>> round(3.5)
4
>>> round(4.5)
4
>>> round(5.5)
6
>>> round(6.5)
6
>>> round(7.5)
8
>>> round(8.5)
8
І не забувайте прибиратися після себе. Принцип простий. Ви відкрили якийсь файли? Ви відкрили, вам і закривати.
Документація третього Python вимагає так:
If you’re not using the with keyword, then you should call f.close() to close the file and immediately free up any system resources used by it. If you don’t explicitly close a file, Python’s garbage collector will eventually destroy the object and close the open file for you, but the file may stay open for a while. Another risk is that different Python implementations will do this clean-up at different times.
Успіхів!
На дошці виписані числа від 1 до 2150.
Кожну хвилину кожне число піддається наступній операції: якщо число націло ділиться на 100, то його ділять на 100, якщо ж не ділиться, то від нього віднімають 1. Знайдіть найбільше серед чисел на дошці через 87 хвилин.
Спочатку пробуйте самостійно, а потім можете перевірити свою відповідь, переглянути розумне математичне пояснення і код перебору на python
Розбираємо задачу.
https://www.e-olymp.com/uk/problems/7670
Сьогодні Степан чекає в гості свого друга Василя. Щоб підготуватися до зустрічі, Степану необхідно відвідати два магазини, розташованих поряд з його будинком.

Від будинку до першого магазину веде доріжка довжини d1
метрів, а до другого магазину веде доріжка довжини d2
метри. Також існує доріжка, яка безпосередньо сполучає два магазини один з одним, довжиною d3
метри.
Допоможіть Степану обчислити мінімальну відстань, яку йому буде потрібно пройти, щоб відвідати обидва магазини і повернутися додому.
Степан завжди стартує зі свого будинку. Він повинен відвідати обидва магазини, переміщаючись тільки за наявними трьома доріжками, і повернутися назад додому. При цьому його абсолютно не бентежить, якщо йому доведеться відвідати один і той же магазин або пройти по одній і тій же доріжці більше одного разу. Єдине його завдання - мінімізувати сумарну пройдену відстань.
Вхідні дані
У першому рядку вхідних даних знаходяться 3 цілих числа d1
, d2
, d3
(1 ≤ d1, d2, d3 ≤ 108)
- довжини доріжок.
d1
- довжина доріжки, що з'єднує будинок Степана і перший магазин;
d2
- довжина доріжки, що з'єднує будинок Степана і другий магазин;
d3
- довжина доріжки, що з'єднує два магазина.
Вихідні дані
Виведіть мінімальну кількість метрів, яку доведеться пройти Степану, щоб відвідати обидва магазини і повернутися додому.
Ліміт часу 0.1 секунда
Ліміт використання пам'яті 64 MiB
Джерело ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року
Прекрасна задача на логіку. Давайте спочатку розберем, як взагалі може ходити Степан. Розпишемо всі його можливі маршрути:
Отже - перший машрут. Це коли Степан йде по колу. Тоді відстань буде d1+d3+d2.
Якщо він іде по колу, але в зворотньому напрямку, то його шлях буде d2+d3+d1.
Так як при обох цих вариантах відстань буде однаковою, то будемо вважати ці маршрути як один.
Записуємо, перший маршрут ми визначили.
m1 = d1+d3+d2
Давайте подумаємо, як ще може ходити Степан.
Ще один варіант: він може піти в перший магазин, потім повернутися додому, потім піти в другий магазин і знову повернутися додому.
Записуємо цей маршрут:
m2 = d1+d1+d2+d2
Можна математично гарно це записати:
m2 = (d1+d2)*2
Наступний варіант:
Степан іде в перший магазин, потім в другий магазин. І повертається назад тією ж дорогою.
Записуємо цей маршрут:
m3 = d1+d3+d3+d1
Можна математично гарно це записати:
m3 = (d1+d3)*2
І останній варіант:
Степан іде в другий магазин, потім в перший магазин. І повертається назад тією ж дорогою.
Записуємо цей маршрут:
m4 = d2+d3+d3+d2
Можна математично гарно це записати:
m4 = (d2+d3)*2
В результаті аналізу ми сформували чотири маршрути.
Нам треба визначити найменший.
Відповідна функція python вміє шукати найменше серед і елементів списку і просто змінних:
result = min(m1,m2,m3,m4)
Що нам допомогло розв'язати задачу? Звичайний аналіз і малюнок.
Успіхів!
При роботі з текстовими даними в python важливо пам’ятати про іммутабельність даного типу даних. Тобто якщо зі списками ми можемо змінити елемент списку прямо у списку, то при роботі з текстовими даними, нам буде потрібно фактично створення нової змінної. Для прикладу замінимо третій елемент в списку:
>>> a = [11, 22, 33, 44, 55]
>>> a[3] = 99
>>>a
[11, 22, 33, 99, 55]
Все логічно. Для тих, хто здивувався, нагадаємо, що індекс відраховується від нуля.
Тепер поміняємо в слові третю букву.
>>>a = 'бабайка'
>>>print(a[3])
a
>>>a[3] = 'у'
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
a[3] = 'у'
TypeError: 'str' object does not support item assignment
Тобто ми отримали помилку python. Задачу заміни букви можна легко розв'язати за допомогою зрізів і конкатенації:
>>>a = 'бабайка'
>>>a = a[:3] + 'у' + a[4:]
>>>a
'бабуйка'
Якщо нам треба не третій символ в рядковій величині, а символи замінити на інши символи, то для цього у Python є готовий інструментарій і це простіше.
А тепер – дискотека. Тобто задача.
Перше та останнє входження (4726)
https://www.e-olymp.com/uk/problems/4726
Задано рядок літер. Якщо у ньому літера f зустрічається лише один раз, виведіть її індекс (нумерація індексів з 0).
Якщо вона зустрічається два або більше разів, виведіть індекс її першої та останньої появи.
Якщо літера f у заданому рядку не зустрічається, нічого не виводьте.
Вхідні дані
Один рядок з не більш ніж 255 літер.
Вихідні дані
Виведіть відповідь в залежності від того скільки разів у вхідному рядку зустрічається літера f.
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
comfort
Вихідні дані #1
3
Вхідні дані #2
office
Вихідні дані #2
1 2
Дозволю собі пояснити більшу частину програми, тому що майже в кожному рядку можуть зустрітися цікаві речі.
s = input()
first = s.find('f')
# функція s.find() повертає індекс позиції, де зустрічається символ 'f',
# пошук відбувається від початку рядкової змінної.
# Якщо символ не знайдено, функція повертає -1
if first != -1:
print (first, end = '')
s = s.replace('f','z',1)
# Функція s.replace(old, new, count) замінить count символів old на new, якщо не вказати count, то замінить всі.
Для закінчення написання програми вам, думаю, згодиться функція s.rfind() що повертає індекс позиції, де зустрічається певний символ, але пошук відбувається з кінця рядкової змінної. Якщо символ не знайдено, функція повертає -1.
А є ще більш гарний розв'язок - використовувати find і rfind для знаходження крайнього лівого і крайнього правого індексу, потім порівнювати отримане. Якщо числа рівні між собою і не рівні -1 - виводити одне. Якщо не рівні і жодне з них не -1 - виводити обидва.
Успіхів!
Задача 520 — Сума всіх
e-olymp.com/uk/problems/520
Обчисліть суму всіх заданих чисел.
Вхідні дані
Містить n (1 ≤ n ≤ 105) цілих чисел. Всі числа не перевищують 109 за абсолютною величиною.
Вихідні дані
Виведіть суму всіх заданих чисел.
Вхідні дані #1
2 3
1 1
Вихідні дані #1
7
Дана задача – яскравий приклад задачі, для розв’язання якої необхідно використати роботу з файлами. В даній задачі невідомо наперед, в скількох рядках будуть вхідні дані. Коли ж ми отримаємо рядок з вхідного файлу, то далі просто – ми занесемо дані в список, потім знайдемо суму елементів списку за допомогою стандартної функції. Через традиції «Плетива» не публікувати повні лістинги, приведений код вичитує рядки з вхідного файлу і записую їх у вихідний. Модифікувати даний код для розв’язку задачі 502 – сподіваюсь, не проблема.
inputfile = open('input.txt', 'r')
outputfile = open('output.txt', 'w')
for line in inputfile:
outputfile.write(line + '\n')
inputfile.close()
outputfile.close()
ps. Зверніть увагу, на два аспекти:
1. При виводі в файл — outputfile.write(line + '\n') — ми в кінці кожного рядка ставимо '\n' Це символ переведення рядка, якщо його не ставити, то всі рядки будуть "клеїтися" один до одного.
2. Якщо вам треба вивести у вихідний файл число, то необхідно конвертувати його в рядкову величину.
Тобто outputfile.write(str(2017) + line + '\n')
Задача 2097 — Трьохзначі числа
https://www.e-olymp.com/uk/problems/2097
На заданому проміжку [A, B] виведіть у зростаючому порядку всі трьохзначні числа, у яких усі цифри різні.
Вхідні дані
У єдиному рядку два натуральних числа з вказаного проміжку. 100 ≤ A ≤ B ≤ 999.
Вихідні дані
Кожне число виводьте на новому рядку.
Вхідні дані #1
100 105
Вихідні дані #1
102
103
104
105
Джерело: Китеня 2011 м. Ковров
Розв'язання.
Перебираємо всі числа проміжку. В тестовому прикладі це буде:
100
101
102
103
104
105
Але деякі числа нам не підходять, бо мають повтори цифр. Наприклад в числі 101 дві одиниці, тобто не всі цифри різні.
Давайте переберемо всі числа проміжку, кожне з них відконвертуємо в текст, використовуючи стандартну функцію str()
Далі скористаємося функцією створення множини set()
Дана функція на основі відконвертованого в текст числа створить множину, в якій будуть елементи без повторів. Тобто дана функція створить нам множину, в якій не буде дублікатів. До речі, не гарантується, що буде збережено порядок елементів, але для нашої задачі це неважливо.
Ось приклад, що ілюструє роботу функції set()
>>> a = [1,3,5,4,3,3]
>>> a
[1, 3, 5, 4, 3, 3]
>>> b = set(a)
>>> b
{1, 3, 4, 5}
Отже, якщо в тризначному числі всі цифри різні, то довжина множини, що утворена функцією set() буде дорівнювати трьом. Ось як просто це на python:
if len(set(str(i))) == 3
Ось так просто. Зверніть увагу, що писати перебір чисел таким чином:
for i in range (a,b)
невірно, тому що останній елемент (b) в такому разі не буде перебиратися циклом.
Голосні
https://www.e-olymp.com/uk/problems/494
До голосних літер в латинському алфавіті відносяться літери A, E, I, O, U і Y. Інші літери вважаються приголосними. Напишіть програму, яка підраховує кількість голосних літер в тексті.
Вхідні дані
У вхідному файлі міститься один рядок тексту, який складається лише із заглавних латинських літер та проміжків. Довжина рядка не перевищує 100 символів.
Вихідні дані
У вихідний файл вивести одне ціле число – кількість голосних у вхідному тексті.
Вхідні дані
COBRA
Вихідні дані
2
Для розв’язання даної задачі можна скористатися функцією in
Загальна ідея така: Пробіл в тексті також вважаємо буквою (власне, так воно і є). Перебираємо по черзі всі букви тексту. Якщо вибрана буква є серед голосних, то загинаємо палець. Після перевірки всіх букв тексту виводимо кількість загнутих пальців.
В даному випадку доцільно текст і голосні ввести в текстові змінні:
golosni = 'AEIOUY'
Перебір букв тексту проводимо за допомогою циклу, функція in повертає True у випадку, коли буква тексту знайдена серед голосних:
for x in txt:
if x in golosni:
kilkist += 1
Зверніть увагу на конструкцію kilkist+=1 Це і є загинання пальців. Тобто після виконання даної операції значення змінної kilkist збільшується на одиницю. Але якщо до виконання цієї операції змінна kilkist не використовувалась, то ми отримаємо помилку. Тому перед перебиранням букв тексту давайте зробимо так:
kilkist = 0
Так ми і заявимо, що у нас є така змінна (ініціалізуємо її) і встановимо цій змінній початкове значення.
ps. А чи багато, на вашу думку, треба змінити в програмі, щоб вона рахувала не кількість голосних, а кількість пробілів? І чи можна в такому випадку обійтися без функції in ? А яка, на вашу думку, програма буде працювати швидше на одному і тому тексті - та, що рахує кількість голосних чи та, що рахує кількість пробілів?
Середнє арифметичне додатних
https://www.e-olymp.com/uk/problems/910
Задано послідовність дійсних чисел. Визначити середнє арифметичне додатних чисел.
Вхідні дані
У першому рядку задано кількість дійсних чисел n (0 < n ≤ 100). У наступному рядку задано n чисел, значення яких не перевищують за модулем 100.
Вихідні дані
Вивести середнє арифметичне додатних чисел з 2 десятковими знаками. У випадку відсутності додатних чисел вивести повідомлення "Not Found" (без лапок).
Вхідні дані #1
3
5.2 -2 4
Вихідні дані #1
4.60
Використання list comprehension для розв’язання даної задачі допоможе нам ввести дані з одночасним їх фільтруванням. Розбираючи рядок введення, ми можемо вибрати лише додатні елементи. Наприклад, при введенні даних таким чином:
lst = [float(x) for x in input().split()]
ми в списку lst отримаємо всі вхідні дані. А використання умови в list comprehension дозволить нам додати в список лише додатні елементи вхідних даних:
lst = [float(x) for x in input().split() if float(x)>0]
А отримав список додатних чисел ми можемо проаналізувати довжину цього списку за допомогою функції len(). Якщо довжина нульова, це означає що у вхідних даних немає жодного додатного числа. Якщо так сталося, виводимо відповідне повідомлення, інакше виводимо середнє арифметичне. Формати виведення реальних чисел можна знайти у нашому довіднику «input_print», а для обрахування середнього арифметичного, хто забув, треба суму елементів поділити на їх кількість, в python це просто sum(lst)/len(lst).
ps. Якщо ваші батьки збираються на батьківські збори і у вас є список всіх ваших оцінок, то що буде з даним списком після такого:
otsynky = [x for x in otsynky if 10 <= x <= 12]
Ну і додаткове питання – що буде, коли вас піймають? :)
https://www.e-olymp.com/uk/problems/2400
Трикутники
Михайлик любив малювати трикутники, але він це робив у незвичний спосіб. Спочатку малював довільний трикутник, потім кожну сторону ділив на n рівних частин і проводив через точки поділу прямі, паралельні сторонам трикутника. У результаті виходить декілька рівних між собою трикутників. Допоможіть Михайлику знайти найбільшу кількість однакових трикутників у його фінальному рисунку.
Вхідні дані
Ціле число n (0 < n < 2 * 109).
Вихідні дані
Вивести найбільшу кількість рівних між собою трикутників.
Вхідні дані #1
2
Вихідні дані #1
4
Дану задачу пропоную розв’язувати з папером і олівцем. Це той випадок коли ми можемо намалювати декілька варіантів забави Михайлика. Тобто спочатку намалюємо довільний трикутник і поділимо його сторони на 2 рівні частини, тобто n=2.

Потім намалюємо такий трикутник при n=3 і n=4:

Підрахував кількість отриманих маленьких однакових трикутників ми запишемо відповідність вхідних і вихідних даних. При n=2 відповідь 4, давайте запишемо так:
Вхідні дані |
Вихідні дані |
2 |
4 |
3 |
9 |
4 |
16 |
Подивіться уважно відповідність. Якщо бачите логіку – здавайте задачу. Якщо не бачите, то беріть цю таблицю, топайте до вчителькі математики і скажіть їй: «Я більше не буду прогулювати матема-а-а-тику. Яка тут відповідність?». Якщо вчителька кине в вас підручником математики за п’ятий клас, ухиляйтесь, але не дивуйтесь.