?? problem 1108.htm
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1108 -->
<HTML><HEAD><TITLE>Problem 1108</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2769" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1108.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>FatMouse's Speed</FONT></CENTER>
<HR>
<CENTER><FONT color=green>Time limit:</FONT> 1 Seconds <FONT
color=green>Memory limit: </FONT>32768K </FONT><FONT
color=blue>Special Judge</FONT><BR><FONT color=green>Total Submit:</FONT>
1240 <FONT color=green>Accepted Submit:</FONT> 567
</CENTER>
<HR>
<P><IMG src="Problem 1108.files/showimg.jpg" align=right> FatMouse believes that
the fatter a mouse is, the faster it runs. To disprove this, you want to take
the data on a collection of mice and put as large a subset of this data as
possible into a sequence so that the weights are increasing, but the speeds are
decreasing. </P>
<P><B>Input Specification</B>
<P>Input contains data for a bunch of mice, one mouse per line, terminated by
end of file.
<P>The data for a particular mouse will consist of a pair of integers: the first
representing its size in grams and the second representing its speed in
centimeters per second. Both integers are between 1 and 10000. The data in each
test case will contain information for at most 1000 mice.
<P>Two mice may have the same weight, the same speed, or even the same weight
and speed. </P>
<P><B>Output Specification</B>
<P>Your program should output a sequence of lines of data; the first line should
contain a number <TT>n</TT>; the remaining <TT>n</TT> lines should each contain
a single positive integer (each one representing a mouse). If these <TT>n</TT>
integers are <TT>m[1]</TT>, <TT>m[2]</TT>,..., <TT>m[n]</TT> then it must be the
case that <PRE> W[m[1]] < W[m[2]] < ... < W[m[n]]
</PRE>and <PRE> S[m[1]] > S[m[2]] > ... > S[m[n]]
</PRE>In order for the answer to be correct, <TT>n</TT> should be as large as
possible.
<P>All inequalities are strict: weights must be strictly increasing, and speeds
must be strictly decreasing. There may be many correct outputs for a given
input, your program only needs to find one. </P>
<H3>Sample Input</H3><PRE>6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
</PRE>
<H3>Output for Sample Input</H3><PRE>4
4
5
9
7
</PRE>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>Zhejiang University Training
Contest 2001</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1108">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=2">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1108">Status</A> </CENTER>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/"><FONT color=red>Zhejiang University
Online Judge</FONT></A> <A href="http://acm.zju.edu.cn/"><FONT
color=red>V1.0</FONT></A><BR></CENTER></BODY></HTML>
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -