?? 1794 -- castle walls.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0061)http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1794 -->
<HTML><HEAD><TITLE>1794 -- Castle Walls</TITLE>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<STYLE type=text/css>A {
TEXT-DECORATION: none
}
A:hover {
COLOR: red; TEXT-DECORATION: underline
}
</STYLE>
<META content="MSHTML 6.00.2900.2722" name=GENERATOR></HEAD>
<BODY vLink=blue aLink=blue link=blue leftMargin=5><A name=top></A>
<TABLE style="BORDER-COLLAPSE: collapse" borderColor=#ffffff width=980
border=1><TBODY>
<TR>
<TD align=middle colSpan=5><IMG height=97
src="1794 -- Castle Walls.files/logo.jpg" width=980 border=0></TD></TR>
<TR vAlign=top align=middle bgColor=#6589d1>
<TH width=196>Online Judge</TH>
<TH width=196>Problem Set</TH>
<TH width=196>Authors</TH>
<TH width=197>Online Contests</TH>
<TH width=197>User</TH></TR>
<TR vAlign=top align=middle bgColor=#f1f1fd>
<TD><A href="http://acm.pku.edu.cn/JudgeOnline/bbs">Web Board</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/">Home Page</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/faq.htm"
target=_blank>F.A.Qs</A><BR>Announcement</TD>
<TD>
<FORM action=gotoproblem method=get><A
href="http://acm.pku.edu.cn/JudgeOnline/problemlist">Problems</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/submitpage">Submit
Problem</A><BR><A href="http://acm.pku.edu.cn/JudgeOnline/status">Status
(Online)</A><BR><FONT color=blue>Prob.ID:</FONT><INPUT size=6 name=pid><INPUT type=submit value=Go name=pb1></FORM></TD>
<TD>
<FORM action=searchuser method=get><A
href="http://acm.pku.edu.cn/JudgeOnline/registerpage">Register</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/modifyuserpage">Update your
info</A><BR><A href="http://acm.pku.edu.cn/JudgeOnline/userlist">Authors
ranklist</A><BR><INPUT size=10 name=user_id><INPUT type=submit value=Search name=B1></FORM></TD>
<TD><FONT color=#1a5cc8>Current Contest</FONT><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/pastcontests">Past
Contests</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/contests">Scheduled
Contests</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/awardcontest_announce.htm"
target=_blank><FONT color=red>Award Contest</FONT></A></TD>
<TD align=left><IFRAME border=0 align=middle
src="1794 -- Castle Walls.files/login.htm" frameBorder=0 width=197
scrolling=no height=90></IFRAME></TD></TR></TBODY></TABLE>
<TABLE width="100%" background="1794 -- Castle Walls.files/table_back.jpg"
border=0>
<TBODY>
<TR>
<TD>
<P align=center><FONT color=blue size=5>Castle Walls</FONT></P>
<P align=center>Time Limit:1000MS Memory Limit:30000K<BR>Total
Submit:404 Accepted:110 </P><B><FONT color=#333399
size=5>Description</FONT></B>
<P><FONT face="Times New Roman" size=3>Background <BR>In medieval times,
knights commanded big armies of peasants. When they had to storm a castle
they would line up neatly in front of the castle's wall and throw their
grappling hooks over the walls. If one does not throw straight it can
easily happen that two hooks cross, making it impossible for the two
peasants to climb the wall. That's why every knight made his peasants
practice a lot so that this would not happen in combat. <BR>Due to the
recent Sir Arthur-Madam Claire Marriage (ACM), two peasant armies have to
be merged. <BR>Traditionally Sir Arthur's peasants wear blue and Madame
Claire's peasants wear red. When practicing together, both armies mix up
in front of a castle's wall. On Sir Arthur's command, they all throw their
grappling hooks. Due to their perfect training the hooks will never cross
within an army, however it can happen that a hook thrown by a blue peasant
crosses one thrown by a peasant of the red army. <BR>For statistical
purposes, Sir Arthur now needs to find out how many grappling hooks have
crossed so that he can measure how well their armies have already been
merged. <BR>Problem <BR>Given the positions of blue and red peasants as
well as the positions they threw their grappling hooks at,determine how
many distinct pairs of blue and red peasants crossed their hooks. <BR>If
there are n blue and m red peasants, the positions in the line where the
peasants are standing are numbered from 1 to n + m. The positions on the
castle's wall are numbered from 1 to n + m as well,where position i is
directly opposite of position i on the line the peasants are standing on.
A grappling hook thrown from position i to j is said to cross another hook
thrown from k to l if and only if <BR>(i < k and j >= l) or (i >
k and j <= l) <BR>Grappling hooks of the same color will never cross
each other, nor will two peasants occupy the same position on the line.
However, two hooks (of different color) can be thrown to the same position
in which case they are said to cross each other as
well.</FONT></P><B><FONT color=#333399 size=5>Input</FONT></B>
<P><FONT face="Times New Roman" size=3>The first line contains the number
of scenarios. <BR>In each scenario, you are first given a line with two
integers n and m, the number of blue and red peasants, respectively (1
<= n,m <= 30 000). <BR>The next n lines describe the blue peasants
followed by m more lines for the red peasants. Each line consists of two
integer i and j separated by a space, indicating the peasant's position i
and the position j he threw his grappling hook to (1 <= i, j <= n +
m).</FONT></P><B><FONT color=#333399 size=5>Output</FONT></B>
<P><FONT face="Times New Roman" size=3>For each scenario first output a
line "Scenario #i:" where i is the number of the scenario starting with 1,
followed by a line containing the number of distinct pairs of peasants
whose grappling hooks are crossed,and print a blank line at the end of
each scenario.</FONT></P><B><FONT color=#333399 size=5>Sample
Input</FONT></B>
<P><FONT face="Times New Roman" size=3><PRE>2
2 2
1 2
3 4
2 1
4 3
2 3
1 3
2 5
5 3
3 1
4 2</PRE></FONT>
<P></P><B><FONT color=#333399 size=5>Sample Output</FONT></B>
<P><FONT face="Times New Roman" size=3><PRE>Scenario #1:
2
Scenario #2:
6
</PRE></FONT>
<P></P><B><FONT color=#333399 size=5>Source</FONT></B>
<P><FONT face="Times New Roman" size=3>TUD Programming Contest 2004,
Darmstadt, Germany</FONT></P></TD></TR></TBODY></TABLE><FONT color=#333399
size=3>
<P align=center>[<A
href="http://acm.pku.edu.cn/JudgeOnline/submitpage?problem_id=1794">Submit</A>]
[<A href="javascript:history.go(-1)">Go Back</A>] [<A
href="http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1794">Status</A>]
[<A href="http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=1794">Discuss</A>]
</FONT></P>
<P><IMG height=29 src="1794 -- Castle Walls.files/home.jpg" width=40
border=0><FONT size=3><A href="http://acm.pku.edu.cn/JudgeOnline/">Home Page</A>
</FONT> <IMG height=29 src="1794 -- Castle Walls.files/goback.jpg"
width=40 border=0><FONT size=3><A href="javascript:history.go(-1)">Go
Back</A> <IMG height=29 src="1794 -- Castle Walls.files/top.jpg"
width=40 border=0><A
href="http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1794#top">To
top</A></FONT><BR>
<HR>
<P align=center><FONT size=3>All Copyright Reserved 2003-2005 Ying Fuchen,Xu
Pengcheng<BR>Any problem, Please <A href="mailto:hawking@pku.edu.cn">Contact
Administrator</A></FONT></P></BODY></HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -