Задача 6397. Источник: Поляков. Задание КИМ 26
(М. Шагитов) В течение дня в магазине электроники каждые t минут, начиная с момента t, предлагается один товар со скидкой. В течение дня магазин посещает N клиентов, желающих приобрести товар со скидкой (по скидочной карте). Известны время прихода и ухода каждого клиента, а также число товаров, уже приобретенных ранее с использованием скидочной карты. Клиент может купить товар со скидкой, если он присутствует в магазине в момент начала продажи товара и он купил ранее по скидочной карте менее, чем M товаров. В случае, когда несколько клиентов могут купить товар, выбирается тот, кто до этого купил по скидочной карте меньше товаров. При равенстве количества товаров, преимущество получает тот, кто уходит позже. После покупки число купленных товаров на скидочной карте клиента увеличивается на один. На последней минуте, когда покупатель уходит из магазина, он также может купить скидочный товар.
Определите, сколько минут провёл в магазине покупатель, купивший наибольшее количество товаров со скидкой, и сколько товаров он приобрел.
Входные данные представлены в файле 26-118.txt следующим образом. Первая строка содержит три натуральных числа: t (1 ≤ t ≤ 1440) - интервал между продажами товаров, N (1 ≤ N ≤ 1000) – количество покупателей, и M (1 ≤ M ≤ 109) – ограничение для скидки. В следующих N строках указаны три значения: минута прихода покупателя в магазин, минута ухода покупателя из магазина (натуральные числа, не превышающие 1440) и количество товаров, купленных ранее по скидочной карте (натуральное число, не превышающее 109).
В ответе укажите два целых числа: количество минут, которое провел в магазине покупатель, купивший наибольшее количество товаров со скидкой, и количество товаров, которые он приобрел.
Пример входного файла:
10 5 4
5 50 3
1 30 2
10 56 1
4 40 3
20 40 2
При таких исходных данных товары для пришедших покупателей продавались в единственном экземпляре в минуты: 10, 20, 30, 40, 50. В итоге покупатель {10, 56, 1} купил наибольшее количество товаров – 3 (на минутах 10, 20 и 40) и находился в магазине 47 минут (с 10 по 56-ю минуту). Покупатели {20, 40, 2} и {5, 50, 3} купили только один товар каждый (на минутах 30 и 50 соответственно), а остальные покупатели не смогли ничего приобрести. Ответ: 47 3.
Решение
Считываем исходные данные и сортируем их по времени посещения в в порядке возрастания. Помимо имеющихся трех полей для покупателя добавим четвертое поле, где будем подсчитывать количество купленных товаров. Создадим массив/список/вектор shop, куда будем добавлять индексы покупателей, которые в данный момент находятся в магазине. Организуем цикл, перебирающий моменты времени продажи товара со скидкой (для получения конечного значения цикла в исходных данных находим максимальное время выхода покупателя из магазина maxt). Для текущего момента времени удаляем из shop всех покупателей, которые покинули магазин или имеют максимальное количество покупок и добавляем покупателей, которые в магазин пришли, имея возможность совершить покупку. Из покупателей, находящихся в магазине, выбираем покупателя согласно условиям задачи и увеличиваем для него счетчик покупок. После обработки всех моментов времени ищем покупателя с максимальным количеством покупок и выводим данные для него.
PS: если внимательно проанализировать исходный файл, то можно обнаружить, что подавляющее большинство покупателей уже превысили ограничение M. Если изначально отфильтровать покупателей, которые могут купить товар, то останется менее двух десятков записей. В приведенном решении такая фильтрация не осуществляется, но покупатели с превышением лимита в shop не добавляются, а покупатели, набравшие лимит в магазине удаляются до наступления времени выхода.
Python
f = open('26-118.txt')
t, n, m = map(int, f.readline().split())
a = [[int(y) for y in x.split()] + [0] for x in f]
a.sort()
maxt = max(map(lambda x: x[1], a))
shop = []
z = 0
for i in range(t, maxt, t):
j = 0
while j < len(shop):
if a[shop[j]][1] < i or a[shop[j]][2] + a[shop[j]][3] == m:
del shop[j]
else:
j += 1
while z < n and a[z][0] <= i:
if a[z][2] < m:
shop.append(z)
z += 1
if len(shop) > 0:
p = 0
for j in range(1, len(shop)):
if (a[shop[j]][2] < a[shop[p]][2] or
a[shop[j]][2] == a[shop[p]][2] and a[shop[j]][1] > a[shop[p]][1]):
p = j
a[shop[p]][3] += 1
maxi = 0
for i in range(1, n):
if a[i][3] > a[maxi][3]:
maxi = i
print(a[maxi][1] - a[maxi][0] + 1, a[maxi][3])
PascalABC
var
n, m, t, maxt, maxi, min, i, j, p, z, tmp: Integer;
a: array [1..1000, 1..4] of Integer;
shop: array of Integer = new Integer[0];
f: TEXT;
begin
Assign(f, '26-118.txt');
Reset(f);
Readln(f, t, n, m);
maxt := 0;
for i := 1 to n do
begin
Readln(f, a[i, 1], a[i, 2], a[i, 3]);
a[i, 4] := 0;
if a[i][2] > maxt then
maxt := a[i][2];
end;
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j, 1] < a[min, 1] then
min := j;
if min <> i then
begin
tmp := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := tmp;
tmp := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := tmp;
tmp := a[i, 3];
a[i, 3] := a[min, 3];
a[min, 3] := tmp;
end;
end;
z := 1;
i := t;
while i <= maxt do
begin
j := 0;
while j < shop.Length do
if (a[shop[j], 2] < i) or (a[shop[j], 3] + a[shop[j], 4] = m) then
if j < shop.Length - 1 then
shop := shop[:j] + shop[j + 1:]
else
shop := shop[:j]
else
j := j + 1;
while (z <= n) and (a[z, 1] <= i) do
begin
if a[z, 3] < m then
shop := shop + Arr(z);
z := z + 1;
end;
if shop.Length > 0 then
begin
p := 0;
for j := 1 to shop.Length - 1 do
if (a[shop[j], 3] < a[shop[p], 3]) or
(a[shop[j], 3] = a[shop[p], 3]) and (a[shop[j], 2] > a[shop[p], 2]) then
p := j;
a[shop[p], 4] := a[shop[p], 4] + 1;
end;
i := i + t;
end;
maxi := 1;
for i := 2 to n do
if a[i, 4] > a[maxi, 4] then
maxi := i;
Writeln(a[maxi, 2] - a[maxi, 1] + 1, ' ', a[maxi, 4]);
end.
C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-118.txt");
int t, n, m, maxt = 0;
f >> t >> n >> m;
int a[1000][4];
for (int i = 0; i < n; i++)
{
f >> a[i][0] >> a[i][1] >> a[i][2];
a[i][3] = 0;
if (a[i][1] > maxt)
maxt = a[i][1];
}
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j][0] < a[min][0])
min = j;
if (min != i)
{
int t = a[i][0];
a[i][0] = a[min][0];
a[min][0] = t;
t = a[i][1];
a[i][1] = a[min][1];
a[min][1] = t;
t = a[i][2];
a[i][2] = a[min][2];
a[min][2] = t;
}
}
vector<int> shop;
int z = 0;
for (int i = t; i <= maxt; i+= t)
{
int j = 0;
while (j < shop.size())
if (a[shop[j]][1] < i || a[shop[j]][2] + a[shop[j]][3] == m)
shop.erase(shop.begin() + j);
else
j++;
while (z < n && a[z][0] <= i)
{
if (a[z][2] < m)
shop.push_back(z);
z++;
}
if (shop.size() > 0)
{
int p = 0;
for (j = 1; j < shop.size(); j++)
if (a[shop[j]][2] < a[shop[p]][2] ||
a[shop[j]][2] == a[shop[p]][2] && a[shop[j]][1] > a[shop[p]][1])
p = j;
a[shop[p]][3]++;
}
}
int maxi = 0;
for (int i = 1; i < n; i++)
if (a[i][3] > a[maxi][3])
maxi = i;
cout << a[maxi][1] - a[maxi][0] + 1 << " " << a[maxi][3] << endl;
}
Ответ
1261 211