第四次（暴力枚举）

A - 一元三次方程求解

有形如：ax3+bx2+cx1+dx0=0
这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 −100 至 100 之间），且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后 2
位。
提示：记方程 f(x)=0
，若存在 2 个数 x1 和 x2，且 x1 之间一定有一个根。

输入格式

一行，4
个实数 A,B,C,D
。

输出格式

一行，3
个实根，并精确到小数点后 2
位。
Sample Input
1 -5 -4 20
Sample Output
-2.00 2.00 5.00

B - Cantor表

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

我们以 Z 字形给上表的每一项编号。第一项是 1/1
，然后是 1/2，2/1，3/1，2/2
，…

输入格式

整数 N(1≤N≤10000000)

输出格式

表中的第 N项。
Sample Input
7
Sample Output
1/4

D - 铺地毯

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标 系的第一象限）铺上一些矩形地毯。一共有 n
张地毯，编号从 1 到 n
。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 n+2
行。
第一行，一个整数 n
，表示总共有 n
张地毯。
接下来的 n
行中，第 i+1 行表示编号 i 的地毯的信息，包含四个正整数 a,b,g,k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 (a,b) 以及地毯在 x 轴和 y
轴方向的长度。
第 n+2
行包含两个正整数 x 和 y，表示所求的地面的点的坐标 (x,y)
。

输出格式

输出共 1
行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 −1
。

数据范围

对于 30%
的数据：有 n≤2
。
对于 50%
的数据：0≤a,b,g,k≤100
。
对于 100%
的数据：有 0≤n≤10000，0≤a,b,g,k≤100000
。

样例说明

样例1：

如下图，1
号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点 (2,2) 的最上面一张地毯是 3
号地毯。

样例2：

如上图，1
号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点 (4,5) 没有被地毯覆盖，所以输出 −1
。
Sample Input
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
Sample Output
3
Sample Input 2
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
Sample Output 2
-1

E - 三连击

将 1,2,⋯,9
共 9 个数分成 3 组，分别组成 3 个三位数，且使这 3 个三位数构成 1:2:3 的比例，试求出所有满足条件的 3
个三位数。

输入格式

无

输出格式

若干行，每行 3
个数字。按照每行第 1
个数字升序排列。
Sample Input
无
Sample Output
192 384 576
…
…

F - 最大公约数和最小公倍数问题(辗转相除法)

输入二个正整数 x0,y0(2≤x0<100000,2≤y0≤1000000)
，求出满足下列条件的 P,Q
的个数。条件：

1. P,Q
   

• 是正整数
  

• 要求 P,Q
  

  以 x0 为最大公约数，以 y0

1. 为最小公倍数。
   

试求：满足条件的所有可能的两个正整数的个数。

输入格式

2
个正整数 x0,y0
。

输出格式

1
个数，表示求出满足条件的 P,Q
的个数。
Sample Input
3 60
Sample Output
4

G - 连续自然数和

对一个给定的自然数 M
，求出所有的连续的自然数段（连续个数大于 1），这些连续的自然数段中的全部数之和为 M
。
例子：1998+1999+2000+2001+2002=10000
，所以从 1998 到 2002 的一个自然数段为 M=10000
的一个解。

输入格式

输入包含一个整数 M(10≤M≤2,000,000)
。

输出格式

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出的行按照第一个数从小到大排序，对于给定的输入数据，保证至少有一组解。
Sample Input
15
Sample Output
1 5
4 6
7 8
Sponsor 对一个给定的自然数 M
，求出所有的连续的自然数段（连续个数大于 1），这些连续的自然数段中的全部数之和为 M
。
例子：1998+1999+2000+2001+2002=10000
，所以从 1998 到 2002 的一个自然数段为 M=10000
的一个解。

输入格式

输入包含一个整数 M(10≤M≤2,000,000)
。

输出格式

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出的行按照第一个数从小到大排序，对于给定的输入数据，保证至少有一组解。
Sample Input
15
Sample Output
1 5
4 6
7 8

H - 约瑟夫

约瑟夫问题是这样的：n
个人站成一圈，从某个人开始数数（从 1 开始），每次数到 m
的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。
现在有 2k
个人站成一圈，k 个好人站在一起，k 个坏人站在一起。从第一个好人开始数数，你要确定一个最小的 m，使得在所有好人被杀死前，k
个坏人先被杀死。

输入格式

一个整数 k (1≤k≤15)
。

输出格式

一个整数 m
。
Sample Input
3
Sample Output
5
Sample Input 2
4
Sample Output 2
30

I - 子数整除

对于一个五位数 ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯a1a2a3a4a5
，可将其拆分为三个子数：
sub1=¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯a1a2a3
sub2=¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯a2a3a4
sub3=¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯a3a4a5
例如，五位数 20207
可以拆分成
sub1=202
sub2=020(=20)
sub3=207
现在给定一个正整数 k
，要求你编程求出 10000 到 30000 之间所有满足下述条件的五位数，条件是这些五位数的三个子数 sub1,sub2,sub3 都可被 k
整除。

输入格式

一个整数 k (0。

输出格式

每一行为一个满足条件的五位数，要求从小到大输出。不得重复输出或遗漏。如果无解，则输出"No"。
Sample Input
21
Sample Output
25252
27357
Sample Input 2
22
Sample Output 2
No

J - 手机

手机的键盘是这样的：

1        2 abc    3 def
4  ghi    5 jkl    6 mno
7  pqrs    8 tuv    9 wxyz
0  *#

要按出英文字母就必须要按数字键多下。例如要按出 x
就得按 9 两下，第一下会出 w，而第二下会把 w 变成 x。0
键按一下会出一个空格。
你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。

输入格式

一行一个句子，只包含英文小写字母和空格，且不超过 200
个字符。

输出格式

一行一个整数，表示按键盘的总次数。
Sample Input
i have a dream
Sample Output
23

K - 回文日期

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 8
位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2
位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。
牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8
位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。
一个 8
位数字是回文的，当且仅当对于所有的i （ 1≤i≤8 )从左向右数的第 i 个 数字和第 9−i 个数字（即从右向左数的第 i
个数字）是相同的。
例如：

• 对于 2016
  

  年 11 月 19 日，用 8 位数字 20161119

• 表示，它不是回文的。
  

• 对于 2010
  

  年 1 月 2 日，用 8 位数字 20100102

• 表示，它是回文的。
  

• 对于 2010
  

  年 10 月 2 日，用 8 位数字 20101002

• 表示，它不是回文的。
  

每一年中都有 12
个月份：
其中，1
、3、5、7、8、10、12 月每个月有 31 天；4、6、9、11 月每个月有 30 天；而对于 2 月，闰年时有 29 天，平年时有 28
天。
一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1. 这个年份是 4
   

   的整数倍，但不是 100

• 的整数倍；
  
• 这个年份是 400
  

1. 的整数倍。
   

例如：

• 以下几个年份都是闰年：2000
  

、2012、2016

• 。
  
• 以下几个年份是平年：1900
  

、2011、2014

• 。
  

  输入格式

  输入包括两行，每行包括一个 8
  位数字。
  第一行表示牛牛指定的起始日期。
  第二行表示牛牛指定的终止日期。
  保证 datei
  和都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0
  。
  保证 date1
  —定不晚于 date2
  。

  输出格式

  输出一行，包含一个整数，表示在 date1
  和 date2
  之间，有多少个日期是回文的。

  数据范围

  对于 60%
  的数据，满足 date1=date2
  。

  样例解释

  样例1：

  符合条件的日期是 20111102
  。

  样例2：

  符合条件的日期是 20011002
  和 20100102。
  Sample Input
  20110101
  20111231
  Sample Output
  1
  Sample Input 2
  20000101
  20101231
  Sample Output 2
  2

L - 棋盘问题(提示:找规律)

设有一个 n×m
方格的棋盘 (1≤n≤100,1≤m≤100)
求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。

输入格式

一行两个整数，分别是 n
和 m
。

输出格式

正方形的个数与长方形的个数。
Sample Input
2 3
Sample Output
8 10