下载文档原格式
CCF全国信息学奥林匹克联赛NOIP普及组复赛试题CCF全国信息学奥林匹克联赛（NOIP2018）复赛普及组（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-****************，内存32GB。
上述时限以此配置为准。
4、只提供Linux格式附加样例文件。
5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。
1. 标题统计(title.cpp/c/pas)【问题描述】凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。
统计标题字符数时，空格和换行符不计算在内。
【输入格式】输入文件名为title.in。
输入文件只有一行，一个字符串s。
【输出格式】输出文件名为title.out。
输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。
见选手目录下的title/title1.in和title/title1.ans。
【输入输出样例1说明】标题中共有3个字符，这3个字符都是数字字符。
见选手目录下的title/title2.in和title/title2.ans。
【输入输出样例2说明】标题中共有5个字符，包括1个大写英文字母，1个小写英文字母和2个数字字符，还有1个空格。
由于空格不计入结果中，故标题的有效字符数为4个。
【数据规模与约定】规定|s|表示字符串s的长度（即字符串中的字符和空格数）。
对于40%的数据，1≤|s|≤5，保证输入为数字字符及行末换行符。
对于80%的数据，1≤|s|≤5，输入只可能包含大、小写英文字母、数字字符及行末换行符。
对于100%的数据，1≤|s|≤5，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。
NOIP2006复赛模拟题（普及组水平）（时间：3小时）注意事项：1. 严格按照题目所要求的格式进行输入、输出。
2. 题目测试数据有严格的时间，超时不得分。
所有题目的时限均为1秒。
3. 输入文件格式不用判错。
程序文件名、输入输出文件名等请严格按照要求。
4. 本次比赛共4题。
5. 同时提交pas、exe文件，请使用freepascal编译。
编译后的exe请留意是否能正确运行。
为方便测试，所有pas、exe均存在一个文件夹中，该文件夹用你的中文名字命名，然后把整个文件夹压缩为一个rar文件（该文件也是用你的中文名字命名）提交到老师邮箱：*************。
第一题位置（posi.pas）求数A在数组B中的位置.输入及格式：第一行是数A ，一维数组B的元素个数N（N<=105），中间用空格隔开。
第二行是已按升序排列的一维数组B (-32768<B[i],A<32767),数间用空格隔开。
输出及格式：数A在B中的下标。
B中如果存在多个A，则输出下标最小的一个。
如果B 中不存在A，则输出“-1”输入样例1：3 61 3 3 4 5 10输出样例1：2输入样例2：1 33 4 5输出样例2：-1第二题面积（area.pas）一幅图由0和*组成，编程计算由“*”号所围成的图形的面积。
面积是指*号所围成的闭合曲线中0的数目。
输入：由0，*组成的图输出：面积数输入样例：0000000000000**000000*00*0000*000*00000***000000000000输出样例：5输入样例2：000000000000*000*0*0输出样例2：第三题阶乘位数（jc.pas）问题描述：在很多软件中需要用到较大的整数。
比如一些软件将大数用于数据安全传送的密匙或者密码编译等等。
在这个问题中，你要根据给你的整数，算出这个数的阶乘的位数。
输入格式：输入文件包含若干行整数。
第一行为n，表示有n组数据，接下来是n行，每行一个整数m（1≤m≤107）。
【NOIP复赛模拟题（六）】【第1题】卫星照片Time Limit:1000MS Memory Limit:65536KTotal Submit:12 Accepted:3Description卫星照片（satel.pas\c\cpp）【题目描述】农夫John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行C (1 <= C <= 75) 列的字符矩阵表示.如下图:．．．．．．．．．．．．．．．．．．．．＃＃＃＃＃．．．．．．．＃＃．．．．＃＃＃＃＃．．．．．．＃＃．．．．．．．．．．．．．．．．．．．．．＃．．．．．．．＃＃＃．．．．．＃．＃．．．．．＃＃＃＃＃．．．．．．．图上的一块相连通的"#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连.而下面的两块则是分开的:．．．．．＃．．．．＃．．．．．John现在根据卫星照片上的的这些"#"块的形状来判断哪些是牛群,哪些是房间.如果一个"#"块形状的边是水平或垂直的矩形,则是房间.其它的则认为都是牛群.在第一个图中,有三个房间( 2x1, 2x5, and 1x1)和2群牛.请根据输入文件中的数据,统计出房间数和牛群数.数据中牛群不会包围另一个牛群或房间.Input输入文件satel.in第一行,两个整数: R 和 C.2..R+1行: 第i+1 行表示照片的第i 行情况,由 C 字符组成.Output输出文件satel.out的第一行: 房间数.第二行: 牛群数.Sample Input5 8#####..######.##......#..###...#.###..##Sample Output22Source解法：对一个区域进行搜索，记录该区域内的＃的个数，记录这个区域的最大和最小的x,y的值，若为矩形则＃的个数与最大和最小的x,y的值可用(maxx-minx+1)*(maxy-miny+1)=siz ；来表达关系。
noip普及组复赛试题及答案一、选择题1. 在计算机科学中，以下哪个概念与数据结构最相关？A. 算法B. 操作系统C. 网络协议D. 编译原理答案：A2. 以下哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D3. 在C++中，以下哪个关键字用于定义类？A. structB. unionC. enumD. typedef答案：A4. 以下哪个选项不是数据库管理系统（DBMS）的特性？A. 数据持久性B. 数据共享C. 数据加密D. 数据独立性答案：C5. 在计算机网络中，TCP和UDP协议分别属于哪一层？A. 传输层B. 应用层C. 网络层D. 物理层答案：A二、填空题1. 在计算机程序中，______ 用于定义数据的存储方式和组织形式。
答案：数据结构2. 一个算法的时间复杂度为O(1)，表示该算法的执行时间与输入数据的规模______。
答案：无关3. 在C++中，______ 是一种特殊的类，它提供了一种方式来定义数据类型。
答案：typedef4. 数据库管理系统（DBMS）通常包含数据定义语言（DDL）、数据操纵语言（DML）和______。
答案：数据控制语言（DCL）5. 在计算机网络中，______ 协议负责在网络层进行数据包的路由选择。
答案：IP三、简答题1. 请简述面向对象编程（OOP）的三个基本特征。
答案：封装、继承、多态2. 描述二分查找算法的基本步骤。
答案：二分查找算法的基本步骤包括：首先确定数组是有序的，然后取中间元素与目标值比较，如果中间元素等于目标值，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找，直到找到目标值或查找范围为空。
四、编程题1. 编写一个函数，实现对整数数组的排序。
答案：以下是一个简单的冒泡排序算法实现：```cppvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);}}}}```2. 编写一个函数，实现计算一个整数的阶乘。
1．计算机发明之前，数学家们需要手工进行数学计算。
遇到复杂计算往往要花去大量时间，而且正确率也不高。
现在可不一样了，有了计算机人们能快速而正确地求解数学问题。
小雪是个中学生，可已经能熟练的运用计算机编写程序了。
为了提高自己的计算机水平，小学经常将数学老师布置的题目用计算机加以求解。
有一次，数学老师提出这样一个问题：对于给定的一对自然数m 与n )(n m 在m 与n 之间（包含m 和n ）有多少素数呢？小雪很快得出了答案。
现在请你也编写程序实现。
（1不为素数）输入：文件的第一行为一个数k ，表示有k 对自然数。
以后k 行每行有两个自然数，第一个自然数为m ，第二个自然数为n 。
输出：依次输出每一对数之间的素数个数。
每个结果占一行。
例如：输入:21 510 20输出:342．当前有面值分别为a 分，b 分，c 分，d 分(a>b>c>d)的硬币，请给出找n 分钱的最佳方案（要求找出的硬币数目最少）输入:a,b,c,d,n输出:硬币各几个例:输入:25 10 5 1 36输出:25 10 5 11 1 0 1又例:输入:10 8 5 1 13输出: 10 8 5 10 1 1 03．在下面的算式中每个“#”都表示一个素数数字。
###* ###—————#####请编写程序确定这些数字，输出所有的解。
注意：ABC*DEF 与DEF*ABC 为同一种解的两种不同形式。
请不要将同一组解以不同形式多次输出。
屏幕输出：依次打印输出每一种解。
每行表示一种解，格式为：###*### = ##### 4．一个整数被称为“怪数”，它至少有两对因数，并且其中有一对因数的差等于另一对因数的和。
例如：6是怪数，因为6 × 1 = 6, 2 × 3 = 6, 6 - 1 = 2 + 3；24也是怪数，因为12 - 2 = 6 + 4。
编程输入A和B表示的整数区间（1 ≤ A ≤ B ≤ 32767），输出该区间的所有怪数，一行一个，若没有输出为空。
一、新龟兔赛跑（文件名xgtsp.pas）新龟兔赛跑比赛即将举行，此次龟兔赛跑比赛的规则与以往有所不同，不再考察兔子和乌龟谁在最短的时间内跑完规定的路程，而是考察谁在规定时间内跑的路程更长，且兔子和乌龟跑步都是匀速的。
由于兔子的坏习惯，它总喜欢把比赛的总时间T小时中的K小时拿来睡觉。
现在给你比赛的总时间T、兔子的睡觉时间K、兔子的速度U、乌龟的速度V，需要你求出该次比赛谁最后获胜。
输入第一行为一个整数X，表示有X组输入数据。
每组数据只有一行，包括4个数T、K、U、V (1 ≤ T≤ 300，0 ≤ K ≤ T，1 ≤ U ≤ 100，1 ≤ V ≤ 100)。
对于每组数据，输出只有一个数，如果兔子获胜则输出-1，如果乌龟获胜则输出1，如果同时到达则输出0。
允许输入一组数后立即输出对应的结果。
样例输入：21 12 16 2 6 3样例输出：1-1varv,u,t,k,n,i:integer;beginreadln(n);for i:=1 to n do beginreadln(t,k,u,v);if v*t>U*(t-k) then writeln(1);if v*t<U*(t-k) then writeln(-1);if v*t=U*(t-k) then writeln(0);end;end.1、输入：26 2 6 28 6 8 2输出：-12、输入：2300 280 60 20120 0 12 13输出：113、输入：3100 20 50 30100 50 45 25100 80 27 17输出：-1114、输入：3150 77 29 23127 11 22 13139 22 13 7输出：1-1-1二、小球路程（文件名：XQLC.PAS ）已知小球从100米高度自由下落，落地后反弹起，又落地，又弹起，……。
每次弹起的高度都是上一次高度的一半。
求小球第N次反弹起的高度和球在整个过程所经过的路程（包括下落和反弹），用键盘输入N，输出反弹高度和经过路程，结果保留两位小数。
冲刺NOIP2021模拟试题六（提高组复赛）问题：1油滴膨胀[问题描述]在一个长方形框子里，最多有n（0≤n≤6）个相异的点。
在其中任何一个点上给一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。
必须等一个油滴扩展完毕才能放置下一个油滴。
那么应该按照怎样的顺序在这n个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）注：圆的面积公式v=pi*r*r，其中r为圆的半径。
【输入】第一行是一个整数n。
第二行为长方形边框一个顶点及其对角顶点的坐标，x，y，x’，y’。
接下去n行，每行两个整数xi，yi，表示盒子内n个顶点的坐标。
以上所有的整数都在[-1000,1000]内。
【输出】一行，一个整数，矩形框中剩余的最小空间（结果四舍五入到输出）。
[输入示例]，20010103377【输出样例】502.顺序[问题描述]虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。
有一天，她在纸上写了一串数字：1,1,2,5,4。
接着他擦掉了一个1，结果发现剩下1,2,4都在自己所在的位置上，即1在第1为，2在第2为，4在第4位。
她希望擦掉某些数后，剩下的数列中在自己的位置上的数尽量多。
她发现这个游戏很好玩，于是开始乐此不彼地玩起来…不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！【输入】第一行是数字n，代表序列的长度。
接下来一行为n个用空格隔开的正整数，第i行表示数ai。
【输出】一行中的整数表示删除某些数字后最后剩余序列中的最大数字数，即AI=I。
[示例]序列in5的最大数字11254sequence.out3数据量表对于20%的数据，n≤20对于60%的数据，n≤100对于100%的数据，n≤10003.软件一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的多用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能有一个人独立完成而不能由多个人协同完成。
模拟题11. 1.分数(mark.cpp)高考分数刚刚公布.共有n人参加考试,为了便于填报志愿,教育部把所有考生的成绩平均分为m档.保证n是m的倍数.考试成绩名次在(k-1)*(n/m)+1名到k*(n/m)名的考生被分在第k档(k=1,2,3…..m).并列第i名的所有考生都算第i名.小Y刚参加完高考,迫切想知道自己被分在第几档,你能帮助他吗?输入格式:第一行两个整数n,m<=1000,保证n是m的倍数.接下来n行,每行一个整数ai表示第i 个考生的成绩.最后一行,一个整数x,1<=x<=n,表示询问第i 个考生被分在哪一档.输出格式:一行一个数,表示被分在哪一档.输入输出样例:mark.in3 36326516243mark.out32. 2.背单词(words.cpp)英语四级考试临近了,小Y却发现他已经把以前学的单词几乎忘光了.好在现在离考试还有一段时间.小Y决定从现在开始夜以继日地背单词,也就是一天24小时地背. 今天的日期(时间)是yyyy年mm月dd日hh时min分.这之间的所有时间小Y都用来背单词了,那么考试之前他最多能背多少个单词呢?时间紧张,小Y只管数量不管质量.当然有的单词长一些,有的单词短一些.长单词难背一些,短的单词好背一些.根据小Y的经验,他能一眼看出背某一个单词需要的时间,以分钟记. 现在给你一个字典,请你挑出最多的单词使小Y能在考前背出来.输入格式:第一行一个整数n,表示字典中的单词数,n<=5000.接下来n行,每行一个整数表示背这个单词需要的时间,以分钟记.小于等于10000,(这个单词本身是什么并不重要)接下来两行依次是当前时间和考试时间.时间给出的格式是:yyyy-mm-dd-min.例如:2010-04-22-02:00,采用24小时制,每天从00:00-23:59.年份从0000到9999.输出格式:一行,一个数,表示考前小Y最多能背出的单词数.输入输出样例:words.in2112007-06-23-11:592007-06-23-12:00words.out13溶液模拟器(simulator.cpp)小Y到网上下载了一个溶液配置模拟器。
Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。
一共有n 张地毯，编号从1 到n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。
注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】输入文件名为 carpet.in。
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
【输出】输出文件名为 carpet.out。
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。
【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。
【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。
【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。
置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。
注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。
NOIP 2011复赛练习卷（六）
1、数三角形个数（triangle.pas/c/cpp）
【问题描述】
求在M x N的网格上有多少的格点三角形。
下面的图形说明在1x2的网格上共有18个不同的三角形。
【输入】(triangle.in)
输入文件有多组测试数据，每组一行，为两个整数N, M（1 <= N, M <= 100），之间用一个空格隔开，文件最后一行以0 0结束，但不要求0X0网格有多少个三角形。
【输出】(triangle.out)
对于每组输入，请输出一个数，表示不同三角形的个数。
【输入样例】
1 1
1 2
0 0
【输出样例】
4
18
2、线性递推式(recursion.pas/c/cpp)
【问题描述】
DP的实现形式之一是递推，因此递推在OI中十分重要。
在某信息学的分支学科中，小明学会了如何求一阶线性递推数列。
由于他想在正在学习主干学科，因此希望知道求出N 阶线性递推数列。
为此，他了解到了以下的内容：
一个N阶线性递推式是这样的式子：
F i=A0F i-n + A1F i-(n-1) + … + A n-1F i-1 + A n
也就是说，这个数列的每一项都是由它之前的连续N项相加所得，且其中还包括一个常数A n。
小明对这如何去求这个式子一筹莫展，因此请你来帮助他。
你的任务就是对于一个给定的N阶线性递推式，求出它的第K项是多少。
【输入】(recursion.in)
第1行：两个整数N，K，其中N表示这个式子是N阶线性递推式，K表示你需要求得的那一项。
第2行：为N+1个整数A0，A1，…，A n，表示这个递推式的系数。
第3行：为N个整数F0，F1，…，F n-1，表示数列的初始值。
【输出】(recursion.out)
仅一行，为一个整数，表示这个数列第K项的值。
由于数据较大，你只需输出结果 mod 9937后的值。
【输入样例】
2 10
1 1 0
0 1
【输出样例】
55
【数据范围】
50%的数据： N<=K<=10^6；
100%的数据： 1<N<10, N<=K<=101^8, 1<=Ai、Fi<=10^4。
3、化学反应(alchemy.pas/c/cpp)
【问题描述】
JSOI教练组对选手的要求是：不但在信息学竞赛的知识与能力方面要突出，同时还要全面发展，基础知识也要功底扎实。
于是，在一次集训时，教练组给出了如下的一道题：给定K种化学物质和N种反应类型，每种反应都有一些反应物和和生成物，且反应需要一定的时间。
假设每次反应后的若干生成物都可以完全分离，且每次反应后的生成物可以立即用于其他反应，每种物质的数量都是无限的。
现在，请你编写一个程序，给定一些已有物质后，求由此得到一种指定物质至少要多少时间。
【输入】(alchemy.in)
第1行：4个整数，分别为K (3<=K<=250)、N (3<=N<=500)，已有物质的数量M (1<=M<K)和所求物质的编号；
接下来是关于N种反应的描述，每种反应的描述有3行，第一行是反应的时间，第二行第一个数是这个反应的反应物的数量，接着是这些反应物的编号；第三行第一个数是生成物的数量，接着是生成物的编号。
已有物质的编号总是为1到M，编号为M+1到K的为开始时没有的物质。
【输出】(alchemy.out)
1行：一个整数，表示生成指定的物质需要的最短的时间。
如果无法生成指定的物质，则输出-1。
4、交错匹配（cross.pas/c/cpp）
【问题描述】
有两排非负整数A[1..N]和B[1..M]，如果A[i]=B[j]=K，那么，可以在A[i]、B[j]之间连一条线，称为一条K匹配。
每个数至多连一条线。
另外，每个K匹配都必须跟一个L匹配相交，且K<>L。
现在，要求一个最大的匹配数。
例如，如下两行数的最大匹配数为8。
一个数最多只能和另一个数连线。
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2
4 12 1
5 5 3
【输入】（cross.in）
第1行：两个正整数N和M。
第2行：N个自然数，表示A[i]。
第3行：M个自然数，表示B[i]。
【输出】（cross.out）
输出一个数字，即最大匹配数。
【输入样例1】
12 11
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2
4 12 1
5 5 3
【输出样例1】
8
【输入样例2】
4 4
1 1 3 3
1 1 3 3
【输出样例2】
【数据规模】
30%的数据： N,M<=30；
60%的数据： N,M<=200；
100%的数据： N,M<=1000, 0< 所有数 <=32767。
5、树网的核（core.pas/c/cpp）
【问题描述】
设T=(V, E, W)是一个无圈且连通的无向图（也称为无根树），每条边都有一个正整数的权值，我们称T为树网（tree network），其中V，E分别表示结点与边的集合，W表示各边长度的集合，并设T有n个结点。
路径：树网中任何两结点a，b都存在唯一的一条简单路径，用d(a, b)表示以a, b为端点的路径的长度，它是该路径上各边长度之和。
我们称d(a, b)为a, b两结点间的距离。
D(v, P)=min{d(v, u), u为路径P上的结点}。
树网的直径：树网中最长的路径成为树网的直径。
对于给定的树网T，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。
偏心距ECC(F)：树网T中距路径F最远的结点到路径F的距离，即
ECC(F)=max{d(v, F)，v∈V}
任务：对于给定的树网T=(V, E, W)和非负整数s，求一个路径F，它们是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过s（可以等于s），使偏心距ECC(F)最小。
我们称这个路径为树网T=(V, E, W)的核（Core）。
必要时，F可以退化为某个结点。
一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。
下面的图给出了树网的一个实例。
图中，A-B与A-C是两条直径，长度均为20。
点W 是树网的中心，EF边的长度为5。
如果指定s=11，则树网的核为路径DEFG（也可以取为路径DEF），偏心距为8。
如果指定s=0（或s=1、s=2），则树网的核为结点F，偏心距为12。
【输入】
输入文件core.in包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。
其中n为树网结点的个数，s为树网的核的长度的上界。
设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。
例如，“2 4 7”表示连接结点2与4的边的长度为7。
所给的数据都是正确的，不必检验。
【输出】
输出文件core.out只有一个非负整数，为指定意义下的最小偏心距。
【输入输出样例1】
40%的数据满足：5<=n<=15
70%的数据满足：5<=n<=80
100%的数据满足：5<=n<=300，0<=s<=1000。
边长度为不超过1000的正整数。
