Dominoes
Time Limit:1000MS Memory Limit:65536K
Total Submit:1022 Accepted:333
Description
A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table:
The number of dots in the top line is 6+1+1+1=9 and the number of dots in the bottom line is 1+5+3+2=11. The gap between the top line and the bottom line is 2. The gap is the absolute value of difference between two sums.
Each domino can be turned by 180 degrees keeping its face always upwards.
What is the smallest number of turns needed to minimise the gap between the top line and the bottom line?
For the figure above it is sufficient to turn the last domino in the row in order to decrease the gap to 0. In this case the answer is 1.
Write a program that: computes the smallest number of turns needed to minimise the gap between the top line and the bottom line.
Input
The first line of the input contains an integer n, 1 <= n <= 1000. This is the number of dominoes laid out on the table.
Each of the next n lines contains two integers a, b separated by a single space, 0 <= a, b <= 6. The integers a and b written in the line i + 1 of the input file, 1 <= i <= 1000, are the numbers of dots on the i-th domino in the row, respectively, in the top line and in the bottom one.
Output
Output the smallest number of turns needed to minimise the gap between the top line and the bottom line.
Sample Input
4
6 1
1 5
1 3
1 2
Sample Output
1
Source
CEOI 1997
#include
<
iostream
>
using
namespace
std;
const
int
MAXN
=
8000
;
const
int
INF
=
1
<<
28
;
struct
DATA
{
int
da[MAXN];
int
dx;
int
q;
}
;
DATA dp[
2
*
MAXN];
bool
f[
2
*
MAXN];
int
queue[MAXN], front, rear;
int
main()
{
int
n;
int
a[MAXN], x, y;
int
i, j, k, w, l;
int
d
=
0
;
int
ans
=
INF;
scanf(
"
%d
"
,
&
n);
for
(i
=
0
; i
<
n; i
++
)
{
scanf(
"
%d%d
"
,
&
x,
&
y);
a[i]
=
x
-
y;
d
+=
a[i];
}
memset(f,
false
,
sizeof
(f));
dp[d
+
7500
].dx
=
d; dp[d
+
7500
].q
=
0
; f[d
+
7500
]
=
true
;
for
(i
=
0
; i
<
n; i
++
) dp[d
+
7500
].da[i]
=
a[i];
front
=
0
; rear
=
0
; w
=
0
;
do
{
for
(i
=
0
; i
<
n; i
++
)
{
j
=
dp[d
+
7500
].da[i];
k
=
d
-
j
*
2
;
if
(
!
f[k
+
7500
]
||
dp[k
+
7500
].q
>
w
+
1
)
{
if
(k
==
0
)
{
printf(
"
%d\n
"
, w
+
1
);
system(
"
pause
"
);
return
0
;
}
f[k
+
7500
]
=
true
;
queue[rear
++
]
=
k;
dp[k
+
7500
].dx
=
k;
dp[k
+
7500
].q
=
w
+
1
;
for
(l
=
0
; l
<
n; l
++
) dp[k
+
7500
].da[l]
=
dp[d
+
7500
].da[l];
dp[k
+
7500
].da[i]
=
-
dp[d
+
7500
].da[i];
}
}
d
=
queue[front
++
];
w
=
dp[d
+
7500
].q;
}
while
(front
<=
rear);
j
=
7500
;
bool
isFind
=
false
;
for
(i
=
0
; i
<
7500
; i
++
)
{
if
(f[j
+
i])
{
isFind
=
true
;
if
(ans
>
dp[j
+
i].q) ans
=
dp[j
+
i].q;
}
if
(f[j
-
i])
{
isFind
=
true
;
if
(ans
>
dp[j
-
i].q) ans
=
dp[j
-
i].q;
}
if
(isFind)
break
;
}
printf(
"
%d\n
"
, ans);
system(
"
pause
"
);
return
0
;
}
posted on 2006-10-29 20:42
豪 阅读(779)
评论(0) 编辑 收藏 引用 所属分类:
ACM题目