2012福建省信息学奥林匹克CCF NOIP夏令营第一天训练(附解题思路及参考程序).doc

2012福建省信息学奥林匹克CCF NOIP夏令营第一天训练 （附解题思路及参考程序） 问题名称 文件名 输入文件 输出文件 时限 分值 足球 football football .in football.out 1s 100 数列排序 seqsort seqsort.in seqsort.out 1s 100 计算概率 calculate calculate.in calculate.out 1s 100 三角形牧场 pasture pasture.in pasture.out 1s 100 数列 seq seq.in seq.out 1s 100 内存限制均为256M 足球(football) 【问题描述】 我们当中有很多热爱中国足球的同学，我们都知道中超（中国足球超级联赛）的规则： 一场比赛中，若获胜（即你的得分严格大于对手得分）则获得3的积分，若打平（即你的得分等于对手得分）则获得1分，若失败（即你的得分严格小于对手得分）获得0积分。 这个问题很简单，假设N轮比赛中你一共攻入S个球，丢掉T个球，那么你可能获得的最大得分和最小得分是多少？ 【输入文件】 多组数据，每组数据一行： 一行三个整数S、T、N（S、T = 0，N = 1）。 【输出文件】 对于每组数据输出一行，两个整数表示最大得分和最小得分。 【样例输入】 1 1 1 1 1 2 【样例输出】 1 1 3 2 数列排序(seqsort) 【问题描述】 给定一个数列{an}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？ 【输入文件】 第一行，正整数n (n=100,000)。 以下若干行，一共n个数，用空格分隔开，表示数列{an},任意-231ai231。 【输出文件】 只有一行，包含一个数，表示最少的交换次数。 【样例输入】 8 8 23 4 16 77 -5 53 100 【样例输出】 5 计算概率(calculate) 【问题描述】 小明有n个长度不一的小木棍，这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l，让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l，则小明胜，否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。 【输入文件】 输入包含两行。第一行为两个整数n和l，其中n和l都不超过100000。第二行包含n个整数，分别为n个木棍的长度。 【输出文件】 输出包含一个实数，小明胜出的概率，保留两位小数。 【输入样例】 4 5 1 2 3 4 【输出样例】 0.67 三角形牧场（pasture） 【问题描述】 和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N（3≤N≤40）块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。 请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。 【输入文件】 第1行：一个整数N 第2..N＋1行：每行包含一个整数，即是木板的长度。 【输出文件】 仅一个整数：最大牧场面积乘以100然后舍尾的结果。 如果无法构建，输出-1。 【输入样例】 5 1 1 3 3 4 【输出样例】 692 数列(seq) 【问题描述A1、A2、A3、……An，其中A1=0，且对任意一项Ai满足|Ai-Ai+1|=1（1=in）。设S=A1+A2+A3+……+An，表示前n项之和。 现在给出数列长度n与数列前n项之和S，要求： 输出满足条件的数列的总数。 输出满足条件的100个数列（如果不满100个就全部输出）。 【输文件】 n和S（1=n=100），用1个空格隔开。 【输出文件】 1行一个整数t（0=t=263-1），表示满足条件的数列总数。 接下来每行输出一个数列，数列各项之间用一个空格隔开。 若满足条件的数列数目不满100个，全部输出即可。 【样例输入4 0 【样例输2 0 -1 0 1 0 1 0 -1 足球 先全部分配进球数到每场 有不够的就把失球全部放在那一场里 否则将进球与失球抵消 反之亦然 参考程序： const inf = ; ouf = ; maxS = 10; maxT = 10; maxN = 20; var s, t, n : int64; p, q : int64; begin assign(input, football.in); assign(output, football