Задания
Версия для печати и копирования в MS Word

Ор­га­ни­за­ция ку­пи­ла для своих со­труд­ни­ков все места в не­сколь­ких под­ряд иду­щих рядах на кон­церт­ной пло­щад­ке. Из­вест­но, какие места уже рас­пре­де­ле­ны между со­труд­ни­ка­ми. Най­ди­те ряд с наи­боль­шим но­ме­ром, в ко­то­ром есть два со­сед­них места, таких что слева и спра­ва от них в том же ряду места уже рас­пре­де­ле­ны (за­ня­ты). Га­ран­ти­ру­ет­ся, что есть хотя бы один ряд, удо­вле­тво­ря­ю­щий усло­вию. В от­ве­те за­пи­ши­те два целых числа: номер ряда и наи­мень­ший номер места из най­ден­ных в этом ряду под­хо­дя­щих пар.

Вход­ные дан­ные.

За­да­ние 26

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся одно число: N  — ко­ли­че­ство за­ня­тых мест (на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000). В сле­ду­ю­щих N стро­ках на­хо­дят­ся пары чисел: ряд и место вы­куп­лен­но­го би­ле­та (числа не пре­вы­ша­ют 100 000).

В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла мак­си­маль­ный номер ряда, где на­шлись обо­зна­чен­ные в за­да­че места и ми­ни­маль­ный номер места.

При­мер вход­но­го файла:

6

50 12

50 15

60 157

60 160

60 22

60 25

Для дан­но­го при­ме­ра от­ве­том будет яв­лять­ся пара чисел 60 и 23.

 

Ответ:

Спрятать решение

Ре­ше­ние.

1.  Счи­та­ем все пары в дву­мер­ный мас­сив, где пер­вое число  — номер ряда, вто­рое  — номер места.

a.  Номер места счи­та­ем как от­ри­ца­тель­ное зна­че­ние, чтобы при сор­ти­ров­ке места с мень­шим но­ме­ром (по дан­ным из файла) были боль­ше (в дан­ных). Это су­ще­ствен­но со­кра­тит поиск нуж­но­го места.

2.  От­сор­ти­ру­ем мас­сив.

3.  Най­дем по­след­ний эле­мент в от­сор­ти­ро­ван­ном мас­си­ве, ко­то­рый удо­вле­тво­ря­ет усло­вию.

a.  Два за­ня­тых места на­хо­дят­ся в одном ряду.

b.  Раз­ни­ца между про­ве­ря­е­мым ме­стом и преды­ду­щим равна 3 (со­от­вет­ству­ет схеме «за­ня­то»  — «сво­бод­но»  — «сво­бод­но»  — «за­ня­то»).

c.  Так как надо опре­де­лить ми­ни­маль­ный номер сво­бод­но­го места, до­ба­вим к но­ме­ру най­ден­но­го места 1 (со­сед­нее спра­ва от ми­ни­маль­но­го зна­че­ния в паре за­ня­тых).

 

Пас­каль

var f: text;

    n, i, r, m, a, b: integer;

    nums: array of array of integer;

begin

    setlength(nums, 0);

    assign(f, '26.txt');

    reset(f);

    readln(f, n);

    loop n do begin

        readln(f, a, b);

        nums := nums + ||a, -b||;

    end;

    Sort(nums, (x, y) -> ((x[0] < y[0]) or (x[0] = y[0]) and (x[1] < y[1])));

    r := 0; m := 0;

    for i := 1 to nums.Length – 1 do

        if nums[i, 0] = nums[i-1, 0] then

            if nums[i, 1] – nums[i-1, 1] = 3 then begin

                r := nums[i, 0];

                m := -nums[i, 1] + 1;

            end;

    print(r, m);

end.

Python

f = open('26.txt’)

n = int(f.readline())

nums = []

for _ in range(n):

    pair = list(map(int, f.readline().split()))

    pair[1] = -pair[1]

    nums += [pair]

nums.sort()

r, m = 0, 0

for i in range(1, len(nums)):

    if nums[i][0] == nums[i-1][0]:

        if nums[i][1] – nums[i-1][1] == 3:

            r = nums[i][0]

            m = -nums[i][1] + 1

print(r, m)

С++

#include <iostream>

#include <algorithm>

#include <fstream>

#include <vector>

using namespace std;

int main(){

    ifstream f("26.txt");

    int n, a, b, r, m;

    f >> n;

    vector <vector <int>> nums;

    for(int i=1; i<=n; i++){

        f >> a >> b;

        vector<int> temp = {a, -b};

        nums.push_back(temp);

    }

    sort(nums.begin(), nums.end());

    r = 0; m = 0;

    for(int i=1; i < nums.size(); i++)

        if(nums[i][0] == nums[i-1][0])

            if(nums[i][1] - nums[i-1][1] == 3){

                r = nums[i][0];

                m = -nums[i][1] + 1;

            }

    cout << r << " " << m;

}

 

В ре­зуль­та­те ра­бо­ты дан­но­го ал­го­рит­ма при вводе дан­ных из файла в усло­вии по­лу­ча­ем ответ  — 8631 7311.

 

Ответ: 8631 7311.

 

При­ме­ча­ние. Путь к файлу не­об­хо­ди­мо ука­зать со­глас­но рас­по­ло­же­нию файла на Вашем ком­пью­те­ре.

 

При­ведём ре­ше­ние Юрия Кра­силь­ни­ко­ва на языке Python.

a = sorted([list(map(int,s.split())) for s in open('26.txt')][1:])

lefts = [a[i] for i in range(len(a) - 1) if a[i][0] == a[i+1][0] and a[i+1][1] - a[i][1] == 3]

lefts.sort(key = lambda x: (x[0],-x[1]))

print(lefts[-1][0],lefts[-1][1] + 1)

Источник: ЕГЭ по ин­фор­ма­ти­ке 24.06.2021. Ос­нов­ная волна
Раздел кодификатора ФИПИ: