A - Generous Kefa

One day Kefa found n baloons. For convenience, we denote color of i-th baloon as si — lowercase letter of the Latin alphabet. Also Kefa has k friends. Friend will be upset, If he get two baloons of the same color. Kefa want to give out all baloons to his friends. Help Kefa to find out, can he give out all his baloons, such that no one of his friens will be upset — print «YES», if he can, and «NO», otherwise. Note, that Kefa’s friend will not upset, if he doesn’t get baloons at all.

Input
The first line contains two integers n and k (1 ≤ n, k ≤ 100) — the number of baloons and friends.

Next line contains string s — colors of baloons.

Output
Answer to the task — «YES» or «NO» in a single line.

You can choose the case (lower or upper) for each letter arbitrary.

Examples
Input
4 2
aabb
Output
YES
Input
6 3
aacaab
Output
NO
Note
In the first sample Kefa can give 1-st and 3-rd baloon to the first friend, and 2-nd and 4-th to the second.

In the second sample Kefa needs to give to all his friends baloons of color a, but one baloon will stay, thats why answer is «NO».

这题的意思是kefa想给朋友发气球，但是发给一个朋友两个一样颜色的朋友就伐开心（2333），所以只要保证每个字母不超过k次就可以，第一想法就是开一个char–int map来记录，最后遍历一遍查看是否有大于k的 代码：

#include<bits/stdc++.h>
using namespace std;
map<char,int>mp;
int main()
{
  int n,k;
  cin>>n>>k;
  string a;
  cin>>a;
  int l=a.size();
  int ans=0;
  for(int i=0;i<l;i++)
  {
    mp[a[i]]++;
    ans=max(ans,mp[a[i]]);
  }
  if(ans>k)
  {
    cout<<"NO";
  }
  else
  cout<<"YES";
}

B - Godsend

Leha somehow found an array consisting of n integers. Looking at it, he came up with a task. Two players play the game on the array. Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?

Input
First line of input data contains single integer n (1 ≤ n ≤ 106) — length of the array.

Next line contains n integers a1, a2, …, an (0 ≤ ai ≤ 109).

Output
Output answer in single line. “First”, if first player wins, and “Second” otherwise (without quotes).

Examples
Input
4
1 3 2 3
Output
First
Input
2
2 2
Output
Second
Note
In first sample first player remove whole array in one move and win.

In second sample first player can’t make a move and lose.

这题的意思是有两个人在做游戏，第一个人可以拿走和是奇数的序列，第二个人拿走是偶数个的序列，最终到谁不能取未知，不能取的那个人就输了。 可以分为以下几种情况：
① 和是奇数，这样的话第一个人第一轮就可以拿走所有的数，第二个人就没有办法取，这样第一个人就赢了
② 和是偶数：
（1）全都是偶数，这种情况上来就是第一个人无法取，所以就输了。
（2）有奇数个奇数，这样第一个人可以选择取走偶数个奇数和所有的偶数，比如说有7个数：1 2 3 4 5 6 7，第一个人可以拿走2 3 4 5 6 ，剩下一个奇数第二个人就没有办法拿走了，所以是第一个人赢了
在和是偶数的情况下不会出现偶数个奇数，所以这就是全部的情况了，综上所述：只要有奇数或者所有的数字加在一起是一个奇数就是第一个人赢了，否则是第二个人 代码：

还有就是这个题一定要关同步！！！这个题虽然a了但是很险，1809ms

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  int f=0;
  long long sum=0;
  for(int i=0;i<n;i++)
  cin>>a[i],sum+=a[i];
  if(sum%2!=0)
  {
    cout<<"First";
    return 0;
  }
  for(int i=0;i<n;i++)
  {
    if(a[i]%2!=0)
    f=1;
  }
  if(f)
  cout<<"First";
  else
  cout<<"Second";
}

C - Leha and Function

Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, …, n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition Ai ≥ Bj holds. Help Leha rearrange the numbers in the array A so that the sum is maximally possible, where A’ is already rearranged array.

Input
First line of input data contains single integer m (1 ≤ m ≤ 2·105) — length of arrays A and B.

Next line contains m integers a1, a2, …, am (1 ≤ ai ≤ 109) — array A.

Next line contains m integers b1, b2, …, bm (1 ≤ bi ≤ 109) — array B.

Output
Output m integers a’1, a’2, …, a’m — array A’ which is permutation of the array A.

Examples
Input
5
7 3 5 3 4
2 1 3 2 3
Output
4 7 3 5 3
Input
7
4 6 5 8 8 2 6
2 1 2 2 1 1 2
Output
2 6 4 5 8 8 6

此处无声胜有声（待解决2333）

D - Leha and another game about graph

Leha plays a computer game, where is on each level is given a connected graph with n vertices and m edges. Graph can contain multiple edges, but can not contain self loops. Each vertex has an integer di, which can be equal to 0, 1 or  - 1. To pass the level, he needs to find a «good» subset of edges of the graph or say, that it doesn’t exist. Subset is called «good», if by by leaving only edges from this subset in the original graph, we obtain the following: for every vertex i, di =  - 1 or it’s degree modulo 2 is equal to di. Leha wants to pass the game as soon as possible and ask you to help him. In case of multiple correct answers, print any of them.

Input
The first line contains two integers n, m (1 ≤ n ≤ 3·105, n - 1 ≤ m ≤ 3·105) — number of vertices and edges.

The second line contains n integers d1, d2, …, dn ( - 1 ≤ di ≤ 1) — numbers on the vertices.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) — edges. It’s guaranteed, that graph in the input is connected.

Output
Print  - 1 in a single line, if solution doesn’t exist. Otherwise in the first line k — number of edges in a subset. In the next k lines indexes of edges. Edges are numerated in order as they are given in the input, starting from 1.

Examples
Input
1 0
1
Output
-1
Input
4 5
0 0 0 -1
1 2
2 3
3 4
1 4
2 4
Output
0
Input
2 1
1 1
1 2
Output
1
1
Input
3 3
0 -1 1
1 2
2 3
1 3
Output
1
2
Note
In the first sample we have single vertex without edges. It’s degree is 0 and we can not get 1.

此处无声胜有声（待解决2333）

E - New Year and Ancient Prophecy

Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn’t know any ancient languages and thus is unable to understand the prophecy. But he knows digits!

One fragment of the prophecy is a sequence of n digits. The first digit isn’t zero. Limak thinks that it’s a list of some special years. It’s hard to see any commas or spaces, so maybe ancient people didn’t use them. Now Limak wonders what years are listed there.

Limak assumes three things:

Years are listed in the strictly increasing order;
Every year is a positive integer number;
There are no leading zeros.
Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo 109 + 7.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of digits.

The second line contains a string of digits and has length equal to n. It’s guaranteed that the first digit is not ‘0’.

Output
Print the number of ways to correctly split the given sequence modulo 109 + 7.

Examples
Input
6
123434
Output
8
Input
8
20152016
Output
4
Note
In the first sample there are 8 ways to split the sequence:

“123434” = “123434” (maybe the given sequence is just one big number)
“123434” = “1” + “23434”
“123434” = “12” + “3434”
“123434” = “123” + “434”
“123434” = “1” + “23” + “434”
“123434” = “1” + “2” + “3434”
“123434” = “1” + “2” + “3” + “434”
“123434” = “1” + “2” + “3” + “4” + “34”
Note that we don’t count a split “123434” = “12” + “34” + “34” because numbers have to be strictly increasing.

In the second sample there are 4 ways:

“20152016” = “20152016”
“20152016” = “20” + “152016”
“20152016” = “201” + “52016”
“20152016” = “2015” + “2016”

此处无声胜有声（待解决2333）

F - New Year and Days

Today is Wednesday, the third day of the week. What’s more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn’t sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.

Input
The only line of the input is in one of the following two formats:

“x of week” where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.
“x of month” where x (1 ≤ x ≤ 31) denotes the day of the month.
Output
Print one integer — the number of candies Limak will save in the year 2016.

Examples
Input
4 of week
Output
52
Input
30 of month
Output
11
Note
Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.

这道题我一看只有2016年，于是就对着日历一个数一个数数的= = 最后数出来星期五和星期六都有53天还有点不敢相信又查了一遍，等我查完发现大家都a完这道题了。。。而且2016是闰年，2月有29天，所以29天是个分界点，输入的时候输入两个字符串就ok 代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x;
  cin>>x;
  string of;
  string y;
  cin>>of>>y;
  int ans=0;
  if(y=="week")
  {
    if(x==5||x==6)
    {
      ans=53;
    }
    else
      ans=52;
  }
  else if(y=="month")
  {
    if(x>=1&&x<=29)
    ans=12;
    else if(x==30)
    ans=11;
    else
    ans=7;
  }
  cout<<ans;
}

G - New Year and Domino

They say “years are like dominoes, tumbling one after the other”. But would a year fit into a grid? I don’t think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by ‘.’) or forbidden (denoted by ‘#’). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?

Input
The first line of the input contains two integers h and w (1 ≤ h, w ≤ 500) – the number of rows and the number of columns, respectively.

The next h lines describe a grid. Each line contains a string of the length w. Each character is either ‘.’ or ‘#’ — denoting an empty or forbidden cell, respectively.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains four integers r1i, c1i, r2i, c2i (1 ≤ r1i ≤ r2i ≤ h, 1 ≤ c1i ≤ c2i ≤ w) — the i-th query. Numbers r1i and c1i denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2i and c2i denote the row and the column (respectively) of the bottom right cell of the rectangle.

Output
Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.

Examples
Input
5 8
…#…#
.#…
##.#…
##…#.##
…
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
Output
4
0
10
15
Input
7 39
…
.###…###…#…###…###…###…#…###.
…#…#.#…#…#…#…#.#…#…#…
.###…#.#…#…###…###…#.#…#…###.
.#…#.#…#…#…#…#.#…#…#.#.
.###…###…#…###…###…###…#…###.
…
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8
Output
53
89
120
23
0
2
Note
A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.

此处无声胜有声（待解决2333）

H - New Year and Old Property

The year 2015 is almost over.

Limak is a little polar bear. He has recently learnt about the binary system. He noticed that the passing year has exactly one zero in its representation in the binary system — 201510 = 111110111112. Note that he doesn’t care about the number of zeros in the decimal representation.

Limak chose some interval of years. He is going to count all years from this interval that have exactly one zero in the binary representation. Can you do it faster?

Assume that all positive integers are always written without leading zeros.

Input
The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 1018) — the first year and the last year in Limak’s interval respectively.

Output
Print one integer – the number of years Limak will count in his chosen interval.

Examples
Input
5 10
Output
2
Input
2015 2015
Output
1
Input
100 105
Output
0
Input
72057594000000000 72057595000000000
Output
26
Note
In the first sample Limak’s interval contains numbers 510 = 1012, 610 = 1102, 710 = 1112, 810 = 10002, 910 = 10012 and 1010 = 10102. Two of them (1012 and 1102) have the described property.

这题的意思是看看输入范围内有多少个转成二进制只有一个0的解，第一时间就想到了学了一段时间的python，因为python转进制比较方便（结果赛后朋哥说不让用python2333），第一步是用map输入两个数，然后转成二进制，因为直接转的话输出的二进制数字会出现前导的"0b"所以需要用[2:]切片切一下，从下标2开始往后取，然后取二进制数的长度，因为第二个数总是比第一个数二进制数要大或者等于，所以就让i从左边界（第一个数的长度）开始，到右边界结束
这里要注意的是python的range设定的是左闭右开的区间，所以必须让右边界+1才行 举个例子：l=3，r=4 如果不加这个+1意思就是for(int i=3;i<4;i++) 就走了一次循环

然后就是位移问题了，举个例子，1往左移三位就变成了1000，减去1就变成了111，再减去1向左移动2、1位就是110和101，这样就保证了满足题目要求，随后利用python特性直接加两个>=就可以判断在不在区间，在区间的话就+=1就行了

python代码：

a,b= map(int,input().split())
sum=0 
c=bin(a)[2:]
d=bin(b)[2:]
l=len(c)
r=len(d)
for i in range(l,r+1):
    for j in range(0,i-1):
        if (a<=(1<<i)-1-(1<<j)<=b):
            sum+=1
print(sum)

后来看了mhr大佬的博客感觉学到了，c++用这个原理也完全可以做，而且不需要转成2进制了，因为8对应着1000，16对应着10000，这个特性和二进制紧密挂钩的，而且往左移动三位其实就等同于乘以2^3，所以就有了以下代码：

我看还需要开long double 这是我从来没有开过的，可能精度更高把

还有一个问题就是使用pow函数的时候一定要用double类型，不然很小的位数用int都会有误差，上次做一道cf上的b题就因为这个pow函数wa了两次。。。 如果想用int类型的话直接可以写一个qpow

最终代码：

#include<bits/stdc++.h>
using namespace std;
int len(long long n)
{
  long long ans=0;
  while(n)
  {
    ans++;
    n/=2;
  }
  return ans;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int l,r;
  cin>>l>>r;
  long long sum=0;
  for(long long int i=len(l);i<=len(r);i++)
  for(long long int j=0;j<i-1;j++)
  {
    long double ans=pow(2,i)-1-pow(2,j);
    if(ans>=l&&ans<=r)
    sum++;
  }
  cout<<sum;
}