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個(gè)boy,m個(gè)girl,若每對(duì)舞伴中至少有一個(gè)之前一次也沒(méi)都跳過(guò),問(wèn)能夠組成多少對(duì)舞伴,并輸出。
貪心,再加上點(diǎn)數(shù)學(xué)。稍微動(dòng)點(diǎn)數(shù)學(xué)常識(shí)就可以得出,最多可以組成 n+m-1 對(duì)滿足要求的舞伴,然后就是怎么構(gòu)造這么多對(duì)舞伴了。可以這樣想,我們先用1號(hào)boy跟所有的
girl配對(duì),然后再用剩下的n-1個(gè)boy分別跟最后一個(gè)girl配對(duì)即可。
AC代碼:
#include#include #include #include #include #include #include #include
聲明:本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí),若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系,我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com