Имеется ряд из N лампочек, которые пронумерованы от 1 до N. Изначально ни одна из лампочек не горит. Далее происходит K последовательных линейных инверсий этого ряда ламп. Под линейной инверсией понимается инверсия каждой P-й лампочки в ряде. Например, если P=3, то произойдет инверсия 3й, 6й, 9й и т.д. лампочек.
Требуется определить: сколько горящих лампочек останется после реализации всех заданных линейных инверсий?
Входные данные
В первой строке входного файла INPUT.TXT заданы числа N и K – число лампочек и число линейных инверсий. Вторая строка состоит из K целых чисел Pi, задающих период данных инверсий. (1 ≤ N ≤ 1000000000, 1 ≤ K ≤ 100, 1 ≤ Pi ≤ 50)
Выходные данные
В выходной файл OUTPUT.TXT следует вывести ответ на задачу.
Примеры
|
№ |
INPUT.TXT |
OUTPUT.TXT |
|
1 |
20 3 |
8 |
|
2 |
172 10 |
99 |
Решение
f = open("input.txt","r") # открываем файл для чтения
s = f.readline() # считываем первую строку данных
l,i=map(int,s.split()) # присваиваем значения переменным l - количество ламп, i - количество инверсий
p=[int(x) for x in f.readline().split()] # считываем вторую строку в список p периоды инверсий
f.close() # закрываем файл
b=[] # определяем спилок состояния ламп
b=[0]*l # все лампы выключены (равны нулю)
for j in range(i): # цикл для перебора периодов инверсий
g=p[j]
e=g-1 # индекс первой лампочки для инверсии
while e<=l-1: # цикл для проведения всех инверсий
if b[e]==0: # проверка состояния лампочки
b[e]=1
else:
b[e]=0
e+=g
otv=b.count(1) # подсчет количества включенных
f1=open("output.txt","w") # открытие файла для вывода ответа
f1.write(str(otv)) # вывод
f1.close() # закрытие файла
Ещё одно решение
f = open("input.txt","r")
s = f.readline()
n,i=map(int,s.split())
p=[int(x) for x in f.readline().split()]
f.close()
b=[]
for t in range(i):
a=p[t]
while a<=n:
d=b.count(a)
if d==0:
b.append(a)
else:
ind=b.index(a)
b.pop(ind)
a+=p[t]
otv=len(b)
f1=open("output.txt","w")
f1.write(str(otv))
f1.close()
Комментариев нет:
Отправить комментарий