次のような計算を行なう演算子@と、計算のために要するコストCを考えます。 演算子@の計算規則は以下の通りです。
(a,b)@(b,c) = (a,c)
(a,b)@(b,c)@(c,d) = ((a,b)@(b,c))@(c,d) = (a,c)@(c,d) = (a,d)
あるいは
= (a,b)@((b,c)@(c,d)) = (a,b)@(b,d) = (a,d)
一般にn2=n3であるとき，(n1,n2)@(n3,n4)=(n1,n4)であるとします(n2≠n3の時は定義されない)。
また、 (n1,n2)@(n3,n4)@(n5,n6) ... についてどの隣接する任意のペアから計算を
行なっても答えは同じとなることが保証されているものとします。つまり、
(n1,n2)@(n3,n4)@(n5,n6)
== ((n1,n2)@(n3,n4))@(n5,n6)
== (n1,n2)@((n3,n4)@(n5,n6))
例)
(3,4)@(4,9) = (3,9)
(4,8)@(8,5)@(5,13) = (4,5)@(5,13) = (4,13)
あるいは
(4,8)@(8,13) = (4,13)
さて、@に関する計算はどの順番に計算しても答えは同じであることを説明しましたが、
計算に要するコストCは順番によって異なってきます。コストCを次のように見積もります。
(a,b)@(b,c) = (a,c) の場合、 C=a+b+c
(a,b)@(b,c)@(c,d) = ((a,b)@(b,c))@(c,d) = (a,c)@(c,d) = (a,d) の場合
(a,b)@(b,c) = (a,c) の部分で a+b+c ついで、
(a,c)@(c,d) = (a,d) の部分で a+c+d 最後に両者併せて
2a+b+2c+d
= (a,b)@((b,c)@(c,d)) = (a,b)@(b,d) = (a,d) の場合
(b,c)@(c,d) = (b,d)の部分で b+c+d ついで
(a,b)@(b,d) = (a,d)の部分で a+b+d 最後に両者併せて
a+2b+c+2d
先の例で計算すると、
(3,4)@(4,9) = (3,9)
3+4+9=16
(4,8)@(8,5)@(5,13) = (4,5)@(5,13) = (4,13)
(4+8+5) + (4+5+13) = 39
(4,8)@(8,5)@(5,13) = (4,8)@(8,13) = (4,13)
(8+5+13)+(4+8+13) = 51
となります。
入力
一行に１ペア。ペアの各要素はint型の整数で、空白で区切られているものします。 また、ペアの個数の上限は500とします。なお、(n1,n2)@(n3,n4)において、 n2≠n3となるような入力データはないと仮定します。
例) 4 8 8 5 5 13出力
コストCを出力します。
プログラミング言語
ANSI Cのみを仮定します。
順位について
正解を出力したプログラムに対し、計算時間のより短いものを上位とします。
計算時間に関する注意
本センターが所有する計算機において、実行時間が５分を越えるものに関しては 途中で処理を打ち切ることがあります。
参考
データの入力と出力に関するプログラムコードの一部を示しておきます。 この例では入力データはファイルにあると仮定し、各ペアの値を変数a, bに 代入しています。ただし、新しい値を代入するたびに、古い値は消えています。
#include <stdio.h>
int main(int argc, char *argv[]){
int a,b; int cost; FILE *fp;
/** 入力 **/
fp = fopen(argv[1], "r");
while(fscanf(fp, "%d %d",&a, &b) != EOF){
}
/** costを計算 **/
/** 出力 **/
printf("Cost = %d\n", cost);
return 0;}