ACM题目

1002: [NKPC1]Lucy的难题

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 5167 (824 users) Accepted Submit : 785 (502 users) Page View : 12630

Font Style: Aa Aa Aa

Lucy上了初中，她很喜欢数学，经常做数学奥林匹克的题目，可是今天她遇到了难题，于是就向她在南开大学上学的哥哥Feagle请教，聪明的哥哥不一会功夫就编程解决了妹妹的问题（^_^，南开大学的学生就是优秀）！ 妹妹的题目是这样的：对给定的f(n) 当 n>=50025002 的时候，f(n)=n-5；当 n<50025002 的时候，f(n)=f(f(n+2005))。现在请您试试编程解决Lucy的难题！

Input

输入有多个测试数据，每行一个 -2147483647

Output

每行输出一个对应的f(n)

Sample Input

50025002 50025000

Sample Output

50024997 50026995

Hint

递归嵌套层数过多会导致Runtime Error 或 Memory Limit Exceeded 1008: [NKPC2]三食堂宣传栏

Time Limit: 2000 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases)

Total Submit : 1079 (228 users) Accepted Submit : 271 (176 users) Page View : 6052

Font Style: Aa Aa Aa

在南开大学，三食堂外的宣传栏是一个竞争很激烈的资源，每天总有大量的海报张贴，后贴的往往会盖住原先的，为此很多学生抱怨。学校相关部门下决心解决这个问题，他们要求海

报在张贴的前一天登记，然后他们根据各海报申请的位置确定第二天要贴哪些海报。选择的标准就是：海报的数量尽可能多，且不能相互重叠。 学校相关部门委托你编程选择最优的方案。

为了简化问题我们规定：

1. 宣传栏用一个区间[-9999,9999]来表示；

2. 海报的高度均与宣传栏的高度相同，各海报要登记两个整数left，right（right>left），

表示传单要占据区间[left，right]；

3. 其中左右边框left和right没有文字，所以可以重叠； 4. 要求海报张贴的数量尽可能多，以最大程度满足需求。

Input

输入的第一行是一个整数 n (n<1000)，表示要张贴的海报张数。

下面有n行，每行两个整数 left, right （不一定按大小顺序排列，-9999

Output

输出为一个整数，表示要张贴的海报数。

Sample Input

3 6 4 1 4 3 5

Sample Output

2

1010: [NKPC2]二主楼找座

Time Limit: 2000 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases)

Total Submit : 1336 (281 users) Accepted Submit : 242 (194 users) Page View : 5420

Font Style: Aa Aa Aa

二主楼建成了，可以自习的教室也多了，所以，往常从不自习的Rock也开始上自习了。二主楼虽然很大而且座位众多，但找到满意座位也确实能算一门学问……

由于Rock找座不是很有经验，而且他还有一些特殊的要求，所以Rock请你来帮他选择座

位。

Rock 对于座位的要求有:

1. 旁边有另一个空座位，可以是左边，也可以是右边(放书包用的...)；

2. 为了环境相对稳定，满足要求1的同时，Rock的座位必须是离两边过道最远的； 3. 在教室的最后一排 (-__-!)。 为了使问题更加明确，我们做以下假定：

1. 只考虑教室最后一排中间部分的座位，两边就是过道；

2. 每个座位都有一个编号，若有N(1<=N<=50)个座位，则座位编号从左到右依次为

0,1,2,…,N-1，

3. 输入数据使用一个长度等于座位数的字符串 Seat 表示，字符串中的每一个字符对应一

个座位的状态，其中的E（大写字母）表示座位没人，P（大写字母）表示座位已经有人了。

例如：Seat=\表示以下的情况：

Empty 0 People 1 Empty 2 People 3 Empty 4 Empty 5 Empty 6 现在需要你来找出满足Rock要求的座位的编号。

Input

输入数据的第一行是一个数字N，(1<=N<=50)，表示该教室最后一排有N个座位。 第二行是一个字符串，表示字符串seat。

Output

输出只有一行，即为你所找到的座位的编号。

如果有多个符合条件的座位，则仅输出其中编号最小的那个； 如果不存在这样的座位，输出-1。

Sample Input

7

EPEPEEE

Sample Output

4

1019: 计算 A+B (超级大数相加)

Time Limit: 2000 ms Memory Limit: 10000 kB

Judge type: Multi-cases

Total Submit : 1094 (387 users) Accepted Submit : 416 (333 users) Page View : 6234

Font Style: Aa Aa Aa

计算2个超级大数的和

Input

输入只有2个超级大数A,B，以空格分开。

A,B最多有100位。

Output

输出只有一个数 即为 A、B之和。

Sample Input

111111111111111111111111111 111111111111111111111111112

Sample Output

222222222222222222222222223

1020 小学生游戏

某天，无聊的小杰叫上几个同学玩游戏，其中有比较笨的小凤，比较傻的小雪，可爱的小鑫和自以为是的小练。他们去找聪明的小艺去给他们当裁判。判定谁取得游戏胜利。而这个游戏是：由小艺给出一个数 a ，再给出一个数 b ，经过规定的运算，使得数 a 变换成数 b ，且使用最少的变换次数 n .谁先说对这个 n ，谁就取得胜利。当然，因为都是小学生，所以假定如果n>6 ，就算是没有答案。那么裁判小艺试图通过编程来使自己尽快的获得答案。请你帮帮他吧......

问题描述：

题目给出数a(a是一个正整数，不超过50位)，再给出目标数b(同样是一个正整数，不超过50位)， 数的运算有三种：

1：使当前数加上1985429 2：使当前数加上2006 3：使当前数乘2

需要你求出这个最小的n，如果n>6，输出-1。(此为负一)。

例1：小艺给出数a=1，给出数b=1987437

那么最快我们经过3次指定运算可以使1变成1987437 1*2=2；（第3种变换）

2+1985429=1985431；（第1种变换） 1985431+2006=1987437；（第2种变换）

例2：小艺给出数a=1，给出数b=128

那么最快我们经过7次指定运算可以使1变成128

1*2*2*2*2*2*2*2=128（均采用第3种变换），但是因为n>6，所以按题意输出-1。

Input

输入仅包含两个整数A、B，每行一个数字，0

Output

输出只有一行，即为最少的变换次数 n ，若 n>6 则输出-1。 请注意结尾含有一个换行。

Sample Input

1

1987437

Sample Output

3

1021: [NKPC2]小S的子集

Time Limit: 2000 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases)

Total Submit : 665 (185 users) Accepted Submit : 203 (138 users) Page View : 4503

Font Style: Aa Aa Aa

============================================== 【第二届\我为程序狂\最终数据]】

=============================================== 小S正在学习集合，他对各种有奇妙特征的集合很感兴趣。现在他在研究集合SP。 SP 是所有3的幂的集合，即SP={ 1，3，9，…… }。

他想知道 SP 的所有子集中，按元素之和按递增顺序排在第n位的集合（SPn）是什么。 他知道你是编程高手，所以他请求你帮他解决这个问题。

Input

输入数据只有一个整数n（1

Output

输出即为SPn的元素。按递增顺序，每行输出一个。即每输出一个元素，就换一次行。

Sample Input

50

Sample Output

1 81 243

1038: Lotto

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 410 (96 users) Accepted Submit : 128 (88 users) Page View : 3269

Font Style: Aa Aa Aa

In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset（子集） S containing k (k>6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = {1,2,3,5,8,13,21,34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.

Input

The input file will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending（上升 攀登） order. Input will be terminated by a value of zero (0) for k.

Output

For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

Sample Input

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34 0

Sample Output

1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7

1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34

1052: 圆的重叠问题

Time Limit: 1500 ms Memory Limit: 10000 kB

Judge type: Multi-cases

Total Submit : 1160 (261 users) Accepted Submit : 330 (239 users) Page View : 5461

Font Style: Aa Aa Aa

确定平面一般位置上n个互相交叠的圆所形成的区域数。

所谓互相交叠是指任意两个圆相交在不同的两点上，因此，不相交或相切的圆是不允许的。一般位置指不允许存在三个或三个以上的圆有一个公共交点。

Input

输入数据包含多组测试数据，每组测试数据仅包含一个正整数n，即平面一般位置上互相交叠的圆的个数。(1≤n≤65535)

Output

对每组输入数据，输出一个数，即这n个圆所形成的区域数。

Sample Input

1 6

Sample Output

2 32

Hint

本题目测试规模较大，请使用scanf()函数读入数据，printf()函数输出数据，以避免超时。

1053: 哥德巴赫猜想

Time Limit: 4000 ms Memory Limit: 10000 kB

Total Submit : 1619 (245 users) Accepted Submit : 416 (180 users) Page View : 5669

Font Style: Aa Aa Aa

哥德巴赫猜想：对于任一个大于或等于4的偶数n，至少存在一对素数p1和p2,使得n＝p1+p2。

这个猜想目前既没有被证明，也没有被否定。没有人确定这个猜想是否成立。但是，如果对于给定的一个偶数，存在这样一对素数的话，人们是可以找到的。我们的要求是编写一个程序，对于给定的一个偶数，计算出存在多少对素数满足这个猜想。

在输入中给出一系列偶数。对于每一个数，程序输出存在的素数对数。注意：我们关心的是真正不同的数字对数，所以不能将(p1,p2)和(p2,p1)作为不同的两对数。

Input

每行给出一个整数。假设每个整数为偶数，并且大于或等于4，小于等于2的15次方。输入文件的结尾用0表示。

Output

每个输出行包含一个整数。不要在输出中出现其他字符。

Sample Input

6 10 12 0

Sample Output

1 2 1

1073: Number Triangle

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 785 (156 users) Accepted Submit : 252 (139 users) Page View : 3576

Font Style: Aa Aa Aa

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

7

3 8 8 1 0

2 7 4

4 4 5 2 6 5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

Input

There are multiple test cases.The first line of each test case contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

Output

Print a single line containing the largest sum using the traversal specified for each test case.

Sample Input

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

Sample Output

30

1081: All in All

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 352 (73 users) Accepted Submit : 117 (66 users) Page View : 2846

Font Style: Aa Aa Aa

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.

Input

The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace. Input is terminated by EOF.

Output

For each test case output, if s is a subsequence of t.

Sample Input

sequence subsequence person compression

VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter

Sample Output

Yes No Yes No

1115 嫦娥姐姐的玉兔

传说嫦娥姐姐在月宫里闷得慌，想养一些玉兔。

于是，她在第一个月的时候，找来了一对新生的玉兔，第二个月它们成年，第三个月生下性别相反的玉兔一对，以后每月生产一对性别相反的玉兔，而所生玉兔亦在第二个月成年，第三个月生产另一对玉兔，以后亦每月生产一对玉兔。

嫦娥姐姐非常爱护她的兔子，玉兔都不会死亡，她想要知道，第n个月的时候，她一共养了多少对兔子。

Input

输入数据包括多组测试数据，每组测试数据仅有一行，仅包含一个数n。(n<＝80)

Output

对每组测试数据，输出一行，即第n个月时，月宫里的兔子有几对。

Sample Input

2 13

Sample Output

1 233

1133: 铁皮容器

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 156 (52 users) Accepted Submit : 57 (45 users) Page View : 2931

Font Style: Aa Aa Aa

使用白铁皮制作圆柱容器（有盖），其中每个容器耗用的铁皮量（表面积）固定为1000平方厘米。在已知容器的容积情况下，编程计算容器底半径的最小可能取值。其中容器的容积为整数，半径精确到小数点后面一位。

Input

输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数。后面紧接着k行，每行对应一个测试例，含一个整数n(0<=n<=20000)，代表容积。

Output

每个测试例对应一行输出，含一个实数，表示半径的值，若无解则输出“NO”。

Sample Input

2 1000 3000

Sample Output

2.1 NO

1159: Triangle

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 215 (63 users) Accepted Submit : 69 (60 users) Page View : 2309

Font Style: Aa Aa Aa

A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie completely inside of the triangle (points on the edges or vertices of the triangle do not count).

Input

The input test file will contain multiple test cases. Each input test case consists of six integers x1,

y1, x2, y2, x3, and y3, where (x1, y1), (x2, y2), and (x3, y3) are the coordinates of vertices of the

triangle. All triangles in the input will be non-degenerate (will have positive area), and ?15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000. The end-of-file is marked by a test case with x1 =y1 = x2 = y2 =

x3 = y3 = 0 and should not be processed.

Output

For each input case, the program should print the number of internal lattice points on a single line.

Sample Input

0 0 1 0 0 1 0 0 5 0 0 5 0 0 0 0 0 0

Sample Output

0 6

1177: Rectangles

Time Limit: 9000 ms Memory Limit: 10000 kB

Total Submit : 105 (38 users) Accepted Submit : 46 (33 users) Page View : 1950

Font Style: Aa Aa Aa

A specialist in VLSI design testing must decide if there are some components that cover each other for a given design. A component is represented as a rectangle. Assume that each rectangle is rectilinearly oriented (sides parallel to the x and y axis), so that the representation of a rectangle consists of its minimum and maximum x and y coordinates.

Write a program that counts the rectangles that are entirely covered by another rectangle.

Input

The input contains the text description of several sets of rectangles. The specification of a set consists of the number of rectangles in the set and the list of rectangles given by the minimum and maximum x and y coordinates separated by white spaces, in the format:

nr_rectangles

xmin1 xmax1 ymin1 ymax1 xmin2 xmax2 ymin2 ymax2 ...

xminn xmaxn yminn ymaxn

For each set,there will be less than 5000 rectangles.

Output

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of rectangles that are covered).

Sample Input

3

100 101 100 101 0 3 0 101 20 40 10 400 4

10 20 10 20 10 20 10 20 10 20 10 20 10 20 10 20

Sample Output

0 4

1200: Euclid's Game

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 185 (46 users) Accepted Submit : 59 (42 users) Page View : 1871

Font Style: Aa Aa Aa

Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from

the greater to reach 0, and thereby wins. For example, the players may start with (25,7):

25 7

11 7 4 7 4 3 1 3 1 0

an Stan wins.

Input

The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.

Output

For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed.

Sample Input

34 12 15 24 0 0

Sample Output

Stan wins Ollie wins

1215: 小鼠迷宫问题

Time Limit: 1500 ms Memory Limit: 10000 kB

Judge type: Multi-cases

Total Submit : 180 (45 users) Accepted Submit : 60 (36 users) Page View : 3340

Font Style: Aa Aa Aa

小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。

编程任务

对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。

Input

本题有多组输入数据，你必须处理到EOF为止。

每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。

Output

对于每组数据，将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出。每组数据输出两行，第一行是最短路长度；第2行是不同的最短路数。每组输出之间没有空行。 如果小鼠a无法通向小鼠b则输出“No Solution!”。

Sample Input

8 8 3 3 3 4 5 6 6 2 1 7 7

Sample Output

11 96

1249: 分解素因子

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 538 (258 users) Accepted Submit : 301 (254 users) Page View : 4840

Font Style: Aa Aa Aa

假设x是一个正整数，它的值不超过65535(即1

Input

输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。

Output

每个测试例对应一行输出，输出x的素数乘积表示式，式中的素数从小到大排列，两个素数之间用“*”表示乘法。

Sample Input

2 11 9828

Sample Output

11

2*2*3*3*3*7*13

1263: 粗心的物理学家

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 642 (143 users) Accepted Submit : 191 (122 users) Page View : 3827

Font Style: Aa Aa Aa

世界著名的物理学家Albert正在计算的值。不幸的是，由于这项工作十

分枯燥无味，这位伟大的物理学家得到了错误的答案。由于这一错误，它制造的几颗原子弹失去了控制，射向了五座重要的城市和一片热带雨林……

现在你的任务是帮助这位物理学家纠正这一错误，从而拯救世界。对于给定的n (n≤5*10^6)，

计算代数式的值。

Input

输入数据由多组数据组成。每组数据一行，仅有一个整数，表示n的值。

Output

对于每组数据，输出代数式的值(小数点后保留12位有效数字)。

Sample Input

2

Sample Output

1.500000000000

1278: 区间相交问题

Time Limit: 1500 ms Memory Limit: 10000 kB

Judge type: Multi-cases

Total Submit : 245 (64 users) Accepted Submit : 86 (57 users) Page View : 3211

Font Style: Aa Aa Aa

给定x 轴上n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。 编程任务：

给定n 个闭区间，编程计算去掉的最少闭区间数。

Input

第一行是正整数n，表示闭区间数。接下来的n行中， 每行有2 个整数，分别表示闭区间的2个端点。

Output

去掉的最少闭区间数。

Sample Input

3

10 20 10 15 20 15

Sample Output

2

1282: 计算循环冗余码

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 56 (28 users) Accepted Submit : 26 (25 users) Page View : 2895

Font Style: Aa Aa Aa

计算机网络中采用循环冗余码来校验数据的正确性。其原理是:发送方计算出待发送的二进制数据的循环冗余码，并随同原数据一起发送到接收方；接收方通过重新计算接收到的数据的循环冗余码，并和收到的循环冗余码进行比较，如果两者相同则可判定所收到的数据是正确的，否则说明数据是错误的。其中计算二进制数据的循环冗余码的计算过程如下：

1.协议事先约定一个二进制生成表达式，本题设为10011； 2.将待发送的二进制数据串的末尾加4个0；

3.将补上0的数据串按模2除法除于生成表达式，取余数； 4.该余数就是该二进制数据串的循环冗余码。

例如:

数据串为：1101011011 生成表达式为：10011 循环冗余码为：1110

计算过程如下：

根据上述的计算方法，请编写一个循环冗余码计算程序，假设二进制数据串的长度不超过20位，生成表达式固定为10011。

Input

输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数。后面紧接着k行，每行对应一个测试例，含一个N位二进制串(1<=N<=20)，代表数据。

Output

每个测试例对应一行输出，含一个5位二进制串，表示循环冗余码。

Sample Input

2

1101011011 10101010

Sample Output

01110 01001

1430: Fibonacci

Time Limit: 9000 ms Memory Limit: 10000 kB

Total Submit : 101 (47 users) Accepted Submit : 50 (40 users) Page View : 1902

Font Style: Aa Aa Aa

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn?1 + Fn?2 for n ≥ 2. For example, the first

ten terms of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

An alternative formula1 for the Fibonacci sequence

is

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where

0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number -1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’;

otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0 9

999999999 1000000000 -1

Sample Output

0 34 626 6875

Hint

Source

1541: 校门外的树

Time Limit: 1500 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases)

Total Submit : 142 (58 users) Accepted Submit : 71 (56 users) Page View : 2086

Font Style: Aa Aa Aa

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

Input

输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

Output

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

Sample Input

500 3 150 300 100 200 470 471

Sample Output

298

Hint

对于20%的数据，区域之间没有重合的部分； 对于其它的数据，区域之间有重合的情况。

1542: 采药

Time Limit: 1500 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases)

Total Submit : 272 (69 users) Accepted Submit : 96 (62 users) Page View : 2345

Font Style: Aa Aa Aa

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

Input

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

Output

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

Sample Input

70 3 71 100 69 1 1 2

Sample Output

3

Hint

对于30%的数据，M <= 10；

对于全部的数据，M <= 100。

1559: Jungle Roads

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 90 (40 users) Accepted Submit : 52 (38 users) Page View : 1476

Font Style: Aa Aa Aa

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for

the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

Sample Input

9

A 2 B 12 I 25

B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44

E 2 F 60 G 38 F 0

G 1 H 35 H 1 I 35 3

A 2 B 10 C 40 B 1 C 20 0

Sample Output

216 30

1576: Self Numbers

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 71 (36 users) Accepted Submit : 49 (31 users) Page View : 1729

Font Style: Aa Aa Aa

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 =

87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.

Input

No input for this problem.

Output

Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.

Sample Input Sample Output

1 3 5 7 9 20 31 42 53 64 |

| <-- a lot more numbers | 9903 9914 9925 9927 9938 9949 9960

9971 9982 9993

1635: Subsequence

Time Limit: 1500 ms Memory Limit: 35536 kB

Total Submit : 311 (65 users) Accepted Submit : 98 (56 users) Page View : 2095

Font Style: Aa Aa Aa

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2

10 15

5 1 3 5 10 7 4 9 2 8 5 11

1 2 3 4 5

Sample Output

2 3

Common Subsequence

Time Limit: 1500 ms Memory Limit: 10000 kB

Total Submit : 81 (30 users) Accepted Submit : 45 (28 users) Page View : 1528

Font Style: Aa Aa Aa

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a

subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab programming contest abcd mnp

Sample Output

4 2 0

1760: 最大数字子串

Time Limit: 1500 ms Memory Limit: 10000 kB

Judge type: Multi-cases

Total Submit : 763 (148 users) Accepted Submit : 255 (125 users) Page View : 3697

Font Style: Aa Aa Aa

输入n(1<=n<=1e6)和n个整数，这n个整数的绝对值均小于1000，求最大数字子串之和。

Input

输入为多组样例数据，每组第一行为一个正整数n，第二行为n个整数组成的数字串。

Output

对于每组样例，输出仅为一行，表示最大数字子串的各项之和。

Sample Input 9 -3 4 9 2 -10 -7 11 3 -8 13 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 Sample Output 15 17 Hint 在第一组中，最大的数字子串是4 9 2的和 在第二组中，最大的数字子串是2 6 -3 5 -7 14的和 1846: Best Messenger Tool——NKQQ Time Limit: 1500 ms Memory Limit: 10000 kB Judge type: Multi-cases (Detailed Mode - 10 cases) Total Submit : 943 (244 users) Accepted Submit : 352 (220 users) Page View : 2735 Font Style: Aa Aa Aa

Mr. Wysuperfly uses a messenger tool called NKQQ to communicate with his friends on the net. The NKQQ accumulates 1 point score every hour automatically. When the score reach certain level, there will be a level-up. The relationship between the score and the level is listed as below: Level 1 Level 2 Level 3 Level 4 Level 5 Level 6 Level 7 0 － 100 101 － 500 501 － 2000 2001 － 10000 10001 － 50000 50001 － 200000 200001 － infinity Mr. Wysuperfly finds that other Nankai ACM teammates also use NKQQ everyday like him. He wants to know that after several hours, how many teammates reach a certain level. Can you help him? Input The first line is an integer N (N<=100000) which represents the amount of the teammates to be considered. The second line includes N numbers which represent the scores of the teammates. The third line is a positive integer Q (Q<=100000) which represents how many questions in the input data. In the following Q lines, each line which includes two integers D (0<=D<=109) and L (1<=L<=7) stands for a question: ?After D hours, how many teammates will reach level L?? Output

For every question, output one line to show the answer to the question (one nonnegative integer).

Sample Input

3

1 2 3 2 98 1 98 2

Sample Output

2 1

本文来源：https://www.bwwdw.com/article/teq7.html