Задача 7015. Источник: Поляков. Задание КИМ 26

Страница задачи 7015

Решение

Считываем и сортируем исходные данные по началу усвещенного участка. В переменной count будем подсчитывать количество выключенных фонарей, kk - количество фонарей, освещающих k-ый метр, last - первый метр, который нуждается в освещении (инициализируется значением начала участка самого первого фонаря в отсортированных данных)<, max (mx) - максимальный конечный участок среди всех фонарей, которые пересекаются или соприкасаются с последним фонарем, который остался включенным (значение меньше или равно last). Последовательно обрабатываем фонари. Если начальный участок очередного фонаря больше last, "включаем" фонарь, который дал текущее значение max (уменьшаем счетчик count на единицу, а last присваиваем значение max увеличенное на единицу, т.к. этот фонарь осветил участок до данного значения). Обрабатываемый фонарь "выключаем" (увеличиваем count). Если он освещает участок дальше max, меняем значение этой переменной. Если фонарь освещает k-ый метр, увеличиваем счетчик kk. В цикле не будет "включатся" самый последний фонарь с наибольшим max. Поэтому, в качестве результата выводим count уменьшенный на единицу.

Python

f = open('26-139.txt')
n, k = map(int,f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
count = 0
kk = 0
last = a[0][0]
mx = 0
for i in a:
    if i[0] > last:
        count -= 1
        last = mx + 1
    count += 1
    mx = max(mx, i[1])
    if i[0] <= k <= i[1]:
        kk += 1
print(count - 1, kk)

PascalABC

var
    n, k, count, kk, max, last, min, i, j, t: Integer;
    a: array [1..10000, 1..2] of Integer;
    f: TEXT;
begin
    Assign(f, '26-139.txt');
    Reset(f);
    Readln(f, n, k);
    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;
    count := 0;
    kk := 0;
    last := a[1, 1];
    max := 0;
    for i := 1 to n do
    begin
        if a[i, 1] > last then
        begin
            count := count - 1;
            last := max + 1;
        end;
        count := count + 1;
        if a[i, 2] > max then
            max := a[i, 2];
        if (a[i, 1] <= k) and (a[i, 2] >= k) then
          kk := kk + 1;
    end;
    Writeln(count - 1, ' ', kk);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-139.txt");
    int n, k;
    f >> n >> k;
    int a[10000][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 count = 0, kk = 0, last = a[0][0], max = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i][0] > last)
        {
            count--;
            last = max + 1;
        }
        count++;
        if (a[i][1] > max)
            max = a[i][1];
        if (a[i][0] <= k && a[i][1] >= k)
            kk++;
    }
    cout << count - 1 << " " << kk << endl;
}

Ответ

9887 3

Отправить замечание по решению