ez_code   8달 전

문제

당신은 2025 ICPC 아시아-태평양 챔피언십에 참여하러 가는 길이다. 유감스럽게도 지금은 비행에서 최악의 단계인 탑승 수속 줄을 기다리는 중이다.

당신은 줄 앞에서 뒤까지 1부터 N까지 번호가 매겨진 N명의 여행자와 함께 줄에 서 있다.

탑승 수속 대기 공간은 R개의 행과 C개의 열로 이루어진 격자로, 행은 (위에서 아래까지) 1부터 R까지 번호가 매겨져 있고 열은 (왼쪽에서 오른쪽까지) 1부터 C까지 번호가 매겨져 있다. 각 여행자는 격자에서 하나의 칸을 홀로 차지한다. 두 여행자는 각자 있는 칸이 선을 공유한다면 인접한 상태이다. 2 <= T <= N에 대해 T번 여행자와 T-1번 여행자는 인접함이 보장된다.

예를 들어, 그림 L.1은 가능한 여행자의 위치이다. 이 예시에서 1번 여행자는 2번, 10번 여행자와 인접하지만 11번 여행자와는 인접하지 않다.

(그림 L.1 참조)

탑승 수속 각 단계에서 다음의 과정이 동시에 발생한다:

  • 여행자 T가 줄 맨앞에 있다고 하면, 해당 여행자가 비행기에 타고 탑승 수속 대기 공간을 벗어난다.
  • 모든 T'에 대해 (T + 1 <= T' <= N), 직전 단계에서 T'-1번 여행자가 있던 칸을 T'번 여행자가 점유한다.

예를 들어, 그림 L.2는 위의 초기 상태에서 첫 세 번의 탑승 수속 단계가 지났을 때 여행자의 위치를 나타낸다.

(그림 L.2 참조)

당신은 P번 여행자이다 (즉, P-1명의 여행자가 당신 앞에 있다). 당신은 당신의 팀 코치가 줄 어딘가 있다는 사실은 알지만 어디 있는지는 모른다. 팀 코치가 (P를 제외한) 1번부터 N번 여행자일 확률이 모두 동일하다고 할 때, 당신은 비행기에 탑승하기 전 어느 시점엔가 당신이 팀 코치와 인접하게 될 확률을 구하려 한다. 엄밀하게 말해, S번의 탑승 수속 단계 이후 P번 여행자와 Q번 여행자가 인접하게 되는 정수 S가 존재한다면 (0 <= S < P) 당신은 Q번 여행자와 어느 시점엔가 인접하게 된다.

입력

첫 줄에는 네 정수 R, C, N, P가 주어진다. (1 <= R, C <= 1000; 2 <= N <= R X C; 1 <= P <= N) 다음 각 R개 줄에는 C개 정수가 입력된다. i번째 줄의 j번째 정수는 Gi,j인데, Gi,j가 0이 아니라면 Gi,j번 여행자가 탑승 수속 구역의 i번째 행 j번째 열에 있음을 의미하고 Gi,j가 0이라면 해당 칸에 아무도 없음을 의미한다. 모든 (i, j)에 대해 1부터 N까지 정수는 정확히 한 번씩 Gi,j에 등장한다. 입력에서 모든 2 <= T <= N에 대해 T번 여행자와 T-1번 여행자가 인접함은 보장된다.

출력

당신이 비행기에 타기 전 어느 시점엔가 팀 코치와 인접하게 될 확률을 나타내는 분수를 x/y 형식으로 출력하여라. y는 무조건 N-1이어야 한다. 정수와 / 구분자 사이 공백이 없음에 유의하라.

댓글을 작성하려면 로그인해야 합니다.