DMOPC '20 Contest 5 P2 - On The Clock

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:
AvaLovelace
Problem types

Bob just got an internship writing a graphics driver for a computer screen! The screen can be represented as an N-pixel-high by M-pixel-wide grid of square pixels, all the same size. Pixel coordinates range from (1,1) in the bottom-left to (N, M) in the top-right.

Bob's first task is to display a diagonal line across the screen. More specifically, if you imagine a straight line going from the bottom-left to the top-right corner of the screen, Bob needs to light up all the pixels touching that line. The line must fully intersect a pixel for it to be lit up; pixels that only touch the line at a corner should not be lit.

For example, if N = 6 and M = 10, he should light up the pixels like this (yellow for lit, black for unlit):

Bob needs to know exactly which pixels should be lit. Please help him out so he doesn't get fired!

Constraints

Subtask 1 [20%]

1 \le N, M \le 1000

Subtask 2 [80%]

1 \le N, M \le 10^6

Input Specification

Two space-separated integers, N and M.

Output Specification

On the first line, print K, the total number of pixels that should be lit.
Then on the next K lines, print r_i and c_i, the coordinates (row and column) of the i^\text{th} lit pixel. Pixels with lower r_i should be printed first. If there is still a tie, print pixels with lower c_i first.

Sample Input

6 10

Sample Output

14
1 1
1 2
2 2
2 3
2 4
3 4
3 5
4 6
4 7
5 7
5 8
5 9
6 9
6 10

Comments


  • -2
    i_love_vanshita  commented on May 9, 2021, 12:18 p.m.

    why i am not able to see other coders code ?


    • 4
      Kirito  commented on May 9, 2021, 1:02 p.m.

      You need to solve the problem before you can see other's code.


  • -1
    Sharad  commented on April 27, 2021, 6:44 a.m.

    The only thing I can say, precision errors are the worst. I wrote dda based solution and didn't able to figure out what was wrong, but now after dozens of wrong submissions, it turns out that it was a precision error.


    • 14
      kevinyang  commented on April 27, 2021, 4:51 p.m. ← edited

      The only thing I can say, compiler errors are the worst. I wrote a c++ solution and wasn't able to figure out what as wrong, but after a dozen wrong submissions, it turns out it was a compiler error because I submitted in Java.


      • 22
        Averesoft  commented on April 27, 2021, 5:07 p.m. ← edit 2

        The only thing I can say, kevinyang is the worst. I wrote a comment to him on DMOJ and wasn't able to figure out what was wrong, but after a dozen of wrong comments, it turns out it was a kevinyang problem because I didn't post the comment.


      • -8
        dxke02  commented on April 27, 2021, 4:55 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


  • -27
    suguruchhaya  commented on April 26, 2021, 8:58 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.