COCI 2019/2020 - Contest 5 - Političari

View as PDF

Submit solution

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

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

Ở một quốc gia nọ, các nhà chính trị gia đang cáo buộc lẫn nhau trên sóng truyền hình thay vì làm việc. Tất cả bắt đầu vào một chiều chủ nhật khi chính khách thứ nhất trở thành khách mời trong buổi toạ đàm. Trong buổi toạ đàm, chính khách đó cáo buộc chính khách thứ hai vì tình hình nghèo đói của nước họ. Đương nhiên, trong tập tiếp theo của chương trình, chính khách thứ hai lại tiếp tục được mời. Người dẫn chương trình đã chỉ ra rằng chính người chính khách thứ nhất đã buộc tội người chính khách thứ hai, và người chính khách thứ hai ấy lại tiếp tục đổ lỗi một nhà chính trị gia khác. Người bị đổ lỗi lại tiếp tục trở thành khách mời của buổi toạ đàm tiếp theo, và cứ tiếp diễn như vậy.

Cho đến tận hôm nay, gần 20 năm đã trôi qua, một chính khách mới lại tiếp tục là khách mời của chương trình và được biết rằng ai là người đã buộc tội người đó vì tình hình nghèo đói của đất nước. Nhà chính khách đó lại tiếp tục đổ lỗi và vòng tròn luẩn quẩn đó lại tiếp diễn. Để làm mọi thứ thú vị hơn, chúng tôi đã nhận ra rằng mỗi nhà chính khách có một chiến lược cố định về cách hành động trong mỗi tập: Mỗi chính khách đều biết phải đổ lỗi cho ai, dựa trên người đã đổ lỗi cho chính mình ở trong tập trước. Bạn sẽ được cung cấp thông tin này, và chúng tôi hi vọng bạn có thể viết ~1~ chương trình tính toán xem chính khách nào sẽ là khách mời của chương trình thứ ~K~.

Input

  • Dòng đầu chứ số nguyên ~N~ ~(2 ≤ N ≤ 500)~ và ~K~ (~1~ ≤ ~K~ ≤ ~10^{18}~)

  • N dòng tiếp theo mỗi dòng chứa N số nguyên, số nguyên thứ ~j~ ở dòng thứ i cho chúng ta biết ai là người sẽ bị chính khách thứ ~i~ buộc tội nếu như anh ấy bị chính khách thứ ~j~ buộc tội trong buổi toạ đàm ngay trước đó.

  • Không có chính khách nào tự đổ lỗi cho chính mình. Vì vậy không có bất kì số nguyên nào ở dòng thứ ~i~ trong ma trận sẽ có giá trị bằng ~i~. Tương tự, số nguyên thứ ~i~ tại dòng ~i~ trong ma trận sẽ luôn luôn bằng ~0~.

Output

  • Số hiệu của người chính khách sẽ được mời trong tập thứ ~K~ của show.

Sample Input 1

2 4
0 2
1 0

Sample Output 1

2

Sample Input 2

3 7
0 3 2
3 0 3
2 1 0

Sample Output 2

1

Sample Input 3

4 7
0 4 3 2
4 0 4 1
2 1 0 1
3 2 3 0

Sample Output 3

3

Subtask

  • 47% (8/17) test có ~1 \le K \le 10^5~
  • 53% (9/17) test không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.