Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBFIREWK - VOI05 Pháo hoa

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbfirewk


Nhằm chào mừng các ngày lễ lớn trong năm 2005 người ta đã chế tạo một loại đạn pháo hoa mới, khi bắn, đạn nổ thành bông hoa 2n cánh màu ( 1 ≤ n ≤ 30). Nguyên vật liệu cho phép tạo được m màu khác nhau, đánh số từ 1 đến m (2 ≤ m ≤ 32).

Để đảm bảo tính mỹ thuật, việc chuyển tiếp màu giữa 2 cánh hoa kề nhau phải tuân theo quy tắc chuyển màu cầu vồng sau đây:

- Bên cạnh cánh hoa màu i phải là cánh hoa màu i-1 hoặc i+1, với 1 < i < m.

- Bên cạnh cánh hoa màu 1 chỉ có thể là cánh hoa màu 2.

- Bên cạnh cánh hoa màu m chỉ có thể là cánh hoa màu m-1.

Một bông hoa không nhất thiết phải có đầy đủ m màu. Mỗi bông hoa tương ứng với một vòng tròn 2n số thể hiện màu của các cánh hoa. Ví dụ, hình 1 là bông hoa 24 cánh (n = 12) và hình 2 là vòng tròn số tương ứng với nó. Mỗi bông hoa được mô tả bằng dãy 2n số nguyên liệt kê các chỉ số màu của các cánh hoa theo chiều kim đồng hồ. Ví dụ, bông hoa ở hình 1 có thể được mô tả bằng dãy số

3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2.

Hình minh họa

Dãy có thứ tự từ điển nhỏ nhất trong các dãy có thể dùng để mô tả hoa được gọi là mã hoa. Khi đó, mã hoa của bông hoa ở hình 1 sẽ là

1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2 3 4 3 2.

Trong các ngày lễ, Ban tổ chức yêu cầu bắn các đạn pháo hoa 2n cánh có đúng k cánh màu C (0 ≤ k ≤ 2). Các mã hoa thỏa mãn yêu cầu vừa nêu cũng được sắp xếp theo thứ tự từ điển và đánh số bắt đầu từ 1. Hơn nữa, nhằm tạo ra các hoa không giống nhau, đội bắn pháo hoa cần đảm bảo hai viên đạn pháo hoa bắn liên tiếp phải có mã khác nhau. Do vậy, người ta đã thiết kế một Hệ thống chụp ảnh và phân tích tự động để báo cho đội bắn pháo hoa biết số thứ tự của viên đạn pháo hoa vừa nổ trên trời. Em được giao viết chương trình giải quyết nhiệm vụ chính trong phần mềm phân tích tự động này.

Yêu cầu: Cho biết n, m, k và C. Gọi X là tập tất cả các mã hoa 2n cánh có đúng k cánh màu C.

- Hãy xác định số lượng p các phần tử của X.

- Cho một mã hoa nào đó trong tập X. Hãy xác định số thứ tự từ điển của nó trong X.

Input

Dòng đầu tiên chứa 4 số nguyên n, m, k, C.

Dòng tiếp theo chứa 2n số nguyên mô tả một mã hoa.

Các số trên một dòng của file dữ liệu cách nhau ít nhất một dấu cách.

Output

Dòng đầu tiên ghi số nguyên p.

Dòng tiếp theo ghi số thứ tự tìm được của mã hoa.

Example

Input:
3 4 0 1
2 3 4 3 4 3 

Output:
4
3 


Được gửi lên bởi:special_one
Ngày:2008-09-30
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:Vietnam Olympiad of Informatics 2005 - Bảng A

hide comments
2018-07-27 09:17:04
35 đấm suốt 2 tháng chưa ac :<
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.