DMOPC '20 Contest 5 P2 - On The Clock

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
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


  • 0
    i_love_vanshita  commented on May 9, 2021, 8:18 a.m.

    why i am not able to see other coders code ?


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

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


  • 0
    Sharad  commented on April 27, 2021, 2: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.


    • 13
      kevinyang  commented on April 27, 2021, 12: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.


      • 15
        Averesoft  commented on April 27, 2021, 1: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.


      • -7
        Tony1234  commented on April 27, 2021, 12:55 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


  • -21
    suguruchhaya  commented on April 26, 2021, 4:58 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • -10
      vishnus  commented on April 26, 2021, 6:53 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


    • 25
      kevinyang  commented on April 26, 2021, 5:47 p.m. edited

      (A heads up for c++ users)

      I am a c++ user. I took an approach to https://dmoj.ca/problem/aplusb which was really similar to the editorial. However, a very small mistake of using the subtraction symbol instead of the addition symbol costed me to lose points. Correct: a+b. Wrong: a-b. Really ridiculous in my opinion but I guess it is a precision thing.

      Full correct submission: https://dmoj.ca/submission/3590927

      Full incorrect submission: https://dmoj.ca/submission/3590928


    • 12
      EpicChadGamer  commented on April 26, 2021, 5:27 p.m. edit 2

      get gud


    • 17
      verybadallen  commented on April 26, 2021, 5:19 p.m.

      Your code was wrong so you don't get AC. Please tell me what's ridiculous about it, should the judge just let anything get AC? If that you fancy that, please check out https://dmoj.ca/problem/acc6p9.