루미 알고리즘

#1613다이아Quicksand

PO 2025 훈련 캠프코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Sand (https://commons.wikimedia.org/wiki/File:Morocco_Africa_Flickr_Rosino_December_2005_84527213.jpg), CC BY-SA 2.0

Sandra has moved to Sandsvall to study. After spending a few days in the new city, Sandra has noticed that there is quicksand in several locations. If you go to any of these locations, you get stuck in the sand and cannot escape. Sandra wants to know exactly where the quicksand is located so she can avoid these places. Fortunately, unlike Gothenburg, Sandsvall has a well-functioning travel planning app. Using the travel planner, Sandra has found out how long it takes to travel from her residence to each of the other locations in the city.

Sandsvall can be represented by a grid with N rows and M columns. Sandra's residence is in one of the cells of this grid. It takes one minute to travel between two adjacent cells (two cells are adjacent if they share at least one of the 4 sides). In some cells, there is quicksand, and it is impossible to travel from those cells at all.

Let (r, c) be the cell at row r and column c. You are given the number d_{r,c} for each cell in the grid, which represents the minimum possible number of minutes it takes to travel from Sandra's residence to that cell. Your task is to handle Q queries of the following types:

  • ? r c: Determine if there is quicksand in cell (r, c). You should answer ja (yes), nej (no), kanske (maybe), or fel (error).
  • ! r c d: Change the value of d_{r, c} to d.

Input

The first line contains three integers N, M, and Q (1 ≤ N,M,Q ≤ 3 · 10^5, N · M ≤ 3 · 10^5).

The following N lines contain M integers each. The i-th of these lines contains the integers d_{i,1}, d_{i,2}, d_{i,3}, … d_{i,M} (-1 ≤ d_{i,j} ≤ 3 · 10^5).

There will be exactly one cell that satisfies d_{r, c} = 0, which is Sandra's residence. If d_{r, c} = -1, it means that it is impossible to reach cell (r, c) at all.

The following Q lines contain the queries to be processed, in the format described above. The numbers r, c that appear in the queries satisfy 1 ≤ r ≤ N and 1 ≤ c ≤ M. The numbers d that appear satisfy -1 ≤ d ≤ 3 · 10^5, d ≠ 0. Sandra's residence will always have a distance of zero, and no other cell's distance will be changed to zero.

Output

Write the answer to each query of the form ? r c.

  • If there is no way to distribute the quicksand that is consistent with the given numbers d, you should output fel.
  • Otherwise, if there must be quicksand in cell (r, c), output ja.
  • If there is guaranteed to be no quicksand in cell (r, c), output nej.
  • If it is both possible and not possible for there to be quicksand in cell (r, c), output kanske.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
117N = 1
228N,M,Q ≤ 100
320The answer is never fel.
435No additional constraints.

Explanation of Sample

(그림은 원문 저장소에서 볼 수 있습니다)

This is what the grid looks like in the sample case.

In the first query, we need to determine if (3, 5) (highlighted in gray) has quicksand, and it must have it. In the third query, we need to determine if (1, 6) has quicksand, and it is impossible to determine because it is unreachable. After the update that changes the value of (5, 4) to 7, the distances no longer correspond to any valid distribution of quicksand.

예제

예제 1

입력
5 6 7
2 3 4 5 6 -1
1 2 3 4 5 6
0 1 4 5 6 -1
1 2 3 6 7 -1
2 3 4 5 6 -1
? 3 5
? 2 4
? 1 6
! 5 4 7
? 5 3
! 5 6 7
? 1 6
출력
ja
nej
kanske
fel
fel

출처 표기

출처: Programmeringsolympiaden 2025년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.