Question

Новое правило в чемпионате мира по программированию ICPC: можно использовать три компьютера. Давайте посмотрим как это повлияла на одну из сильнейших команд с Казахстана. Кирилл, Айбар и Султан начали писать контест. В контесте всего n задач и длится 5 часов. Они уже оценили время которое они потратят на каждую задачу. Кирилл решает задачу с номером i за ai минут. Айбар за bi. Султан за ci. Как и всегда нужно решить как можно больше задач с меньшим штрафом. Штраф определяется как сумма времени решения для каждой принятой задачи. Например, если команда сдаст первую задачу на 5 минуте, а вторую на 10 минуте то штраф будет равен 5 + 10 = 15. Вам нужно определить какой самый лучший результат может получить команда. Формат входных данных В первой строке дано одно целое числа n (1 6 n 6 10) - количество задача на контесте. В следующих n строк даны по три числа ai, bi и ci (1 6 ai; bi; ci 6 500) - время которое Кирилл, Айбар и Султан потратят на задачу соответственно. Формат выходных данных Выведи максимальное количество задач и минимальный штраф.

Answer 1

Ответ:

program deb;

var f,w:text;

   i,n:integer;

begin

 assign(f,'standard.input');

 reset(f);

 readln(f,n);

 for i:=1 to n do begin

   readln(f,a1,b1,c1);

   a:=a+a1;

   b:=b+b1;

   c:=c+c1;

 end;

 close(f);

 min:=a;

 if (a>b) then min:=b;

 if (b>c) then min:=c;

 writeln(n,' ',min);

end.

Объяснение:

Answer 2

Для решения этой задачи можно воспользоваться методом динамического программирования. Создадим трехмерный массив dp, где dp[i][j][k] будет представлять максимальное количество задач, которое можно решить, используя первые i задач и имея доступ к компьютерам Кирилла, Айбара и Султана на j, k компьютеров соответственно. Также создадим трехмерный массив penalties, чтобы хранить минимальные штрафы для каждой комбинации задач.

Инициализируем dp и penalties следующим образом:

• dp[0][0][0] = 0
• penalties[0][0][0] = 0

Затем мы будем перебирать задачи от 1 до n и количество доступных компьютеров от 0 до 3 для каждого из трех участников (Кирилла, Айбара и Султана). Для каждой комбинации задач и компьютеров будем вычислять максимальное количество задач и минимальный штраф, используя следующие рекуррентные формулы:

dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1], dp[i-1][j-1][k], dp[i-1][j][k-1], dp[i][j-1][k-1], dp[i-1][j-1][k-1]) + 1, если j + k >= i

penalties[i][j][k] = penalties[i-1][j][k], penalties[i][j-1][k], penalties[i][j][k-1], penalties[i-1][j-1][k], penalties[i-1][j][k-1], penalties[i][j-1][k-1], penalties[i-1][j-1][k-1] + ai + bi + ci, если j + k >= i

Итак, после вычисления значений dp и penalties для всех комбинаций задач и компьютеров, максимальное количество задач и минимальный штраф можно найти в dp[n][3][3] и penalties[n][3][3] соответственно.

Вот Python-код для решения этой задачи:

pythonCopy code
n = int(input())
tasks = []
for _ in range(n):
    a, b, c = map(int, input().split())
    tasks.append((a, b, c))

dp = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
penalties = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(4):
        for k in range(4):
            for x in range(4):
                if j + k + x <= i:
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1], dp[i - 1][j - 1][k], dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]) + 1
                    penalties[i][j][k] = min(
                        penalties[i][j][k],
                        penalties[i - 1][j][k],
                        penalties[i][j - 1][k],
                        penalties[i][j][k - 1],
                        penalties[i - 1][j - 1][k],
                        penalties[i - 1][j][k - 1],
                        penalties[i][j - 1][k - 1] + tasks[i - 1][0] + tasks[i - 1][1] + tasks[i - 1][2]
                    )

max_tasks = dp[n][3][3]
min_penalty = penalties[n][3][3]
print(max_tasks, min_penalty)

Этот код найдет максимальное количество задач, которое команда может решить, и минимальный штраф, который они получат.