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».
題意：分氣球，氣球的顔色用小寫字母來表示，必須保證每個人拿到的氣球是不一樣顔色的。
水題，隻需要保證任何一種顔色的氣球的數目不大于k即可。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int n,k,a[200];
int main()
{
while(cin>>n>>k){
char c;
bool flag=true;
for(int i=1;i<=n;i++){
cin>>c;
a[c-'0']++;
if(a[c-'0']>k){
printf("NO\n");
flag=false;
break;
}
}
if(flag==true)
printf("YES\n");
}
}
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.
題意：由n個數字組成的數組，第一個隻能取連續的，加起來為奇數的數字，第二個人隻能取連續的，加起來為偶數的數字。
分析題目：如果這些數字的和為奇數，那麼第一個人可以直接将所有的都取走，那麼第一個獲勝；
如果這些數字全部為偶數，還是第一個人先取，隻要這些數中有一個奇數，第一個人取走，剩下的數的和還是奇數，第二個就算取了一段偶數，那麼第一個人再取一次就可以全部取走。
是以綜上分析，隻要這n個數中有一個數是奇數，那麼第一個人赢，否則第二個人赢。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int n;
int main()
{
while(~sc(n)){
int a;
bool flag=true;
for(int i=1;i<=n;i++){
sc(a);
if(a&1)
flag=false;
}
if(flag==true)
printf("Second\n");
else
printf("First\n");
}
}
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 題意：自我感覺這個題目不大好懂，所謂F（n,k）就是在1,2...n中所有的k個的組合中找最小的取平均值，
舉個栗子：
F（5,2）=（1,2)（1,3）（1,4）（1,5）（2,3）（2,4）（2,5）（3,4）（3,5）（4,5），這10個組合中取最小的也就是1,1,1,1,2,2,2,3,3,4，求平均值，（1+1+1+1+2+2+2+3+3+4）/10=2.
然後給兩個數組，A,B，求怎樣把A數組變換位置使sigmaF（A',B）最大。
根據上面這個例子我們可以發現這樣一個規律，F（n，k）中，n越大也就意味着分子上的數越多值也就越大，k越小也就意味着組合的數目越少值也就越小，也就是等價于讓A越大的同時B越小
當然這個規律我沒辦法驗證......大家也可以舉幾個例子看看，像F（4,1），F（4,2），F（5,2），試試就可以發現這個規律
剩下的求解也就簡單了，将A從大到小排序，B從小到大排序，将B離散化即可
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
const int N=2e5+10;
int n,a[N],ran[N];
struct node
{
int a;
int p;
}b[N];
bool cmp(const int a,const int b)
{
return a>b;
}
bool cmp1(node c,node b)
{
return c.a<b.a;
}
int main()
{
while(~sc(n)){
for(int i=1;i<=n;i++)
sc(a[i]);
for(int i=1;i<=n;i++){
sc(b[i].a);
b[i].p=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp1);
for(int i=1;i<=n;i++)
ran[b[i].p]=i; //離散化的過程
for(int i=1;i<=n;i++){
printf("%d",a[ran[i]]);
if(i!=n)
printf(" ");
}
printf("\n");
}
}
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年攢糖果，它可以選擇每周攢一次，可以是周一到周日的任何一天攢，或者每月攢一次，也可以是每個月的任何一天攢。是以就是求可以攢多少個？
題目說這個北極熊用的是一個 Gregorian月曆，我是直接按正常月曆算的......
2016是閏年，是以有366天，因為2016年的第一天是周五，是以366/7=52---2,是以除了周五周六有53個，其他的都隻有52個。
再看月份的，2月有29天，是以1号到29号都有12個，30号11個，31号隻有7個。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int n;
char s1[10],s2[10];
int main()
{
while(~scanf("%d%s%s",&n,s1,s2)){
if(s2[0]=='w'){
if(n==5||n==6)
printf("53\n");
else printf("52\n");
}
else {
if(n==30)
printf("11\n");
else if(n==31)
printf("7\n");
else printf("12\n");
}
}
}
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 1through 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
Copy
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
output
Copy
4
0
10
15
input
Copy
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
Copy
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.
題意： 在給定的n×m的方格中，擺多米諾骨牌，一塊多米諾骨牌占兩個位置，可以豎着也可以橫着，給q個詢問，兩個坐标構成的矩形，問這個矩形内可以有多少種擺法？
很明顯用二維字首和，這跟我之前做過的一個擺戰艦的題感覺很像，也是在一個方格中問有多少種戰艦的擺法，戰艦占幾個格子和怎麼擺忘了。
那具體這個題可以分别兩個二維數組存橫着擺和豎着擺的擺法數量，先預處理，在相減就可以了。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int a[510][510],b[510][510],n,m,q;
char c[510][510];
int main()
{
while(~scanf("%d%d",&n,&m)){
met(a,0);
met(b,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
if(c[i][j]==c[i][j+1]&&c[i][j]=='.')
a[i][j]++;
}
for(int i=1;i<=m;i++)
for(int j=1;j<n;j++){
if(c[j][i]==c[j+1][i]&&c[j][i]=='.')
b[j][i]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]+=a[i][j-1]; //求字首和
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
b[j][i]+=b[j-1][i]; //求字首和
sc(q);
int r1,c1,r2,c2;
while(q--){
int ans=0;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
for(int i=r1;i<=r2;i++)
ans+=a[i][c2-1]-a[i][c1-1]; //這裡-1是因為前面求的時候是目前格子和後一個格子判斷
for(int i=c1;i<=c2;i++)
ans+=b[r2-1][i]-b[r1-1][i];
printf("%d\n",ans);
}
}
}
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
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的個數為1的有多少個
雖然題意好懂，但是我對着題目懵逼了好長時間，本來想用字首和做，發現10^18次方，數組貌似存不下。。。
最後找了老半天規律才有了些思路
因為要0的個數隻有一個的，是以從1開始找，1乘上2，二進制就從1變成了10，這樣就符合要求了，10如果想要繼續找下去，10<<1,成了100，是以要加上1，就是101，是以繼續*2+1即可，那這隻是0在第二個位置上，如果在第三個位置呢？根據上面的描述就可以想到1先*2+1，成了11，在*2即可。
于是就有了一個規律，如果一個數不符合規律，*2即可使它符合規律，*2+1則不符合規律，
如果一個數符合規律，那麼如果想要繼續找下去隻能*2+1，
這其實算是一個深搜的過程，不斷找下去，如果這個數在區間内計數器ans就+1，直到這個數大于區間的最大值為止。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
ll a,b,ans;
void dfs(ll x,bool y)
{
if(x>b)
return ;
if(x>=a&&x<=b&&y==1)
ans++;
if(!y){
dfs(2*x,1);
dfs(2*x+1,0);
}
else
dfs(2*x+1,1);
}
int main()
{
while(~scanf("%lld%lld",&a,&b)){
ans=0;
dfs(1,0);
printf("%lld\n",ans);
}
}