Решение задачи Тихий класс с Codeforces

Без пояснения   Просмотров: 32


В первый класс школы в Нлогонии набрали n учеников. Директор хочет разделить их в два класса, каждый ученик должен оказаться ровно в одном из этих классов. Если в один класс попадут два школьника, имена которых начинаются с одной и той же буквы, то они будут слишком много болтать друг с другом (ведь наверняка у них много общего). Обозначим за x количество таких пар учеников в некотором разбиении на два класса. Пары (a,b) и (b,a) считаются одинаковыми и учитываются один раз.

Например, если всего в классе 6 учеников — «olivia», «jacob», «tanya», «jack», «oliver» и «jessica», то:

разделение на два класса («jack», «jacob», «jessica», «tanya») и («olivia», «oliver») даст x=4 (3 пары будут болтать в первом классе, 1 пара будет болтать во втором классе),
разделение на два класса («jack», «tanya», «olivia») и («jessica», «oliver», «jacob») даст x=1 (0 пар будут болтать в первом классе, 1 пара будет болтать во втором классе).
Вам дан список из n имен. Какое минимальное значение x мы можем получить, распределив этих школьников на два класса?

Обратите внимание, не запрещается распределять всех учеников в один и тот же класс, оставив другой пустым.

Код

#include<bits/stdc++.h>
using namespace std;
int a[26]={0};
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		a[s[0]-'a']++;
	}
	int sum=0;
	for(int i=0;i<26;i++){
		int t1=a[i]/2;
		int t2=a[i]-t1;
		sum=sum+(t1-1)*t1/2+(t2-1)*t2/2;
	}
	cout<<sum<<endl;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться