JOI 2016 Open Contest

Ông JOI rất thích trò chơi “JOIRIS”, nhưng lại không giỏi chơi trò này. JOIRIS được chơi trên một bảng hình chữ nhật chia thành các ô vuông. Bảng có chiều rộng \(N\) ô và chiều cao đủ lớn. Ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ dưới lên được ký hiệu là \((i,j)\). Trong suốt trò chơi, mỗi ô hoặc chứa một khối vuông, hoặc để trống.

Trò chơi diễn ra như sau:

• Cho dãy số nguyên \(A_1,A_2,\ldots,A_N\) mô tả trạng thái ban đầu của bảng.
• Ban đầu, ở cột thứ \(i\) (\(1\le i\le N\)), mỗi ô trong \(A_i\) ô dưới cùng chứa một khối vuông; các ô còn lại đều trống. Nói cách khác, ô \((i,j)\) chứa khối vuông khi và chỉ khi \(1\le j\le A_i\).
• Người chơi có \(10\,000\) mảnh ghép hình chữ nhật, mỗi mảnh gồm \(1\times K\) khối vuông. Người chơi lặp lại thao tác đặt mảnh ghép theo quy tắc dưới đây.

Đầu tiên, người chơi chọn đặt mảnh ghép theo chiều dọc hoặc chiều ngang.

Nếu đặt theo chiều dọc, người chơi chọn một số nguyên \(x\) với \(1\le x\le N\), rồi đặt mảnh ghép thẳng đứng ngay phía trên khối vuông cao nhất trong cột \(x\). Cụ thể, gọi \(y\) là số nguyên lớn nhất sao cho ô \((x,y)\) chứa khối vuông; nếu cột này trống thì lấy \(y=0\). Đặt một khối vuông vào mỗi ô sau:

Nếu đặt theo chiều ngang, người chơi chọn một số nguyên \(x\) với \(1\le x\le N-K+1\), rồi đặt mảnh ghép nằm ngang ngay phía trên khối vuông cao nhất trong các cột từ \(x\) đến \(x+K-1\). Cụ thể, gọi \(y\) là số nguyên lớn nhất sao cho tồn tại \(i\) (\(1\le i\le K\)) mà ô \((x+i-1,y)\) chứa khối vuông; nếu tất cả các cột này đều trống thì lấy \(y=0\). Đặt một khối vuông vào mỗi ô sau:

Sau mỗi lần đặt, nếu cả \(N\) ô của một hàng đều chứa khối vuông, tất cả các khối vuông trong hàng đó biến mất. Sau đó, mỗi khối vuông phía trên hàng vừa xóa dịch xuống một ô. Nói cách khác, khi hàng \(y\) được lấp đầy, trạng thái của mọi ô \((i,j)\) với \(1\le i\le N\) và \(j\ge y\) được đồng thời thay bằng trạng thái của ô \((i,j+1)\). Nếu nhiều hàng cùng được lấp đầy, thực hiện việc xóa hàng theo thứ tự từ dưới lên.

Mục tiêu của JOIRIS là xóa hết các khối vuông trên bảng bằng không quá \(10\,000\) lần đặt mảnh ghép. Vì không giỏi trò chơi này, ông JOI không biết cách đạt được mục tiêu đó.

Yêu cầu

Cho trạng thái ban đầu của bảng và kích thước mảnh ghép, hãy xác định liệu có thể xóa hết các khối vuông trên bảng bằng không quá \(10\,000\) lần đặt hay không. Nếu có thể, hãy tìm một cách thực hiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,K\) cách nhau bởi một dấu cách: chiều rộng của bảng và kích thước \(1\times K\) của mỗi mảnh ghép.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa số nguyên \(A_i\): số ô dưới cùng chứa khối vuông ở cột \(i\) trong trạng thái ban đầu.

Dữ liệu ra

Nếu không thể xóa hết các khối vuông bằng không quá \(10\,000\) lần đặt, in số nguyên -1 trên một dòng.

Ngược lại, in \(X+1\) dòng, trong đó \(X\) là số lần đặt mảnh ghép và \(0\le X\le 10\,000\):

• Dòng đầu tiên chứa số nguyên \(X\).
• Dòng thứ \(i\) trong \(X\) dòng tiếp theo mô tả lần đặt thứ \(i\), theo đúng thứ tự thực hiện:
• In 1 x nếu đặt theo chiều dọc tại cột \(x\), với \(1\le x\le N\).
• In 2 x nếu đặt theo chiều ngang, bắt đầu tại cột \(x\), với \(1\le x\le N-K+1\).

Trong mỗi dòng mô tả thao tác, hai số nguyên được ngăn cách bởi một dấu cách. Sau khi thực hiện tất cả các thao tác và xóa các hàng đầy theo quy tắc, bảng phải hoàn toàn trống. Có thể in bất kỳ dãy thao tác hợp lệ nào thỏa mãn giới hạn; không cần tối thiểu hóa \(X\). Bộ chấm chỉ đánh giá đúng hoặc sai, không cho điểm dựa trên số lần đặt.

Ràng buộc

• \(2\le N\le 50\).
• \(1\le K\le N\).
• \(0\le A_i\le 50\) với mọi \(1\le i\le N\).
• Có ít nhất một chỉ số \(i\) (\(1\le i\le N\)) thỏa mãn \(A_i=0\).
• Có ít nhất một chỉ số \(i\) (\(1\le i\le N\)) thỏa mãn \(A_i>0\).

Phân nhóm

1. 15 điểm: \(K=2\) và \(N\) chẵn.
2. 15 điểm: \(K=2\) và \(N\) lẻ.
3. 15 điểm: \(N\) chia hết cho \(K\).
4. 55 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 2
1
0
1
2

4
2 2
1 1
2 3
1 2

3 2
2
0
1

3
1 2
1 3
2 1

2 2
0
1

-1

5 3
1
0
1
0
1

9
1 4
1 5
2 1
2 1
2 2
1 1
1 2
2 3
2 3

Bạn có biết Công ty TNHH Just Odd Inventions không? Công việc kinh doanh của công ty này là tạo ra “những phát minh kỳ lạ”. Trong bài này, ta gọi tắt là công ty JOI.

Gần đây, lợi nhuận của công ty JOI sụt giảm nghiêm trọng vì chỉ kinh doanh những phát minh kỳ lạ. Công ty dự định bắt đầu một hoạt động kinh doanh mới: bán dung dịch chứa các chuỗi RNA. Một chuỗi RNA được xem là một xâu chỉ gồm bốn ký tự A, G, C, U. Công ty JOI đã chuẩn bị \(N\) chuỗi RNA để kinh doanh.

Công ty nhận đơn hàng từ khách hàng theo hình thức sau: khách hàng chọn hai xâu \(P,Q\). Trong số các chuỗi RNA đã chuẩn bị, công ty bán những chuỗi có \(|P|\) ký tự đầu tiên là \(P\) và \(|Q|\) ký tự cuối cùng là \(Q\). Ở đây, \(|P|\) và \(|Q|\) lần lượt là độ dài của \(P\) và \(Q\).

Có bao nhiêu chuỗi RNA mà công ty đã chuẩn bị thỏa mãn điều kiện của từng đơn hàng?

Yêu cầu

Cho thông tin về các chuỗi RNA đã chuẩn bị và các đơn hàng của khách hàng, hãy tính số chuỗi RNA thỏa mãn điều kiện của mỗi đơn hàng.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,M\) cách nhau bởi một dấu cách: số chuỗi RNA công ty đã chuẩn bị và số đơn hàng.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa xâu \(S_i\), là chuỗi RNA thứ \(i\).
• Dòng thứ \(j\) trong \(M\) dòng tiếp theo (\(1\le j\le M\)) chứa hai xâu \(P_j,Q_j\) cách nhau bởi một dấu cách, là hai xâu khách hàng chọn trong đơn hàng thứ \(j\).

Dữ liệu ra

In \(M\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le M\)) chứa một số nguyên: số chuỗi RNA đã chuẩn bị thỏa mãn điều kiện của đơn hàng thứ \(j\).

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le M\le 100\,000\).
• Mỗi xâu chỉ chứa các ký tự A, G, C, U.
• \(1\le |S_i|\le 100\,000\) với mọi \(1\le i\le N\).
• \(1\le |P_j|\le 100\,000\) với mọi \(1\le j\le M\).
• \(1\le |Q_j|\le 100\,000\) với mọi \(1\le j\le M\).

Các tổng độ dài thỏa mãn riêng từng giới hạn sau:

• \(|S_1|+|S_2|+\cdots+|S_N|\le 2\,000\,000\).
• \(|P_1|+|P_2|+\cdots+|P_M|\le 2\,000\,000\).
• \(|Q_1|+|Q_2|+\cdots+|Q_M|\le 2\,000\,000\).

Phân nhóm

Subtask 1 (10 điểm)

• \(N\le 100\).
• \(M\le 100\).
• \(|S_i|\le 100\) với mọi \(1\le i\le N\).
• \(|P_j|\le 100\) với mọi \(1\le j\le M\).
• \(|Q_j|\le 100\) với mọi \(1\le j\le M\).

Subtask 2 (25 điểm)

• \(N\le 5\,000\).
• \(M\le 5\,000\).

Subtask 3 (25 điểm)

Các tổng độ dài thỏa mãn riêng từng giới hạn sau:

• \(|S_1|+|S_2|+\cdots+|S_N|\le 100\,000\).
• \(|P_1|+|P_2|+\cdots+|P_M|\le 100\,000\).
• \(|Q_1|+|Q_2|+\cdots+|Q_M|\le 100\,000\).

Subtask 4 (40 điểm)

Không có ràng buộc bổ sung.

Ví dụ

2 3
AUGC
AGC
G C
AU C
A C

0
1
2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

2
1
1

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

1
0
1
2
3
2
0

Kỳ thi Olympic Tin học Quốc tế sẽ được tổ chức tại thành phố Tsukuba, Nhật Bản. Để chuẩn bị cho IOI, chúng ta dự định xây dựng các tòa nhà chọc trời trên đường phố chính của thành phố. Vì muốn tạo ra một địa điểm tham quan mới, các tòa nhà phải thỏa mãn những điều kiện sau.

Có \(N\) tòa nhà được xây dọc theo một đường thẳng trên đường phố chính. Chiều cao của chúng là \(A_1,A_2,\ldots,A_N\), đôi một khác nhau. Thứ tự của các tòa nhà chưa được quyết định, nên ta có thể hoán vị các chiều cao này tùy ý.

Chúng ta sẽ trang trí các tòa nhà để chào đón IOI. Do giới hạn về vật liệu trang trí, tổng các trị tuyệt đối của hiệu chiều cao giữa hai tòa nhà kề nhau phải không vượt quá \(L\). Nói cách khác, nếu chiều cao các tòa nhà theo thứ tự nhìn từ một đầu của đường phố là \(f_1,f_2,\ldots,f_N\), thì phải có:

Ở đây, \(|x|\) là giá trị tuyệt đối của \(x\).

Có bao nhiêu hoán vị của các tòa nhà thỏa mãn điều kiện trên?

Yêu cầu

Cho số tòa nhà \(N\), chiều cao của chúng và giới hạn \(L\), hãy tính số hoán vị thỏa mãn điều kiện. Vì kết quả có thể rất lớn, hãy in phần dư của kết quả khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,L\) cách nhau bởi một dấu cách: số tòa nhà và giới hạn trên của tổng các trị tuyệt đối của hiệu chiều cao giữa hai tòa nhà kề nhau.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\) cách nhau bởi dấu cách. Số nguyên \(A_i\) là chiều cao của tòa nhà thứ \(i\) (\(1\le i\le N\)).

Dữ liệu ra

In một số nguyên trên một dòng ra đầu ra chuẩn: phần dư của số hoán vị thỏa mãn điều kiện khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1\le N\le 100\).
• \(1\le L\le 1\,000\).
• \(1\le A_i\le 1\,000\) với mọi \(1\le i\le N\).
• \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).

Phân nhóm

1. 5 điểm: \(N\le 8\).
2. 15 điểm: \(N\le 14\) và \(L\le 100\).
3. 80 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 10
3 6 2 9

6

    Với $(f_1,f_2,f_3,f_4)=(2,3,9,6)$:

    Với $(f_1,f_2,f_3,f_4)=(3,2,6,9)$:

    Với $(f_1,f_2,f_3,f_4)=(6,9,3,2)$:

    Với $(f_1,f_2,f_3,f_4)=(9,6,2,3)$:

    Với $(f_1,f_2,f_3,f_4)=(9,6,3,2)$:

8 35
3 7 1 5 10 2 11 6

31384