|
|
|
|
背景 Background |
|
|
|
每天中午的下课铃一响，浙江镇海中学的同学们都会冲出学校来附近的小饭馆吃饭，刹那间天昏地暗，飞砂走石，家家餐馆内都是一片黑压压的人 。馄饨店、饺子馆，在学校附近开一家红一家。身为镇海中学信息中心首席科学顾问兼资深信息学竞赛辅导老师Dennis看到了，他为了在业余时间方便学生，他租了学校附近的一家店面，雇了几个拉面师傅，开了一家“正宗兰州牛肉拉面馆”，生意还不错。
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
话说Dennis的拉面馆隆重开张后，由于厨师手艺还未达到炉火纯青的地步，每碗拉面的重量并不都全部相等，故Dennis每天需亲自出马调节。
不过Dennis的拉面十分特殊，每碗都分成上下两部分，每部分的拉面重量均在1至6之间，且是整数，例如：现有排成行的4碗拉面
第一碗，上部分拉面重量为6，下部分拉面重量为1；
第二碗，上部分拉面重量为1，下部分拉面重量为5；
第三碗，上部分拉面重量为1，下部分拉面重量为3；
第四碗，上部分拉面重量为1，下部分拉面重量为2；
所有拉面上部分的重量之和为sum-up=6+1+1+1=9，下部分的数量之和为sum-down=1+5+3+2=11。这4碗拉面的上下数量之差的绝对值为11-9=2。
但是Dennis的每碗拉面上下可以互换，但只限于同一碗拉面，交换一次成为一次操作。请你帮助Dennis用最少的操作次数使给出的n份拉面的上下数量之差的绝对值最小。
例如这以上的4碗拉面，只需将第四碗拉面的上下部分交换，便可使上下部分之差为0。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行是一个正整数n (1≤n≤1000)，表示拉面的碗数。
接下来的n行表示n碗拉面的详细情况。
每行有两个用空格隔开的正整数，分别表示每碗拉面上下部分的数量a和b（1≤a，b≤6）。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
输出一个整数。表示求得的最小操作数。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
共10点，每点1秒。 |
|
|
|
|
|
|
|
注释 Hint |
|
|
|
30%的数据，n<=15
100%的数据，n<=1000
|
|
|
|
|
|
|
|
来源 Source |
|
|
|
fangyuhua&ycglovewxx |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1222 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
