Дано число 
, затем 
натуральных чисел. Найдите количество пар элементов, где оба элемента будут являться различными числами, при этом хотя бы одно число является полным квадратом.
Входные данные
В первой строке подается натуральное число 
. В каждой строке после записано одно натуральное число, не превышающее 
.
Переборное решение:
f = open("11_A.txt")
n = int(f.readline())
a = []
for i in range(n):
a.append(int(f.readline()))
cnt = 0
for i in range(n):
for j in range(i + 1, n):
if a[i] != a[j] and (a[i] ** 0.5 == int(a[i] ** 0.5) or a[j] ** 0.5 == int(a[j] ** 0.5)):
cnt += 1
print(cnt)
Эффективное решение:
f = open(’11_B.txt’)
n = int(f.readline())
# Список количеств чисел, где индекс равен корню из числа
# Например, под индексом 7 хранится количество чисел 49
nums = [0] * 101
count = 0 # Общее количество квадратов
ans = 0
for i in range(n):
x = int(f.readline())
# Проверяем, является ли текущее число полным квадратом
if x ** 0.5 == int(x ** 0.5):
# Так как числа должны быть разными, x составляет пары со всеми
# встреченными до этого числами, исключая самого себя
ans += i - nums[int(x ** 0.5)]
# Увеличиваем количество встреченных чисел x
nums[int(x ** 0.5)] += 1
# Увеличиваем общее количество квадратов
count += 1
else:
# Если x не полный квадрат, он составляет пары со всеми квадратами
ans += count
print(ans)