Матч 19, Устройство РубГолдберг (RubeGoldberg)

Люси необходимо сконструировать устройство преобразования энергии РубГолдберг. Возможные преобразования описываются элементами массива parts в формате “INPUT OUTPUT TIME”, где INPUT и OUTPUT представляют собой входную и выходную энергии, TIME – время преобразования энергии в секундах. В наличии имеются четыре типа энергий: “CHEMICAL”, “ELECTRIC”, “MECHANICAL” и “THERMAL”. Время работы устройства должно быть как можно ближе к target секундам. Устройство состоит из последовательных преобразований энергии, где результат очередного преобразования подается на вход следующего. В конце работы устройства на выходе должна быть энергия last.

Необходимо найти наименьшую возможную разность между target и временем работы построенного устройства.

Класс: RubeGoldberg

Метод: int howClose(vector<string> parts, string last,

int target)

Ограничения: parts содержит от 0 до 50 элементов в формате “INPUT OUTPUT TIME”, 1 £ TIME, target £ 250000.

Вход. Массив преобразований энергии parts, энергия на выходе устройства last и время работы устройства target.

Выход. Наименьшая возможная разность между target и временем работы построенного устройства.

Пример входа

parts	last	target
{"CHEMICAL CHEMICAL 5"}	"CHEMICAL"	12
{"CHEMICAL THERMAL 6", "THERMAL CHEMICAL 3", "THERMAL CHEMICAL 5"}	"THERMAL"	123
{"CHEMICAL MECHANICAL 12", "MECHANICAL THERMAL 13", "THERMAL CHEMICAL 14"}	"ELECTRIC"	123456

Пример выхода

2

0

123456

РЕШЕНИЕ

динамическое программирование

Закодируем типы энергий номером индекса в массиве energy[] = {'C','E','M','T'}. Например, механической энергии будет соответствовать 2. Информацию о правилах преобразования энергии (их не более 50) занесем в массив prt[50][3], где prt[i] содержит массив из трех чисел: коды входной и выходной энергии, а также время преобразования. Например, правило "CHEMICAL THERMAL 6" будет представлено массивом {0, 3, 6} (0 = CHEMICAL, 3 = THERMAL).

Заведем двумерный массив dp, в котором dp[time][e] равно 1, если ровно через time секунд можно получить энергию e. Иначе присвоим dp[time][e] = 0. Поскольку можно начинать преобразования с любого типа энергии, положим dp[0][i] = 1 для каждого из четырех типов энергии (i = 0, 1, 2, 3). Последовательно вычисляем значения dp[time][e], time = 1, 2, 3, …, 2 * target, 1 £ e £ 4. Для каждой ячейки dp[time][e] перебираем все правила преобразования. Пусть k - ое правило, информация о котором находится в prt[k], начинается с энергии e = prt[k][0]. Тогда в time + prt[k][2] секунд можно получить энергию prt[k][1], поэтому положим

dp[time + prt[k][2]] [prt[k][1]] = 1

Вычислим код энергии last в переменной j. Просматриваем значения dp[target + i][j] и dp[target – i][j] i = 0, 1, 2, 3, . . . , и как только одно из них станет равным 1, возвращаем i.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <memory>

#define MAX 1000000

using namespace std;

char dp[MAX][4];

int prt[50][3];

class RubeGoldberg

{

public:

int howClose(vector<string> parts, string last, int target)

{

int i,j,k,time,n=(int)parts.size();

char energy[] = {'C','E','M','T'},from[11],to[11];

for(i=0;i<n;i++)

{

sscanf(parts[i].c_str(),"%s %s %d",from,to,&time);

for(j=0;j<4;j++) if (from[0] == energy[j]) break;

prt[i][0] = j;

for(j=0;j<4;j++) if (to[0] == energy[j]) break;

prt[i][1] = j; prt[i][2] = time;

}

memset(dp,0,sizeof(dp));

for(i=0;i<4;i++) dp[0][i] = 1;

for(i=0;i<2*target;i++) // i-th second

for(j=0;j<4;j++) // j-th type of energy

if (dp[i][j])

for(k=0;k<n;k++) // for all transformation rules

if (prt[k][0] == j) dp[i+prt[k][2]][prt[k][1]] = 1;

for(j=0;j<4;j++) if (last[0] == energy[j]) break;

for(i=0;;i++)

{

if (dp[target+i][j]) break;

if (dp[target-i][j]) break;

}

return i;

}

};