Буває так, що задача нескладна, але умова не відразу є зрозумілою. І тоді звичайний графічний аналіз дуже допомогає розв’язанню. Пропоную розібрати задачу «Гра з перемикачами»
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)
У даному випадку графічний аналіз значно допоміг нам знайти логіку і розв'язок.