三个题，各位大佬别喷我，我很菜
A Silent Classroom
There are n students in the first grade of Nlogonia high school. The principal wishes to split the students into two classrooms (each student must be in exactly one of the classrooms). Two distinct students whose name starts with the same letter will be chatty if they are put in the same classroom (because they must have a lot in common). Let x be the number of such pairs of students in a split. Pairs (a,b) and (b,a) are the same and counted only once.
For example, if there are 6 students: “olivia”, “jacob”, “tanya”, “jack”, “oliver” and “jessica”, then:
splitting into two classrooms (“jack”, “jacob”, “jessica”, “tanya”) and (“olivia”, “oliver”) will give x=4 (3 chatting pairs in the first classroom, 1 chatting pair in the second classroom),
splitting into two classrooms (“jack”, “tanya”, “olivia”) and (“jessica”, “oliver”, “jacob”) will give x=1 (0 chatting pairs in the first classroom, 1 chatting pair in the second classroom).
You are given the list of the n names. What is the minimum x we can obtain by splitting the students into classrooms?
Note that it is valid to place all of the students in one of the classrooms, leaving the other one empty.
Input
The first line contains a single integer n (1≤n≤100) — the number of students.
After this n lines follow.
The i-th line contains the name of the i-th student.
It is guaranteed each name is a string of lowercase English letters of length at most 20. Note that multiple students may share the same name.
Output
The output must consist of a single integer x — the minimum possible number of chatty pairs.
Examples
Input
4
jorge
jose
oscar
jerry
Output
1
Input
7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo
Output
2
Input
5
mike
mike
mike
mike
mike
Output
4
Note
In the first sample the minimum number of pairs is 1. This can be achieved, for example, by putting everyone except jose in one classroom, and jose in the other, so jorge and jerry form the only chatty pair.
In the second sample the minimum number of pairs is 2. This can be achieved, for example, by putting kambei, gorobei, shichiroji and kyuzo in one room and putting heihachi, katsushiro and kikuchiyo in the other room. In this case the two pairs are kambei and kyuzo, and katsushiro and kikuchiyo.
In the third sample the minimum number of pairs is 4. This can be achieved by placing three of the students named mike in one classroom and the other two students in another classroom. Thus there will be three chatty pairs in one classroom and one chatty pair in the other classroom.
只有首字母相同的才会说话，问最小有多少个人能互相说话。
最小的时候就是一个房间里有一半人。。。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
map<char,int>mp;
string s;
int main()
{
while(scanf("%d",&n)!=EOF)
{
int cnt=1;
mp.clear();
for(int i=0;i<n;i++)
{
cin>>s;
mp[s[0]]++;
}
int sum=0;
for(map<char,int> ::iterator it=mp.begin();it!=mp.end();it++)
{
ll x=it->second/2;
ll y;
if(x*2!=it->second) y=x+1;
else y=x;
sum+=(x)*(x-1)/2+y*(y-1)/2;
}
cout<<sum<<endl;
}
}
B All the Vowels Please
Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length k is vowelly if there are positive integers n and m such that n⋅m=k and when the word is written by using n rows and m columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.
You are given an integer k and you must either print a vowelly word of length k or print −1 if no such word exists.
In this problem the vowels of the English alphabet are ‘a’, ‘e’, ‘i’, ‘o’ ,‘u’.
Input
Input consists of a single line containing the integer k (1≤k≤104) — the required length.
Output
The output must consist of a single line, consisting of a vowelly word of length k consisting of lowercase English letters if it exists or −1 if it does not.
If there are multiple possible words, you may output any of them.
Examples
Input
7
Output
-1
Input
36
Output
agoeuioaeiruuimaeoieauoweouoiaouimae
Note
In the second example, the word “agoeuioaeiruuimaeoieauoweouoiaouimae” can be arranged into the following 6×6 grid:
It is easy to verify that every row and every column contain all the vowels.
构造，每一行每一列都要有5个元音字母，嘤嘤嘤，一开始理解错了wa了几发
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
using namespace std;
int n;
int main()
{
while(~scanf("%d",&n))
{
int pos;
int flag=0;
for(int i=5;i<=sqrt(n);i++)
{
if(n%i==0)
{
if(i>=5&&n/i>=5)
{
flag=1;
pos=i;
break;
}
}
}
if(flag==0)
{
cout<<"-1"<<endl;
continue;
}
string s[6];
s[1]="aeiou";
s[2]="eaoui";
s[3]="iuaeo";
s[4]="oiuae";
s[5]="uoeia";
for(int i=1;i<=n/pos;i++)
{
cout<<s[(i%5)?i%5:5];
for(int j=0;j<pos-5;j++)
{
if(j==0) cout<<s[(i%5)?i%5:5][1];
else cout<<s[(i%5)?i%5:5][(j%4)+1];
}
//cout<<endl;
}
cout<<endl;
}
}
/*
aoeui
oaeiu
uiaeo
ieuoweouoiaouimae
*/
C A Tale of Two Lands
The legend of the foundation of Vectorland talks of two integers x and y. Centuries ago, the array king placed two markers at points |x| and |y| on the number line and conquered all the land in between (including the endpoints), which he declared to be Arrayland. Many years later, the vector king placed markers at points |x−y| and |x+y| and conquered all the land in between (including the endpoints), which he declared to be Vectorland. He did so in such a way that the land of Arrayland was completely inside (including the endpoints) the land of Vectorland.
Here |z| denotes the absolute value of z.
Now, Jose is stuck on a question of his history exam: “What are the values of x and y?” Jose doesn’t know the answer, but he believes he has narrowed the possible answers down to n integers a1,a2,…,an. Now, he wants to know the number of unordered pairs formed by two different elements from these n integers such that the legend could be true if x and y were equal to these two values. Note that it is possible that Jose is wrong, and that no pairs could possibly make the legend true.
Input
The first line contains a single integer n (2≤n≤2⋅105) — the number of choices.
The second line contains n pairwise distinct integers a1,a2,…,an (−109≤ai≤109) — the choices Jose is considering.
Output
Print a single integer number — the number of unordered pairs {x,y} formed by different numbers from Jose’s choices that could make the legend true.
Examples
Input
3
2 5 -3
Output
2
Input
2
3 6
Output
1
Note
Consider the first sample. For the pair {2,5}, the situation looks as follows, with the Arrayland markers at |2|=2 and |5|=5, while the Vectorland markers are located at |2−5|=3 and |2+5|=7:
The legend is not true in this case, because the interval [2,3] is not conquered by Vectorland. For the pair {5,−3} the situation looks as follows, with Arrayland consisting of the interval [3,5] and Vectorland consisting of the interval [2,8]:
As Vectorland completely contains Arrayland, the legend is true. It can also be shown that the legend is true for the pair {2,−3}, for a total of two pairs.
In the second sample, the only pair is {3,6}, and the situation looks as follows:
Note that even though Arrayland and Vectorland share 3 as endpoint, we still consider Arrayland to be completely inside of Vectorland.
咋说嘞，因为最后都是绝对值，都是正数。如果x<y，那么最后的式子就可以化为y-x<x<y<y+x,只有y-x<x这个式子需要判定条件，就是y<2*x。这样的话，我们给数组排个序，二分去找y，最后把结果加起来就好了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#define ll long long
using namespace std;
const int maxx=2e5+100;
ll a[maxx];
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
a[i]=abs(a[i]);
//s.insert(abs(a[i]));
}
int cnt=0;
//for(set<int> ::iterator it=s.begin();it!=s.end();it++) a[cnt++]=*it;
sort(a,a+n);
ll sum=0;
for(int i=0;i<n;i++)
{
int pos=upper_bound(a,a+n,a[i]*2ll)-a;
sum+=pos-i-1;
}
cout<<sum<<endl;
}
}
努力加油a啊，(o)/~