VOEASY - Dãy biến đổi
Giới hạn- Thời gian: 0.5s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho bộ N số nguyên không âm (a 1 , a 2 , …, a N ) và một danh sách gồm M bộ quy tắc biến đổi.
Ta định nghĩa một quy tắc biến đổi (u, oper, v) là phép biến đổi dãy số A gồm N phần tử (a1, a2, ... , aN) thành một dãy số B gồm N phần tử (b1, b2, ..., bN) Với dãy b thỏa mãn bi = au oper av. Oper chỉ gồm {and, or, xor}Ta định nghĩa một bộ quy tắc biến đổi gồm N quy tắc biến đổi (u, oper, v). Những quy tắc này sẽ biến đổi dãy số A gồm N phần tử (a 1 , a 2 , …, a N ) thành dãy số B cũng gồm N phần tử (b 1 , b 2 , ... , b N ). Trong đó, quy tắc thứ i như sau:
b i = a u oper a v , với oper là 1 trong 3 phép toán and, or, xor.
Yêu cầu: Cho bộ (a
1
, a
2
, ... , a
N
) ban đầu, M bộ quy tắc biến đổi và số K. Ta lần lượt biến đổi dãy A ban đầu thông qua các bộ quy tắc theo thứ tự sau: 1, 2, …, M, 1, 2, …,M, 1, 2, ... Hãy xác định giá trị cuối cùng của (a
1
, a
2
, …, a
N
) sau K lần biến đổi.
Input
Gồm một dòng ghi 3 số N, M và K.
Dòng thứ 2 ghi N số ban đầu a 1 , a 2 , …, a N
Tiếp theo là M nhóm dòng mô tả M bộ quy tắc biến đổi; mỗi bộ quy tắc được ghi trên N dòng gồm 3 giá trị u oper v. Các bộ quy tắc biến đổi được ghi cách nhau một dòng trống.
Output
In ra N số nguyên là bộ số thu được sau K lần biến đổi.
Giới hạn
1 ≤ M ≤ 100 cho tất cả các test.
- Trong 30% test đầu tiên: 1 ≤ N ≤ 10; 0 ≤ a i ≤ 10 9 ; 0 ≤ K ≤ 100.
- Trong 30% test tiếp theo: 1 ≤ N ≤ 3; 0 ≤ a i ≤ 100; 0 ≤ K ≤ 10 9 .
- Trong 40% test tiếp theo: 1 ≤ N ≤ 10; 0 ≤ a i ≤ 10 9 , K ≤ 10 9 .
Thời gian chạy: 0.5s cho mỗi test
Chú ý:
- Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
- Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone . Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.
Example
Input: 2 3 5 1 2 1 and 2 1 or 2 1 or 2 1 xor 2 1 xor 2 1 and 2 Output: 3 3
Giải thích
(1, 2) ⇒ (0, 3) ⇒ (3, 3) ⇒ (0, 3) ⇒ (0, 3) ⇒ (3, 3)
- Người up: voj
- Nguồn bài: VO 2015