Tôi đã viết một số chính phương lớn ở hệ nhị phân, sau đó thay thế một số chữ số bằng các dấu chấm hỏi. Bạn có thể tìm ra số ban đầu của tôi là gì không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ trên một dòng. Mỗi dòng chứa \(S\): một số chính phương được viết ở hệ nhị phân, nhưng có một số chữ số bị thay thế bởi dấu chấm hỏi.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(N\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(N\) là một số chính phương viết ở hệ nhị phân, thu được bằng cách thay thế mỗi ký tự '?' trong \(S\) bằng ký tự '0' hoặc '1'.

Ràng buộc

• \(1 \le T \le 25\).
• \(S\) bắt đầu bằng '1'.
• \(S\) chỉ chứa các ký tự '0', '1', và '?'.
• Trong mọi bộ test, luôn có đúng một lựa chọn duy nhất cho \(N\).

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(S\) có độ dài tối đa 60 ký tự.
  • \(S\) chứa tối đa 20 ký tự '?'.

• Large dataset (Test set 2 - Hidden):

  • \(S\) có độ dài tối đa 125 ký tự.
  • \(S\) chứa tối đa 40 ký tự '?'.

Đ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
1???
1
10??110??00??1000??

Case #1: 1001
Case #2: 1
Case #3: 1011110110000100001

Nguồn

Google Code Jam 2011, Vòng 3, bài Mystery Square.

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