Ciel and Dancing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Fox Ciel and her friends are in a dancing room. There are n boys and m girls here, and they never danced before. There will be some songs, during each song, there must be exactly one boy and one girl are dancing. Besides, there is a special rule:
Help Fox Ciel to make a schedule that they can dance as many songs as possible.
Input
The first line contains two integers n and m (1?≤?n,?m?≤?100) ? the number of boys and girls in the dancing room.
Output
In the first line print k ? the number of songs during which they can dance. Then in the following k lines, print the indexes of boys and girls dancing during songs chronologically. You can assume that the boys are indexed from 1 to n, and the girls are indexed from 1 to m.
Sample test(s)
input
2 1
output
21 12 1
input
2 2
output
31 11 22 2
Note
In test case 1, there are 2 boys and 1 girl. We can have 2 dances: the 1st boy and 1st girl (during the first song), the 2nd boy and 1st girl (during the second song).
And in test case 2, we have 2 boys with 2 girls, the answer is 3.
解题思路:n个boy,m个girl,若每对舞伴中至少有一个之前一次也没都跳过,问能够组成多少对舞伴,并输出。
贪心,再加上点数学。稍微动点数学常识就可以得出,最多可以组成 n+m-1 对满足要求的舞伴,然后就是怎么构造这么多对舞伴了。可以这样想,我们先用1号boy跟所有的
girl配对,然后再用剩下的n-1个boy分别跟最后一个girl配对即可。
AC代码:
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;#define INF 0x7fffffffint main(){ #ifdef sxk freopen("in.txt","r",stdin); #endif int n,m; while(scanf("%d%d",&n, &m)!=EOF) { printf("%d\n", m + n - 1); for(int i=1; i <br> <br> <p></p> <p><br> </p> </time.h></stdlib.h></math.h></string></map></set></queue></vector></algorithm></iostream></string.h></stdio.h>