JOI 2011 Representative Selection - Ngày 2 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2011 - Guess Them All	100 (p)	2.0s	64M
2	JOI 2011 - Keycards	100 (p)	1.0s	64M
3	JOI 2011 - Shiritori	100 (p)	5.0s	64M

1. JOI 2011 - Guess Them All

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Bạn đang chơi trò đoán số với JOI-chan. Trước tiên, JOI-chan sắp xếp mỗi số nguyên từ \(1\) đến \(N\) đúng một lần theo một thứ tự nào đó để tạo thành một dãy số. Gọi dãy này là đáp án. Bạn được thực hiện nhiều nhất \(L\) lần dự đoán; bạn thắng nếu đoán đúng đáp án trong không quá \(L\) lần.

Trong mỗi lần dự đoán, bạn đưa cho JOI-chan một dãy gồm \(N\) số nguyên từ \(1\) đến \(N\). Dãy dự đoán được phép chứa các số nguyên trùng nhau. Sau mỗi lần dự đoán, bạn được biết có bao nhiêu vị trí mà dãy dự đoán trùng với đáp án.

Yêu cầu

Hãy viết chương trình đoán đúng dãy đáp án trong số lần dự đoán cho phép. Đây là bài toán tương tác: chương trình trao đổi với hệ thống chấm qua đầu vào chuẩn và đầu ra chuẩn.

Dữ liệu vào

Khi bắt đầu, đọc một dòng từ đầu vào chuẩn chứa số nguyên \(N\).

Giới hạn \(L\) được quy định trong phần Phân nhóm; đầu vào ban đầu chỉ chứa \(N\). Các dữ liệu nhận được sau đó là phản hồi cho từng dự đoán, theo giao thức dưới đây.

Dữ liệu ra

Các dự đoán được gửi qua đầu ra chuẩn theo giao thức dưới đây.

Giao thức tương tác

Sau khi đọc \(N\), chương trình phải luân phiên gửi một dự đoán ra đầu ra chuẩn và đọc một phản hồi từ đầu vào chuẩn:

Để gửi một dự đoán, in đúng \(N\) dòng. Dòng thứ \(i\) chứa số nguyên thứ \(i\) của dãy dự đoán. Mọi số được in phải nằm trong đoạn từ \(1\) đến \(N\); các số trong cùng một dự đoán có thể trùng nhau. Một dự đoán chỉ gồm \(N\) số này, mỗi số trên một dòng, không có ký hiệu lệnh hay tiền tố khác.
Sau khi gửi dự đoán, đọc một dòng chứa một số nguyên: số vị trí mà dãy vừa dự đoán trùng với đáp án.
Nếu phản hồi bằng \(N\), bạn đã đoán đúng. Chương trình phải kết thúc ngay tại thời điểm đó và không được in thêm bất kỳ nội dung nào. Nếu chưa đoán đúng, có thể tiếp tục dự đoán, nhưng tổng số lần dự đoán không được vượt quá \(L\).

Để tránh việc đọc đầu vào bị chặn do dữ liệu đầu ra còn nằm trong bộ đệm, cần đẩy dữ liệu đầu ra trước khi chờ phản hồi. Gọi fflush(stdout); hoặc thực hiện thao tác tương đương trước khi đọc.

Đoạn chương trình C sau minh họa cách trao đổi với hệ thống chấm:

#include <stdio.h>
int main(void) {
    int i, N, ret;
    scanf("%d", &N);
    for (;;) {
        for (i = 1; i <= N; i++) {
            printf("%d\n", i);     // Gui du doan
        }
        fflush(stdout);           // Day dau ra truoc khi doc phan hoi
        scanf("%d", &ret);         // Doc phan hoi cua he thong cham
        if (ret == N) break;
    }
    return 0;
}

Đây là chương trình minh họa giao tiếp; nó lặp lại dự đoán \(1,2,\ldots,N\).

Ràng buộc

Đáp án là một hoán vị của các số nguyên \(1,2,\ldots,N\).
Mỗi dự đoán gồm đúng \(N\) số nguyên trong đoạn \([1,N]\), không nhất thiết là một hoán vị.
Độ dài \(N\) và giới hạn số lần dự đoán \(L\) tuân theo các nhóm bên dưới.
Với mọi bộ dữ liệu chấm, nếu dùng thuật toán thích hợp thì có thể đoán đúng trong không quá \(L\) lần, bất kể đáp án là hoán vị nào của các số nguyên từ \(1\) đến \(N\).
Giới hạn thời gian CPU: \(2\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(1\le N\le7\) và \(L=6000\).
Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(1\le N\le50\) và \(L=3000\).
Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(1\le N\le100\) và \(L=1000\).
Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(1\le N\le100\) và \(L=700\).

Ví dụ giao tiếp

Cột Input là dữ liệu hệ thống chấm gửi cho chương trình; cột Output là dữ liệu chương trình gửi cho hệ thống chấm. Mỗi số nằm trên một dòng riêng. Các nhãn cột chỉ dùng để trình bày, không thuộc dữ liệu giao tiếp.

Ví dụ 1

Input

Output

Trong ví dụ này, chương trình đọc \(N=3\), rồi lần lượt dự đoán \((3,2,1)\), \((1,2,3)\) và \((2,3,1)\). Các phản hồi tương ứng là \(1\), \(0\) và \(3\). Chương trình đoán đúng sau \(3\) lần dự đoán và kết thúc khi nhận được phản hồi cuối cùng.

2. JOI 2011 - Keycards

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Chìa khóa phòng ở khu lưu trú của cơ sở tổ chức trại xuân JOI là những tấm thẻ có đục lỗ. Có \(N\) vị trí có thể đục lỗ. Người ta đã tạo ra \(2^N\) chiếc chìa khóa khác nhau, tương ứng với tất cả các cách chọn những vị trí được đục lỗ.

Bạn nhận được một tập gồm từ \(1\) đến \(2^N\) chiếc chìa khóa để dùng trong trại xuân JOI. Khi xếp chồng các thẻ sao cho các vị trí có thể đục lỗ trùng nhau, bạn nhận thấy có đúng \(K\) vị trí mà tất cả các thẻ nhận được đều có lỗ.

Yêu cầu

Có bao nhiêu cách chọn tập chìa khóa nhận được để điều này xảy ra? Cho \(N\) và \(K\), hãy tính số cách đó lấy phần dư khi chia cho \(1\,000\,000\,007\), là một số nguyên tố.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số cách chọn tập chìa khóa thỏa mãn điều kiện, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

\(1\le N\le1\,000\,000\): số vị trí có thể đục lỗ.
\(0\le K\le N\): số vị trí mà tất cả các chìa khóa nhận được đều có lỗ.
Giới hạn thời gian CPU: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(2\) bộ dữ liệu, mỗi bộ \(5\) điểm, và \(9\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỉ lệ sau là tỉ lệ tích lũy:

Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le10\).
Các bộ dữ liệu chiếm \(70\%\) tổng số điểm thỏa mãn \(N\le1000\).

Ví dụ

Ví dụ 1

Input

3 3

Output

Giải thích

Khi \(N=3\), có tất cả \(8\) chiếc chìa khóa. Ta đặt tên cho chúng theo hình dưới đây; cột bên trái mô tả các lỗ trên thẻ, cột bên phải là tên thẻ.

Thẻ không có lỗ được ký hiệu là \(\phi\); ba thẻ có một lỗ được gọi là \(A\), \(B\), \(C\); các thẻ có hai lỗ là \(AB\), \(BC\), \(AC\); thẻ có cả ba lỗ là \(ABC\).

Nếu chỉ nhận một thẻ \(ABC\), số vị trí mà tất cả các thẻ nhận được đều có lỗ là \(3\). Không có cách nhận thẻ nào khác cho đúng \(3\) vị trí như vậy. Do đó, chỉ có \(1\) cách thỏa mãn điều kiện.

Ví dụ 2

Input

3 2

Output

Giải thích

Nếu nhận hai thẻ \(\{AB,ABC\}\), có đúng \(2\) vị trí mà tất cả các thẻ nhận được đều có lỗ. Tương tự, các cách nhận \(\{AC,ABC\}\), \(\{BC,ABC\}\), \(\{AB\}\), \(\{AC\}\) và \(\{BC\}\) cũng có đúng \(2\) vị trí như vậy.

Ví dụ 3

Input

3 1

Output

Giải thích

Có \(30\) cách nhận thẻ thỏa mãn điều kiện, chẳng hạn \(\{A\}\), \(\{A,AB\}\), \(\{A,AC\}\), \(\{A,ABC\}\), \(\{A,AB,AC\}\), \(\{A,AB,ABC\}\), \(\{A,AC,ABC\}\), \(\{A,AB,AC,ABC\}\), \(\{AB,AC\}\) và \(\{AB,AC,ABC\}\).

Ví dụ 4

Input

3 0

Output

3. JOI 2011 - Shiritori

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Đất nước JOI sử dụng \(100\) ký tự khác nhau. Vì khó biểu diễn trực tiếp các ký tự này trên máy tính, người ta dùng cách viết thay thế sau:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

Như vậy, mỗi ký tự được biểu diễn bằng hai chữ số, với \(10\times10\) khả năng. Từ điển của đất nước JOI sắp xếp các từ theo thứ tự ký tự trong bảng này: ký tự ở hàng phía trên đứng trước; trong cùng một hàng, ký tự nằm bên trái đứng trước.

Hiện nay, trò chơi nối từ shiritori đang rất thịnh hành ở đất nước JOI. Người chơi lần lượt nói một từ bắt đầu bằng ký tự cuối cùng của từ mà người trước vừa nói. Không được dùng lại một từ đã được nói.

Yêu cầu

Một ngày nọ, bạn chơi “shiritori 5” cùng bạn bè. Ngoài các quy tắc thông thường của shiritori, trò chơi này yêu cầu mọi từ được sử dụng đều phải có đúng \(5\) ký tự. Bạn đã ghi lại trên máy tính danh sách \(N\) từ được nói, nhưng vô tình sắp xếp lại danh sách. Hãy khôi phục diễn biến của trò chơi “shiritori 5” từ danh sách đó.

Dữ liệu vào

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

Dòng đầu chứa số nguyên \(N\), là số từ.
\(N\) dòng tiếp theo, mỗi dòng chứa một từ. Mỗi từ được biểu diễn bằng một chuỗi gồm đúng \(10\) chữ số, tương ứng với \(5\) ký tự của đất nước JOI. Các từ được cho theo thứ tự xuất hiện trong từ điển và đôi một khác nhau.

Dữ liệu ra

Nếu không thể tạo thành một trò chơi “shiritori 5” sử dụng tất cả \(N\) từ đã cho, in ra đầu ra chuẩn một dòng chứa impossible.

Nếu có thể, in \(N\) từ theo thứ tự được nói, mỗi từ trên một dòng và mỗi từ được dùng đúng một lần. Nếu có nhiều thứ tự hợp lệ, chọn thứ tự theo các ưu tiên sau:

Trước hết, chọn phương án có từ thứ nhất đứng sớm nhất trong từ điển.
Nếu vẫn còn nhiều phương án, chọn phương án có từ thứ hai đứng sớm nhất trong từ điển.
Tiếp tục xét lần lượt các vị trí như vậy; nếu đến vị trí cuối cùng vẫn chưa xác định được, chọn phương án có từ thứ \(N\) đứng sớm nhất trong từ điển.

Ràng buộc

\(1\le N\le500\,000\).
Mỗi từ gồm đúng \(5\) ký tự, mỗi ký tự được biểu diễn bằng một cặp chữ số từ 00 đến 99.
Các từ đôi một khác nhau và đã được sắp theo thứ tự từ điển trong dữ liệu vào.
Giới hạn thời gian CPU: \(5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm. Các tỉ lệ dưới đây mô tả những tập dữ liệu có thể giao nhau:

Các bộ dữ liệu chiếm \(65\%\) tổng số điểm chỉ sử dụng \(20\) loại ký tự từ 00 đến 19.
Các bộ dữ liệu chiếm \(65\%\) tổng số điểm thỏa mãn \(N\le1000\).
Các bộ dữ liệu chiếm \(40\%\) tổng số điểm vừa chỉ sử dụng các ký tự từ 00 đến 19, vừa thỏa mãn \(N\le1000\).
Các bộ dữ liệu chiếm \(90\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: chỉ sử dụng các ký tự từ 00 đến 19, hoặc \(N\le1000\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có hai thứ tự “shiritori 5” hợp lệ:

0000010201 → 0102030403 → 0308090002 → 0206070801 → 0104050603.
0000010201 → 0104050603 → 0308090002 → 0206070801 → 0102030403.

Từ thứ nhất giống nhau. Khi so sánh từ thứ hai theo thứ tự từ điển, phương án đầu tiên được chọn để in ra.

Ví dụ 2

Input

Output

impossible

Giải thích

Không tồn tại thứ tự “shiritori 5” hợp lệ cho ví dụ này.

Ví dụ 3

Input

Output