Google Code Jam 2014 - Round 1B

Xổ số đang thay đổi! Trước đây, Xổ số sử dụng một máy để tạo ra một số trúng thưởng ngẫu nhiên. Nhưng do các vấn đề gian lận, Xổ số đã quyết định thêm một máy nữa. Số trúng thưởng mới sẽ là kết quả của phép toán bitwise-AND giữa hai số ngẫu nhiên được tạo ra bởi hai máy.

Để tìm bitwise-AND của \(X\) và \(Y\), hãy viết cả hai ở dạng nhị phân; khi đó một bit trong kết quả nhị phân là \(1\) nếu các bit tương ứng của \(X\) và \(Y\) đều là \(1\), và bằng \(0\) nếu ngược lại. Trong hầu hết các ngôn ngữ lập trình, phép bitwise-AND của \(X\) và \(Y\) được viết là X & Y.

Ví dụ:

• Máy cũ tạo ra số \(7 = 0111_2\).
• Máy mới tạo ra số \(11 = 1011_2\).
• Số trúng thưởng sẽ là \((7 \text{ AND } 11) = (0111_2 \text{ AND } 1011_2) = 0011_2 = 3\).

Với biện pháp này, Xổ số hy vọng sẽ giảm bớt các trường hợp khiếu nại gian lận, nhưng không may một nhân viên từ công ty Xổ số đã rò rỉ thông tin sau: máy cũ sẽ luôn tạo ra một số nguyên không âm nhỏ hơn \(A\) và máy mới sẽ luôn tạo ra một số nguyên không âm nhỏ hơn \(B\).

Catalina muốn thắng giải xổ số này và để thử vận may, cô ấy quyết định mua tất cả các số nguyên không âm nhỏ hơn \(K\).

Cho \(A\), \(B\) và \(K\), Catalina muốn biết có bao nhiêu cách khác nhau mà các máy có thể tạo ra một cặp số để giúp cô ấy trở thành người chiến thắng.

Bạn có thể giúp cô ấy 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\) dòng tiếp theo, mỗi dòng chứa ba số \(A\), \(B\) và \(K\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng cặp số khả thi mà các máy có thể tạo ra để Catalina thắng cuộc.

Ràng buộc

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

Phân nhóm

• Small dataset:

  • \(1 \le A \le 1000\).
  • \(1 \le B \le 1000\).
  • \(1 \le K \le 1000\).

  • Large dataset:

  • \(1 \le A \le 10^9\).

  • \(1 \le B \le 10^9\).
  • \(1 \le K \le 10^9\).

Đ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ụ

5
3 4 2
4 5 2
7 8 5
45 56 35
103 143 88

Case #1: 10
Case #2: 16
Case #3: 52
Case #4: 2411
Case #5: 14377

Nguồn

Google Code Jam 2014, Vòng 1B, bài New Lottery Game.

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

Sếp của bạn đang cử bạn đi một chuyến công tác bán hàng quốc tế. Thật là vui mừng!

Bạn có \(N\) thành phố (được đánh số từ \(1\) đến \(N\)) cần ghé thăm và có thể di chuyển giữa chúng bằng một tập hợp các chuyến bay khứ hồi giữa các thành phố.

Tất cả các thành phố phải được ghé thăm ít nhất một lần. Để làm điều này, bạn có thể đặt bất kỳ số lượng vé nào, tuân theo các điều kiện sau:

• Mỗi vé bao gồm 2 chuyến bay, một chuyến từ thành phố \(X\) cụ thể đến một thành phố \(Y\) cụ thể khác (gọi là chuyến bay đi), và chuyến còn lại từ thành phố \(Y\) về thành phố \(X\) (gọi là chuyến bay về).
• Bạn phải sử dụng chuyến bay đi trước chuyến bay về tương ứng (bạn có thể sử dụng các chuyến bay khác ở giữa).
• Có tối đa 1 chuyến bay đi đến mỗi thành phố, mặc dù không có giới hạn về các chuyến bay về (nhiều chuyến bay về có thể đi đến cùng một thành phố).
• Bạn phải sử dụng tất cả các chuyến bay thuộc về các vé mà bạn đã đặt.
• Ngoài ra, bạn có thể ghé thăm các thành phố theo bất kỳ thứ tự nào bạn muốn.
• Bạn có thể bắt đầu chuyến hành trình từ bất kỳ thành phố nào bạn chọn. Bạn không được thực hiện chuyến bay đi đến thành phố xuất phát của mình.

Bây giờ bạn có thể cố gắng giảm thiểu tổng quãng đường di chuyển, nhưng bạn đã làm điều đó lần trước rồi, nên việc đó sẽ rất nhàm chán. Thay vào đó, bạn nhận thấy rằng mỗi thành phố có một mã bưu chính (ZIP code) gồm 5 chữ số riêng biệt. Khi bạn ghé thăm một thành phố lần đầu tiên (bao gồm cả thành phố bạn bắt đầu), bạn viết mã ZIP đó xuống và nối chúng thành một số lớn (nối theo thứ tự bạn ghé thăm mỗi thành phố lần đầu tiên). Số nhỏ nhất bạn có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo.
Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa hai số nguyên: số lượng thành phố \(N\) và số lượng chuyến bay khứ hồi có thể có \(M\).
\(N\) dòng tiếp theo, với dòng thứ \(i\) chứa mã ZIP gồm 5 chữ số của thành phố thứ \(i\). Không có mã ZIP nào có số 0 ở đầu và tất cả các mã ZIP trong mỗi bộ thử nghiệm là khác nhau.
\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i < j \le N\)) cho biết có một chuyến bay khứ hồi tồn tại giữa thành phố thứ \(i\) và thành phố thứ \(j\). Tất cả các chuyến bay sẽ khác nhau trong mỗi bộ thử nghiệm.

Đảm bảo rằng bạn có thể ghé thăm mọi thành phố theo các quy tắc trên.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số nhỏ nhất bạn có thể đạt được bằng cách nối các mã ZIP dọc theo chuyến đi của mình.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le M \le N \times (N - 1) / 2\).

Phân nhóm

• Small dataset: \(1 \le N \le 8\).
• Large dataset: \(1 \le N \le 50\).

Đ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ụ

4
3 2
10001
20000
10000
1 2
2 3
5 4
36642
28444
50012
29651
10953
1 4
2 3
2 5
4 5
5 5
36642
28444
50012
29651
10953
1 2
1 4
2 3
2 5
4 5
6 6
10001
10002
10003
10004
10005
10006
1 2
1 6
2 3
2 4
3 5
4 5

Case #1: 100002000010001
Case #2: 1095328444500122965136642
Case #3: 1095328444366422965150012
Case #4: 100011000210003100041000510006

Nguồn

Google Code Jam 2014, Vòng 1B, bài The Bored Traveling Salesman.

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

Fegla và Omar rất thích chơi trò chơi mỗi ngày. Nhưng giờ họ đã chán tất cả các trò chơi cũ và muốn chơi một trò chơi mới. Vì vậy, họ quyết định tự sáng tạo ra trò chơi của riêng mình mang tên "The Repeater" (Người lặp lại).

Họ đã phát minh ra một trò chơi dành cho 2 người. Fegla viết xuống \(N\) chuỗi ký tự. Nhiệm vụ của Omar là làm cho tất cả các chuỗi này trở nên giống hệt nhau, nếu có thể, bằng cách sử dụng số lượng thao tác ít nhất (có thể là 0 thao tác) thuộc hai loại sau:

• Chọn bất kỳ ký tự nào trong bất kỳ chuỗi nào và lặp lại nó (thêm một bản sao của ký tự này ngay sau nó). Ví dụ, trong một bước di chuyển, Omar có thể thay đổi "abc" thành "abbc" (bằng cách lặp lại ký tự 'b').
• Chọn bất kỳ hai ký tự kề nhau và giống hệt nhau trong bất kỳ chuỗi nào, và xóa một trong số chúng. Ví dụ, trong một bước di chuyển, Omar có thể thay đổi "abbc" thành "abc" (xóa một trong các ký tự 'b'), nhưng không thể biến nó thành "bbc".

Hai loại thao tác này là độc lập; không nhất thiết một thao tác loại thứ nhất phải được theo sau bởi một thao tác loại thứ hai (hoặc ngược lại).

Hãy giúp Omar thắng trò chơi này bằng cách viết một chương trình để tìm xem có thể làm cho các chuỗi đã cho trở nên giống hệt nhau hay không, và tìm số bước di chuyển tối thiểu nếu có thể.

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\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\) là số lượng các chuỗi. Tiếp theo là \(N\) dòng, mỗi dòng chứa một chuỗi không rỗng (mỗi chuỗi sẽ chỉ bao gồm các ký tự tiếng Anh viết thường, từ 'a' đến 'z').

Dữ liệu ra

Với mỗi bộ test, hãy in ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số bước di chuyển tối thiểu để làm cho các chuỗi giống hệt nhau. Nếu không có cách nào để làm cho tất cả các chuỗi giống hệt nhau, hãy in "Fegla Won" (trong ngoặc kép để cho rõ ràng).

Ràng buộc

\(1 \le T \le 100\).
\(1 \le\) độ dài của mỗi chuỗi \(\le 100\).

Phân nhóm

• Small dataset: \(N = 2\).
• Large dataset: \(2 \le N \le 100\).

Đ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ụ

5
2
mmaw
maw
2
gcj
cj
3
aaabbb
ab
aabb
2
abc
abc
3
aabc
abbc
abcc

Case #1: 1
Case #2: Fegla Won
Case #3: 4
Case #4: 0
Case #5: 3

Nguồn

Google Code Jam 2014, Vòng 1B, bài The Repeater.

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