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:
either the boy in the dancing pair must dance for the first time (so, he didn't dance with anyone before); or the girl in the dancing pair must dance for the first time. 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 #include #include #include #include #include #include #include #include #include #include #include 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