Задача 6791. Источник: Поляков. Задание КИМ 26
(ЕГЭ-2023) На производстве штучных изделий N деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена. На ленте транспортёра имеется N мест для каждой из N деталей. На ленте транспортёра детали располагают по следующему алгоритму:
- все 2N чисел, обозначающих время окрашивания и шлифовки для N деталей, упорядочивают по возрастанию;
- если минимальное число в этом упорядоченном списке – это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;
- если минимальное число – это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра;
- если число обозначает время окрашивания или шлифовки уже рассмотренной детали, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N деталей. Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые будут отшлифованы до неё.
Входные данные представлены в файле 26-129.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество деталей. Следующие N строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные).
Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено её место на ленте транспортёра, затем количество деталей, которые будут отшлифованы до неё.
Пример входного файла:
5
30 50
100 155
150 170
10 160
120 55
При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали. Ответ: 3 3.
Решение
Поместим исходные данные в двухмерный массив/список, где каждая деталь будет представлена двумя строчками. В строке будет содержаться время, номер детали и тип обработки в виде числового или логического значения. Сортируем получившийся массив по времени обработки. В массиве/списке d будем помечать логическим значением детали, которые еще не были помещены на транспортер. Последовательно обрабатывая получившийся список, обрабатываем строки для неразмещенных деталей. Сохраняем в переменной last номер последней размещенной детали, last0 - тип обработки последней детали, k - количество деталей, размещенных по минимальному времени шлифовки. После обработки всех данных, если последняя деталь была размещена для шлифовки, переменную k нужно уменьшить на единицу.
Python
f = open('26-129.txt')
n = int(f.readline())
a = []
for i in range(1, n + 1):
x, y = map(int, f.readline().split())
a.append([x, i, True])
a.append([y, i, False])
a.sort()
d = [True] * (n + 1)
last = -1
last0 = False
k = 0
for i in a:
if d[i[1]]:
last = i[1]
last0 = i[2]
d[i[1]] = False
if i[2]:
k += 1
if last0:
k -= 1
print(last, k)
PascalABC
var
n, last, last0, k, min, i, j, t: Integer;
a: array [1..1994, 1..3] of Integer;
d: array [1..997] of Boolean;
f: TEXT;
begin
Assign(f, '26-129.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
begin
Readln(f, a[i * 2 - 1, 1], a[i * 2, 1]);
a[i * 2 - 1, 2] := i;
a[i * 2, 2] := i;
a[i * 2 - 1, 3] := 0;
a[i * 2, 3] := 1;
d[i] := True;
end;
for i := 1 to n * 2 - 1 do
begin
min := i;
for j := i + 1 to n * 2 do
if (a[j, 1] < a[min, 1]) or (a[j, 1] = a[min, 1]) and (a[j, 2] < a[min, 2]) 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;
t := a[i, 3];
a[i, 3] := a[min, 3];
a[min, 3] := t;
end;
end;
last := 0;
last0 := 0;
k := 0;
for i := 1 to n * 2 do
if d[a[i, 2]] then
begin
last := a[i, 2];
last0 := a[i, 3];
d[a[i, 2]] := False;
if a[i, 3] = 0 then
k := k + 1;
end;
if last0 = 0 then
k := k - 1;
Writeln(last, ' ', k);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-129.txt");
int n;
f >> n;
int a[1994][3];
bool d[998];
for (int i = 0; i < n; i++)
{
f >> a[i * 2][0] >> a[i * 2 + 1][0];
a[i * 2][1] = i + 1;
a[i * 2 + 1][1] = i + 1;
a[i * 2][2] = 0;
a[i * 2 + 1][2] = 1;
d[i] = true;
}
for (int i = 0; i < n * 2 - 1; i++)
{
int min = i;
for (int j = i + 1; j < n * 2; j++)
if (a[j][0] < a[min][0] || a[j][0] == a[min][0] && a[j][1] < a[min][1])
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;
}
}
int last = 0, last0 = 0, k = 0;
for (int i = 0; i < n * 2; i++)
if (d[a[i][1]])
{
last = a[i][1];
last0 = a[i][2];
d[a[i][1]] = false;
if (a[i][2] == 0)
k++;
}
if (last0 == 0)
k--;
cout << last << " " << k << endl;
}
Ответ
895 488