TSOC '15 Contest 1 #2 - Special Store

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Knowing the ingredients that go into making cheesecake, BMP and MSA decide to travel to the nearest store to obtain them. However, the store they want to go to is a very special store that sells premium brand items only.

Their goal is defined as the following. There is a rectangular map consisting of R rows and C buildings in each row. Initially, all of the buildings are invisible. In one move, BMP can pinpoint (make visible) any building. If BMP pinpoints a building that is already visible, it stays visible. BMP is able to find the special store when a W \times L rectangle of visible buildings is formed.

BMP has already thought of the coordinates of the buildings that he wants to pinpoint. He wants to pinpoint exactly N buildings, denoting the row X and the column Y of the building for each.

Input Specification

The first line of input will contain two space-separated integers R and C (10 \le R, C \le 1\,000). The next line of input will contain two space-separated integers W and L (1 \le W, L \le 5). The next line will contain the integer N (0 \le N \le 1\,000).

The next N lines contain BMP's moves in the order he makes them. Each line i will contain integers X_i and Y_i (1 \le X_i \le R, 1 \le Y_i \le C), representing the row number and column number of the building that was pinpointed during move i.

Output Specification

If BMP finds the special store, print Special store was found on: followed by the number of the move when the W \times L visible building was found. Otherwise, if the building was not found, print Special store was not located.

Sample Input

15 40
2 2
4
1 1
2 1
1 2
2 2

Sample Output

Special store was found on: 4

Comments


  • 3
    SourSpinach  commented on March 7, 2015, 9:26 p.m.

    W must be the width (range of x-coordinates), and L must be the height (range of y-coordinates), though this isn't stated anywhere.


    • 0
      bobhob314  commented on March 7, 2015, 9:45 p.m.

      BMP is able to find the special store when a W×L rectangle of visible buildings is formed.

      The convention for defining rectangles is typically widthxlength, and I assume BMP assumed that the readers would assume the convention.


      • 3
        snowblind  commented on March 7, 2015, 10:10 p.m.

        is that why you asked if W and L are lattice points on a hypothetical cartesian plane that lie on an edge of a rectangle?


        • -1
          bobhob314  commented on March 7, 2015, 10:43 p.m.

          RIP in peces hob


  • -1
    bobhob314  commented on Feb. 23, 2015, 10:17 p.m.

    Are W and L the number of lattice points on a hypothetical Cartesian plane that lie on an edge of a rectangle?

    Or are they the actual width and length of a rectangle?

    Because in the Sample Input, the specified four points create a square with side length 1.