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<=m; i++) printf("%d %d\n", 1, i); for(int j=2; j<=n; j++) printf("%d %d\n", j, m); } return 0;}
