- A - Splitting in Teams
- B - Radio Station
- C - Proper Nutrition
- D - Rumor
- E - K-Dominant Character
- F - Field of Wonders
A - Splitting in Teams
There were n groups of students which came to write a training contest. A group is either one person who can write the contest with anyone else, or two people who want to write the contest in the same team.
The coach decided to form teams of exactly three people for this training. Determine the maximum number of teams of three people he can form. It is possible that he can’t use all groups to form teams. For groups of two, either both students should write the contest, or both should not. If two students from a group of two will write the contest, they should be in the same team.
Input
The first line contains single integer n ( 2 ≤ n ≤ 2 ⋅ 1 0 5 ) n (2 ≤ n ≤ 2·10^5) n(2 ≤ n ≤ 2⋅105) — the number of groups.
The second line contains a sequence of integers a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ 2 ) a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2) a1, a2, ..., an(1 ≤ ai ≤ 2), where a i a_i ai is the number of people in group i i i.
Output
Print the maximum number of teams of three people the coach can form.
Input
4
1 1 2 1
Output
1
Input
2
2 2
Output
0
Input
7
2 2 2 1 1 1 1
Output
3
Input
3
1 1 1
Output
1
Note
In the first example the coach can form one team. For example, he can take students from the first, second and fourth groups.
In the second example he can’t make a single team.
In the third example the coach can form three teams. For example, he can do this in the following way:
- The first group (of two people) and the seventh group (of one person),
- The second group (of two people) and the sixth group (of one person),
- The third group (of two people) and the fourth group (of one person).
思路
优先让 1 1 1与 2 2 2配对，再考虑让剩下的 1 1 1彼此之间配对。
#include<cstdio>
#include<algorithm>
using namespace std;
int a,b,ans,n,v;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&v);
if(v==1) b++;
else a++;
}
int mn=min(a,b);
ans+=mn; a-=mn,b-=mn;
ans+=b/3;
printf("%d\n",ans);
}
B - Radio Station
As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin’s task was to add comments to nginx configuration for school’s website. The school has n servers. Each server has a name and an ip (names aren’t necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we’ll assume that an nginx command is of form “command ip;” where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.
Each ip is of form “a.b.c.d” where a, b, c and d are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has m commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is “command ip;” Dustin has to replace it with “command ip; #name” where name is the name of the server with ip equal to ip.
Dustin doesn’t know anything about nginx, so he panicked again and his friends asked you to do his task for him.
Input
The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000).
The next n lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1 ≤ |name| ≤ 10, name only consists of English lowercase letters). It is guaranteed that all ip are distinct.
The next m lines contain the commands in the configuration file. Each line is of form “command ip;” (1 ≤ |command| ≤ 10, command only consists of English lowercase letters). It is guaranteed that ip belongs to one of the n school servers.
Output
Print m lines, the commands in the configuration file after Dustin did his task.
Input
2 2
main 192.168.0.2
replica 192.168.0.1
block 192.168.0.1;
proxy 192.168.0.2;
Output
block 192.168.0.1; #replica
proxy 192.168.0.2; #main
Input
3 5
google 8.8.8.8
codeforces 212.193.33.27
server 138.197.64.57
redirect 138.197.64.57;
block 8.8.8.8;
cf 212.193.33.27;
unblock 8.8.8.8;
check 138.197.64.57;
Output
redirect 138.197.64.57; #server
block 8.8.8.8; #google
cf 212.193.33.27; #codeforces
unblock 8.8.8.8; #google
check 138.197.64.57; #server
思路
用map映射就可以了。
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n,m;
string a,b;
map<string,string> mp;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
cin>>a>>b;
mp[b]=a;
}
for(int i=0;i<m;i++){
cin>>a>>b;
int s=b.size();
b.erase(s-1,1);
cout<<a<<" "<<b<<"; #"<<mp[b]<<"\n";
}
}
C - Proper Nutrition
Vasya has n burles. One bottle of Ber-Cola costs a burles and one Bars bar costs b burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number of Bars bars.
Find out if it’s possible to buy some amount of bottles of Ber-Cola and Bars bars and spend exactly n burles.
In other words, you should find two non-negative integers x and y such that Vasya can buy x bottles of Ber-Cola and y Bars bars and x·a + y·b = n or tell that it’s impossible.
Input
First line contains single integer n (1 ≤ n ≤ 10 000 000) — amount of money, that Vasya has.
Second line contains single integer a (1 ≤ a ≤ 10 000 000) — cost of one bottle of Ber-Cola.
Third line contains single integer b (1 ≤ b ≤ 10 000 000) — cost of one Bars bar.
Output
If Vasya can’t buy Bars and Ber-Cola in such a way to spend exactly n burles print «NO» (without quotes).
Otherwise in first line print «YES» (without quotes). In second line print two non-negative integers x and y — number of bottles of Ber-Cola and number of Bars bars Vasya should buy in order to spend exactly n burles, i.e. x·a + y·b = n. If there are multiple answers print any of them.
Any of numbers x and y can be equal 0.
Input
7
2
3
Output
YES
2 1
Input
100
25
10
Output
YES
0 10
Input
15
4
8
Output
NO
Input
9960594
2551
2557
Output
YES
1951 1949
Note
In first example Vasya can buy two bottles of Ber-Cola and one Bars bar. He will spend exactly 2·2 + 1·3 = 7 burles.
In second example Vasya can spend exactly n burles multiple ways:
buy two bottles of Ber-Cola and five Bars bars;
buy four bottles of Ber-Cola and don’t buy Bars bars;
don’t buy Ber-Cola and buy 10 Bars bars.
In third example it’s impossible to but Ber-Cola and Bars bars in order to spend exactly n burles.
思路
拓展欧几里得。如果
g
c
d
（
a
,
b
）
gcd（a,b）
gcd（a,b）不能整除
n
n
n，直接得出结论，答案不存在。否则，用拓展欧几里得求出一对特解
x
0
，
y
0
x_0，y_0
x0，y0，使得
x
0
a
+
y
0
b
=
g
c
d
(
a
,
b
)
x_0a+y_0b=gcd(a,b)
x0a+y0b=gcd(a,b)，将
x
0
，
y
0
x0，y0
x0，y0同乘
n
g
c
d
\frac{n}{gcd}
gcdn，得到
x
0
a
+
y
0
b
=
n
x_0a+y_0b=n
x0a+y0b=n的一组特解。
x与y的通解为
x
=
n
g
c
d
x
0
+
k
b
g
c
d
x=\frac{n}{gcd}x_0+k\frac{b}{gcd}
x=gcdnx0+kgcdb，
y
=
n
g
c
d
y
0
+
k
a
g
c
d
y=\frac{n}{gcd}y_0+k\frac{a}{gcd}
y=gcdny0+kgcda。若存在一组解使得x与y均非负，则这组解就是答案之一；若不存在x与y均非负的情况，则无解。
#include<cstdio>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int n,a,b,x,y,gcd;
int exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return a;}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
signed main(){
scanf("%lld%lld%lld",&n,&a,&b);
gcd=exgcd(a,b,x,y);
if(n%gcd!=0){ puts("NO");return 0;}
x=x*n/gcd; y=y*n/gcd;
while(x<0&&y>0) x+=b/gcd,y-=a/gcd;
while(x>0&&y<0) x-=b/gcd,y+=a/gcd;
if(x<0||y<0){ puts("NO");return 0;}
printf("YES\n%lld %lld\n",x,y);
}
D - Rumor
Vova promised himself that he would never play computer games… But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.
Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.
Vova knows that there are n characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; i-th character wants ci gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.
The quest is finished when all n characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?
Take a look at the notes if you think you haven’t understood the problem completely.
Input
The first line contains two integer numbers n n n and m ( 1 ≤ n ≤ 1 0 5 , 0 ≤ m ≤ 1 0 5 ) m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5) m(1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of characters in Overcity and the number of pairs of friends.
The second line contains n n n integer numbers c i ( 0 ≤ c i ≤ 1 0 9 ) ci (0 ≤ c_i ≤ 10^9) ci(0 ≤ ci ≤ 109) — the amount of gold i-th character asks to start spreading the rumor.
Then m lines follow, each containing a pair of numbers ( x i , y i ) (x_i, y_i) (xi, yi) which represent that characters xi and yi are friends ( 1 ≤ x i , y i ≤ n , x i ≠ y i ) . (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i). (1 ≤ xi, yi ≤ n,xi = yi). It is guaranteed that each pair is listed at most once.
Output
Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.
Input
5 2
2 5 3 4 8
1 4
4 5
Output
10
Input
10 0
1 2 3 4 5 6 7 8 9 10
Output
55
Input
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
Output
15
Note
In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.
In the second example Vova has to bribe everyone.
In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.
思路
用并查集维护每个集合的最小值。
#include<cstdio>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],fa[maxn],vis[maxn];
int n,m,u,v,ans;
int get(int x){
if(fa[x]==0) return x;
return fa[x]=get(fa[x]);
}
void add(int u,int v){
int x=get(u),y=get(v);
if(x==y) return ;
a[x]=min(a[x],a[y]);
fa[y]=x;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
while(m--){
scanf("%lld%lld",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
int root=get(i);
if(vis[root]){ continue;}
ans+=a[root];
vis[root]=1;
}
printf("%lld\n",ans);
}
E - K-Dominant Character
You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.
You have to find minimum k such that there exists at least one k-dominant character.
Input
The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).
Output
Print one number — the minimum value of k such that there exists at least one k-dominant character.
Input
abacaba
Output
2
Input
zzzzz
Output
1
Input
abcde
Output
3
思路
二分答案转换为判定。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
int len,l,r,mid,mp[26],tmp[26];
char s[maxn];
bool judge(){
memset(mp,0,sizeof(mp));
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=mid;i++){
tmp[s[i]-'a']++; mp[s[i]-'a']=1;
}
for(int i=2;i+mid-1<=len;i++){
tmp[s[i+mid-1]-'a']++;
tmp[s[i-1]-'a']--;
if(tmp[s[i-1]-'a']==0){
mp[s[i-1]-'a']=0;
}
}
for(int i=0;i<26;i++)
if(mp[i]==1) return true;
return false;
}
signed main(){
scanf("%s",s+1);
len=strlen(s+1);
l=1,r=len;
while(l<r){
mid=(l+r)/2;
if(judge()) r=mid;
else l=mid+1;
}
printf("%d",l);
}
F - Field of Wonders
Polycarpus takes part in the “Field of Wonders” TV show. The participants of the show have to guess a hidden word as fast as possible. Initially all the letters of the word are hidden.
The game consists of several turns. At each turn the participant tells a letter and the TV show host responds if there is such letter in the word or not. If there is such letter then the host reveals all such letters. For example, if the hidden word is “abacaba” and the player tells the letter “a”, the host will reveal letters at all positions, occupied by “a”: 1, 3, 5 and 7 (positions are numbered from left to right starting from 1).
Polycarpus knows m words of exactly the same length as the hidden word. The hidden word is also known to him and appears as one of these m words.
At current moment a number of turns have already been made and some letters (possibly zero) of the hidden word are already revealed. Previously Polycarp has told exactly the letters which are currently revealed.
It is Polycarpus’ turn. He wants to tell a letter in such a way, that the TV show host will assuredly reveal at least one more letter. Polycarpus cannot tell the letters, which are already revealed.
Your task is to help Polycarpus and find out the number of letters he can tell so that the show host will assuredly reveal at least one of the remaining letters.
Input
The first line contains one integer n (1 ≤ n ≤ 50) — the length of the hidden word.
The following line describes already revealed letters. It contains the string of length n, which consists of lowercase Latin letters and symbols “". If there is a letter at some position, then this letter was already revealed. If the position contains symbol "”, then the letter at this position has not been revealed yet. It is guaranteed, that at least one letter is still closed.
The third line contains an integer m (1 ≤ m ≤ 1000) — the number of words of length n, which Polycarpus knows. The following m lines contain the words themselves — n-letter strings of lowercase Latin letters. All words are distinct.
It is guaranteed that the hidden word appears as one of the given m words. Before the current move Polycarp has told exactly the letters which are currently revealed.
Output
Output the single integer — the number of letters Polycarpus can tell so that the TV show host definitely reveals at least one more letter. It is possible that this number is zero.
Input
4
a**d
2
abcd
acbd
Output
2
Input
5
lo*er
2
lover
loser
Output
0
Input
3
a*a
2
aaa
aba
Output
1
Note
In the first example Polycarpus can tell letters “b” and “c”, which assuredly will be revealed.
The second example contains no letters which can be told as it is not clear, which of the letters “v” or “s” is located at the third position of the hidden word.
In the third example Polycarpus exactly knows that the hidden word is “aba”, because in case it was “aaa”, then the second letter “a” would have already been revealed in one of previous turns.
思路
将第一行字符串(记为a)的小写字母标记到int amp[26]中。对于之后的m条字符串(记这些字符串为b)，若b与a的非’*'部分不相同，直接跳过；在b对应a的“*”部分的字符，若在amp中出现过，也跳过，判断下一条字符串。
对于所有合法的字符串b，将它们的字母出现情况记录在bmp[26]中，若出现，则记为1，否则为0。将bmp[26]与ansmp[26]相与（ansmp初始全为1），判断完所有字符串b后，ansmp[26]中1的数量就是答案。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,amp[26],bmp[26],ansmp[26],cnt;
string a,b;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i=0;i<26;i++) ansmp[i]=1;
cin>>n>>a>>m;
for(int i=0;i<n;i++){
if(a[i]=='*') continue;
amp[a[i]-'a']=1;
}
bool flag=0;
while(m--){
cin>>b;
bool Next=0;
memset(bmp,0,sizeof(bmp)); cnt=0;
for(int i=0;i<n;i++){
if(a[i]!='*'&&b[i]!=a[i]){
Next=true;
break;
}
if(a[i]=='*'&&[b[i]-'a']){
Next=true;
break;
}
if(amp[b[i]-'a']) continue;
bmp[b[i]-'a']=1;
}
if(Next==1) continue;
flag=1;
for(int i=0;i<26;i++) ansmp[i]&=bmp[i];
}
if(flag==0){ printf("0\n");return 0;}
int ans=0;
for(int i=0;i<26;i++) if(ansmp[i]) ans++;
printf("%d\n",ans);
}