[UVA][隨機] 10982 - Troublemakers
Troublemakers
Time Limit: 1 second
|
[after seeing that the room is on fire; Ted has a needle in his hand while holding the leg of a dead woman; Sara has a bottle of champagne in her hand, and Juancho is smoking] Man: Did they misbehave? |
Every school class has its troublemakers - those kids who can make the teacher's life miserable. On his own, a troublemaker is manageable, but when you put certain pairs of troublemakers together in the same room, teaching a class becomes very hard. There are n kids in Mrs. Shaida's math class, and there are m pairs of troublemakers among them. The situation has gotten so bad that Mrs. Shaida has decided to split the class into two classes. Help her do it in such a way that the number of troublemaker pairs is reduced by at least a half.
Input
The first line of input gives the number of cases, N.
N test cases follow. Each one starts with a line containing
n
Output
For each test case, output one line containing "Case #x:"
followed by L - the number of kids who will be moved to a
different class (in a different room). The next line should list
those kids. The total number of troublemaker pairs in the two rooms
must be at most
| Sample Input | Sample Output |
2 4 3 1 2 2 3 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 |
Case #1: 3 1 3 4 Case #2: 2 1 2 |
Problemsetter: Igor Naverniouk
題目描述：
搗蛋鬼的分班，搗蛋鬼兩兩存在會鬧事，分兩班使鬧事的情況減少一半。
題目解法：
目前是用隨機分班去做測試，不過這個做法不好，由於測資太弱了。可以說是假解吧
#include <stdio.h>
#include <stdlib.h>
int main() {
int testcase, cases = 0;
int u[5050], v[5050];
int n, m, i, j, k;
scanf("%d", &testcase);
srand(514);
while(testcase--) {
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++)
scanf("%d %d", &u[i], &v[i]);
int Aclass[105] = {}, ret = 0;
while(true) {
for(i = 1; i <= n; i++)
Aclass[i] = rand()%2;
int trouble = 0;
for(i = 0; i < m; i++) {
if(Aclass[u[i]] != Aclass[v[i]])
trouble++;
}
if(trouble >= (m+1)/2)
break;
}
for(i = 1; i <= n; i++)
ret += Aclass[i];
printf("Case #%d: %d\n", ++cases, ret);
int st = 0;
for(i = 1; i <= n; i++) {
if(Aclass[i] == 1) {
if(st) putchar(' ');
st = 1;
printf("%d", i);
}
}
puts("");
}
return 0;
}