Du Thuyền Xa Xỉ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ cảng được đánh số từ $1$ đến $N$ . Mỗi cảng có đúng hai con sông đi ra: một sông bên trái và một sông bên phải, mỗi sông dẫn đến một cảng khác (hoặc chính nó).

Xuất phát từ cảng số $1$ , bạn đi theo một chuỗi $M$ hướng dẫn (mỗi hướng dẫn là L hoặc R), lặp lại đúng $K$ lần (tổng cộng $K \times M$ bước di chuyển).

Hãy xác định bạn kết thúc ở cảng nào.

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $M$ , $K$ .
$N$ dòng tiếp theo: Dòng $i + 1$ chứa hai số nguyên là cảng đích khi đi theo sông trái và sông phải từ cảng $i$ .
Dòng cuối: $M$ ký tự cách nhau bởi dấu cách, mỗi ký tự là L hoặc R.

Dữ liệu ra

Một số nguyên duy nhất: số thứ tự cảng cuối cùng.

Ràng buộc

$1 \leq N \leq 1 000$
$1 \leq M \leq 500$
$1 \leq K \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 3 3 2 4 3 1 4 2 1 3 L L R	4	Chuỗi LLR lặp 3 lần: 1→2→3→2→3→4→3→4→1→4. Kết thúc tại cảng 4.
50 10 10 6 4 42 48 2 41 40 8 17 29 28 7 34 46 4 9 36 27 9 37 28 32 22 10 30 48 16 31 11 33 36 3 14 39 45 5 46 13 34 23 29 6 3 38 44 30 21 15 41 50 12 9 30 24 45 6 19 39 11 14 2 46 39 22 14 9 48 43 16 50 30 9 32 2 25 24 3 38 11 24 25 3 4 19 9 22 10 19 37 13 14 25 36 29 33 34 21 48 33 2 L L R L L R R R R R	50	Sau 100 bước (10 lần lặp × 10 hướng dẫn), kết thúc tại cảng 50.

Bình luận

Không có bình luận tại thời điểm này.