FOI2分区模拟赛试题

大榕树 \ 信息学奥赛 \ 竞赛题库

FOI2分区模拟赛试题

原文链接：http://www.mydrs.org/program/list.asp?id=445
1.银币问题。(t1.exe，30分，时限1s)有n(<=10000)银币，C1，C2，...
，Cn中有一块不合格，不合格的银币比较重。现用一天平找不出合格的
来，要求在最坏的情况下，用的天平次数最少。

输入文件：input1.txt。文件仅一行，为N。
输出文件：output1.txt。输出使用天平的最少次数M。

示例：input1.txt output1.txt
4 2
---------------------------------------------------------------
2.魔兽争霸。(t2.exe，30分，时限1s)史前的一个部落里，混居着三个种
族：人族(man=M)，兽族(pig=P)和不死族(man&pig=&)。他们之间的称呼
只有“人”和“兽”两种。
人很诚实的称呼人和兽本来的名称，但是人为了防御兽族的侵害，拉拢
了不死族，称不死族为“人”。兽是很自大的动物，他称呼自己为“人”，
称呼其他种族为“兽”。而不死族很虚伪，他们称自己为“兽”，称其他
种族为“人”。
你的任务是根据他们之间的称呼确定每个个体所属的种族。
输入文件：input2.txt。给出了部落中任一个个体的对另一个个体的称
呼。格式：第一行为个体的总数N(<=100)，下面是一个N行N列的矩阵，第I
行第J个字符表示个体I对个体J的称呼，用“M”表示人，用“P”表示兽，
用“S”表示自己(I=J)。
输出文件：outpunt2.txt。部落中各族中所包含的个体个数，若有多种
组成方式，要全部输出。格式：若无解，则输出0，否则第一行输出组成方式
的总数为K，随后的K行，每行表示一种组成方式，第I行的格式为：
<i>M=…P=…&=…。
示例： input2.txt output2.txt
5 3
SMMMM <1>M=5 P=0 &=0
MSMMM <2>M=4 P=0 &=1
MMSMM <3>M=0 P=5 &=0
MMMSM
MMMMS
--------------------------------------------------------------------
3.分割多边形(t3.exe，40分，时限5s) (50分)
预备知识:平面上的点可用坐标(X,Y)表示,X,Y为绝对值不超过10000的整
数.平面上的直线L可用A*X+B*Y+C=0表示,其中A,B,C为常数.点(X1,Y1)在直
线L上的充分必要条件是 A*X1+B*Y1+C=0.两个点(X1,Y1),(X2,Y2)在直线L的
同侧的充分必要条件是 (A*X1+B*Y1+C)与(A*X2+B*X2+C)同号.由三个点(X1,Y1)
,(X2,Y2),(X3,Y3)构成的三角形的面积等于 0.5*│(X2-X1)*(Y3-Y1)-(Y2-Y1)
*(X3-X1)│,这里│a│表示数a 的绝对值.一个多边形为凸多边形的充分必要
条件是:对任意给定的一条边,其余各顶点都在该边所在的直线的同侧.
编程要求:
(1)(20分) 判断所给的多边形是否为凸多变形.
(2)(30分) 对于凸多边形,则应求出一条对角线,它将凸多边形分割成两部
分,这两部分的面积之差为最小.最后输出:① 该对角线对应的两顶点的编号
及坐标.② 两部分的面积及面积之差.
输入:由文本文件input3.txt按下述格式输入一个N边形的已知数据:
第1行:整数N (200≥N≥4,N为多边形的边数)
第 2--N+1 行: 每行两个整数,中间用空格隔开 (第i行为N边形第i-1个顶点
坐标按逆时针方向排列,顶点号(1--N)不得改动).
输出：第1行如果是凸多边形，输出1，否则输出0
第2行如果是凸多边形，输出对角线对应的两顶点的编号及坐标，格式
为：(x1,y1)
第3行如果是凸多边形，输出两部分面积及面积之差，保留2位小数，用
空格隔开。

作者：Fruit Ikari
来源：
时间：2002-11-06

上一篇：第八届普及组初赛参考答案
下一篇：各地信息学分区初赛分数线