Xếp chỗ ngồi

View as PDF

Submit solution

Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Viettel Programming Challenge 2023
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Kì thi Viettel Programming Challenge 2023 được tổ chức với địa điểm thi ngay tại hội trường trung tâm. Theo thể lệ, các đội tham dự cuộc thi đều phải có đúng ba thành viên. Ngoài các đội thi chính thức thì kì thi còn có sự góp mặt tham gia của một đội thi khách mời đặc biệt cũng gồm ba thành viên. Tuy nhiên, do sự cố tắc đường mà đội thi khách mời đã đến địa điểm thi muộn hơn so với các đội còn lại.

Hội trường được bố trí ~r \times c~ chiếc ghế được xếp ngay ngắn thành ~r~ hàng và ~c~ cột. Nhìn từ trên cao, các hàng ghế được đánh số từ ~1~ đến ~r~ từ trên xuống dưới, các chiếc ghế trong cùng hàng được đánh số từ ~1~ đến ~c~ theo thứ tự từ trái qua phải. Ta gọi ghế ngồi ở hàng ~i~ và cột ~j~ là ghế ~(i, j)~. Hội trường có một cửa ra vào nằm ở góc trên bên trái.

Hiện tại, các đội thi chính thức đều đã được bố trí chỗ ngồi trong hội trường, sao cho các bạn thuộc cùng một đội sẽ ngồi ở ba ghế liên tiếp nhau trong cùng một hàng. Ban tổ chức (BTC) cần bố trí chỗ ngồi cho đội khách mời bằng cách chọn ra một vị trí hàng ~p~ và cột ~q~ sao cho cả ba ghế ~(p, q)~, ~(p, q+1)~, ~(p, q+2)~ đều chưa có người ngồi. Đồng thời, để tiện cho việc di chuyển vào vị trí của đội khách mời, nếu có nhiều vị trí ngồi khả thi thì BTC sẽ ưu tiên lựa chọn vị trí ngồi có chỉ số hàng ~p~ thấp nhất, nếu vẫn có nhiều vị trí ngồi khả thi trong hàng đó thì BTC sẽ ưu tiên lựa chọn vị trí có chỉ số cột ~q~ nhỏ nhất.

Hãy tìm vị trí ngồi mà BTC đã sắp xếp cho đội khách mời. Dữ liệu vào đảm bảo rằng luôn có cách sắp xếp vị trí ngồi cho đội khách mời.

Input

Dòng đầu tiên gồm hai số nguyên ~r~, ~c~ (~1 \le r \le 100~, ~3 \le c \le 100~) — số hàng ghế và số ghế trong từng hàng.

~r~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~s_{i,1}, s_{i,2}, \ldots, s_{i,c}~, với ~s_{i,j} =~ 'x' nếu ghế ~(i, j)~ đã có người ngồi và ~s_{i,j} =~ '.' nếu ghế ~(i, j)~ còn trống.

Output

In ra hai số nguyên ~p~ và ~q~ cho biết chỉ số hàng và cột của vị trí ngồi mà BTC đã sắp xếp cho đội khách mời.

Sample Input 1

4 7
xxxxxx.
..xxx..
xxx....
...xxx.

Sample Output 1

3 4

Sample Input 2

3 4
....
....
....

Sample Output 2

1 1

Sample Input 3

3 6
xxxxxx
xxx...
xxxxxx

Sample Output 3

2 4

Sample Input 4

5 4
xxx.
.xxx
xxx.
.xxx
....

Sample Output 4

5 1

Notes

Ở ví dụ thứ nhất, có ba vị trí khả thi cho đội khách mời:

  • Dòng ~3~, cột ~4~: các bạn sẽ ngồi vào các ghế ~(3, 4)~, ~(3, 5)~, ~(3, 6)~

  • Dòng ~3~, cột ~5~: các bạn sẽ ngồi vào các ghế ~(3, 5)~, ~(3, 6)~, ~(3, 7)~

  • Dòng ~4~, cột ~1~: các bạn sẽ ngồi vào các ghế ~(4, 1)~, ~(4, 2)~, ~(4, 3)~

Trong số các vị trí có chỉ số dòng nhỏ nhất ~(3, 4)~, ~(3, 5)~ thì vị trí ~(3, 4)~ có chỉ số cột nhỏ nhất. Do đó, đây là vị trí ngồi mà BTC đã sắp xếp cho đội khách mời.

image

Hình vẽ minh họa ba vị trí khả thi cho đội khách mời ở ví dụ thứ nhất. Màu đỏ biểu thị ghế đã được ngồi, màu xanh biểu thị ghế mà đội khách mời sẽ ngồi.


Comments

Please read the guidelines before commenting.



  • -33
    Xcode  commented on July 31, 2023, 9:34 a.m.

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