Буває так, що задача нескладна, але умова не відразу є зрозумілою. І тоді звичайний графічний аналіз дуже допомогає розв’язанню. Пропоную розібрати задачу «Гра з перемикачами»
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)))
Який шлях краще обрати для розв’язку? Якщо у програміста цейтнот і немає обмежень по пам’яті, то, можливо, варто скористатися простим і логічним варіантом з третім списком. А якщо ви прийшли на співбесіду щодо працевлаштування, то, мабуть… також. Як це не дивно. Але ж ми ж використовуємо менше пам’яті! Це правда, але давайте уважно перечитаємо умову: «Потрібно вивести ті елементи першого масиву…». Хто ж нам дозволяв змінювати цей масив? :)
