U E D R , A S I H C RSS

3rdPCinCAUCSE/ProblemC

C ��� : 구�� ��기. ����������� : ball.c or ball.cpp

���� 같��나, 무게가 모두 다른 N개�� 구���� 다. N�� ����며, 구����는 ���가 1,2, .... N��로 붙��다. �� 구�� ����� 무게가 ���� ����� (무게 �로 (N+1)/2���) 구�� ��기 ���� 같�� �� ��려 ��다.
��리��게 ������ ���� ������다. �� ���� 구�� 골라���� ������ ������ ��나�� ��려 보면 ��느 ���� 무��� 가를 �� 다. ��렇게 M개�� �� 골라� 각각 ���� ������ ��려��느 것�� 무��� 가를 모두 ��다. �� 결과를 �������� 무게가 ����� 될 가능�� �� ��는 구��들�� 먼�� ������다.
를 들��, N=5 ��고, M=4 ���� 구���� 대����느 ���� 무���가를 ��낸 결과가 �� 다.

1. 구�� 2��� 구�� 1�보다 무겁다.
2. 구�� 4��� 구�� 3�보다 무겁다.
3. 구�� 5��� 구�� 1�보다 무겁다.
4. 구�� 4��� 구�� 2�보다 무겁다.

�� 같�� �� 개�� 결과만 ��고 ��면, 무게가 ����� 구�� ������게 �� �는 ����만, 1���과 4����� 무게가 ����� 구���� 대 될 ��다는 것�� ���� �� 다. 1���보다 무��� 것�� 2,4,5�����고, 4�보다 가벼�� 것�� 1,2,3���다. 따라� 답�� 2개��다.
M개�� ���� 대�� 결과를 보고 무게가 ����� 구���� 될 ��는 구���� 개�를 구��는 로그램 ��������.

��력

��력�� ���� ��력��다. ��력�� ���� ������ �������� 개�를 나��내는 ��� T(10 ����)가 ����다. 다�� � T개�� ������ ������가 ����다. 각 ������ �������� �� �� 구���� 개�를 나��내는 ��� N (1<=N<=99) 과 저울에 올려 본 쌍의 개수 M 이 주어진다. 그 다음 M개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

��력

��력�� ���� ��력��다. ��력�� T���다. 각 ������ �������� 대��� 무게가 ����� 대로 될 ��는 구���� �를 ��력��다. T개�� ������ ������를 모두 맞���� �� 문��를 맞�� 것��다.

��력��

~cpp 
2
5 4
2 1
4 3
5 1
4 2
3 1
1 2

��력�� �� 대�� ��력

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:17
Processing time 0.0120 sec