## CF Solutions 41-60 ∞

18/20

```
选择题目的顺序是按照CodeForces上面Sovled排序而得到的。
该文档中包含前41-60道题目的解题方法和相应Python代码，他们分别是：
149A 41A 278A 270A 344A 313A 124A 158C 339B 230A
334A 318A 337A 158D 276A 214A 37A 330A 285A 233A
```

##### 关于Sample Test样式的问题

目前我是直接用的pygments bash类型来对test进行处理，实际上我觉得input和output如果能带上颜色，那么会更直观一些。

如果有人对Hacking For Pygments感兴趣，可以试着增加对input和output的过滤识别并上色，或者也可以试着尝试一下pygments支持的哪种语言可以对其上色。

# 149A Business trip

What joy! Petya's parents went on a business trip for the whole year and the playful kid is left all by himself. Petya got absolutely happy. He jumped on the bed and threw pillows all day long, until...

Today Petya opened the cupboard and found a scary note there. His parents had left him with duties: he should water their favourite flower all year, each day, in the morning, in the afternoon and in the evening. "Wait a second!" — thought Petya. He know for a fact that if he fulfills the parents' task in the i-th (1 ≤ i ≤ 12) month of the year, then the flower will grow by ai centimeters, and if he doesn't water the flower in the i-th month, then the flower won't grow this month. Petya also knows that try as he might, his parents won't believe that he has been watering the flower if it grows strictly less than by k centimeters.

Help Petya choose the minimum number of months when he will water the flower, given that the flower should grow no less than by k centimeters.

Input

The first line contains exactly one integer k (0 ≤ k ≤ 100). The next line contains twelve space-separated integers: the i-th (1 ≤ i ≤ 12) number in the line represents ai (0 ≤ ai ≤ 100).

Output

Print the only integer — the minimum number of months when Petya has to water the flower so that the flower grows no less than by k centimeters. If the flower can't grow by k centimeters in a year, print -1.

Note

Let's consider the first sample test. There it is enough to water the flower during the seventh and the ninth month. Then the flower grows by exactly five centimeters. In the second sample Petya's parents will believe him even if the flower doesn't grow at all (k = 0). So, it is possible for Petya not to water the flower at all.

#### Sample test(s):

```
input
5
1 1 1 1 2 2 3 2 2 1 1 1
output
2
input
0
0 0 0 0 0 0 0 1 1 2 3 0
output
0
input
11
1 1 4 1 1 5 1 1 4 1 1 1
output
3
```

#### Code:

```
#统计最少需要交几个月的水花能长k厘米。
#将第二行输入进行逆序排序，然后相加直到大于等于第一行输入
#那么被加数的个数就是本题的输出
import sys
k = int(sys.stdin.readline())
monthi = sorted(sys.stdin.readline().split(), key=int, reverse=True)
n = 0
wateredK = 0
for i in range(len(monthi)):
if wateredK >= k: break
wateredK += int(monthi[i])
n += 1
print (n if wateredK >= k else -1)
```

# 41A Translation

The translation from the Berland language into the Birland language is not an easy task. Those languages are very similar: a berlandish word differs from a birlandish word with the same meaning a little: it is spelled (and pronounced) reversely. For example, a Berlandish word code corresponds to a Birlandish word edoc. However, it's easy to make a mistake during the «translation». Vasya translated word s from Berlandish into Birlandish as t. Help him: find out if he translated the word correctly.

Input

The first line contains word s, the second line contains word t. The words consist of lowercase Latin letters. The input data do not consist unnecessary spaces. The words are not empty and their lengths do not exceed 100 symbols.

Output

If the word t is a word s, written reversely, print YES, otherwise print NO.

#### Sample test(s):

```
input
code
edoc
output
YES
input
abb
aba
output
NO
input
code
code
output
NO
```

#### Code:

```
#这道题就是比较第一行和第二行字符串是否是互逆的
#[begin:end:step]---> [::-1]可以逆序输出字符串
#所以这道题就解决了
import sys
print ("YES" if sys.stdin.readline().strip() == sys.stdin.readline().strip()[::-1] else "NO")
```

# 278A Circle Line

The circle line of the Berland subway has n stations. We know the distances between all pairs of neighboring stations:

- d1 is the distance between the 1-st and the 2-nd station;
- d2 is the distance between the 2-nd and the 3-rd station;

...- dn - 1 is the distance between the n - 1-th and the n-th station;
- dn is the distance between the n-th and the 1-st station.
The trains go along the circle line in both directions. Find the shortest distance between stations with numbers s and t.

Input

The first line contains integer n (3 ≤ n ≤ 100) — the number of stations on the circle line. The second line contains n integers d1, d2, ..., dn (1 ≤ di ≤ 100) — the distances between pairs of neighboring stations. The third line contains two integers s and t (1 ≤ s, t ≤ n) — the numbers of stations, between which you need to find the shortest distance. These numbers can be the same.The numbers in the lines are separated by single spaces.

Output

Print a single number — the length of the shortest path between stations number s and t.

Note

- In the first sample the length of path 1 → 2 → 3 equals 5, the length of path 1 → 4 → 3 equals 13.
- In the second sample the length of path 4 → 1 is 100, the length of path 4 → 3 → 2 → 1 is 15.
- In the third sample the length of path 3 → 1 is 1, the length of path 3 → 2 → 1 is 2.
- In the fourth sample the numbers of stations are the same, so the shortest distance equals 0.

#### Sample test(s):

```
input
4
2 3 4 9
1 3
output
5
input
4
5 8 2 100
4 1
output
15
input
3
1 1 1
3 1
output
1
input
3
31 41 59
1 1
output
0
```

#### Code:

```
#这道题要求求出环形站台A和B之间的最短距离，可以是A到B，或者B到A。
#len1表示A到B的距离，len2表示B到站台Sn，再有Sn到Sa站台的距离和。
#输出len1和len2中小的距离就是题目要求的距离
import sys
stationAmount = int(sys.stdin.readline())
stations = sys.stdin.readline().split()
s = sorted(sys.stdin.readline().split(), key=int)
startS = int(s[0])
endS = int(s[1])
len1 = 0
len2 = 0
for i in range(startS-1,endS-1,1):
len1 += int(stations[i])
for i in range(endS-1,len(stations),1):
len2 += int(stations[i])
for i in range(0,startS-1,1):
len2 += int(stations[i])
print min(len1,len2)
```

# 270A Fancy Fence

Emuskald needs a fence around his farm, but he is too lazy to build it himself. So he purchased a fence-building robot.

He wants the fence to be a regular polygon. The robot builds the fence along a single path, but it can only make fence corners at a single angle a.

Will the robot be able to build the fence Emuskald wants? In other words, is there a regular polygon which angles are equal to a?

Input

The first line of input contains an integer t (0 < t < 180) — the number of tests. Each of the following t lines contains a single integer a (0 < a < 180) — the angle the robot can make corners at measured in degrees.

Output

For each test, output on a single line "YES" (without quotes), if the robot can build a fence Emuskald wants, and "NO" (without quotes), if it is impossible.

Note

In the first test case, it is impossible to build the fence, since there is no regular polygon with angle .

In the second test case, the fence is a regular triangle, and in the last test case — a square.

#### Sample test(s):

```
input
3
30
60
90
output
NO
YES
YES
```

#### Code:

```
#多边形形的外角和为360度
#只需要计算外角能否被360整除就可以得出其是否能圈出一个固定角度的围栏
import sys
for case in range(int(sys.stdin.readline())):
print ("YES" if (360 % (180 - int(sys.stdin.readline())) == 0) else "NO")
```

# 344A Magnets

Mad scientist Mike entertains himself by arranging rows of dominoes. He doesn't need dominoes, though: he uses rectangular magnets instead. Each magnet has two poles, positive (a "plus") and negative (a "minus"). If two magnets are put together at a close distance, then the like poles will repel each other and the opposite poles will attract each other.

Mike starts by laying one magnet horizontally on the table. During each following step Mike adds one more magnet horizontally to the right end of the row. Depending on how Mike puts the magnet on the table, it is either attracted to the previous one (forming a group of multiple magnets linked together) or repelled by it (then Mike lays this magnet at some distance to the right from the previous one). We assume that a sole magnet not linked to others forms a group of its own.

Mike arranged multiple magnets in a row. Determine the number of groups that the magnets formed.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100000) — the number of magnets. Then n lines follow. The i-th line (1 ≤ i ≤ n) contains either characters "01", if Mike put the i-th magnet in the "plus-minus" position, or characters "10", if Mike put the magnet in the "minus-plus" position.

Output

On the single line of the output print the number of groups of magnets.

Note

The first testcase corresponds to the figure. The testcase has three groups consisting of three, one and two magnets.The second testcase has two groups, each consisting of two magnets.

#### Sample test(s):

```
input
6
10
10
10
01
10
10
output
3
input
4
01
01
10
10
output
2
```

#### Code:

```
#判断连续输入是否相同，相同则一组
#统计总共有多少组
import sys
currentMag = ""
groupN = 0
for i in range(int(sys.stdin.readline())):
mag = sys.stdin.readline().strip()
if currentMag != mag:
groupN += 1
currentMag = mag
print groupN
```

# 313A Ilya and Bank Account

Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

Input

The single line contains integer n (10 ≤ |n| ≤ 10**9) — the state of Ilya's bank account.

Output

In a single line print an integer — the maximum state of the bank account that Ilya can get.

Note

In the first test sample Ilya doesn't profit from using the present.In the second test sample you can delete digit 1 and get the state of the account equal to 0.

#### Sample test(s):

```
input
2230
output
2230
input
-10
output
0
input
-100003
output
-10000
```

#### Code:

```
#如果输入为整数，直接输出
#如果为负数，排除末尾或者倒数第二位，选择最大的数输出
import sys
balance = sys.stdin.readline().strip()
if balance[0] != "-": print balance
else: print max(int(balance[:-1]),int(balance[:-2] + balance[-1]))
```

# 124A The number of positions

Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing behind him. Find the number of different positions Petr can occupy.

Input

The only line contains three integers n, a and b (0 ≤ a, b < n ≤ 100).

Output

Print the single number — the number of the sought positions.

Note

The possible positions in the first sample are: 2 and 3 (if we number the positions starting with 1).In the second sample they are 3, 4 and 5.

#### Sample test(s):

```
input
3 1 1
output
2
input
5 2 3
output
3
```

#### Code:

```
#有n个人，Petr前面最少有a个人，后面最多有b个人
#输出Petr所站可能的位置的数量
#实际上就是n-a和b+1中小的那个
import sys
inputs = sys.stdin.readline().split()
print min(int(inputs[0])-int(inputs[1]),int(inputs[2])+1)
```

# 158C Cd and pwd commands

Vasya is writing an operating system shell, and it should have commands for working with directories. To begin with, he decided to go with just two commands: cd (change the current directory) and pwd (display the current directory).

Directories in Vasya's operating system form a traditional hierarchical tree structure. There is a single root directory, denoted by the slash character "/". Every other directory has a name — a non-empty string consisting of lowercase Latin letters. Each directory (except for the root) has a parent directory — the one that contains the given directory. It is denoted as "..".

The command cd takes a single parameter, which is a path in the file system. The command changes the current directory to the directory specified by the path. The path consists of the names of directories separated by slashes. The name of the directory can be "..", which means a step up to the parent directory. «..» can be used in any place of the path, maybe several times. If the path begins with a slash, it is considered to be an absolute path, that is, the directory changes to the specified one, starting from the root. If the parameter begins with a directory name (or ".."), it is considered to be a relative path, that is, the directory changes to the specified directory, starting from the current one.

The command pwd should display the absolute path to the current directory. This path must not contain "..".

Initially, the current directory is the root. All directories mentioned explicitly or passed indirectly within any command cd are considered to exist. It is guaranteed that there is no attempt of transition to the parent directory of the root directory.

Input

The first line of the input data contains the single integer n (1 ≤ n ≤ 50) — the number of commands.Then follow n lines, each contains one command. Each of these lines contains either command pwd, or command cd, followed by a space-separated non-empty parameter.

The command parameter cd only contains lower case Latin letters, slashes and dots, two slashes cannot go consecutively, dots occur only as the name of a parent pseudo-directory. The command parameter cd does not end with a slash, except when it is the only symbol that points to the root directory. The command parameter has a length from 1 to 200 characters, inclusive.

Directories in the file system can have the same names.

Output

For each command pwd you should print the full absolute path of the given directory, ending with a slash. It should start with a slash and contain the list of slash-separated directories in the order of being nested from the root to the current folder. It should contain no dots.

#### Sample test(s):

```
input
7
pwd
cd /home/vasya
pwd
cd ..
pwd
cd vasya/../petya
pwd
output
/
/home/vasya/
/home/
/home/petya/
input
4
cd /a/b
pwd
cd ../a/b
pwd
output
/a/b/
/a/a/b/
```

#### Code:

```
import sys
def normalizePWD(currentPWD):
if currentPWD[len(currentPWD) - 1] != "/":
currentPWD = currentPWD + "/"
#print currentPWD
while True:
n = currentPWD.find("..")
#print n
if n == -1 : break
for i in range(n-2, -1, -1):
if currentPWD[i] == "/":
#print i
currentPWD = currentPWD[:i] + currentPWD[n+2:]
break
return currentPWD
n = int(sys.stdin.readline())
currentPWD = "/"
for index in range(n):
c = sys.stdin.readline().strip()
if c == "pwd":
print currentPWD
elif c == "cd ..":
for i in range(len(currentPWD)-2,-1,-1):
if currentPWD[i] == "/":
currentPWD = currentPWD[:i+1]
break
else:
targetD = c.split()[1]
if targetD[0] == "/":
currentPWD = targetD
else:
currentPWD += targetD
currentPWD = normalizePWD(currentPWD)
```

# 339B Xenia and Ringroad

Xenia lives in a city that has n houses built along the main ringroad. The ringroad houses are numbered 1 through n in the clockwise order. The ringroad traffic is one way and also is clockwise.

Xenia has recently moved into the ringroad house number 1. As a result, she's got m things to do. In order to complete the i-th task, she needs to be in the house number ai and complete all tasks with numbers less than i. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105). The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ n). Note that Xenia can have multiple consecutive tasks in one house.

Output

Print a single integer — the time Xenia needs to complete all tasks.Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Note

In the first test example the sequence of Xenia's moves along the ringroad looks as follows: 1 → 2 → 3 → 4 → 1 → 2 → 3. This is optimal sequence. So, she needs 6 time units.

#### Sample test(s):

```
input
4 3
3 2 3
output
6
input
4 3
2 3 3
output
2
```

#### Code:

```
#这个城市有n个房屋，成环形围绕在一条路上，人只能逆时针行走
#Xenia要去不同的房屋办事，去的房屋顺序为第二行的输入
#他只能顺时针走
#输出要办完所有的事情需要走多远
#如果即将办事地址等于正在办事地址，则time不变
#如果即将办事地址大于正在办事地址，则加上task-currentTask即可
#如果即将办事地址小于正在办事地址，则需要绕一圈，即n-currentTask+task的时间
import sys
inputs = sys.stdin.readline().split()
(n,m) = (int(inputs[0]),int(inputs[1]))
tasks = sys.stdin.readline().split()
currentTask = 1
time = 0
for i in range(m):
task = int(tasks[i])
if(task == currentTask): continue
elif(task > currentTask):
time += task - currentTask
elif(task < currentTask):
time += n - currentTask + task
currentTask = task
print time
```

# 230A Dragons

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals s.

If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength xi, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by yi.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input

The first line contains two space-separated integers s and n (1 ≤ s ≤ 10**4, 1 ≤ n ≤ 10**3). Then n lines follow: the i-th line contains space-separated integers xi and yi (1 ≤ xi ≤ 10**4, 0 ≤ yi ≤ 10**4) — the i-th dragon's strength and the bonus for defeating it.

Output

On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.

Note

In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.In the second sample Kirito's strength is too small to defeat the only dragon and win.

#### Sample test(s):

```
input
2 2
1 99
100 0
output
YES
input
10 1
100 100
output
NO
```

#### Code:

```
#Kirito玩屠龙游戏
#只有Kirito的力量大于龙的力量，才能将其杀死
#一旦将龙杀死，Kirito将获得力量奖励，从而提升自己的力量值
#杀龙的顺序随意，问是否能把龙都杀死
#将所有龙按照力量值进行排序，优先杀力量值小的
#这样如果都杀完了输出YES，否则输出NO
import sys
inputs = sys.stdin.readline().split()
(s,n) = (int(inputs[0]),int(inputs[1]))
dragons = []
for i in range(n):
inputs = sys.stdin.readline().split()
dragons.append((int(inputs[0]),int(inputs[1])))
dragons.sort()
flag = True
for i in range(n):
dragon_s = dragons[i][0]
dragon_bonus = dragons[i][1]
if(s <= dragon_s):
print "NO"
flag = False
break
else:
s += dragon_bonus
if flag: print "YES"
```

# 334A Candy Bags

Gerald has n younger brothers and their number happens to be even. One day he bought n**2 candy bags. One bag has one candy, one bag has two candies, one bag has three candies and so on. In fact, for each integer k from 1 to n**2 he has exactly one bag with k candies.

Help him give n bags of candies to each brother so that all brothers got the same number of candies.

Input

The single line contains a single integer n (n is even, 2 ≤ n ≤ 100) — the number of Gerald's brothers.

Output

Let's assume that Gerald indexes his brothers with numbers from 1 to n. You need to print n lines, on the i-th line print n integers — the numbers of candies in the bags for the i-th brother. Naturally, all these numbers should be distinct and be within limits from 1 to n**2. You can print the numbers in the lines in any order.It is guaranteed that the solution exists at the given limits.

Note

The sample shows Gerald's actions if he has two brothers. In this case, his bags contain 1, 2, 3 and 4 candies. He can give the bags with 1 and 4 candies to one brother and the bags with 2 and 3 to the other brother.

#### Sample test(s):

```
input
2
output
1 4
2 3
```

#### Code:

```
#n个人(n为偶数)，有n**2个袋子
#袋子按照序号排列，从1到n**2来编号，袋子中有编号个糖果
#即编号n的袋子有n块糖果
#如何分配能使得每个人分配到相等数量的糖果
#输出按如下格式：
#题目很简单，按照这个输出格式去赋值就好了
'''
10
1 20 21 40 41 60 61 80 81 100
2 19 22 39 42 59 62 79 82 99
3 18 23 38 43 58 63 78 83 98
4 17 24 37 44 57 64 77 84 97
5 16 25 36 45 56 65 76 85 96
6 15 26 35 46 55 66 75 86 95
7 14 27 34 47 54 67 74 87 94
8 13 28 33 48 53 68 73 88 93
9 12 29 32 49 52 69 72 89 92
10 11 30 31 50 51 70 71 90 91
'''
import sys
n = int(sys.stdin.readline())
result = [[] for i in range(n)]
flag = False
for i in range(n**2):
if i%n == 0:
flag = (False if flag else True)
if flag:
result[i%n].append(i+1)
else:
result[n-1-i%n].append(i+1)
for i in range(n):
print " ".join([str(x) for x in result[i]])
```

# 318A Even Odds

Being a nonconformist, Volodya is displeased with the current state of things, particularly with the order of natural numbers (natural number is positive integer number). He is determined to rearrange them. But there are too many natural numbers, so Volodya decided to start with the first n. He writes down the following sequence of numbers: firstly all odd integers from 1 to n (in ascending order), then all even integers from 1 to n (also in ascending order). Help our hero to find out which number will stand at the position number k.

Input

The only line of input contains integers n and k (1 ≤ k ≤ n ≤ 10**12).Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print the number that will stand at the position number k after Volodya's manipulations.

Note

In the first sample Volodya's sequence will look like this: {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}. The third place in the sequence is therefore occupied by the number 5.

#### Sample test(s):

```
input
10 3
output
5
input
7 7
output
6
```

#### Code:

```
#这道题给定n和k，n表示总共有多少数字，k表示输出第k个数字
#n个数字按照奇数从小到大然后是偶数从小到大排列
#这道题要注意大数据的问题
#因为输入可能很大，所以不能简单的把数据进行排列，然后输出第n位
#找出规律来直接根据n和k输出第k位置的数字即可
import sys
inputs = sys.stdin.readline().split()
(n,k) = (int(inputs[0]), int(inputs[1]))
flag = True if n%2 == 0 else False
if flag:
print k*2-1 if k<=n/2 else (k-n/2)*2
else:
print k*2 - 1 if (k <= n/2 + 1) else (k - n/2 -1)*2
```

# 337A Puzzles

The end of the school year is near and Ms. Manana, the teacher, will soon have to say goodbye to a yet another class. She decided to prepare a goodbye present for her n students and give each of them a jigsaw puzzle (which, as wikipedia states, is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces).

The shop assistant told the teacher that there are m puzzles in the shop, but they might differ in difficulty and size. Specifically, the first jigsaw puzzle consists of f1 pieces, the second one consists of f2 pieces and so on.

Ms. Manana doesn't want to upset the children, so she decided that the difference between the numbers of pieces in her presents must be as small as possible. Let A be the number of pieces in the largest puzzle that the teacher buys and B be the number of pieces in the smallest such puzzle. She wants to choose such n puzzles that A - B is minimum possible. Help the teacher and find the least possible value of A - B.

Input

The first line contains space-separated integers n and m (2 ≤ n ≤ m ≤ 50). The second line contains m space-separated integers f1, f2, ..., fm (4 ≤ fi ≤ 1000) — the quantities of pieces in the puzzles sold in the shop.

Output

Print a single integer — the least possible difference the teacher can obtain.

Note

Sample 1. The class has 4 students. The shop sells 6 puzzles. If Ms. Manana buys the first four puzzles consisting of 10, 12, 10 and 7 pieces correspondingly, then the difference between the sizes of the largest and the smallest puzzle will be equal to 5. It is impossible to obtain a smaller difference. Note that the teacher can also buy puzzles 1, 3, 4 and 5 to obtain the difference 5.

#### Sample test(s):

```
input
4 6
10 12 10 7 5 22
output
5
```

#### Code:

```
#第二行排序
#i+n个元素减去i个元素的值，找到最小的输出就可以了
import sys
n,m = [int(x) for x in sys.stdin.readline().split()]
presents = sorted([int(x) for x in sys.stdin.readline().split()])
minPiece = 1000000
for i in range(len(presents)-n+1):
tmpMin = presents[i+n-1] - presents[i]
if tmpMin < minPiece: minPiece = tmpMin
print minPiece
```

# 158D Ice Sculptures

The Berland University is preparing to celebrate the 256-th anniversary of its founding! A specially appointed Vice Rector for the celebration prepares to decorate the campus. In the center of the campus n ice sculptures were erected. The sculptures are arranged in a circle at equal distances from each other, so they form a regular n-gon. They are numbered in clockwise order with numbers from 1 to n.

The site of the University has already conducted a voting that estimated each sculpture's characteristic of ti — the degree of the sculpture's attractiveness. The values of ti can be positive, negative or zero.

When the university rector came to evaluate the work, he said that this might be not the perfect arrangement. He suggested to melt some of the sculptures so that:

the remaining sculptures form a regular polygon (the number of vertices should be between 3 and n), the sum of the ti values of the remaining sculptures is maximized. Help the Vice Rector to analyze the criticism — find the maximum value of ti sum which can be obtained in this way. It is allowed not to melt any sculptures at all. The sculptures can not be moved.

Input

The first input line contains an integer n (3 ≤ n ≤ 20000) — the initial number of sculptures. The second line contains a sequence of integers t1, t2, ..., tn, ti — the degree of the i-th sculpture's attractiveness ( - 1000 ≤ ti ≤ 1000). The numbers on the line are separated by spaces.

Output

Print the required maximum sum of the sculptures' attractiveness.

Note

In the first sample it is best to leave every second sculpture, that is, leave sculptures with attractivenesses: 2, 4, 5 и 3.

#### Sample test(s):

```
input
8
1 2 -3 4 -5 5 2 3
output
14
input
6
1 -2 3 -4 5 -6
output
9
input
6
1 2 3 4 5 6
output
21
```

#### Code:

```
#这个雕塑是环形的，每个雕塑有个吸引力值
#可以去掉一些雕塑(必须保证剩下的雕塑是正多边型)
#问如何才能保证雕塑的吸引力总值最高
import sys
n = int(sys.stdin.readline())
inputs = sys.stdin.readline().split()
s = []
maxSum = 0
for i in range(n):
number = int(inputs[i])
s.append(number)
maxSum += number
for i in range(1, n/2):
if n % i == 0:
for j in range(i):
currentSum = 0
for k in range(n / i):
currentSum += s[k*i+j]
maxSum = max(maxSum, currentSum)
print maxSum
```

# 276A Lunch Rush

Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers fi and ti. Value ti shows the time the Rabbits need to lunch in the i-th restaurant. If time ti exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal fi - (ti - k). Otherwise, the Rabbits get exactly fi units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value.

Input

The first line contains two space-separated integers — n (1 ≤ n ≤ 104) and k (1 ≤ k ≤ 109) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — fi (1 ≤ fi ≤ 109) and ti (1 ≤ ti ≤ 109) — the characteristics of the i-th restaurant.

Output

In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch.

#### Sample test(s):

```
input
2 5
3 3
4 5
output
4
input
4 6
5 8
3 6
2 3
2 2
output
3
input
1 5
1 7
output
-1
```

#### Code:

```
n,k = [int(x) for x in raw_input().split()]
for i in range(n):
f,t = [int(x) for x in raw_input().split()]
maxf = (f - t + k if not locals().has_key("result") or f - t + k > maxf else maxf) if t > k else (f if not locals().has_key("result") or f > maxf else maxf)
print maxf
```

214A

#### Code:

```
n,m = map(int, raw_input().split())
print sum([1 for a in range(n+1) if n >= a**2 and m == a + (a**2 - n)**2])
```

37A

#### Code:

```
n = input()
inputs = map(int, raw_input().split())
totalN = 0
maxHeight = 1
for i in range(n):
bar = inputs[i]
height = 1
if bar == -1:
continue
else: totalN += 1
for j in range(i+1,n):
if inputs[j] == bar:
inputs[j] = -1
height += 1
maxHeight = max(maxHeight, height)
print "%d %d" %(maxHeight, totalN)
```

```
#Really cool solution
n = input()
s = raw_input().split()
print max(s.count(i) for i in s), len(set(s))
```

330A

#### Code:

```
rows, columns = map(int, raw_input().split())
cells = []
for rowN in range(rows): cells.append(list(raw_input()))
result = 0
for i in range(rows):
flag = True
for j in range(columns):
if cells[i][j] == 'S':
flag = False
break
if flag:
for j in range(columns):
cells[i][j] = 'x'
for j in range(columns):
flag = True
for i in range(rows):
if cells[i][j] == 'S':
flag = False
break
if flag:
for i in range(rows):
cells[i][j] = 'x'
for i in range(rows):
for j in range(columns):
if cells[i][j] == 'x': result += 1
print result
```

285A

#### Code:

```
```