Решение задачи Ранклист с Codeforces

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


Завершилось очередное соревнование по программированию. К Вам в руки попала таблица с финальными результатами этого соревнования. Для каждой команды в ней было указано количество задач, решенных данной командой, а также суммарное штрафное время данной команды по всем решенным ей задачам. Однако ни для одной команды в этой таблице не было указано ее финальное место.

Вам известны правила, по которым можно сравнить результаты двух заданных команд. Пусть команда a решила p a задач с суммарным штрафным временем t a, а команда b решила p b задач с суммарным штрафным временем t b. Тогда команда a займет более высокое итоговое место, чем команда b, если она решила больше задач на соревновании, либо она решила такое же количество задач, но с меньшим суммарным временем. Другими словами, команда a окажется выше команды b в финальной таблице результатов, если p a > p b, либо p a = p b и при этом t a < t b.

При этом считается, что команды, решившие одинаковое количество задач с одинаковым штрафным временем, делят между собой все соответствующие места. Более формально, пусть есть группа из x команд, которые решили одинаковое количество задач с одинаковым штрафным временем. Пусть также y команд выступили лучше команд из этой группы. Тогда все команды из группы разделят между собой y + 1, y + 2, ..., y + x места. Команды, результат которых хуже чем у команд из группы, получат свои места в итоговой таблице, начиная с y + x + 1 места.

Вашей задачей будет посчитать, какое количество команд из заданного списка разделило между собой k-ое место.

Код

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;cin>>n>>k;
	vector<pair<int,int>>A(n+1);
	for(int i=1;i<=n;i++)
	{
		int x,t;cin>>x>>t;
		A[i].first=x;
		A[i].second=50-t;
	}
	sort(A.begin()+1,A.end());
	reverse(A.begin()+1,A.end());
	int ans=0;
	for(int i=1;i<=n;i++)
	if(A[i].first==A[k].first && A[i].second==A[k].second)
	ans++;
	cout<<ans;
	
}
		
		
			

	

         

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



Комментарии

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