Blue và Orange là những chú rô-bốt thân thiện. Một kẻ chủ mưu máy tính độc ác đã nhốt chúng vào các hành lang riêng biệt để kiểm tra chúng, và sau đó có thể sẽ cho chúng ăn bánh.

Mỗi hành lang có 100 nút bấm được đánh số bằng các số nguyên dương \(\{1, 2, \dots, 100\}\). Nút \(k\) luôn cách điểm bắt đầu của hành lang \(k\) mét, và cả hai rô-bốt đều bắt đầu tại nút 1. Trong khoảng thời gian một giây, một rô-bốt có thể đi bộ một mét theo bất kỳ hướng nào, hoặc nó có thể nhấn nút tại vị trí của mình một lần, hoặc nó có thể đứng yên tại vị trí của mình và không nhấn nút. Để hoàn thành bài kiểm tra, các rô-bốt cần nhấn một dãy nút nhất định theo một thứ tự nhất định. Cả hai rô-bốt đều biết toàn bộ dãy nút trước. Chúng có thể hoàn thành bài kiểm tra nhanh nhất là bao lâu?

Ví dụ, hãy xem xét dãy nút sau:
O 2, B 1, B 2, O 4

Ở đây, O 2 nghĩa là nút 2 trong hành lang của Orange, B 1 nghĩa là nút 1 trong hành lang của Blue, và tương tự. Các rô-bốt có thể nhấn dãy nút này trong 6 giây bằng chiến lược dưới đây:

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

Lưu ý rằng Blue phải đợi cho đến khi Orange nhấn xong nút O 2 trước khi nó có thể bắt đầu nhấn nút B 1.

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 bao gồm một dòng duy nhất bắt đầu bằng một số nguyên dương \(N\), đại diện cho số lượng nút cần nhấn. Tiếp theo là \(N\) cụm có dạng "\(R_i\) \(P_i\)" trong đó \(R_i\) là màu của rô-bốt (luôn là 'O' hoặc 'B'), và \(P_i\) là vị trí của nút bấm.

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ố giây tối thiểu cần thiết để các rô-bốt nhấn các nút đã cho theo đúng thứ tự.

Ràng buộc

\(1 \le P_i \le 100\) với mọi \(i\).

Phân nhóm

• Small dataset (Test set 1 - Visible):
  \(1 \le T \le 20\).
  \(1 \le N \le 10\).

• Large dataset (Test set 2 - Hidden):
  \(1 \le T \le 100\).
  \(1 \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ụ

3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

Case #1: 6
Case #2: 100
Case #3: 4

Nguồn

Google Code Jam 2011, Vòng loại, bài Bot Trust.

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

Sean và Patrick là hai anh em vừa được bố mẹ cho một túi kẹo ngon. Mỗi viên kẹo có một giá trị nguyên dương. Hai anh em muốn chia số kẹo này cho nhau. Trước tiên, Sean sẽ chia kẹo thành hai đống và chọn một đống để đưa cho Patrick. Sau đó Patrick sẽ cố tính giá trị của mỗi đống, trong đó giá trị của một đống là tổng giá trị của tất cả các viên kẹo trong đống ấy. Nếu Patrick cho rằng hai đống không có giá trị bằng nhau, cậu bé sẽ khóc.

Đáng tiếc, Patrick còn rất nhỏ và chưa biết cộng đúng cách. Cậu gần như biết cộng các số nhị phân, nhưng khi cộng hai bit 1, cậu luôn quên nhớ sang bit tiếp theo. Chẳng hạn, khi muốn cộng 12 (1100 trong hệ nhị phân) và 5 (101 trong hệ nhị phân), cậu cộng đúng hai bit ngoài cùng bên phải, nhưng ở bit thứ ba lại quên nhớ sang bit kế tiếp:

  1100

+ 0101
------
  1001

Vì vậy, sau khi cộng bit cuối cùng mà không có phần nhớ từ bit thứ ba, kết quả cuối cùng là 9 (1001 trong hệ nhị phân). Sau đây là một số ví dụ khác về khả năng tính toán của Patrick:

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Sean cộng rất giỏi và muốn lấy tổng giá trị lớn nhất có thể mà không làm em trai khóc. Nếu có thể, cậu sẽ chia túi kẹo thành hai đống không rỗng sao cho Patrick nghĩ rằng chúng có cùng giá trị. Với giá trị của tất cả các viên kẹo trong túi, hãy xác định việc chia như vậy có thể thực hiện được hay không; nếu có, hãy tìm giá trị lớn nhất có thể của đống kẹo thuộc về Sean.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test được mô tả bằng hai dòng. Dòng đầu chứa một số nguyên \(N\), là số viên kẹo trong túi. Dòng tiếp theo chứa \(N\) số nguyên \(C_i\), cách nhau bởi một dấu cách, là giá trị của từng viên kẹo.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1). Nếu Sean không thể ngăn Patrick khóc, y phải là từ NO. Ngược lại, y là giá trị của đống kẹo mà Sean sẽ giữ.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le C_i \le 10^6\).

Phân nhóm

• Test Set 1 (Nhìn thấy): \(2 \le N \le 15\).
• Test Set 2 (Ẩn): \(2 \le N \le 1000\).

Đ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
5
1 2 3 4 5
3
3 5 6

Case #1: NO
Case #2: 11

Nguồn

Google Code Jam 2011, Vòng loại, bài Candy Splitting.

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

GoroSort

Đề bài

Goro có 4 cánh tay. Goro rất khỏe. Bạn không nên gây sự với Goro. Goro cần sắp xếp một mảng gồm \(N\) số nguyên khác nhau. Thuật toán không phải là thế mạnh của Goro; sức mạnh mới là thế mạnh của Goro. Kế hoạch của Goro là sử dụng các ngón tay trên hai bàn tay của mình để giữ chặt một vài phần tử của mảng và đấm vào bàn bằng nắm đấm thứ ba và thứ tư mạnh nhất có thể. Điều này sẽ làm cho các phần tử không được giữ chặt bay lên không trung, bị xáo trộn ngẫu nhiên và rơi trở lại các vị trí trống trong mảng.

Goro muốn sắp xếp mảng nhanh nhất có thể. Trung bình sẽ mất bao nhiêu lần đấm để Goro sắp xếp mảng đã cho, nếu anh ta hành động thông minh khi chọn phần tử nào của mảng để giữ chặt trước mỗi lần đấm vào bàn? Goro có vô số ngón tay trên hai bàn tay mà anh ta dùng để giữ mảng.

Chính xác hơn, trước mỗi lần đấm, Goro có thể chọn bất kỳ tập con nào của các phần tử trong mảng để giữ cố định tại chỗ. Anh ta có thể chọn khác nhau tùy thuộc vào kết quả của các lần đấm trước đó. Mỗi lần đấm sẽ hoán vị các phần tử không được giữ một cách ngẫu nhiên đồng nhất. Mỗi hoán vị đều có khả năng xảy ra như nhau.

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ộ test gồm hai dòng. Dòng đầu tiên cho biết số \(N\). Dòng thứ hai liệt kê \(N\) phần tử của mảng theo thứ tự ban đầu của chúng.

Dữ liệu ra

Đối 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ần đấm bàn kỳ vọng khi thực hiện chiến lược giữ phần tử tối ưu nhất. Các câu trả lời có sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le T \le 100\);
• Dòng thứ hai của mỗi bộ test sẽ chứa một hoán vị của \(N\) số nguyên dương nhỏ nhất.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 10\).
• Test set 2 (Hidden): \(1 \le N \le 1000\).

Đ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
2
2 1
3
1 3 2
4
2 1 4 3

Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

Nguồn

Google Code Jam 2011, Vòng loại, bài GoroSort.

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

Giới thiệu

Magicka™ là một trò chơi hành động phiêu lưu được phát triển bởi Arrowhead Game Studios. Trong Magicka, bạn đóng vai một pháp sư, triệu hồi và kết hợp các nguyên tố để tạo ra các phép thuật (Magicks). Bài toán này có ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi Magicka.

Lưu ý: "triệu hồi" (invoke) ở đây là một thuật ngữ kỹ thuật trong bài toán này, bạn không cần quan tâm đến nghĩa tiếng Anh thông thường của nó.

Đề bài

Là một pháp sư, bạn có thể triệu hồi tám nguyên tố, gọi là các nguyên tố "cơ bản". Mỗi nguyên tố cơ bản là một ký tự duy nhất từ tập {Q, W, E, R, A, S, D, F}. Khi bạn triệu hồi một nguyên tố, nó sẽ được thêm vào cuối danh sách nguyên tố của bạn. Ví dụ: nếu bạn triệu hồi W rồi sau đó triệu hồi A (gọi tắt là "triệu hồi WA"), danh sách nguyên tố của bạn sẽ là [W, A].

Chúng tôi sẽ chỉ định các cặp nguyên tố cơ bản có thể kết hợp để tạo thành các nguyên tố không cơ bản (18 chữ cái in hoa còn lại). Ví dụ, Q và F có thể kết hợp để tạo thành T. Nếu hai nguyên tố trong một cặp xuất hiện ở cuối danh sách nguyên tố, thì cả hai nguyên tố đó sẽ ngay lập tức bị xóa bỏ và được thay thế bằng nguyên tố mà chúng tạo thành. Trong ví dụ trên, nếu danh sách nguyên tố là [A, Q, F] hoặc [A, F, Q] tại bất kỳ thời điểm nào, nó sẽ trở thành [A, T].

Chúng tôi cũng sẽ chỉ định các cặp nguyên tố cơ bản xung khắc với nhau. Sau khi bạn triệu hồi một nguyên tố, nếu nó không được kết hợp ngay lập tức để tạo thành nguyên tố khác, và nó xung khắc với một nguyên tố nào đó đã có trong danh sách nguyên tố, thì toàn bộ danh sách nguyên tố của bạn sẽ bị xóa sạch.

Ví dụ, giả sử Q và F kết hợp tạo thành T. R và F xung khắc với nhau. Khi đó, việc triệu hồi các chuỗi sau (theo thứ tự từ trái sang phải) sẽ có kết quả như sau:

• QF → [T] (Q và F kết hợp thành T)
• QEF → [Q, E, F] (Q và F không thể kết hợp vì chúng không bao giờ cùng nằm ở cuối danh sách)
• RFE → [E] (F và R xung khắc, nên danh sách bị xóa; sau đó E được triệu hồi)
• REF → [] (F và R xung khắc, nên danh sách bị xóa)
• RQF → [R, T] (QF kết hợp thành T, nên danh sách không bị xóa)
• RFQ → [Q] (F và R xung khắc, nên danh sách bị xóa)

Cho một danh sách các nguyên tố cần triệu hồi, danh sách nguyên tố cuối cùng sẽ là gì?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) bộ dữ liệu tiếp theo. Mỗi bộ dữ liệu nằm trên một dòng duy nhất, chứa các thành phần sau cách nhau bởi dấu cách:

Đầu tiên là một số nguyên \(C\), tiếp theo là \(C\) chuỗi, mỗi chuỗi chứa ba ký tự: hai nguyên tố cơ bản theo sau là một nguyên tố không cơ bản. Điều này cho biết hai nguyên tố cơ bản đó kết hợp tạo thành nguyên tố không cơ bản. Tiếp theo là một số nguyên \(D\), tiếp theo là \(D\) chuỗi, mỗi chuỗi chứa hai ký tự: hai nguyên tố cơ bản xung khắc với nhau. Cuối cùng là một số nguyên \(N\), tiếp theo là một chuỗi duy nhất chứa \(N\) ký tự: chuỗi các nguyên tố cơ bản mà bạn cần triệu hồi. Bạn sẽ triệu hồi chúng theo thứ tự xuất hiện trong chuỗi (ký tự ngoài cùng bên trái trước, v.v.), từng cái một.

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ dữ liệu (bắt đầu từ 1) và y là một danh sách theo định dạng "[e\(_0\), e\(_1\), ...]" trong đó e\(_i\) là nguyên tố thứ \(i\) của danh sách nguyên tố cuối cùng. Vui lòng xem ví dụ để biết định dạng cụ thể.

Ràng buộc

• \(1 \le T \le 100\).
• Mỗi cặp nguyên tố cơ bản chỉ có thể xuất hiện cùng nhau trong tối đa một quy tắc kết hợp, mặc dù chúng có thể vừa nằm trong một quy tắc kết hợp vừa xung khắc với nhau.
• Không có nguyên tố cơ bản nào xung khắc với chính nó.
• Khác với trò chơi Magicka, không có giới hạn về độ dài của danh sách nguyên tố.

Phân nhóm

• Test set 1 (Visible): \(0 \le C \le 1\), \(0 \le D \le 1\), \(1 \le N \le 10\).
• Test set 2 (Hidden): \(0 \le C \le 36\), \(0 \le D \le 28\), \(1 \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
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW

Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

Nguồn

Google Code Jam 2011, Vòng loại, bài Magicka.

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