Буває так, що задача нескладна, але умова не відразу є зрозумілою. І тоді звичайний графічний аналіз дуже допомогає розв’язанню. Пропоную розібрати задачу «Гра з перемикачами»
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 = float(input())
Якщо вам треба ввести в вашу програму кілька дійсних чисел, що записані через пропуск, то це можна зробити так:
a, b, c = map(float, input().split())
Введення тексту:
Якщо вам треба ввести текст від користувача в вашу програму то використовуйте таку конструкцію:
x = input()
Якщо вам треба ввести текст від користувача в вашу програму, при цьому обрізати пропуски на початку тексту і в кінці, то використовуйте таку конструкцію:
x = input().strip()
Пам'ятайте, що з текстом не можна проводити математичні операції. З тексту ви можете вирізати один або кілька символів, і вирізана частина буде також текстом. Якщо ж вам треба виконати математичні дії з цими даними, то треба конвертувати текст в число. Якщо це стосується цілих чисел, то конструкція така:
y = int(x)
Приклад обчислення квадратного кореня:
import math
x = math.sqrt(4)
print(x)
Виведення даних:
Для виведення даних використовується оператор print()
Приклад виведення тексту:
print('Страшно хочу в школу!')
Приклад виведення числа:
a = 5
b = 3
print(a-b)
Для виведення дійсного числа з певною кількістю знаків після коми можна скористатися f-рядками.
Приклад: Треба вивести дійсне число з трьома знаками після коми:
x = 12.34567
print(f"{x:.3f}")
Розгалуження:
Задача для прикладу:
Програма повинна прочитати від користувача ціле число та вивести -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()