Ta nấu tổng cộng \(N\) chiếc bánh kếp: một chiếc bán kính \(1\) cm, một chiếc \(2\) cm, ..., một chiếc \(N\) cm, theo thứ tự bất kỳ. Chiếc đầu đặt lên đĩa; mỗi chiếc sau đặt lên chiếc trước, đồng tâm. Khi vừa thêm, một bánh luôn nhìn thấy từ trên. Nó chỉ bị che khi về sau có bánh bán kính lớn hơn.

Ví dụ với \(4\) bánh: nấu bán kính \(3\) trước, có một bánh thấy được; thêm bán kính \(1\), cả hai thấy được; thêm bán kính \(2\), nó che bánh \(1\) nhưng không che bánh \(3\), còn hai bánh thấy được; cuối cùng bánh \(4\) che tất cả, chỉ còn một. Trong hình, bánh tô kín là thấy được, bánh bán trong suốt là bị che.

Gọi \(V_i\) là số bánh nhìn thấy khi chồng có đúng \(i\) bánh. Ví dụ có \(V=(1,2,2,1)\). Cho \(V_1,\ldots,V_N\), có bao nhiêu trong \(N!\) thứ tự nấu tạo đúng dãy đó? In kết quả modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ gồm hai dòng: \(N\), rồi \(N\) số \(V_1,\ldots,V_N\).

Dữ liệu ra

Với mỗi bộ, in Case #x: y, với \(y\) là số thứ tự nấu hợp lệ modulo \(1000000007\).

Ràng buộc

• \(1\le T\le100\); \(1\le V_i\le i\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le N\le13\).
• Test Set 2 (Hidden Verdict): \(2\le N\le10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Case #1: 1
Case #2: 2
Case #3: 0

Ví dụ bổ sung — Test Set 2

1
24
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Case #1: 234141013

??? "Giải thích"
    Có $316234143225$ thứ tự nấu tạo dãy; modulo $10^9+7$ là $234141013$. Ví dụ không chạy trên lời giải nộp.

Nguồn

Google Code Jam 2021, Vòng 2, bài Hidden Pancakes.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Matryoshka là một loại búp bê xuất xứ từ Nga hơn một thế kỷ trước. Đặc trưng của chúng là một bộ búp bê có kích thước khác nhau, trong đó búp bê nhỏ nằm vừa vặn bên trong búp bê lớn.

Trong bài này, ta làm việc với matrygon: các bộ đa giác lồi đều có kiểu lồng nhau tương tự. Một matrygon gồm các đa giác lồi đều có diện tích dương \(p_1,p_2,\ldots,p_k\) sao cho với mọi \(i\), các đỉnh của \(p_{i+1}\) trùng với một tập con thực sự các đỉnh của \(p_i\); tức \(p_{i+1}\) có ít đỉnh hơn hẳn \(p_i\).

Hai hình sau minh họa hai matrygon. Hình thứ nhất có ba đa giác lồi đều: một đa giác \(24\) cạnh, một lục giác đều \(6\) cạnh và một tam giác đều \(3\) cạnh. Hình thứ hai có hai đa giác: một đa giác đều \(22\) cạnh và một đa giác đều \(11\) cạnh. Tổng số cạnh của các đa giác trong mỗi matrygon đều bằng \(33\).

Cho tổng số cạnh cố định \(N\), hãy tính số đa giác lớn nhất có thể thuộc một matrygon sao cho tổng số cạnh của mọi đa giác đúng bằng \(N\).

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi dòng tiếp theo chứa một số nguyên \(N\), là tổng số cạnh mục tiêu của một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là số đa giác lớn nhất trong một matrygon có tổng số cạnh đúng bằng \(N\).

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(3\le N\le1000\).
• Test Set 2 (Visible Verdict): \(3\le N\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
33
15
41

Case #1: 3
Case #2: 2
Case #3: 1

Nguồn

Google Code Jam 2021, Vòng 2, bài Matrygons.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Minimum Sort

Trong bài này, bạn phải sắp xếp một danh sách gồm \(N=100\) số nguyên phân biệt theo thứ tự tăng nghiêm ngặt. Bạn có thể hoán đổi nội dung của hai vị trí bất kỳ; chúng không cần kề nhau. Tuy nhiên, bạn không thể đọc trực tiếp các nội dung đó.

Bạn lấy thông tin về danh sách bằng truy vấn giá trị nhỏ nhất của một đoạn. Truy vấn trả về vị trí của giá trị nhỏ nhất trong một đoạn vị trí liên tiếp. Ví dụ, trong danh sách \([51,33,100,11]\), giá trị nhỏ nhất trên đoạn vị trí \(2\) đến \(4\) (đánh số từ \(1\)) nằm ở vị trí \(4\); còn giá trị nhỏ nhất trên đoạn \(1\) đến \(3\) nằm ở vị trí \(2\).

Các truy vấn này bị giới hạn bởi ngân sách xu của từng bộ dữ liệu. Đoạn càng dài thì càng rẻ: hỏi vị trí nhỏ nhất giữa \(i\) và \(j\) với \(i<j\) tốn

xu, trong đó \(\lceil x\rceil\) là số nguyên nhỏ nhất không nhỏ hơn \(x\). Trái lại, thao tác hoán đổi không tốn xu.

Hãy viết chương trình sắp xếp danh sách bằng số lần hoán đổi tùy ý và tổng chi phí không quá \(6\times10^8\) xu cho các truy vấn giá trị nhỏ nhất trong mỗi bộ dữ liệu.

Giao thức tương tác

Các mục Dữ liệu vào và Dữ liệu ra dưới đây quy định đầy đủ cuộc đối thoại giữa chương trình và bộ chấm.

Dữ liệu vào

Đây là bài tương tác. Ban đầu, bộ chấm gửi một dòng chứa hai số nguyên \(T,N\): số bộ dữ liệu và số phần tử cần sắp xếp trong mỗi bộ. Bộ chấm đã cố định các danh sách trước khi nhận đầu vào từ chương trình; trong quá trình trao đổi, chúng chỉ thay đổi bởi những phép hoán đổi bạn yêu cầu.

Sau đó, bạn phải xử lý \(T\) bộ dữ liệu. Mỗi bộ gồm một chuỗi lượt trao đổi và một dòng bổ sung để báo đã hoàn tất. Trong mỗi lượt, chương trình in một dòng, rồi bộ chấm in một dòng phản hồi.

Dữ liệu ra

Ở mỗi lượt, chương trình phải in đúng một trong các lệnh sau:

• M i j, với \(i<j\), biểu diễn truy vấn giá trị nhỏ nhất. Bộ chấm trả về một số nguyên là vị trí của giá trị nhỏ nhất trong đoạn vị trí \([i,j]\), đánh số từ \(1\).
• S i j, với \(i<j\), biểu diễn thao tác hoán đổi. Bộ chấm đổi hai phần tử tại vị trí \(i,j\) và trả về 1.
• D, báo rằng bạn đã sắp xếp xong danh sách. Bộ chấm kiểm tra danh sách và trả 1 nếu nó tăng nghiêm ngặt, hoặc -1 nếu không.

Sau khi bộ chấm trả 1 cho lệnh D, nếu đây là bộ cuối thì phiên làm việc kết thúc; nếu không, bộ chấm lập tức chờ lệnh đầu tiên của bộ tiếp theo. Sau khi nhận phản hồi cho bộ dữ liệu thứ \(T\), chương trình phải kết thúc.

Nếu tại bất cứ lúc nào bộ chấm nhận một dòng sai định dạng, một giá trị không hợp lệ, hoặc một truy vấn M làm vượt ngân sách còn lại, nó in -1 và không in thêm gì nữa. Sau khi nhận -1, chương trình phải thoát ngay; nếu tiếp tục chờ, chương trình sẽ bị treo. Hãy nhớ xả bộ đệm đầu ra sau mỗi lệnh.

Ràng buộc

• \(T=100\).
• \(N=100\).

Phân nhóm

• Test Set 1 (Visible Verdict): các ràng buộc như trên.

Ví dụ

Công cụ kiểm thử

Kho bài gốc cung cấp công cụ để kiểm thử cục bộ hoặc trên nền tảng Code Jam. Khi chạy cục bộ, cần chạy công cụ song song với lời giải, chẳng hạn qua interactive runner. Hướng dẫn sử dụng nằm trong phần chú thích của công cụ; bạn được khuyến khích tự thêm bộ dữ liệu.

Công cụ chỉ mô phỏng hệ thống chấm, không phải hệ thống chấm thật và có thể hành xử khác. Việc vượt qua công cụ không bảo đảm vượt qua bộ chấm. Bản chuyển thể LQDOJ dùng interactor đi kèm gói bài thay cho công cụ tải xuống này.

Nguồn

Google Code Jam 2021, Vòng 2, bài Minimum Sort.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Tác phẩm mới nhất của Cody-Jamal là một sàn bếp lát gạch có thể đổi sang nhiều hoa văn. Sàn là ma trận \(R\) hàng, \(C\) cột các viên gạch vuông. Mỗi viên có thể lật: một mặt màu magenta (M), mặt kia màu xanh (G).

Có hai thao tác:

• lật một viên, đổi màu nhìn thấy từ magenta sang xanh hoặc ngược lại;
• hoán đổi hai viên kề cạnh theo ngang hoặc dọc, không theo đường chéo, mà không lật chúng.

Xem sàn miễn phí, nhưng thao tác thì không: một lần lật tốn \(F\) xu, một lần đổi chỗ tốn \(S\) xu. Bạn biết trạng thái hiện tại và hoa văn đích. Cần ít nhất bao nhiêu xu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Dòng đầu mỗi bộ chứa \(R,C,F,S\). Tiếp theo là \(2R\) dòng, mỗi dòng \(C\) ký tự. \(R\) dòng đầu là trạng thái hiện tại; \(R\) dòng cuối là trạng thái mong muốn. Ký tự M nghĩa là mặt magenta đang hiện, G nghĩa là mặt xanh.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(y\) là số xu ít nhất để biến trạng thái hiện tại thành trạng thái đích.

Ràng buộc

• \(1\le T\le100\); \(1\le R,C\le10\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(F=S=1\).
• Test Set 2 (Hidden Verdict): \(1\le F,S\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2 4 1 1
MGMG
MMMG
GMGM
MMMM
3 3 1 1
MGG
GMG
MMM
MMM
MGM
MMG

Case #1: 3
Case #2: 4

Ví dụ bổ sung — Test Set 2

??? "Giải thích"
    Ví dụ này không được chạy trên lời giải nộp.

    !!! question "Ví dụ 2"
        ???+ "Input"
            ```sample
            1
            1 5 1000 1
            MGGGG
            GGGMM
            ```
        ???+ success "Output"
            ```sample
            Case #1: 1003
            ```
        ??? "Giải thích"
            Lật rất đắt nên phải tránh tối đa. Tuy nhiên, đích có nhiều ô magenta hơn hiện tại nên cần ít nhất một lần lật, vì đổi chỗ không thay đổi số lượng. Cách tối ưu: đổi hai ô trái nhất; lật ô phải nhất; đổi ô thứ hai và ba từ trái; đổi ô thứ ba và tư từ trái.

            ![Năm trạng thái sàn của mẫu Test Set 2](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_00c0feba.png)

Nguồn

Google Code Jam 2021, Vòng 2, bài Retiling.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.