Cuộc thi lập trình

Xem dạng PDF

Gửi bài giải

Điểm: 1,67 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Algorithmic Engagement 2009
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cuộc thi lập trình sắp tới mà Byteman tham gia sẽ có ~M~ thí sinh đánh số từ ~1~ đến ~M~, Byteman mang số ~1~. Được biết có ~N~ bài toán được chọn, mỗi bài thuộc ~1~ trong ~K~ dạng đã được công bố trước kì thi (nhiều bài có thể thuộc cùng ~1~ dạng). Dạng bài và độ khó của các bài này đang được ban giám khảo xác định.

Byteman, thay vì luyện tập giải bài, cậu quyết định đi tìm hiểu đối thủ. Cậu biết được các thông số ~A_{x,y}~ là khả năng của người ~x~ tại dạng bài ~y~. Cụ thể, nếu độ khó của ~1~ bài dạng ~y~ được chọn là ~c~:

  • Nếu ~A_{x,y} < c~, người ~x~ không giải được bài này.
  • Nếu ~A_{x,y} \geq c~, người ~x~ giải được và có ~A_{x,y} - c~ điểm thưởng. Điểm thưởng cuối cùng của ~1~ người bằng tổng điểm thưởng có được từ những bài giải được.

Bảng xếp hạng được tính như sau:

  • Người nào giải được nhiều bài hơn sẽ xếp trên
  • Nếu ~2~ người giải được cùng số bài, người có nhiều điểm thưởng hơn sẽ xếp trên.

Byteman muốn xác định xem liệu có cách lựa chọn bài nào cho phép cậu ta đứng nhất (đồng hạng nhất không tính) trong cuộc thi hay không.

Input

  • Dòng ~1~ chứa số ~T~ ~(0 < T \le 10)~ là số bộ test
  • Với mỗi test, dòng đầu chứa ~3~ số ~N~, ~M~, ~K~ ~(0 < N \le 400~; ~0 < k~. m ~\le 400)~
  • Tiếp đó là ~M~ dòng, mỗi dòng chứa ~K~ số nguyên mô tả các giá trị ~A_{x,y}~ (các số nằm trong khoảng ~[1~, ~1000]~)

Output

Mỗi test ghi ra ~1~ dòng: TAK ứng với việc Byteman có thể thắng và NIE nếu không.

Sample Input

2
3 6 5
70 100 100 70 100
205 180 70 200 150
180 200 30 25 45
75 45 80 180 180
120 10 120 90 10
15 110 135 150 210
2 2 2
12 12
20 20

Sample Output

TAK
NIE

Note

Một cách lựa chọn cho trường hợp ~1~:

~3~ bài được chọn: dạng ~1~ với độ khó ~5~, dạng ~2~ với độ khó ~20~ và dạng ~3~ với độ khó ~75~.

Bảng xếp hạng:

  1. Byteman (#1): ~3~ bài, ~170~ điểm
  2. #6: ~3~ bài, ~160~ điểm
  3. #4: ~3~ bài, ~100~ điểm
  4. #2: ~2~ bài, ~360~ điểm
  5. #3: ~2~ bài, ~355~ điểm
  6. #5: ~2~ bài, ~160~ điểm

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -2
    buu_ske155  đã bình luận lúc 15, Tháng 11, 2023, 4:18

    cũng dễ