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

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

Решение

В процессе решения задачи, самым простым будет удаление обработанных данных. Поэтому для решения на Python будем использовать списки, на PascalABC - динамические массивы, а на C++ - вектор. В качестве альтернативы возможно решение через статические массивы с удалением обработанных данных путем сдвига или использования в структуре флагового поля, является ли данная запись обработанной.

Отсортируем исходные данные по времени визита на прием. В переменной time будет содержаться время окончания приема очередного посетителя. Пока значение этой переменной меньше t? среди необработанных посетителей ищем того, кто имеет приоритет выше и пришел раньше. В соответствии с выбранным посетителем меняем значения счетчиков и переменной time. Обязательно необходимо учитывать, что посетитель мог, как стоять в очереди, так и прийти без очереди спустя какое-то время после освобождения начальника. Обработанного посетителя удаляем.

Python

f = open('26-134.txt')
n, t = map(int, f.readline().split())
a = []
for i in f:
    x, y, z = i.split()
    a.append([int(x), int(y), z])
a.sort(key=lambda x: x[0])
time = 0
g = 0
m = 0
w = 0
last = 0
while time < t: 
    z = 0
    j = 1;
    while j < len(a) and a[j][0] <= time:
        if a[j][2] == 'G' and a[z][2] != 'G' or a[j][2] == 'W' and a[z][2] == 'M':
            z = j
        j += 1
    if a[z][2] == 'G':
        g += 1
        last = g
    elif a[z][2] == 'M':
        m += 1
        last = m
    else:
        w += 1
        last = w
    time = max(time + a[z][1], a[z][0] + a[z][1])
    del a[z]
print(g + m + w, last)

PascalABC

type
    Rec = record
        start: Integer;
        time: Integer;
        category: String;
    end;
var
    n, t, i, j, z, min, time, g, m, w, last: Integer;
    a: array of Rec = new Rec[1000];
    tmp: Rec;
    f: TEXT;
begin
    Assign(f, '26-134.txt');
    Reset(f);
    Readln(f, n, t);
    for i := 0 to n - 1 do
    begin
        Readln(f, a[i].start, a[i].time, a[i].category);
        a[i].category := a[i].category[2:];
    end;
    for i := 0 to n - 2 do
    begin
        min := i;
        for j := i + 1 to n - 1 do
            if a[j].start < a[min].start then
                min := j;
        if min <> i then
        begin
            tmp := a[i];
            a[i] := a[min];
            a[min] := tmp;
        end;
    end;
    time := 0;
    g := 0;
    m := 0;
    w := 0;
    last := 0;
    while time < t do
    begin
        z := 0;
        j := 1;
        while (j < a.Length) and (a[j].start <= time) do
        begin
            if (a[j].category = 'G') and (a[z].category <> 'G') or
               (a[j].category = 'W') and (a[z].category = 'M') then
                z := j;
            j := j + 1;
        end;
        if a[z].category = 'G' then
        begin
            g := g + 1;
            last := g;
        end
        else if a[z].category = 'M' then
        begin
            m := m + 1;
            last := m;
        end
        else
        begin
            w := w + 1;
            last := w;
        end;
        if time + a[z].time > a[z].start + a[z].time then
            time := time + a[z].time
        else
            time := a[z].start + a[z].time;
        a := a[:z] + a[z + 1:];
    end;
    Writeln(g + m + w, ' ', last);
end.

C++

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct rec
{
    int start;
    int time;
    string category;
};
int main()
{
    ifstream f;
    f.open("26-134.txt");
    int n, t;
    f >> n >> t;
    vector<rec> a;
    for (int i = 0; i < n; i++)
    {
        rec tmp;
        f >> tmp.start >> tmp.time >> tmp.category;
        a.push_back(tmp);
    }
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j].start < a[min].start)
                min = j;
        if (min != i)
        {
            rec tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
    int time = 0, g = 0, m = 0, w = 0, last = 0;
    while (time < t)
    {
        int z = 0, j = 1;
        while (j < a.size() && a[j].start <= time)
        {
            if (a[j].category == "G" && a[z].category != "G" ||
                a[j].category == "W" && a[z].category == "M")
                z = j;
            j++;
        }
        if (a[z].category == "G")
        {
            g++;
            last = g;
        }
        else if (a[z].category == "M")
        {
            m++;
            last = m;
        }
        else
        {
            w++;
            last = w;
        }
        if (time + a[z].time > a[z].start + a[z].time)
            time = time + a[z].time;
        else
            time = a[z].start + a[z].time;
        a.erase(a.begin() + z);
    }
    cout << g + m + w << " " << last << endl;
}

Ответ

80 77

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