Question

Дано *N* деталей, номер детали совпадает со строкой, и считается от 1 до *N*, в *N* строках соответственно: время шлифовки, время покраски. Есть конвейерная лента длины *N*, требуется отшлифовать и покрасить детали, их ставят на конвейерную ленту следующим образом: строится последовательность 2 · *N*, все числа данные в парах сортируются по возрастанию в этой последовательности от наименьшего к наибольшему.Если минимальное время — время шлифовки, то деталь ставится в первую свободную ячейку с начала.Если минимальное время — время покраски, деталь ставится в первую свободную ячейку с конца.Если минимальное число время окрашивания или шлифовки уже рассмотренной детали, такое время игнорируется.Получается заполненная лента обработки.**Входные данные.**Задание 26

Первая строка входного файла содержит натуральное число *N* (1 ≤ *N* ≤ 1000) — количество деталей. Следующие *N* строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные).Определите номер последней детали, поставленной на конвейер и количество деталей отшлифованных до неё.

Accepted Answer

Answer

### СТАТЕМЕНТ

Дано $N$ деталей. Каждая деталь $i$ (нумерация от 1 до $N$) характеризуется двумя временами: шлифовки и покраски. Необходимо разместить детали на конвейерную ленту длины $N$ по следующему алгоритму:

1. Составляется последовательность из $2N$ пар: (время, номер детали, тип операции), где тип операции — 1 для шлифовки, 2 для покраски.
2. Эта последовательность сортируется по возрастанию времени.
3. Для каждой пары в отсортированном порядке:
   - Если деталь ещё не размещена на ленте:
     - Если операция — шлифовка (тип 1), деталь ставится в первую свободную ячейку с начала.
     - Если операция — покраска (тип 2), деталь ставится в первую свободную ячейку с конца.
     - Деталь помечается как размещённая.
   - Если деталь уже размещена, операция игнорируется.

**Требуется найти:** номер последней размещённой детали и количество деталей, прошедших шлифовку до неё (включительно).

**Входные данные:** первая строка содержит натуральное число $N$ ($1 \le N \le 1000$). Следующие $N$ строк содержат пары натуральных чисел — время шлифовки и время покраски для каждой детали (все числа различны).

---

### РЕШЕНИЕ

Идея решения: построить список всех операций (время, номер детали, тип), отсортировать по времени, затем последовательно размещать детали на ленту, отслеживая последнюю размещённую деталь и подсчитывая количество шлифованных деталей.

```python
f = open('26_59821.txt')
n = int(f.readline())
a = []

for i in range(1, n + 1):
    x, y = map(int, f.readline().split())
    a.append([x, i, 1])  # время шлифовки, номер детали, тип 1
    a.append([y, i, 2])  # время покраски, номер детали, тип 2

a.sort()

conveyor = [1] * (n + 1)  # 1 = не размещена, 2 = размещена
last = -1
det = 2
count = 0

for j in a:
    if conveyor[j[1]] == 1:
        last = j[1]
        det = j[2]
        conveyor[j[1]] = 2
        if j[2] == 1:
            count += 1

if det == 1:
    count -= 1

print(last, count)
```

**Пояснение алгоритма:**

1. Читаем $N$ деталей и создаём список из $2N$ элементов: каждый элемент — это [время, номер_детали, тип_операции].
2. Сортируем список по времени (первому элементу).
3. Проходим по отсортированному списку. Для каждой операции:
   - Если деталь ещё не размещена (значение в массиве `conveyor` равно 1), размещаем её и обновляем `last` (номер последней размещённой детали) и `det` (тип последней операции).
   - Если это была шлифовка, увеличиваем счётчик `count`.
   - Помечаем деталь как размещённую (значение 2).
4. После цикла: если последняя размещённая операция была шлифовкой, уменьшаем счётчик на 1 (так как нужно считать детали, прошедшие шлифовку *до* последней детали, а не включая саму последнюю, если она была шлифована).

Сложность: $O(N \log N)$ (доминирует сортировка).

---

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике