COCI 2019/2020 - Olympiad - Zagrade

View as PDF

Submit solution

Points: 1.10 (partial)
Time limit: 4.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Olympiad
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cơ quan Tình báo Trung ương Hoa Kỳ (CIA) có nhiệm vụ thu thập, xử lí và phân tích các thông tin tình báo có ảnh hưởng tới an ninh quốc gia. CIA cũng bị nghi ngờ rằng họ sở hữu một bộ sưu tập khá lớn các mật khẩu máy tính thường được sử dụng và đang phát triển các phần mềm khá phức tập với khả năng xâm nhập các hệ thống máy tính được bảo vệ bằng mật khẩu.

Tuy nhiên, tình thế đã đảo ngược, nhiệm vụ của bạn bây giờ là xâm nhập hệ thống bảo mật của CIA. Chúc may mắn!

Dĩ nhiên, họ biết rõ các dạng mật khẩu thường thấy do con người tạo ra, vậy nên các lượt thử mật khẩu như 123456, password, 1q2w3e4r hay welcome là vô ích. May mắn thay, chúng tôi đã phát hiện một số thông tin mà bạn có thể sử dụng.

Cụ thể hơn, mật khẩu máy chủ CIA gồm đúng ~N~ kí tự, với ~N~ là một số chẵn. Chính xác một nửa các kí tự đó là kí tự mở ngoặc (, và nửa còn lại là kí tự đóng ngoặc ). Hơn nữa, thay vì chức năng Quên mật khẩu? thông thường, các kĩ sư đã quyết định để lộ một chương trình cho quản lý hay quên của họ có thể nhớ lại mật khẩu. Sử dụng chương trình này, người quản lý có thể thực hiện tối đa ~Q~ truy vấn hỏi liệu đoạn mật khẩu từ kí tự thứ ~a~ đến kí tự thứ ~b~ có hợp lệ hay không.

Nhiệm vụ của bạn là lợi dụng chương trình này để truy ra mật khẩu bí mật của máy chủ CIA.

Sự hợp lệ của một dãy ngoặc được định nghĩa một cách quy nạp như sau:

  • () là một dãy ngoặc hợp lệ.
  • Nếu A là một dãy ngoặc hợp lệ, thì (A) cũng là một dãy ngoặc hợp lệ.
  • Nếu AB đều là các dãy ngoặc hợp lệ, thì AB cũng là một dãy ngoặc hợp lệ.

Interaction

Đây là một bài toán tương tác. Chương trình của bạn phải tương tác với chương trình của tác giả mô phỏng chức năng của một máy chủ CIA ảo từ đề bài.

Trước khi tương tác, chương trình của bạn phải đọc một số nguyên chẵn ~N~ và một số nguyên ~Q~ từ đầu vào chuẩn. Ý nghĩa của hai số nguyên này đã được miêu tả trong đề bài.

Sau đó, chương trình của bạn có thể gửi các truy vấn bằng cách in ra đầu ra chuẩn. Mỗi truy vấn phải được in trên một dòng riêng biệt và có dạng ~?\,a\,b~, với ~1 \le a \le b \le N~. Sau mỗi truy vấn, chương trình của bạn phải flush output. Sau đó, chương trình sẽ trả về kết quả của truy vấn đó là ~0~ hoặc ~1~, bạn có thể lấy đáp án này bằng cách đọc đáp án từ đầu vào chuẩn. Đáp án sẽ là ~1~ nếu như đoạn mật khẩu bắt đầu từ kí tự thứ ~a~ và kết thúc ở kí tự thứ ~b~ tạo thành một dãy ngoặc hợp lệ. Nếu không, đáp án sẽ là ~0~. Chương trình của bạn được phép gửi tối đa ~Q~ truy vấn như vậy.

Sau khi chương trình của bạn đã tìm được mật khẩu bí mật, hãy in ra một dòng trong đầu ra chuẩn có dạng ~!\,\,x_1x_2 \ldots x_N~, với các kí tự ~x_1, x_2, \ldots, x_N~ thể hiện các kí tự của mật khẩu bí mật. Sau đó, chương trình của bạn phải flush output một lần nữa và kết thúc chương trình.

Note: Bạn có thể xem chương trình mẫu tương tác với máy chủ CIA một cách chính xác, bao gồm cả phần flush output ở đây.

Ví dụ tương tác

Input Output Ghi chú
6 9 Mật khẩu bí mật sẽ là ((())) với độ dài ~6~, và chương trình được hỏi tối đa ~9~ truy vấn.
? 1 6 1 Cả dãy mật khẩu hợp lệ
? 1 2 0 (( không phải là dãy ngoặc hợp lệ
? 2 4 0 (() không phải là dãy ngoặc hợp lệ
? 2 5 1 (()) là dãy ngoặc hợp lệ
? 3 4 1 () là dãy ngoặc hợp lệ
! ((())) Mật khẩu đã được tìm thấy và máy chủ của CIA đã bị xâm nhập.

Ràng buộc

  • ~8~ test đầu tiên thỏa mãn ~1 \le N \le 1\,000,\, Q = \frac{N^2}{4}~, cã dãy mật khẩu là một dãy ngoặc hợp lệ.
  • ~8~ test tiếp theo thỏa mãn ~1 \le N \le 1\,000,\, Q = \frac{N^2}{4}~.
  • ~8~ test tiếp theo thỏa mãn ~1 \le N \le 100\,000,\, Q = N - 1~, cã dãy mật khẩu là một dãy ngoặc hợp lệ.
  • ~8~ test còn lại thỏa mãn ~1 \le N \le 100\,000,\, Q = N - 1~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.