Problem1884--汉诺塔组合

1884: 汉诺塔组合

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

    汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
    今天我们来处理的问题并不是汉诺塔移动的问题,而是汉诺塔组合的问题。对于汉诺塔中的任意一块盘片b的大小是b_i,若该盘片上面有盘片a且大小为a_i,则一定有a_i<b_i;若该盘片下面有盘片c且大小为c_i,则一定有b_i<c_i。 现在我们有三组个数均为n(n<100000)的盘片组a、b、c,请编程实现计算,从这三组中任意取出一个盘片,能够组成一个汉诺塔的组合数。(0<a_i<b_i<c_i<100000)。

Input

第一行n 
第二~四行,每行n个用空格隔开的数

Output

所有有效汉诺塔的组合数

Source/Category

分治