Miscellany

#include <iostream>
#include <vector>

using namespace std;

struct Balle {
	int vitesse;
	int position;
	bool collided;
	
};

struct Scenario {
	std::vector<Balle> balles;
	
	int trackedBall_i;	
	int temps;	
};

struct Collision {
	Collision(int &a, int &b): b1(a), b2(b) {}

	int b1, b2;
};

int detectCollision(Balle b1, Balle b2)
{
	if(b1.vitesse == b2.vitesse)
		return -1;

	return (b2.position - b1.position) / (b1.vitesse - b2.vitesse);
}

void handleCollision(Collision c, int temps, Scenario& s)
{
	s.balles[c.b1].position += s.balles[c.b1].vitesse * temps;
	s.balles[c.b2].position += s.balles[c.b2].vitesse * temps;
	
	int tempVitesse = s.balles[c.b1].vitesse;
	s.balles[c.b1].vitesse = s.balles[c.b2].vitesse;
	s.balles[c.b2].vitesse = tempVitesse;

	if (s.balles[c.b1].position >= 100)
	{
		s.balles[c.b2].position = s.balles[c.b1].position = 100;
		s.balles[c.b2].vitesse = s.balles[c.b1].vitesse = 0;		
	}

	if (s.balles[c.b1].position <= 0)
	{
		s.balles[c.b2].position = s.balles[c.b1].position = 0;
		s.balles[c.b2].vitesse = s.balles[c.b1].vitesse = 0;		
	}

	s.balles[c.b2].collided = s.balles[c.b1].collided = true;		
}

void solve(Scenario& s) {

	while(s.temps > 0)
	{
		int shortestTimeToCollision = INT_MAX;
		vector<Collision> listUpdate;
	
		for(int i = 0; i < (int)s.balles.size(); ++i)
		{
			s.balles[i].collided = false;
		}
	
		for(int b1 = 0; b1 < (int)s.balles.size() - 1; ++b1)
		{
			for(int b2 = b1+1; b2 < (int)s.balles.size(); ++b2)
			{
				int tempTime = detectCollision(s.balles[b1], s.balles[b2]);
				if(tempTime > 0 && tempTime < shortestTimeToCollision)
				{
					shortestTimeToCollision = tempTime;
					listUpdate.clear();
				}
				if(tempTime == shortestTimeToCollision)
				{
					listUpdate.push_back(Collision(b1, b2));
				}
			}
		}

		if (shortestTimeToCollision > s.temps)
		{
			shortestTimeToCollision = s.temps;
			listUpdate.clear();
		}

		for(int i = 0; i < (int)listUpdate.size(); ++i)
		{
			handleCollision(listUpdate[i], shortestTimeToCollision, s);
		}

		if(listUpdate.size())
			shortestTimeToCollision++;

		for(int i = 0; i < (int)s.balles.size(); ++i)
		{
			if(!s.balles[i].collided)
			{
				s.balles[i].position += s.balles[i].vitesse * shortestTimeToCollision;
				if (s.balles[i].position >= 100)
				{
					s.balles[i].position = 100;
					s.balles[i].vitesse = 0;
				}

				if (s.balles[i].position <= 0)
				{
					s.balles[i].position = 100;
					s.balles[i].vitesse = 0;
				}
			}
		}

		s.temps -= shortestTimeToCollision;
	}

	cout << s.balles[s.trackedBall_i - 1].position;
}

int main() {
	int n;
	
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		Scenario scenario;
		int nbBalles;
		
		cin >> nbBalles;
		
		for (int j = 0; j < nbBalles; j++) {
			Balle balle;
			
			cin >> balle.position >> balle.vitesse;
			scenario.balles.push_back(balle);			
		}
		
		cin >> scenario.trackedBall_i >> scenario.temps;
		solve(scenario);
		if (i != (n-1)) cout << endl;
	}
	
	return 0;
}