這次題目的代碼都不長，CF的一貫風格

A - Game

?CodeForces - 513A?

Two players play a simple game. Each player is provided with a box with balls. First player's box contains exactly?n₁?balls and second player's box contains exactly?n₂balls. In one move first player can take from 1 to?k₁?balls from his box and throw them away. Similarly, the second player can take from 1 to?k₂?balls from his box in his move. Players alternate turns and the first player starts the game. The one who can't make a move loses. Your task is to determine who wins if both players play optimally.

Input

The first line contains four integers?n₁,?n₂,?k₁,?k₂. All numbers in the input are from 1 to 50.

This problem doesn't have subproblems. You will get 3 points for the correct submission.

Output

Output "First" if the first player wins and "Second" otherwise.

Examples

Input 2 2 1 2 Output Second Input 2 1 1 1 Output First

Note

Consider the first sample test. Each player has a box with 2 balls. The first player draws a single ball from his box in one move and the second player can either take 1 or 2 balls from his box in one move. No matter how the first player acts, the second player can always win if he plays wisely.

A似曾相識，但是又不會做。First有n1個球，他每次可以移動k1個球;Second有n2個球，他每次可以移動k2個球

雖然是博弈，兩個人都選擇最優策略，但是其實兩個人每次都是拿一個球的，所以就是比大小的題目

#include<bits/stdc++.h> using namespace std; int main() {int n1,n2,k1,k2;cin>>n1>>n2>>k1>>k2;if(n1>n2)cout<<"First\n";elsecout<<"Second\n";return 0; }

B - Water The Garden

?CodeForces - 920A?

It is winter now, and Max decided it's about time he watered the garden.

The garden can be represented as?n?consecutive garden beds, numbered from?1?to?n.?kbeds contain water taps (i-th tap is located in the bed?x_i), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed?x_i?is turned on, then after one second has passed, the bed?x_i?will be watered; after two seconds have passed, the beds from the segment?[x_i?-?1,?x_i?+?1]?will be watered (if they exist); after?j?seconds have passed?(j?is an integer number), the beds from the segment?[x_i?-?(j?-?1),?x_i?+?(j?-?1)]?will be watered (if they exist).?Nothing changes during the seconds, so, for example, we can't say that the segment?[x_i?-?2.5,?x_i?+?2.5]?will be watered after?2.5?seconds have passed; only the segment?[x_i?-?2,?x_i?+?2]?will be watered at that moment.

?The garden from test?1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.?The garden from test?1after?2?seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed.

Max wants to?turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

Input

The first line contains one integer?t?— the number of test cases to solve (1?≤?t?≤?200).

Then?t?test cases follow. The first line of each test case contains two integers?nand?k?(1?≤?n?≤?200,?1?≤?k?≤?n) — the number of garden beds and water taps, respectively.

Next line contains?k?integers?x_i?(1?≤?x_i?≤?n) — the location of?i-th water tap. It is guaranteed that for each??condition?x_i?-?1?<?x_i?holds.

It is guaranteed that the sum of?n?over all test cases doesn't exceed?200.

Note that in hacks you have to set?t?=?1.

Output

For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

Example

Input 3
5 1
3
3 3
1 2 3
4 1
1 Output 3
1
4

Note

The first example consists of?3?tests:

There are?5?garden beds, and a water tap in the bed?3. If we turn it on, then after?1?second passes, only bed?3?will be watered; after?2?seconds pass, beds?[1,?3]?will be watered, and after?3?seconds pass, everything will be watered.

There are?3?garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after?1?second passes.

There are?4?garden beds, and only one tap in the bed?1. It will take?4?seconds to water, for example, bed?4.

這個是前一段時間的CF題目，花園要澆水，你有k個水井，1s可以澆當前這個點xi，也就是is你可以澆（xi-i,xi+i）

那我可以枚舉每個點最小的澆灌值啊，所以最小的就是最大的了，和最短路那個很相似

#include<bits/stdc++.h> using namespace std; const int MAXN=205; int x[MAXN]; int main() {int T;scanf("%d",&T);while(T--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=k;i++)scanf("%d",&x[i]);int res=0;for(int i=1;i<=n;i++){int mi=n;for(int j=1;j<=k;j++)mi=min(mi,abs(i-x[j]));res=max(res,mi);}printf("%d\n",res+1);}return 0; }

C - Paper Work

?CodeForces - 250A?

Polycarpus has been working in the analytic department of the "F.R.A.U.D." company for as much as?n?days. Right now his task is to make a series of reports about the company's performance for the last?n?days. We know that the main information in a day report is value?a_i, the company's profit on the?i-th day. If?a_i?is negative, then the company suffered losses on the?i-th day.

Polycarpus should sort the daily reports into folders. Each folder should include data on the company's performance for several consecutive days. Of course, the information on each of the?n?days should be exactly in one folder. Thus, Polycarpus puts information on the first few days in the first folder. The information on the several following days goes to the second folder, and so on.

It is known that the boss reads one daily report folder per day. If one folder has three or more reports for the days in which the company suffered losses?(a_i?<?0), he loses his temper and his wrath is terrible.

Therefore, Polycarpus wants to prepare the folders so that none of them contains information on three or more days with the loss, and the number of folders is minimal.

Write a program that, given sequence?a_i, will print the minimum number of folders.

Input

The first line contains integer?n?(1?≤?n?≤?100),?n?is the number of days. The second line contains a sequence of integers?a₁,?a₂,?...,?a_n?(|a_i|?≤?100), where?a_i?means the company profit on the?i-th day. It is possible that the company has no days with the negative?a_i.

Output

Print an integer?k?— the required minimum number of folders. In the second line print a sequence of integers?b₁,?b₂, ...,?b_k, where?b_j?is the number of day reports in the?j-th folder.

If there are multiple ways to sort the reports into?k?days, print any of them.

Examples

Input 11
1 2 3 -4 -5 -6 5 -5 -6 -7 6 Output 3
5 3 3 Input 5
0 -1 100 -1 0 Output 1
5

Note

Here goes a way to sort the reports from the first sample into three folders:

1 2 3 -4 -5?|?-6 5 -5?|?-6 -7 6

In the second sample you can put all five reports in one folder.

主要就是題意的理解了，超過三個負數是要劃到下一個文件的，就是數夠兩個負數

一個負數要輸出，沒有也是坑點，最后一段也會被處理不好

#include <bits/stdc++.h> using namespace std; int a[105]={0}; int main() {int n,t=0;cin>>n;for(int i=0,x;i<n;i++){cin>>x;if(x<0) a[i]=++t;}if(!t) t++;cout<<(t+1)/2<<endl;int x=0;for(int i=0;i<n;i++){if(a[i]%2==1&&a[i]!=1){if(x==0) cout<<i-x,x=i;else cout<<' '<<i-x,x=i;}}if(x) cout<<' ';cout<<n-x; }

D - Anatoly and Cockroaches

?CodeForces - 719B?

Anatoly lives in the university dorm as many other students do. As you know, cockroaches are also living there together with students. Cockroaches might be of two colors: black and red. There are?n?cockroaches living in Anatoly's room.

Anatoly just made all his cockroaches to form a single line. As he is a perfectionist, he would like the colors of cockroaches in the line to?alternate. He has a can of black paint and a can of red paint. In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color.

Help Anatoly find out the minimum number of turns he needs to make the colors of cockroaches in the line alternate.

Input

The first line of the input contains a single integer?n?(1?≤?n?≤?100?000)?— the number of cockroaches.

The second line contains a string of length?n, consisting of characters 'b' and 'r' that denote black cockroach and red cockroach respectively.

Output

Print one integer?— the minimum number of moves Anatoly has to perform in order to make the colors of cockroaches in the line to alternate.

Examples

Input 5
rbbrr Output 1 Input 5
bbbbb Output 2 Input 3
rbr Output 0

Note

In the first sample, Anatoly has to swap third and fourth cockroaches. He needs?1turn to do this.

In the second sample, the optimum answer is to paint the second and the fourth cockroaches red. This requires?2?turns.

In the third sample, the colors of cockroaches in the line are alternating already, thus the answer is?0.

這個序列要換為rb交替的，也就是可以r開頭，也可以b開頭

你可以交換任意兩個，你也可以直接替換，所以就是找不對的r和b啊

交換任意兩個rb之后替換，其實就是找最多不對的r和b

#include<bits/stdc++.h> using namespace std; int n; string s; int main() {cin>>n;cin>>s;int r=0,b=0;for(int i=0;s[i];i++){char c;if(i%2)c='r';else c='b';if(s[i]!=c&&c=='r')r++;if(s[i]!=c&&c=='b')b++;}int ans=max(r,b);r=0,b=0;for(int i=0;s[i];i++){char c;if(i%2)c='b';else c='r';if(s[i]!=c&&c=='r')r++;if(s[i]!=c&&c=='b')b++;}cout<<min(max(r,b),ans);return 0; }

E - Report

?CodeForces - 631C?

Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are?n?commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of?m?managers. Each of them may reorder the elements in some order. Namely, the?i-th manager either sorts first?r_i?numbers in non-descending or non-ascending order and then passes the report to the manager?i?+?1, or directly to Blake (if this manager has number?i?=?m).

Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence?a_i?of length?n?and the description of each manager, that is value?r_i?and his favourite order. You are asked to speed up the process and determine how the final report will look like.

Input

The first line of the input contains two integers?n?and?m?(1?≤?n,?m?≤?200?000)?— the number of commodities in the report and the number of managers, respectively.

The second line contains?n?integers?a_i?(|a_i|?≤?10⁹)?— the initial report before it gets to the first manager.

Then follow?m?lines with the descriptions of the operations managers are going to perform. The?i-th of these lines contains two integers?t_i?and?r_i?(,?1?≤?r_i?≤?n), meaning that the?i-th manager sorts the first?r_i?numbers either in the non-descending (if?t_i?=?1) or non-ascending (if?t_i?=?2) order.

Output

Print?n?integers?— the final report, which will be passed to Blake by manager number?m.

Examples

Input 3 1
1 2 3
2 2 Output 2 1 3 Input 4 2
1 2 4 3
2 3
1 2 Output 2 4 1 3

Note

In the first sample, the initial report looked like:?1 2 3. After the first manager the first two numbers were transposed:?2 1?3. The report got to Blake in this form.

In the second sample the original report was like this:?1 2 4 3. After the first manager the report changed to:?4 2 1?3. After the second manager the report changed to:?2 4?1 3. This report was handed over to Blake.

歷史總是驚人的相似，我們就是喜歡讀錯題。

1和2對應的是兩種操作，把前b個換為不增或不降，直接寫當然是不行的啊，但是每次都是前b個啊，所以你有些操作就變得無效了

我最后會確定它在哪個位置的，所以就是用單調棧去壓縮一下

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N],t[N],r[N],st[N]; int main() {int n,m,s=0;cin>>n>>m;for(int i=0; i<n; i++)cin>>a[i];for(int i=0,a,b; i<m; i++){cin>>a>>b;while(s>0&&b>r[s-1])s--;t[s]=a,r[s]=b,s++;}r[s]=0,s++;for(int i=0; i<r[0]; i++)st[i]=a[i];sort(st,st+r[0]);int tl=0,tr=r[0]-1;for(int i=1; i<s; ++i)for(int j=r[i-1]; j>r[i]; --j)a[j-1]=(t[i-1]==1)?st[tr--]:st[tl++];for(int i=0; i<n; i++)cout<<a[i]<<" ";return 0; }

?

F - Winnie-the-Pooh and honey

?CodeForces - 120C?

As we all know, Winnie-the-Pooh just adores honey. Ones he and the Piglet found out that the Rabbit has recently gotten hold of an impressive amount of this sweet and healthy snack. As you may guess, Winnie and the Piglet asked to come at the Rabbit's place. Thus, there are?n?jars of honey lined up in front of Winnie-the-Pooh, jar number?i?contains?a_i?kilos of honey. Winnie-the-Pooh eats the honey like that: each time he chooses a jar containing most honey. If the jar has less that?k?kilos of honey or if Winnie-the-Pooh has already eaten from it three times, he gives the jar to Piglet. Otherwise he eats exactly?k?kilos of honey from the jar and puts it back. Winnie does so until he gives all jars to the Piglet. Count how much honey Piglet will overall get after Winnie satisfies his hunger.

Input

The first line contains two integers?n?and?k?(1?≤?n?≤?100,?1?≤?k?≤?100). The second line contains?n?integers?a₁,?a₂, ...,?a_n, separated by spaces (1?≤?a_i?≤?100).

Output

Print a single number — how many kilos of honey gets Piglet.

Examples

Input 3 3
15 8 10 Output 9

---

這個題我們理解錯了啊，three times是三倍，不是三次，但是湊出來了答案 所以就是看它一倍兩倍三倍，減一下就好了 #include<bits/stdc++.h> using namespace std; int main() {freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);int n,k,x,a[105];cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++){if(a[i]>=3*k)a[i]-=3*k;else if(a[i]>=2*k)a[i]-=2*k;else if(a[i]>=k)a[i]-=k;}int maxx=0;for(int i=0;i<n;i++)maxx+=a[i];cout<<maxx;return 0; }

G - Alarm Clock

?CodeForces - 898D?

Every evening Vitalya sets?n?alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer?a_i?— number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute.

Vitalya will definitely wake up if during some?m?consecutive minutes at least?kalarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time.

Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on.

Input

First line contains three integers?n,?m?and?k?(1?≤?k?≤?n?≤?2·10⁵,?1?≤?m?≤?10⁶)?— number of alarm clocks, and conditions of Vitalya's waking up.

Second line contains sequence of?distinct?integers?a₁,?a₂,?...,?a_n?(1?≤?a_i?≤?10⁶) in which?a_i?equals minute on which?i-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for?10⁶?minutes.

Output

Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.

Examples

Input 3 3 2
3 5 1 Output 1 Input 5 10 3
12 8 18 25 1 Output 0 Input 7 7 2
7 3 4 1 6 5 2 Output 6 Input 2 2 2
1 3 Output 0

Note

In first example Vitalya should turn off first alarm clock which rings at minute?3.

In second example Vitalya shouldn't turn off any alarm clock because there are no interval of?10?consequence minutes in which?3?alarm clocks will ring.

In third example Vitalya should turn off any?6?alarm clocks.

這個題目是貪心，主要是知道題目意思，m個鬧鐘會在他的時間點ai響1min

你要讓連續的m分鐘鬧鐘個數小于k個，那就是查m個區段的鬧鐘數量，還有取消這個鬧鐘的情況

#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N]; int main() {int n,m,k;cin>>n>>m>>k;for(int i=0,x;i<n;i++)cin>>x,a[x]=1;int ans=0,cnt=0;for(int i=1;i<N;i++){if(a[i])cnt++;if(i-m>0&&a[i-m])cnt--;//cout<<cnt;if(cnt>=k){ans++;cnt--;a[i]=0;}}cout<<ans;return 0; }

?

H - Indian Summer

?CodeForces - 44A?

Indian summer is such a beautiful time of the year! A girl named Alyona is walking in the forest and picking a bouquet from fallen leaves. Alyona is very choosy — she doesn't take a leaf if it matches the color and the species of the tree of one of the leaves she already has. Find out how many leaves Alyona has picked.

Input

The first line contains an integer?n?(1?≤?n?≤?100) — the number of leaves Alyona has found. The next?n?lines contain the leaves' descriptions. Each leaf is characterized by the species of the tree it has fallen from and by the color. The species of the trees and colors are given in names, consisting of no more than?10lowercase Latin letters. A name can not be an empty string. The species of a tree and the color are given in each line separated by a space.

Output

Output the single number — the number of Alyona's leaves.

Examples

Input 5
birch yellow
maple red
birch yellow
maple yellow
maple green Output 4 Input 3
oak yellow
oak yellow
oak yellow Output 1

---

就是看下這個集合的元素個數

#include<bits/stdc++.h> using namespace std;int main() {int n;string s;map<string,int> ma;cin>>n;cin.get();for(int i=0;i<n;i++){getline(cin,s);ma[s]=1;}cout<<ma.size()<<endl;return 0; }

I - Terse princess

?CodeForces - 148C?

?Next please?, — the princess called and cast an estimating glance at the next groom.

The princess intends to choose the most worthy groom, this is, the richest one. Whenever she sees a groom who is more rich than each of the previous ones, she says a measured ?Oh...?. Whenever the groom is richer than all previous ones added together, she exclaims ?Wow!? (no ?Oh...? in this case). At the sight of the first groom the princess stays calm and says nothing.

The fortune of each groom is described with an integer between 1 and 50000. You know that during the day the princess saw?n?grooms, said ?Oh...? exactly?a?times and exclaimed ?Wow!? exactly?b?times. Your task is to output a sequence of?n?integers?t₁,?t₂,?...,?t_n, where?t_i?describes the fortune of?i-th groom. If several sequences are possible, output any of them. If no sequence exists that would satisfy all the requirements, output a single number?-1.

Input

The only line of input data contains three integer numbers?n,?a?and?b?(1?≤?n?≤?100,?0?≤?a,?b?≤?15,?n?>?a?+?b), separated with single spaces.

Output

Output any sequence of integers?t₁,?t₂,?...,?t_n, where?t_i?(1?≤?t_i?≤?50000) is the fortune of?i-th groom, that satisfies the given constraints. If no sequence exists that would satisfy all the requirements, output a single number?-1.

Examples

Input 10 2 3 Output 5 1 3 6 16 35 46 4 200 99 Input 5 0 0 Output 10 10 6 6 5

Note

Let's have a closer look at the answer for the first sample test.

• The princess said ?Oh...? (highlighted in bold): 5 1 3?6?16 35?46?4 200 99.
• The princess exclaimed ?Wow!? (highlighted in bold): 5 1 3 6?16?35?46 4?200?99.

這個題目就是典型的構造題目

如果你是當前最大的就是Oh，如果你不僅最大了而且比前面總和還大就是Wow

有a次Oh，b次Wow

所以我就想分開構造，但是這個Wow很快就超了，所以現在先構造Wow，這個大佬想到了等比數列，1<<31-1是32967，所以還是夠用的

所以主要是怎么判斷-1，不可能Oh n-1次的，因為這是Wow（但是有0）

#include<bits/stdc++.h> using namespace std; int main() {int n,a,b,sum=1;scanf("%d%d%d",&n,&a,&b);if(a==n-1&&n!=1){cout<<"-1";return 0;}cout<<"1";for(int i=0;i<b;i++)cout<<" "<<sum*2,sum=sum*2;for(int i=0;i<n-a-b-1;i++)cout<<" 1";for(int i=0;i<a;i++)cout<<" "<<sum+1,sum++;return 0; }

J - Strip

?CodeForces - 487B?

?

Alexandra has a paper strip with?n?numbers on it. Let's call them?a_i?from left to right.

Now Alexandra wants to split it into some pieces (possibly?1). For each piece of strip, it must satisfy:

• Each piece should contain at least?l?numbers.
• The difference between the maximal and the minimal number on the piece should be at most?s.

Please help Alexandra to find the minimal number of pieces meeting the condition above.

Input

The first line contains three space-separated integers?n,?s,?l?(1?≤?n?≤?10⁵,?0?≤?s?≤?10⁹,?1?≤?l?≤?10⁵).

The second line contains?n?integers?a_i?separated by spaces (?-?10⁹?≤?a_i?≤?10⁹).

Output

Output the minimal number of strip pieces.

If there are no ways to split the strip, output -1.

Examples

Input 7 2 2
1 3 1 2 4 1 2 Output 3 Input 7 2 2
1 100 1 100 1 100 1 Output -1

Note

For the first sample, we can split the strip into?3?pieces:?[1,?3,?1],?[2,?4],?[1,?2].

For the second sample, we can't let?1?and?100?be on the same piece, so no solution exists.

什么區間最大最小都是可以解決的，但是永遠解決不掉的就是你要確定這個區間的端點，即使我知道這個區間要有的最大值和最小值了，但是我是無法得知現在在前一個區間，還是下一個區間

網上看到了別人的貪心代碼，騷啊

就是你可以去決定這個能不能放進前一個區間的問題啊，太厲害了，不過這樣的話我數組要開兩倍了

被這個數據卡RE

忽悠你們學一波RMQ算法

#include<bits/stdc++.h> using namespace std; const int N=2e5+5,INF=0x3f3f3f3f; int dmi[N][22],dma[N][22],f[N],dp[N]; int n,s,l; void RMQ_init() {for(int j=1; (1<<j)<=n; j++)for(int i=1; i+j-1<=n; i++)dmi[i][j]=min(dmi[i][j-1],dmi[i+(1<<(j-1))][j-1]),dma[i][j]=max(dma[i][j-1],dma[i+(1<<(j-1))][j-1]); } int RMQ(int l,int r) {int k=f[r-l+1];return max(dma[l][k],dma[r-(1<<k)+1][k])-min(dmi[l][k],dmi[r-(1<<k)+1][k]); } int main() {f[0]=-1;scanf("%d%d%d",&n,&s,&l);for(int i=1,x; i<=n; i++)scanf("%d",&x),dmi[i][0]=dma[i][0]=x,f[i]=((i&(i-1))==0)?f[i-1]+1:f[i-1];RMQ_init();fill(dp+1,dp+n+1,INF);int pre=0;for(int i=1; i<=n; i++){while(i-pre>=l&&RMQ(pre+1,i)>s||dp[pre]==INF)pre++;if(i-pre>=l)dp[i]=min(dp[pre]+1,dp[i]);}cout<<(dp[n]==INF?-1:dp[n]);return 0; }

K - Basketball Team

?CodeForces - 107B?

As a German University in Cairo (GUC) student and a basketball player, Herr Wafa was delighted once he heard the news. GUC is finally participating in the Annual Basketball Competition (ABC).

A team is to be formed of?n?players, all of which are GUC students. However, the team might have players belonging to different departments. There are?m?departments in GUC, numbered from?1?to?m. Herr Wafa's department has number?h. For each department?i, Herr Wafa knows number?s_i?— how many students who play basketball belong to this department.

Herr Wafa was also able to guarantee a spot on the team, using his special powers. But since he hates floating-point numbers, he needs your help at finding the probability that he will have at least one teammate belonging to his department.

Note that every possible team containing Herr Wafa is equally probable. Consider all the students different from each other.

Input

The first line contains three integers?n,?m?and?h?(1?≤?n?≤?100,?1?≤?m?≤?1000,?1?≤?h?≤?m) — the number of players on the team, the number of departments in GUC and Herr Wafa's department, correspondingly.

The second line contains a single-space-separated list of?m?integers?s_i?(1?≤?s_i?≤?100), denoting the number of students in the?i-th department. Note that?s_h?includes Herr Wafa.

Output

Print the probability that Herr Wafa will have at least one teammate from his department. If there is not enough basketball players in GUC to participate in ABC, print -1. The answer will be accepted if it has absolute or relative error not exceeding?10^?-?6.

Examples

Input 3 2 1
2 1 Output 1 Input 3 2 1
1 1 Output -1 Input 3 2 1
2 2 Output 0.666667

Note

In the first example all 3 players (2 from department 1 and 1 from department 2) must be chosen for the team. Both players from Wafa's departments will be chosen, so he's guaranteed to have a teammate from his department.

In the second example, there are not enough players.

In the third example, there are three possibilities to compose the team containing Herr Wafa. In two of them the other player from Herr Wafa's department is part of the team.

這個其實就是個簡單的組合數，因為和其他集合沒有關系，你只用知道總數就好了

從不可能入手C(n-1, sum-1-a[h]) / C(n-1, sum-1)

#include<bits/stdc++.h> using namespace std; int a[1005]; int main() {int n,m,h,sum=0;cin>>n>>m>>h;for(int i=1;i<=m;i++)cin>>a[i],sum+=a[i];if(sum<n){cout<<"-1";}else{double ans=1;for(int i=1;i<=n-1;i++)ans*=(sum*1.0-a[h]-i+1)/(sum-i);printf("%.12f\n",1-ans);}return 0; }

L - Number of Parallelograms

?CodeForces - 660D

You are given?n?points on a plane. All the points are distinct and no three of them lie on the same line. Find the number of parallelograms with the vertices at the given points.

Input

The first line of the input contains integer?n?(1?≤?n?≤?2000) — the number of points.

Each of the next?n?lines contains two integers?(x_i,?y_i)?(0?≤?x_i,?y_i?≤?10⁹) — the coordinates of the?i-th point.

Output

Print the only integer?c?— the number of parallelograms with the vertices at the given points.

Example

Input 4
0 1
1 0
1 1
2 0 Output 1

---

給你ｎ個點，這些點任意三點不共線，也就是平行了，只要長度相等就行了

所以直接用中點這定理，兩條線段的中點一樣，就是一條直線

不知道怎么回事，沒用成ｐａｉｒ，直接ｈａｓｈ一下吧，反正數也不大

#include<bits/stdc++.h> using namespace std; #define pair<double,double> pdd const int N=2005,INF=0x3f3f3f3f; map<long long,int>M; struct p {int x,y; }d[N]; int main() {int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d%d",&d[i].x,&d[i].y);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)M[(d[i].x+d[j].x)*1LL*(2e9+5)+d[i].y+d[j].y]++;int ans=0;for(auto X:M){int x=X.second;ans+=x*(x-1)/2;}cout<<ans;return 0; }

卡時間的代碼

#include<bits/stdc++.h> using namespace std; #define pair<double,double> pdd const int N=2005,INF=0x3f3f3f3f; unordered_map<long long,int>M; struct p {int x,y; }d[N]; int main() {int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d%d",&d[i].x,&d[i].y);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)M[(d[i].x+d[j].x)*1LL*(2e9+5)+d[i].y+d[j].y]++;int ans=0;for(auto X:M){int x=X.second;ans+=x*(x-1)/2;}cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/BobHuang/p/8834664.html

總結

以上是生活随笔為你收集整理的浙南联合训练赛20180414的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。