問題概要
（原文が日本語かつ十分に簡潔なので省略）
解法
ある長さ $L$ の竹を作りたいときに，その竹を作るために使う竹の集合を固定したとします．使う竹が $n$ 本で長さがそれぞれ $x_i$ ($1 \leq i \leq n$) であるとすると，
- 合成魔法の使用回数は $n - 1$
- 延長または短縮魔法の（最小の）使用回数は，$x_i$ の総和と $L$ の差 $|L - \sum x|$
という風に定まります．
従って，$A, B, C$ のそれぞれを作るために使う竹の集合を全通り試すことを繰り返すと，各集合に対して最適なコストが一意的に定まるため，問題を解くことができます．これは例えば $$f( i, U )$$ のような再帰関数で実装でき，ここで，$i$ は $A, B, C$ の内いくつを決めたのかを表す整数，$U$ はすでに使途が決まった竹の（添字の）集合（を整数にエンコードしたもの*1）を表し，戻り値は「それ（引数が表す状況）以降の選択を最適に行った場合の最小コスト」です．$f( 0, 0 )$ の値が元の問題の答えになります．
関数の中身について考えます．まず $i = 3$ のとき，$A, B, C$ の全てを作り終わっていてもうやることがないので，値は $0$ です．そうでない場合，$i$ 番目の目標値を作るために使う竹の集合を全部試してそれぞれ再帰し，最適値を探します．このとき考えるべき集合は，$1$ 以上*2かつ $2^N$ 未満の整数で表現される集合 $S$ です．ただし，$U \cap S$ （整数としては $U$ と $S$ のbitwise and）が $\emptyset$ でないときは，同じ竹を二回使おうとしていることになるので飛ばします．重複が無い場合，前述した方法で求まるコストと，$f( i + 1, U \cup S )$ の和が，その集合を採用した場合のコストです（$U \cup S$ は整数としては $U$ と $S$ の bitwise or です）．なので，$S$ を全部試して，最小のものを return すればよいです．なお，feasible な $S$ が存在しない場合（既に竹を使い切ってる）は適当に $\infty$ （と見做せる値）を返しておきます．
まとめると，
- $f( 3, * ) = 0$
- $f( i, U ) = \min_{ S \subseteq \{ 1, 2, \dots, N \}, S \neq \emptyset, S \cap U = \emptyset } 10 ( |S| - 1 ) + | \mathit{ ABC }_i - \sum_{ j \in S } x_j | + f( i + 1, U \cup S )$
となります（あんまりまとまった感じしないね……）．
計算量について考えます．上記関数の再帰呼び出しを木構造で表したものを考えます（再帰木）．このとき，$i = 3$ の呼び出しに対応する葉の数は $O( 4^N )$ 通りしかありません．なぜなら，（同じ竹を二回使うなどの）invalid な状況に対しては再帰呼び出しを行っておらず，valid な状態というのは各竹を，$A$ のために使うか，$B$ のために使うか，$C$ のために使うか，全く使わないかの $4$ 通りだからです．また，再帰木全体の頂点数も $O( 4^N )$ 個です．再帰木の高さが $O( 1 )$ であることから言えます．また，$4^8 = 65536$ なので問題ありません．
特に工夫せずに実装して，竹の集合をそれぞれ試すときに和の計算で $O( N )$ 時間かけた場合，全体の計算量は $O( 4^N N )$ になります．
コード
using VI = vector< int >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; } void in_impl(){}; template < typename T, typename... TS > void in_impl( T &head, TS &... tail ){ cin >> head; in_impl( tail ... ); } #define IN( T, ... ) T __VA_ARGS__; in_impl( __VA_ARGS__ ); #define NUMBERED( name, number ) NUMBERED2( name, number ) #define NUMBERED2( name, number ) name ## _ ## number #define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n ) #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ ) #define SZ( v ) ( (int)( v ).size() ) template < typename T > inline bool chmin( T &a, const T &b ){ if ( b < a ) { a = b; return true; } return false; } constexpr auto INF = LIM<>::max() / 2; int opt_cost( const int T, const VI &L, const int s ) { const int N = SZ( L ); int sum = 0; REP( i, N ) { if ( s & 1 << i ) { sum += L[i]; } } return 10 * ( __builtin_popcount( s ) - 1 ) + abs( sum - T ); } int solve( const VI &ABC, const VI &L, const int i = 0, const int used = 0 ) { const int N = SZ( L ); if ( i == 3 ) { return 0; } int res = INF; REP( s, 1, 1 << N ) { if ( used & s ) { continue; } chmin( res, opt_cost( ABC[i], L, s ) + solve( ABC, L, i + 1, used | s ) ); } return res; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N ); VI ABC( 3 ), L( N ); cin >> ABC >> L; cout << solve( ABC, L ) << endl; return 0; }
