Задача 7012. Источник: Поляков. Задание КИМ 26
(Л. Шастин) В магазине имеется N товаров. Известны цена каждого из товаров и его текущий статус (продан или не продан). Товары разделены на две категории - дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает средний чек M. Остальные, соответственно, являются дешёвыми (цена на них не превышает M). Необходимо найти сумму выручки магазина за продажу самого популярного товара среди дорогих и самого популярного товара среди дешёвых (если известно, что популярность товара тем выше, чем больше раз он был продан), а также сколько товаров этих двух видов остались в наличии.
Входные данные представлены в файле 26-136.txt следующим образом. В первой строке входного файла находится два натуральных числа, не превышающих 10000: N – количество товаров и M – средний чек. В следующих N строках записано по два числа: цена товара (она же вид товара) и статус товара (0 – не продан; 1 – продан).
Запишите в ответе два целых неотрицательных числа: сумму выручки магазина за продажу самого популярного товара среди дорогих и самого популярного товара среди дешёвых, а также количество товаров этих двух видов, оставшихся в наличии.
Пример входного файла:
5 60
43 1
90 1
43 0
43 1
90 0
Для данного примера цена самого популярного дорогого товара – 90 (продан 1 раз), а самого популярного из дешёвых – 43 (продан дважды). Их сумма = 90 + 43·2 = 176. Продано товаров = 3, всего их в наличии было 5. Осталось = 5 - 3 = 2. Ответ: 176 2.
Решение
Считываем данные в массив/список и сортируем их по цене (коду) товара. Последовательно для каждого товара подсчитываем количество продаж в переменной sales и количество оставшегося товара в переменной left. Дойдя до следующего товара или конца списка, проверяем, к какой категории относится данный товар (дешевых или дорогих) и проверяем, является ли данный товар самым популярным в своей категории. Если является, то обновляем значения переменных для дорогих (префикс exp) или дешевых (префикс inexp) товаров.
Python
f = open('26-136.txt')
n, m = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
exp_max = 0
exp_total = 0
exp_left = 0
inexp_max = 0
inexp_total = 0
inexp_left = 0
sales = 0
left = 0
last = 0
for i in range(n):
if i == 0 or a[i][0] == a[i - 1][0]:
last = a[i][0]
if a[i][1] == 0:
left += 1
else:
sales += 1
if i == n - 1 or i != 0 and a[i][0] != a[i - 1][0]:
if last > m:
if sales > exp_max:
exp_max = sales
exp_total = sales * last
exp_left = left
else:
if sales > inexp_max:
inexp_max = sales
inexp_total = sales * last
inexp_left = left
if a[i][1] == 0:
left = 1
sales = 0
else:
left = 0
sales = 1
print(exp_total + inexp_total, exp_left + inexp_left)
PascalABC
var
n, m, sales, left, last, min, i, j, t: Integer;
exp_max, exp_total, exp_left, inexp_max, inexp_total, inexp_left: Integer;
a: array [1..5000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-136.txt');
Reset(f);
Readln(f, n, m);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
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
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;
end;
end;
exp_max := 0;
exp_total := 0;
exp_left := 0;
inexp_max := 0;
inexp_total := 0;
inexp_left := 0;
sales := 0;
left := 0;
last := 0;
for i := 1 to n do
begin
if (i = 1) or (a[i, 1] = a[i - 1, 1]) then
begin
last := a[i, 1];
if a[i, 2] = 0 then
left := left + 1
else
sales := sales + 1;
end;
if (i = n) or (i <> 1 ) and (a[i, 1] <> a[i - 1, 1]) then
begin
if last > m then
begin
if sales > exp_max then
begin
exp_max := sales;
exp_total := sales * last;
exp_left := left;
end;
end
else
if sales > inexp_max then
begin
inexp_max := sales;
inexp_total := sales * last;
inexp_left := left;
end;
if a[i,2] = 0 then
begin
left := 1;
sales := 0;
end
else
begin
left := 0;
sales := 1;
end
end;
end;
Writeln(exp_total + inexp_total, ' ', exp_left + inexp_left);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-136.txt");
int n, m;
f >> n >> m;
int a[5000][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> 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;
}
}
int exp_max = 0, exp_total = 0, exp_left = 0;
int inexp_max = 0, inexp_total = 0, inexp_left = 0;
int sales = 0, left = 0, last = 0;
for (int i = 0; i < n; i++)
{
if (i == 0 || a[i][0] == a[i - 1][0])
{
last = a[i][0];
if (a[i][1] == 0)
left++;
else
sales++;
}
if (i == n - 1 || i != 0 && a[i][0] != a[i - 1][0])
{
if (last > m)
{
if (sales > exp_max)
{
exp_max = sales;
exp_total = sales * last;
exp_left = left;
}
}
else
if (sales > inexp_max)
{
inexp_max = sales;
inexp_total = sales * last;
inexp_left = left;
}
if (a[i][1] == 0)
{
left = 1;
sales = 0;
}
else
{
left = 0;
sales = 1;
}
}
}
cout << exp_total + inexp_total << " " << exp_left + inexp_left << endl;
}
Ответ
2320 51