Magic: the Gathering - это игра с карточными играми, в которой, среди прочего, игроки играют в карты, представляющие существ, которые могут затем атаковать другого игрока или защищаться от атак другого игрока путем блокирования.

В этом соревновании по коду для игры в гольф ваша программа будет заменена игроком-волшебником, который решает, как блокировать в бою.

---

У каждого существа есть два соответствующих атрибута: сила и выносливость. Сила существа - это количество урона, которое оно может нанести в бою, а его прочность - количество урона, необходимого для его уничтожения. Сила всегда по крайней мере 0, а прочность всегда по крайней мере 1.

Во время боя в Магии игрок, ход которого объявил, что некоторые из его существ атакуют противника. Затем другой игрок, известный как защищающийся игрок, может назначить своих существ в качестве блокирующих. Существо может блокировать только одно существо в бою, но несколько существ могут блокировать одно и то же существо.

После объявления блокирующих атакующий игрок решает, для каждого атакующего существа, которое было заблокировано, как распределить урон (равный его силе), который это существо наносит существам, блокирующим его.

Затем наносится урон. Каждое существо наносит урон, равный его силе. Атакующие существа, которые были заблокированы, наносят урон, как описано выше. Разблокированные атакующие существа наносят урон обороняющемуся игроку. Блокирующие существа наносят урон существу, которое они заблокировали. Существа, принадлежащие защищающемуся игроку, которые не блокируют, не наносят никакого урона. (Существа не обязаны блокировать.)

Наконец, любое существо, нанесшее урон, равный или превышающий его выносливость, уничтожается и удаляется с поля битвы. Любое количество урона меньше силы существа не имеет никакого эффекта.

---

Вот пример этого процесса:

Существо с силой P и выносливостью T представляется как P/T

Attacking:
2/2, 3/3
Defending player's creatures:
1/4, 1/1, 0/1
Defending player declares blockers:
1/4 and 1/1 block 2/2, 0/1 does not block.
Attacking player distributes damage:
2/2 deals 1 damage to 1/4 and 1 damage to 1/1
Damage is dealt:
2/2 takes 2 damage, destroyed.
3/3 takes 0 damage.
1/1 takes 1 damage, destroyed.
1/4 takes 1 damage.
0/1 takes 0 damage.
Defending player is dealt 3 damage.

---

У защищающегося игрока есть 3 цели в бою: уничтожить существа противника, сохранить собственные и получить как можно меньше урона. Кроме того, существа с большей силой и выносливостью являются более ценными.

Чтобы объединить их в одну меру, мы скажем, что оценка защищающегося игрока в бою равна сумме сил и выносливости его выживших существ, минус сумма мощностей и выносливости выживающих существ его противника, минус один половина суммы урона, нанесенного защищающемуся игроку. Защищающийся игрок хочет максимизировать этот счет, в то время как атакующий игрок хочет минимизировать его.

В бою, показанном выше, счет был:

Defending player's surviving creatures:
1/4, 0/1
1 + 4 + 0 + 1 = 6
Attacking player's surviving creature:
3/3
3 + 3 = 6
Damage dealt to defending player:
3
6 - 6 - 3/2 = -1.5

Если бы защищающийся игрок вообще не блокировал бой, описанный выше, счет был бы

8 - 10 - (5/2) = -4.5

Оптимальным выбором для защищающегося игрока было бы заблокировать 2/2с 1/1и 1/4и заблокировать 3/3с 0/1. Если бы они сделали это, только 1/4и тот 3/3выжил бы, и защищающемуся игроку не было бы нанесено никакого урона, делая счет

5 - 6 - (0/2) = -1

---

Ваша задача - написать программу, которая выдаст оптимальный вариант блокировки для защищающегося игрока. «Оптимальный» означает выбор, который максимизирует счет, учитывая, что противник распределяет урон таким образом, чтобы минимизировать счет, учитывая то, как вы заблокировали.

Это максимин: максимальный балл по распределению урона, который минимизирует балл для каждой комбинации блокировок.

---

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

Кортежи и списки могут быть представлены в любом удобном формате, например:

[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]

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

[0, 0]    # 1/4 blocks 2/2
[1, 0]    # 1/1 blocks 2/2
[2, 1]    # 0/1 blocks 3/3

Примеры:

Input:
[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]
Output:
[0, 0]
[1, 0]
[2, 1]

Input:
[[3, 3], [3, 3]]
[[2, 3], [2, 2], [2, 2]]
Output:
[1, 0]
[2, 0]
or
[1, 1]
[2, 1]

Input:
[[3, 1], [7, 2]]
[[0, 4], [1, 1]]
Output:
[1, 0]
or
[0, 0]
[1, 0]

Input:
[[2, 2]]
[[1, 1]]
Output:

(No output tuples).

Вход и выход могут быть через STDIN, STDOUT, CLA, функцию ввода / вывода и т. Д. Применяются стандартные лазейки . Это код-гольф: выигрывает самый короткий код в байтах.

---

Чтобы прояснить спецификацию и представить первоначальные идеи, этот pastebin предоставляет эталонное решение на Python. Эта best_blockфункция является примером решения этой проблемы, и запуск программы обеспечит более подробный ввод и вывод.

JavaScript (ES7),  354  348 байт

Принимает вход как ([attackers], [defenders]).

(a,d,O,M)=>eval(`for(N=(A=a.push([,0]))**d.length;N--;)O=a[X='map'](([P,T],i)=>S-=((g=(n,l)=>n?l[X](([t,S],i)=>g(n-1,b=[...l],b[i]=[t-1,S])):m=l[X](([t,S])=>s+=t>0&&S,s=0)&&s>m?m:s)(P,l[n=0,i][X](m=([p,t])=>[t,p+t,n+=p])),n<T&&P+T)+(l[i]<1?T/2:-m),S=0,d[X]((x,i)=>l[(j=N/A**i%A|0)<A-1&&o.push([i,j]),j].push(x),o=[],l=a[X](_=>[])))&&S<M?O:(M=S,o)`)

Попробуйте онлайн!

Менее гольф и отформатированы

Этот код идентичен версии для гольфа, только без mapпсевдонимов и eval()переноса для удобства чтения.

(a, d, O, M) => {
  for(N = (A = a.push([, 0])) ** d.length; N--;)
    O =
      a.map(([P, T], i) =>
        S -=
          (
            (g = (n, l) =>
              n ?
                l.map(([t, S], i) => g(n - 1, b = [...l], b[i] = [t - 1, S]))
              :
                m = l.map(([t, S]) => s += t > 0 && S, s = 0) && s > m ? m : s
            )(
              P,
              l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])
            ),
            n < T && P + T
          ) + (
            l[i] < 1 ? T / 2 : -m
          ),
        S = 0,
        d.map((x, i) =>
          l[
            (j = N / A ** i % A | 0) < A - 1 && o.push([i, j]),
            j
          ].push(x),
          o = [],
          l = a.map(_ => [])
        )
      ) && S < M ? O : (M = S, o)
  return O
}

Как?

Инициализация и основной цикл

$0$push$A$

A = a.push([, 0])

Мы собираемся заблокировать это фиктивное существо вместо того, чтобы вообще ничего не блокировать. Это позволяет некоторые упрощения в коде.

$A^D$$D$$N$

for(N = (A = a.push([, 0])) ** d.length; N--;)

$S$$M$$o$$O$

$M$$O$

O = (...) && S < M ? O : (M = S, o)

Строим нашу оборону

$l$

d.map((x, i) =>              // for each defender x at position i:
  l[                         //   update l[]:
    (j = N / A ** i % A | 0) //     j = index of the attacker that we're going to block
    < A - 1 &&               //     if this is not the 'dummy' creature:
    o.push([i, j]),          //       add the pair [i, j] to the current solution
    j                        //     use j as the actual index to update l[]
  ].push(x),                 //   push x in the list of blockers for this attacker
  o = [],                    //   initialize o to an empty list
  l = a.map(_ => [])         //   initialize l to an array containing as many empty lists
                             //   that there are attackers
)                            // end of map()

Оптимизация атаки

Решения злоумышленников не связаны между собой. Глобальный оптимум для атакующей стороны - это сумма локальных оптимумов для каждого атакующего.

$P$$T$$i$

a.map(([P, T], i) => ...)

$l[i]$

l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])

$n$

$g$$P$

(g = (n, l) =>            // n = remaining damage points; l = list of blockers
  n ?                     // if we still have damage points:
    l.map(([t, S], i) =>  //   for each blocker of toughness t and score S at index i:
      g(                  //     do a recursive call:
        n - 1,            //       decrement the number of damage points
        b = [...l],       //       create a new instance b of l
        b[i] = [t - 1, S] //       decrement the toughness of blocker i
      )                   //     end of recursive call
    )                     //   end of map()
  :                       // else:
    m =                   //   update the best score m (the lower, the better):
      l.map(([t, S]) =>   //     for each blocker of toughness t and score S:
        s += t > 0 && S,  //       add S to s if this blocker has survived
        s = 0             //       start with s = 0
      ) &&                //     end of map()
      s > m ? m : s       //     set m = min(m, s)
)                         //

Обновление счета защитника

После каждой итерации атакующего мы обновляем рейтинг защитника следующим образом:

S -= (n < T && P + T) + (l[i] < 1 ? T / 2 : -m)

Левая часть вычитает счет атакующего, если он выжил. Правая часть вычитает половину выносливости атакующего, если атака вообще не была заблокирована, или добавляет лучший результат атакующего в противном случае (который является худшим с точки зрения обороняющейся стороны).