## CF Solutions 01-20 ∞

release

```
选择题目的顺序是按照CodeForces上面Sovled排序而得到的。
该文档中包含01-20道题目的解题方法和相应Python代码，他们分别是：
1A 4A 158A 71A 118A 158B 50A 116A 231A 82A
131A 282A 266A 119A 112A 133A 148A 96A 160A 228A
```

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

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

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

# 1A Theatre Square

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input

The input contains three positive integer numbers in the first line: n, m and a (1 ≤ n, m, a ≤ 10**9).

Output

Write the needed number of flagstones.

#### Sample test(s):

```
input
6 6 4
output
4
```

#### Code:

```
import sys
import math
#读取输入并将所输入的内容按照空格进行切片分割成数组
inputs = sys.stdin.readline().split()
#分别获取n,m和a的值，并且转换为int类型
n = int(inputs[0])
m = int(inputs[1])
a = int(inputs[2])
#math.ceil函数表示向上取整
#因为n和a都是整数，所以如果直接使用除法，则得到的是舍去小数的整数部分
#所以需要先将其转换为浮点数
x = math.ceil(n * 1.0 / a)
y = math.ceil(m * 1.0 / a)
print int(x*y)
```

# 4A Watermelon

One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.

Pete and Billy are great fans of even numbers, that's why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that's why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.

Input

The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the boys.

Output

Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.

Note

For example, the boys can divide the watermelon into two parts of 2 and 6 kilos respectively (another variant — two parts of 4 and 4 kilos).

#### Sample test(s):

```
input
8
output
YES
```

#### Code:

```
#这道题实际上就是来判断一个数是否可以分成2个偶数
#因为偶数+偶数一定是一个偶数，所以任意奇数都一定不可分
#另外偶数为2只能分成1和1，故如果w为2也返回NO
import sys
w = int(sys.stdin.readline())
if w % 2 == 1 or w == 2: print "NO"
else: print "YES"
```

# 158A Next Round

"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space. The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).

Output

Output the number of participants who advance to the next round.

Note

In the first example the participant on the 5th place earned 7 points. As the participant on the 6th place also earned 7 points, there are 6 advancers. In the second example nobody got a positive score.

#### Sample test(s):

```
input
8 5
10 9 8 7 7 7 5 5
output
6
input
4 2
0 0 0 0
output
0
```

#### Code:

```
#第一行输入为n和k,n表示第二行输入有n个数字
#输出第二行有多少输入的数字的值大于等于第k个数的值，即ak
#ak如果为0，则输出的是有多少数大于ak的值
import sys
#获得第一行输入
inputs = sys.stdin.readline().split()
n = int(inputs[0])
k = int(inputs[1])
#获得第二行输入
an = sys.stdin.readline().split()
#获得ak的值
ak = int(an[k-1])
count = 0
#如果ak为0，则计算大于ak的数字总共有多少个
if ak == 0:
for i in range(n):
if(int(an[i])>0):
count +=1
else:
break
#如果ak不为0，则计算大于等于ak的数字总共有多少个
else:
for i in range(n):
if(int(an[i])>=ak):
count += 1
else:
break
print count
```

# 71A Way Too Long Words

Sometimes some words like "localization" or "internationalization" are so long that writing them many times in one text is quite tiresome.

Let's consider a word too long, if its length is strictly more than 10 characters. All too long words should be replaced with a special abbreviation.

This abbreviation is made like this: we write down the first and the last letter of a word and between them we write the number of letters between the first and the last letters. That number is in decimal system and doesn't contain any leading zeroes.

Thus, "localization" will be spelt as "l10n", and "internationalization» will be spelt as "i18n".

You are suggested to automatize the process of changing the words with abbreviations. At that all too long words should be replaced by the abbreviation and the words that are not too long should not undergo any changes.

Input

The first line contains an integer n (1 ≤ n ≤ 100). Each of the following n lines contains one word. All the words consist of lowercase Latin letters and possess the lengths of from 1 to 100 characters.

Output

Print n lines. The i-th line should contain the result of replacing of the i-th word from the input data.

#### Sample test(s):

```
input
4
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis
output
word
l10n
i18n
p43s
```

#### Code:

```
#这道题主要是对输入的单词进行缩写
#缩写的格式为：
#如果单词小于10个字母，那么正常输出该单词
#如果单词大于10个字母，那么输出首字母+中间字母的个数+尾字母
import sys
#读入第一行输入，第一行输入用来确定总共数据几行单词进行转换
lines = int(sys.stdin.readline())
#进行循环读取
for line in range(lines):
#readline()函数会将一行中的换行符读取进来，所以需要strip()进行格式化
word = sys.stdin.readline().strip()
#len()函数用来统计字符串长度
wordLenght = len(word)
#如果单词长度大于10，则按照首字母+中间字母的个数+尾字母进行输出
if wordLenght > 10:
print "%s%d%s" %(word[0], wordLenght - 2, word[wordLenght-1])
#如果单词长度小于10，则直接输出该单词
else:
print word
```

# 118A String Task

Petya started to attend programming lessons. On the first lesson his task was to write a simple program. The program was supposed to do the following: in the given string, consisting if uppercase and lowercase Latin letters, it:

* deletes all the vowels,

* inserts a character "." before each consonant,

* replaces all uppercase consonants with corresponding lowercase ones.

Vowels are letters "A", "O", "Y", "E", "U", "I", and the rest are consonants. The program's input is exactly one string, it should return the output as a single string, resulting after the program's processing the initial string.

Help Petya cope with this easy task.

Input

The first line represents input string of Petya's program. This string only consists of uppercase and lowercase Latin letters and its length is from 1 to 100, inclusive.

Output

Print the resulting string. It is guaranteed that this string is not empty.

#### Sample test(s):

```
input
tour
output
.t.r
input
Codeforces
output
.c.d.f.r.c.s
input
aBAcAba
output
.b.c.b
```

#### Code:

```
#给定输入的单词，对其进行去元音并在辅音前面加上"."
#另外需要将其变成小写字母
import sys
#读取输入的单词，并把每个字母转换成小写字母
word = sys.stdin.readline().split()[0].lower()
#建立一个map，key是aoyeui这些元音
vowels = {"a":1,"o":1,"y":1,"e":1,"u":1,"i":1}
result = ""
for i in range(len(word)):
#遍历输入的单词的字母
#如果字母为原因则忽略，如果不是原因则加上"."拼接到result字符串上
if not vowels.has_key(word[i]):
result += "." + word[i]
print result
```

# 158B Taxi

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 10**5) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Note

In the first test we can sort the children into four cars like this:

* the third group (consisting of four children),

* the fourth group (consisting of three children),

* the fifth group (consisting of three children),

* the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

#### Sample test(s):

```
input
5
1 2 4 3 3
output
4
input
8
2 3 4 4 2 1 3 1
output
5
```

#### Code:

```
#题目还是很简单清晰的
#第一行输入表示有几组人要去打车
#第二行输入表示每组有多少个人
#题目要求计算最少需要打多少辆车(每组人必须坐一辆车，车上最多坐4个人)
#也就是说：
#4人组的肯定是自己一辆车
#如果还有1人组，那么3人组需要和1人组合乘一辆车，否则3人组自己一辆车
#2人组可以和2个1人组合乘，也可以和另外一个两人组合乘
#1人组可以和其它的一人组合乘
#额...我觉得自己做麻烦了...自己都不愿意看了==！
#这个有人有更简介的做法吗？
import sys
groupN = int(sys.stdin.readline())
groups = sys.stdin.readline().split()
cars = 0
#对组进行排序
groups.sort()
#处理4人组
for i in range(len(groups) - 1, -1, -1):
if groups[i] == '4':
cars += 1
del groups[i]
#print "4 | %d" %cars
else:
break
#处理3人组
threeCount = 0
for i in range(len(groups) - 1, -1, -1):
if groups[i] == '3':
cars += 1
#print "3 | %d" %cars
del groups[i]
threeCount += 1
else:
break
for i in range(len(groups) - 1, -1, -1):
if groups[i] == '1' and threeCount != 0:
del groups[i]
threeCount -= 1
#处理两人组
twoStart = -1
twoEnd = -1
for i in range(len(groups) - 1, -1, -1):
if groups[i] == '2':
if twoStart == -1: twoStart = i
twoEnd = i
else:
break
if twoStart == -1:
twoCount = 0
else:
twoCount = twoStart - twoEnd + 1
if twoCount % 2 == 0:
if twoCount != 0:
cars += twoCount / 2
#print "2 | %d " %(cars)
del groups[twoEnd:]
else:
cars += (twoCount + 1) / 2
#print "2 | %d" %(cars)
del groups[twoEnd :]
for i in range(len(groups)):
if groups[i] == '1':
groups[i] = 0
if i + 1 < twoEnd: groups[i+1] = 0
break
#处理一人组
for i in range(len(groups)):
if groups[i] == '1':
oneCount = len(groups) - i
if oneCount % 4 == 0:
cars += oneCount / 4
break
else:
cars += (oneCount / 4) + 1
break
#输出需要多少量车
print cars
#################################################
#以下是晓琳给出的代码(看不明白的去找张晓琳同学哦)
import sys, math
n,a,s,i,num,num1,num3 = int(sys.stdin.readline()),[int(x)for x in sys.stdin.readline().split()],0,0,0,0,0
for i in range(len(a)): num1,num3 = num1 + 1 if a[i] == 1 else num1, num3 + 1 if a[i] == 3 else num3
if (num3 >= num1): num = num3 - num1
for i in range (n): s = s + a[i]
print int( math.ceil((s - num*3)*1.0/4) + num)
```

# 50A Domino piling

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

1. Each domino completely covers two squares.

2. No two dominoes overlap.

3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

Input

In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).

Output

Output one number — the maximal number of dominoes, which can be placed.

#### Sample test(s):

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

#### Code:

```
#这个题目理解了还是比较容易的...
#其实就是domino铺满整个方形区域，不能覆盖，不能超出，所以能铺多少是多少。
#区域面积是m*n...domino面即使1*2...所以可以铺m*n/2块
import sys
inputs = sys.stdin.readline().split()
m = int(inputs[0])
n = int(inputs[1])
print int(m * n / 2)
```

# 116A Tram

Linear Kingdom has exactly one tram line. It has n stops, numbered from 1 to n in the order of tram's movement. At the i-th stop ai passengers exit the tram, while bi passengers enter it. The tram is empty before it arrives at the first stop. Also, when the tram arrives at the last stop, all passengers exit so that it becomes empty.

Your task is to calculate the tram's minimum capacity such that the number of people inside the tram at any time never exceeds this capacity. Note that at each stop all exiting passengers exit before any entering passenger enters the tram.

Input

The first line contains a single number n (2 ≤ n ≤ 1000) — the number of the tram's stops.

Then n lines follow, each contains two integers ai and bi (0 ≤ ai, bi ≤ 1000) — the number of passengers that exits the tram at the i-th stop, and the number of passengers that enter the tram at the i-th stop. The stops are given from the first to the last stop in the order of tram's movement.

* The number of people who exit at a given stop does not exceed the total number of people in the tram immediately before it arrives at the stop. More formally, . This particularly means that a1 = 0.

* At the last stop, all the passengers exit the tram and it becomes empty. More formally,

* No passenger will enter the train at the last stop. That is, bn = 0.

Output

Print a single integer denoting the minimum possible capacity of the tram (0 is allowed).

Note

For the first example, a capacity of 6 is sufficient:

* At the first stop, the number of passengers inside the tram before arriving is 0. Then, 3 passengers enter the tram, and the number of passengers inside the tram becomes 3.

* At the second stop, 2 passengers exit the tram (1 passenger remains inside). Then, 5 passengers enter the tram. There are 6 passengers inside the tram now.

* At the third stop, 4 passengers exit the tram (2 passengers remain inside). Then, 2 passengers enter the tram. There are 4 passengers inside the tram now.

* Finally, all the remaining passengers inside the tram exit the tram at the last stop. There are no passenger inside the tram now, which is in line with the constraints.

Since the number of passengers inside the tram never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible for the tram to have a capacity less than 6. Hence, 6 is the correct answer.

#### Sample test(s):

```
input
4
0 3
2 5
4 2
4 0
output
6
```

#### Code:

```
#这道题主要是阅读题...
#第一行输入为总共有几站
#接下来的输入就分别是下了多少人，上了多少人
#最后输出的是这个Tram可以容纳多少人
#实际上就是求出一路上下旅客中，旅客最多的时候是多少人
import sys
#第一行输入有多少站
stops = int(sys.stdin.readline())
maxCapacity = 0
capacity = 0
#循环输入
for i in range(stops):
inputs = sys.stdin.readline().split()
stepOut = int(inputs[0])
stepIn = int(inputs[1])
#算出当前车上的人数
#当前车上人数 = 之前车上人数 - 下车的人数 + 上车的人数
capacity = capacity - stepOut + stepIn
#和最大人数进行比较并保存最大人数
maxCapacity = max(maxCapacity, capacity)
#输出车上最大人数
print maxCapacity
```

# 231A Team

One day three best friends Petya, Vasya and Tonya decided to form a team and take part in programming contests. Participants are usually offered several problems during programming contests. Long before the start the friends decided that they will implement a problem if at least two of them are sure about the solution. Otherwise, the friends won't write the problem's solution.

This contest offers n problems to the participants. For each problem we know, which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution.

Input

The first input line contains a single integer n (1 ≤ n ≤ 1000) — the number of problems in the contest. Then n lines contain three integers each, each integer is either 0 or 1. If the first number in the line equals 1, then Petya is sure about the problem's solution, otherwise he isn't sure. The second number shows Vasya's view on the solution, the third number shows Tonya's view. The numbers on the lines are separated by spaces.

Output

Print a single integer — the number of problems the friends will implement on the contest.

Note

In the first sample Petya and Vasya are sure that they know how to solve the first problem and all three of them know how to solve the second problem. That means that they will write solutions for these problems. Only Petya is sure about the solution for the third problem, but that isn't enough, so the friends won't take it.

In the second sample the friends will only implement the second problem, as Vasya and Tonya are sure about the solution.

#### Sample test(s):

```
input
3
1 1 0
1 1 1
1 0 0
output
2
input
2
1 0 0
0 1 1
output
1
```

#### Code:

```
#当三个人中至少有两个人确定能做出来竞赛题目，他们才会去做这道题
#题目要求统计总共有多少行输入里面至少包含2个1
import sys
n = int(sys.stdin.readline())
sovled = 0
for i in range(n):
inputs = sys.stdin.readline().split()
unsure = 0
for j in range(len(inputs)):
#注意直接用split()获取的inputs存放的是字符串而不是数字
if inputs[j] == "0": unsure += 1
if unsure < 2: sovled += 1
print sovled
```

# 82A Double Cola

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on. This process continues ad infinitum.

For example, Penny drinks the third can of cola and the queue will look like this: Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny.

Write a program that will print the name of a man who will drink the n-th can.

Note that in the very beginning the queue looks like that: Sheldon, Leonard, Penny, Rajesh, Howard. The first person is Sheldon.

Input

The input data consist of a single integer n (1 ≤ n ≤ 10**9).

It is guaranteed that the pretests check the spelling of all the five names, that is, that they contain all the five possible answers.

Output

Print the single line — the name of the person who drinks the n-th can of cola. The cans are numbered starting from 1. Please note that you should spell the names like this: "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" (without the quotes). In that order precisely the friends are in the queue initially.

#### Sample test(s):

```
input
1
output
Sheldon
input
6
output
Sheldon
input
1802
output
Penny
```

#### Code:

```
#简单中文描述就是：
#5个人排队喝神奇可乐，分别是Sheldon,Lenard,Penny,Rajesh,Howard
#每个人喝完可乐以后会分裂成2个同样的人，并且到队尾排队继续等待喝可乐。
#比如最开始的时候，首先是Sheldon去喝可乐，喝完以后
#这时候队列就变成了Lenard,Penny,Rajesh,Howard,Sheldon,Sheldon
#这道题要求输出第n个人应该是谁在喝可乐
import sys
import math
n = int(sys.stdin.readline())
#我的做法是定义一个因子factor
#factor表示的第几轮，没经过一轮实际上队列就会翻倍
#第一轮结束，就有1*5个人加入到队列中
#第二轮结束，就有2*5个人假如到队列中
#以此类推
drinked = 0
factor = 1
while True:
if n <= drinked + factor * 5:
people = math.ceil((n - drinked) * 1.0 / factor)
if people == 1: print "Sheldon"
elif people == 2: print "Leonard"
elif people == 3: print "Penny"
elif people == 4: print "Rajesh"
elif people == 5: print "Howard"
break
else:
drinked = drinked + factor * 5
factor = factor * 2
#print "drinked = %d | facotr = %d" %(drinked, factor)
```

# 131A cAPS lOCK

wHAT DO WE NEED cAPS LOCK FOR?

Caps lock is a computer keyboard key. Pressing it sets an input mode in which typed letters are capital by default. If it is pressed by accident, it leads to accidents like the one we had in the first passage.

Let's consider that a word has been typed with the Caps lock key accidentally switched on, if:

* either it only contains uppercase letters; * or all letters except for the first one are uppercase.In this case we should automatically change the case of all letters. For example, the case of the letters that form words "hELLO", "HTTP", "z" should be changed.

Write a program that applies the rule mentioned above. If the rule cannot be applied, the program should leave the word unchanged.

Input

The first line of the input data contains a word consisting of uppercase and lowercase Latin letters. The word's length is from 1 to 100 characters, inclusive.

Output

Print the result of the given word's processing.

#### Sample test(s):

```
input
cAPS
output
Caps
input
Lock
output
Lock
```

#### Code:

```
#当大写Caps Lock无意中被按中的话，输出的字母都是反的
#正常一个单词Caps可以就变成了cACPS
#这道题就是要把这种错误纠正过来。
#第一种情况是全是大写字母，要变成小写字母
#第二种情况是除了首字母以外都是大写，要将其反过来，就像cAPS一样
import sys
word = sys.stdin.readline().strip()
#设置一个布尔类型，用来判断首字母是否为大写
firstCharLower = False
result = ""
for i in range(len(word)):
#如果是首字母，则判断是否为大写并设置firstCharLower
if i == 0:
if word[i].islower():
firstCharLower = True
result = result + word[i].upper()
else:
firstCharLower = False
result = result + word[i].lower()
else:
#如果不是首字母
#则根据firstCharLower来采取不同的判断方式
if firstCharLower:
if word[i].islower():
result = word
break
else:
result = result + word[i].lower()
else:
if word[i].islower():
result = word
break
else:
result = result + word[i].lower()
print result
```

# 282A Bit++

The classic programming language of Bitland is Bit++. This language is so peculiar and complicated.

The language is that peculiar as it has exactly one variable, called x. Also, there are two operations:

* Operation ++ increases the value of variable x by 1.

* Operation -- decreases the value of variable x by 1.A statement in language Bit++ is a sequence, consisting of exactly one operation and one variable x. The statement is written without spaces, that is, it can only contain characters "+", "-", "X". Executing a statement means applying the operation it contains.

A programme in Bit++ is a sequence of statements, each of them needs to be executed. Executing a programme means executing all the statements it contains.

You're given a programme in language Bit++. The initial value of x is 0. Execute the programme and find its final value (the value of the variable when this programme is executed).

Input

The first line contains a single integer n (1 ≤ n ≤ 150) — the number of statements in the programme.

Next n lines contain a statement each. Each statement contains exactly one operation (++ or --) and exactly one variable x (denoted as letter «X»). Thus, there are no empty statements. The operation and the variable can be written in any order.

Output

Print a single integer — the final value of x.

#### Sample test(s):

```
input
1
++X
output
1
input
2
X++
--X
output
0
```

#### Code:

```
#第一行输入表示总共有几步操作
#X初始值为0
#直接判断输入中是否含有"+"或者"-"来进行加减操作就可以了
import sys
n = int(sys.stdin.readline())
result = 0
#循环处理输入，用string.find('+')函数来检查时候含有"+"
#这里用到了三元运算符，在java里是exp1?exp2:exp3
#python里面的使用方式为(相对于java来说):exp2 if exp1 else exp3
#即：如果exp1返回True,则执行exp2，否则执行exp3
for i in range(n):
inputs = sys.stdin.readline()
result = result - 1 if inputs.find('+') == -1 else result + 1
print result
```

# 266A Stones on the Table

There are n stones on the table in a row, each of them can be red, green or blue. Count the minimum number of stones to take from the table so that any two neighboring stones had different colors. Stones in a row are considered neighboring if there are no other stones between them.

Input

The first line contains integer n (1 ≤ n ≤ 50) — the number of stones on the table.The next line contains string s, which represents the colors of the stones. We'll consider the stones in the row numbered from 1 to n from left to right. Then the i-th character s equals "R", if the i-th stone is red, "G", if it's green and "B", if it's blue.

Output

Print a single integer — the answer to the problem.

#### Sample test(s):

```
input
3
RRG
output
1
input
5
RRRRR
output
4
input
4
BRBG
output
0
```

#### Code:

```
#需要拿掉最少多少块带颜色的石头才能保证每块石头与相邻的石头颜色不同
#任意N块挨着的石头就一定得拿走N-1块。
#只需要从头遍历一遍，发现相同颜色的石头则记录下来就可以了
import sys
n = int(sys.stdin.readline())
inputs = sys.stdin.readline().strip()
mini = 0
cmpColor = ""
for i in range(n):
#currentColor用来记录当前石头的颜色
#cmpColor用来记录上一块需要比较颜色的石头的颜色
currentColor = inputs[i]
#如果石头颜色相同，则mini加1，cmpColor不变
#如果石头颜色不同，则改变cmColor为当前石块的颜色
if currentColor == cmpColor:
mini += 1
else:
cmpColor = currentColor
print mini
```

# 119A Epic Game

Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number a and Antisimon receives number b. They also have a heap of n stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take).

Your task is to determine by the given a, b and n who wins the game.

Input

The only string contains space-separated integers a, b and n (1 ≤ a, b, n ≤ 100) — the fixed numbers Simon and Antisimon have received correspondingly and the initial number of stones in the pile.

Output

If Simon wins, print "0" (without the quotes), otherwise print "1" (without the quotes).

#### Sample test(s):

```
input
3 5 9
output
0
input
1 1 100
output
1
```

#### Code:

```
#Simon和Antisimon在玩一个游戏，他们分解获得a和b两个数字
#有一个石头堆，总共有n块石头
#Simon和Antisimon轮流从石头堆中拿石头
#每次拿石头的数量是他们所拥有的数字(a或者b)与剩下石头的最大公约数
#直到没有石头可拿为止
#如果Simon赢了，输出0，如果Antisimon赢了，输出1
import sys
#首先定义一个计算最大公约数的函数
#注意：数字k和0的最大公约数是k(题目中给出的定义)
# def function(para1,para2): 函数定义，具体请参考Python的基础语法教程
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
inputs = sys.stdin.readline().split()
a = int(inputs[0])
b = int(inputs[1])
n = int(inputs[2])
turn = 1 #1 stands for simon's turn, 0 stands for Antisimon's turn
while True:
if n == 0:
print turn
break
if turn == 1:
l = gcd(a, n)
n -= l
turn = 0
else:
l = gcd(b, n)
n -= l
turn = 1
```

# 121A Petya and Strings

Little Petya loves presents. His mum bought him two strings of the same size for his birthday. The strings consist of uppercase and lowercase Latin letters. Now Petya wants to compare those two strings lexicographically. The letters' case does not matter, that is an uppercase letter is considered equivalent to the corresponding lowercase letter. Help Petya perform the comparison.

Input

Each of the first two lines contains a bought string. The strings' lengths range from 1 to 100 inclusive. It is guaranteed that the strings are of the same length and also consist of uppercase and lowercase Latin letters.

Output

If the first string is less than the second one, print "-1". If the second string is less than the first one, print "1". If the strings are equal, print "0". Note that the letters' case is not taken into consideration when the strings are compared.

Note

If you want more formal information about the lexicographical order (also known as the "dictionary order" or "alphabetical order"), you can visit the following site: http://en.wikipedia.org/wiki/Lexicographical_order

#### Sample test(s):

```
input
aaaa
aaaA
output
0
input
abs
Abz
output
-1
input
abcdefg
AbCdEfF
output
1
```

#### Code:

```
#输入两段字符串，比较两段字符串大小
#题目要求忽略大小写，所以首先把字符串全部转换成小写
#从头开始逐字母进行比较
import sys
#lower()函数会将字符串中所有字母转换成小写
#upper()函数会将字符串中所有字母转换成大写
firstS = sys.stdin.readline().strip().lower()
secondS = sys.stdin.readline().strip().lower()
for i in range(len(firstS)):
firstChar = firstS[i]
secondChar = secondS[i]
if firstChar > secondChar:
print 1
break
elif firstChar < secondChar:
print -1
break
if i == len(firstS) - 1:
print 0
```

# 133A HQ9+

HQ9+ is a joke programming language which has only four one-character instructions:

* "H" prints "Hello, World!",

* "Q" prints the source code of the program itself,

* "9" prints the lyrics of "99 Bottles of Beer" song,

* "+" increments the value stored in the internal accumulator.Instructions "H" and "Q" are case-sensitive and must be uppercase. The characters of the program which are not instructions are ignored.

You are given a program written in HQ9+. You have to figure out whether executing this program will produce any output.

Input

The input will consist of a single line p which will give a program in HQ9+. String p will contain between 1 and 100 characters, inclusive. ASCII-code of each character of p will be between 33 (exclamation mark) and 126 (tilde), inclusive.

Output

Output "YES", if executing the program will produce any output, and "NO" otherwise.

Note

In the first case the program contains only one instruction — "H", which prints "Hello, World!".

In the second case none of the program characters are language instructions.

#### Sample test(s):

```
input
Hi!
output
YES
input
Codeforces
output
NO
```

#### Code:

```
#这道题不想多做解释....想多了就杯具了
#上面的不是这道题的code，下面的才是
import sys
#wtf... it is indeed a joke...
#it doesn't need to be taken seriously
#Here is the code for "+" which can increase the
#value of formal letter
'''
inputs = sys.stdin.readline().strip()
flag = False
while True:
n = inputs.find("+")
if n == -1: break
if n == 0: inputs = inputs[1:]
else:
if inputs[n-1] in "GP8":
print "YES"
flag = True
break
else:
inputs = inputs[:n-1] + inputs[n+1:]
if not flag:
for i in range(len(inputs)):
if inputs[i] in "HQ9":
print "YES"
flag = True
break
if not flag:
print "NO"
'''
#here is the code for this stupid question
inputs = sys.stdin.readline().strip()
flag = False
for i in range(len(inputs)):
if inputs[i] in "HQ9":
print "YES"
flag = True
break
if not flag: print "NO"
```

# 148A Insomnia cure

«One dragon. Two dragon. Three dragon», — the princess was counting. She had trouble falling asleep, and she got bored of counting lambs when she was nine.

However, just counting dragons was boring as well, so she entertained herself at best she could. Tonight she imagined that all dragons were here to steal her, and she was fighting them off. Every k-th dragon got punched in the face with a frying pan. Every l-th dragon got his tail shut into the balcony door. Every m-th dragon got his paws trampled with sharp heels. Finally, she threatened every n-th dragon to call her mom, and he withdrew in panic.

How many imaginary dragons suffered moral or physical damage tonight, if the princess counted a total of d dragons?

Input

Input data contains integer numbers k, l, m, n and d, each number in a separate line (1 ≤ k, l, m, n ≤ 10, 1 ≤ d ≤ 10**5).

Output

Output the number of damaged dragons.

Note

In the first case every first dragon got punched with a frying pan. Some of the dragons suffered from other reasons as well, but the pan alone would be enough.

In the second case dragons 1, 7, 11, 13, 17, 19 and 23 escaped unharmed.

#### Sample test(s):

```
input
1
2
3
4
12
output
12
input
2
3
4
5
24
output
17
```

#### Code:

```
#这孩纸睡不着没事数龙玩...还自己制造故事情节...
#第k和k倍数的龙会被她用平底锅打飞(灰太狼的节奏吗)...
#第l和l倍数的龙尾巴会被她用门夹...
#第m和m倍数的龙脚掌会被她用高跟鞋踩...
#第n和n倍数的龙会被她威胁...
#输出的是有多少只龙精神上或者肉体上受到了她的摧残...
import sys
k = int(sys.stdin.readline())
l = int(sys.stdin.readline())
m = int(sys.stdin.readline())
n = int(sys.stdin.readline())
d = int(sys.stdin.readline())
result = 0
#遍历数组，如果能被klmn整除
#则说明这条可怜的龙已然被摧残
for i in range(1,d+1):
if i%k==0 or i%l==0 or i%m==0 or i%n==0:
result += 1
print result
```

# 96A Football

Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

Input

The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.

Output

Print "YES" if the situation is dangerous. Otherwise, print "NO".

#### Sample test(s):

```
input
001001
output
NO
input
1000000001
output
YES
```

#### Code:

```
#如果有至少7个同队球员在一起，则输出YES,否则输出NO
#实际上就是给定包含0和1的输入，计算相连数字的最大个数
#如果大于等于7，则输出YES,否则输出NO
import sys
inputs = sys.stdin.readline().strip()
zeroN = 0
oneN = 0
lastN = -1
result = "NO"
for i in range(len(inputs)):
if inputs[i] == "0":
if lastN == 0:
zeroN += 1
if(zeroN == 7):
result = "YES"
break
else:
zeroN = 1
oneN = 0
lastN = 0
if inputs[i] == "1":
if lastN == 1:
oneN += 1
if(oneN == 7):
result = "YES"
break
else:
oneN = 1
zeroN = 0
lastN = 1
print result
```

# 160A Twins

Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like.

Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, n coins of arbitrary values a1, a2, ..., an. But as Mom was running out of time, she didn't split the coins for you two. So she scribbled a note asking you to split the money equally.

As you woke up, you found Mom's coins and read her note. "But why split the money equally?" — you thought. After all, your twin is sleeping and he won't know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is strictly larger than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you've decided to stick to the following strategy to avoid suspicions: you take the minimum number of coins, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what minimum number of coins you need to take to divide them in the described manner.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of coins. The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the coins' values. All numbers are separated with spaces.

Output

In the single line print the single number — the minimum needed number of coins.

Note

In the first sample you will have to take 2 coins (you and your twin have sums equal to 6, 0 correspondingly). If you take 1 coin, you get sums 3, 3. If you take 0 coins, you get sums 0, 6. Those variants do not satisfy you as your sum should be strictly more that your twins' sum.

In the second sample one coin isn't enough for us, too. You can pick coins with values 1, 2 or 2, 2. In any case, the minimum number of coins equals 2.

#### Sample test(s):

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

#### Code:

```
#简单说，就是给你一堆硬币，每个硬币都有自己的面值
#你需要拿一些硬币，使得你拿走的硬币总面值大于剩下的硬币
#你可能有很多种方案，但是题目要求用最少的硬币数量来实现
#最终输出你总共拿了几个硬币
import sys
coins = []
coinsValueTotal = 0
n = int(sys.stdin.readline())
inputs = sys.stdin.readline().split()
for i in range(len(inputs)):
coin = int(inputs[i])
coins.append(coin)
coinsValueTotal += coin
coins.sort(reverse = True)
minCoins = 0
halfCoinsValueTotal = coinsValueTotal / 2
for i in range(len(coins)):
minCoins += coins[i]
if(minCoins > halfCoinsValueTotal):
print i+1
break
```

# 228A Is your horseshoe on the other hoof?

Valera the Horse is going to the party with friends. He has been following the fashion trends for a while, and he knows that it is very popular to wear all horseshoes of different color. Valera has got four horseshoes left from the last year, but maybe some of them have the same color. In this case he needs to go to the store and buy some few more horseshoes, not to lose face in front of his stylish comrades.

Fortunately, the store sells horseshoes of all colors under the sun and Valera has enough money to buy any four of them. However, in order to save the money, he would like to spend as little money as possible, so you need to help Valera and determine what is the minimum number of horseshoes he needs to buy to wear four horseshoes of different colors to a party.

Input

The first line contains four space-separated integers s1, s2, s3, s4 (1 ≤ s1, s2, s3, s4 ≤ 10**9) — the colors of horseshoes Valera has.

Consider all possible colors indexed with integers.

Output

Print a single integer — the minimum number of horseshoes Valera needs to buy.

#### Sample test(s):

```
input
1 7 3 3
output
1
input
7 7 7 7
output
3
```

#### Code:

```
#输入为4个数字，每个数字代表一个颜色
#题目要求最终要4个不同的颜色
#输出为了要4个不同的颜色，需要更改几个颜色
import sys
colors = sys.stdin.readline().split()
colors.sort()
differentColors = 0
lastColor = ""
for i in range(4):
if colors[i] != lastColor:
differentColors += 1
lastColor = colors[i]
print 4 - differentColors
```