Desktop(模拟)2016-2017 ACM Central Region of Russia Quarterfinal Programming Contest

`-` 2019-08-12 18:30:00

Vasily is a college student who likes to keep everything in order. One of his hobbies is software. Yesterday he installed a new operating system Windows 999999. The key difference between the new system and Windows XP is that Windows 999999 has 999,999 pre-installed utilities and after the installation of the system, the desktop is absolutely empty. Vasily wants to place the maximum number of shortcuts to the utilities on his desktop. His computer screen is a grid sized h × w and the icons are squares sized 2 × 2. Icons must be positioned so that their corners match the borders of grid cells. They can also overlap each other, so the bottom icon will be partly covered by the top one. For comfort, Vasily decided that at least half of an icon (2 cells) must be visible; otherwise it would be hard to click on it. Now Vasily wants to know the maximum number of icons that can be placed on his desktop and the appropriate positioning pattern.


1 ≤ h, w ≤ 500


The first line in the input file contains two integer numbers h and w , representing the height and the width of Vasily’s computer screen.


The first line in the output file must contain the number N – the maximum number of icons that can be fitted on Vasily’s desktop considering the conditions listed above. If N>0, the next N lines must contain pairs of numbers representing the coordinates of the upper right corners of the icons (line number and column number). The icons will be placed in the same order as they are listed, so each subsequent icon might lap over some of the previously listed icons.



2 4



1 1

1 2

1 3


 1 #include <stdio.h>
 3 int main()
 4 {
 5     freopen("input.txt", "r", stdin);
 6     freopen("output.txt", "w", stdout);
 7     int n, m, i, j;
 8     scanf("%d %d", &n, &m);
 9     if(n<2||m<2)
10     {
11         printf("0\n");
12     }
13     else
14     {
15         printf("%d\n", n*m/2-1);
16         if(n%2==1)
17         {
18             for(i=m-1; i-1>=0; i-=2)
19             {
20                 printf("%d %d\n", 1, i);
21             }
22         }
23         for(i=n-1; i-1>=0; i-=2)
24         {
25             for(j=m-1; j-2>=0; j--)
26             {
27                 printf("%d %d\n", i, j);
28             }
29         }
31         for(i=n-1; i-1>=0; i--)
32         {
33             if(i-2<0&&n%2==1) break;
34             printf("%d %d\n", i, 1);
35         }
37     }
38     return 0;
39 }


本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。