Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы.
В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:
— все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию;
— если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
— если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
— если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел, обозначающих соответственно срок хранения продукта с момента
изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Запишите в ответе два натуральных числа: сначала номер последнего продукта, для которого будет определено его место в рейтинге, затем — количество продуктов, которые займут в рейтинге более низкие места.
Ответ:
Приведём решение на языке Python.
f = open('DEMO_26.txt')
n = int(f.readline())
begin, end = [],[]
for i in range(n):
x = f.readline().split()
xran, godnost = int(x[0]), int(x[1])
if xran < godnost:
begin.append([xran,i])
else:
end.append([godnost,i])
print(max(end)[1] + 1, len(end) - 1)
# +1, тк в python нумерация с 0.
# -1, так как надо убрать последний продукт, для которого определено его место в рейтинге
Ответ: 564 444.
Приведём решение Юрия Красильникова на языке Python.
src=[list(map(int,s.split())) for s in open('DEMO_26.txt')][1:]
sroki=[(src[i][j],j,i+1) for i in range(len(src)) for j in range(2)]
sroki.sort(key=lambda x: x[0])
rat1,rat2=[],[]
already=set()
for x in sroki:
if x[2] not in already:
already.add(x[2])
last=x[2]
(rat1 if x[1]==0 else rat2).append(x[2])
rating=rat1+rat2[::-1]
print(last,len(rating)-rating.index(last)-1)
Приведём решение Юрия Красильникова на языке Python.
f = open('DEMO_26.txt')
num,globm,k=0,0,0 # номер товара, глобальный максимум времени, количество товаров с критерием «срок годности»
f.readline() # пропускаем число строк
for s in f:
num+=1
h,g=map(int,s.split()) # срок хранения и срок годности
m=min(h,g)
in2=h > g # товар попадает во вторую группу (срок годности)
k+=in2 # количество товаров во второй группе
if m > globm: # новый максимум времени
globm=m
last=in2 # куда попадает товар с максимальным временем
ans=num # номер этого товара
print(ans,k-last)
#Последняя строчка требует пояснений. Если товар с максимальным временем в первой группе, то за ним - вся вторая группа (k товаров).
#Если же этот товар - во второй группе, то он - первый в этой группе, и за ним следует k-1 товар.
#В программе неоднократно используется тот факт, что когда логические переменные используются в арифметических выражениях,
#то False считается нулем, а True - единицей.
Приведём решение Александра Козлова на языке Python.
with open('DEMO_26.txt') as f:
n = int(f.readline())
max_min, last_num, k = 0, 0, 0 # max min(h,g), номер последнего, число в группе "godnost"
for i in range(1, n + 1):
h, g = map(int, f.readline().split())
curr_min = min(h, g)
in_godnost_group = (h > g)
k += in_godnost_group
if curr_min > max_min:
max_min = curr_min
last_num = i
is_last_in_godnost = in_godnost_group
print(last_num, k - is_last_in_godnost)