COCI 2020/2021 - Contest 1 - Patkice

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 1
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ở một vùng đất nhiệt đới xa xôi, có ba chú vịt đáng yêu sinh sống. Vào một ngày mùa hè nóng nực, khi đã quá chán với việc nằm dài bên bờ biển, chúng quyết định đi du lịch đến một hòn đảo gần đó. Vì những chú vịt rất thích phiêu lưu nên chúng quyết định đi du hành theo dòng hải lưu trong một chiếc ô đen cũ kỹ.

Vì những chú vịt này là những nhà thám hiểm đại dương giàu kinh nghiệm nên trước chuyến đi, chúng sẽ kiểm tra bản đồ các dòng hải lưu. Trên bản đồ, hòn đảo nơi 3 chú vịt sinh sống được đánh dấu bằng chữ cái o. Chúng có thể bắt đầu chuyến đi của mình theo bất kỳ hướng nào trong số bốn hướng: bắc - N, đông - E, tây - Wnam - S.

Các dòng hải lưu trong vùng biển này di chuyển theo một trong bốn hướng và được đánh dấu trên bản đồ như sau cách: tây-đông < , đông-tây >, bắc-nam vnam-bắc ^. Khi một chú vịt nằm trên một ô có dòng hải lưu, chúng sẽ di chuyển ~1~ ô theo hướng của dòng hải lưu này. Các dòng hải lưu ở vùng biển này rất đặc biệt, vì chúng không bao giờ dẫn ra ngoài bản đồkhông tạo thành xoáy (những nơi mà những chú vịt sẽ di chuyển theo vòng tròn nếu chúng chạy theo dòng chảy).

Biển lặng được đánh dấu bằng dấu chấm .. Nếu dòng chảy đưa những chú vịt đến ô biển lặng hoặc quay trở lại hòn đảo bắt đầu, chúng sẽ không thể tiếp tục chuyến đi. Hòn đảo mà những chú vịt muốn đến thăm được đánh dấu bằng chữ cái x.

Những chú vịt không muốn dừng bữa tiệc trên bãi biển của chúng. Chúng rất mong muốn bạn cho chúng biết liệu chúng có thể đến hòn đảo kia hay không, và nếu có, chúng nên bắt đầu chuyến đi theo hướng nào. Vì một trong những chú vịt bị say sóng rất nặng, nên chúng yêu cầu bạn chọn hướng để chuyến đi càng ngắn càng tốt. Nếu có nhiều hướng mang lại thời gian di chuyển tối thiểu như nhau, bạn nên chọn hướng đi theo thứ tự mà xuất hiện trước trong từ điển.

Input

Dòng đầu tiên chứa hai số nguyên ~r~ và ~s~ ~(3 \leq r, s \leq 100)~ mô tả số hàng và số cột của bản đồ.

~r~ dòng tiếp theo chứa ~s~ ký tự từ tập o<>v^.x miêu tả bản đồ các dòng hải lưu. Sẽ luôn có duy nhất một ký tự o và duy nhất một ký tự x trên bản đồ. Ký tự o sẽ không bao giờ được đặt ở hàng/cột đầu tiên hoặc hàng/cột cuối cùng.

Output

Nếu những chú vịt không thể đến được hòn đảo khác, hãy in :(.

Trường hợp còn lại, hãy in :) ở dòng đầu tiên. Dòng thứ hai in hướng bắt đầu (N cho phía bắc, E cho phía đông, W cho phía tây hoặc S cho phía nam).

Scoring

  • ~25~ test có duy nhất một hướng bắt đầu nếu nó tồn tại.
  • ~5~ test còn lại không có ràng buộc gì thêm.

    Sample 1

Input
6 6
..>>>v
.o^..v
.v.<.v
.>>^.v
.x<<<<
......
Output
:)
E

Sample 2

Input
5 5
v<<<<
>v.>^
v<.o.
>>v>v
..>>x
Output
:)
S

Sample 3

Input
3 3
x>.
.o^
^<.
Output
:(

Giải thích

Trong ví dụ đầu tiên, nếu những chú vịt bắt đầu chuyến đi của mình theo bất kỳ hướng nào trừ hướng đông, chúng sẽ kết thúc ở vùng biển lặng và sẽ không đến được hòn đảo khác.

Trong ví dụ thứ hai, những chú vịt có thể đến hòn đảo khác nếu chúng bắt đầu bằng cách đi về phía bắc hoặc nam. Chúng chọn con đường phía nam, vì nó ngắn hơn.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.