Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
连环锁
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 1305Accepted: 427

Description

许多人一定很熟悉九连环(如下图),九个环被串在一起,操作规则如下:第一个(右边)环可以任意装卸,如果第k个环没有被卸掉,而第k个环前边(右边)的所有环都被卸掉,则第k+1个环(第k个环左边的环)可以任意装卸(如果存在的话)。
用0表示此换被卸掉,1表示此环没有被卸掉,则九连环的每个状态可以用一个长度为9的二进制串来表示,如:111111001经过一次操作可以变成111111000,也可以变成111111011,111111111经过一次操作可以变成111111110,也可以变成111111101。

任务描述:
你现在要操作的是一个n连环,n为正整数,给出n连环的两种状态,计算出从第一种状态变换到第二种状态所需要的最少步数。

Input

第一行是一个正整数m,表示有m组测试数据。
每组测试数据一共3行,第一行是一个正整数n (0 < n < 128),后两行每一行描述一种状态,n个数(0或1),用空格隔开。

Output

对于每一组测试数据输出一行,一个非负整数,表示从第一种状态变换到第二种状态所需要的最少步数。

Sample Input

2
3
0 0 0
1 0 0
4
1 0 0 0
0 1 1 0

Sample Output

7
11

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator