Crime House

Trong khi làm việc cho cảnh sát, bạn đã xác định được một ngôi nhà nơi mọi người đến để thực hiện các hành vi phạm tội, được gọi là Crime House. Một ngày nọ, bạn đặt một chiếc camera trước cửa nhà và ghi lại một đoạn video.

Bạn không biết có bao nhiêu người ở trong Crime House vào đầu ngày, nhưng bạn có thể thấy mọi người ra và vào qua cửa trước. Thật không may, vì những người ra vào Crime House là tội phạm, đôi khi họ đeo mặt nạ; và bạn không chắc liệu cửa trước có phải là lối ra vào duy nhất hay không.

Đôi khi bạn có thể đoán được ai là người đeo mặt nạ. Nếu tội phạm số 5 vào nhà, sau đó một người đeo mặt nạ đi ra, rồi tội phạm số 5 lại vào nhà một lần nữa, thì hoặc người đeo mặt nạ đó là tội phạm số 5, hoặc có một lối ra khác khỏi Crime House.

Vào cuối ngày, khi Crime House đã đóng cửa đêm, bạn xem lại video của mình. Vì bạn là một người lạc quan, bạn muốn tìm hiểu xem liệu có khả năng không có lối ra vào nào khác ngoài cửa trước hay không; và nếu có, bạn muốn tìm ra số lượng người tối thiểu có thể ở trong Crime House vào cuối ngày.

Dữ liệu vào

Dòng đầu tiên của dữ liệ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 một số nguyên duy nhất \(N\), số lần mọi người đi qua cửa trước của Crime House trong ngày. Tiếp theo là \(N\) dòng, mỗi dòng chứa thông tin về một người vào hoặc ra khỏi Crime House qua cửa trước.

Thông tin đó bao gồm một ký tự duy nhất, E (vào) hoặc L (ra), tiếp theo là một dấu cách và sau đó là một số nguyên id. Nếu ký tự đầu tiên là E, điều đó cho biết ai đó đã vào Crime House qua cửa trước; nếu là L, ai đó đã ra ngoài qua cửa trước. Nếu id lớn hơn 0, người có mã định danh đó đã vào hoặc ra khỏi Crime House. Nếu id bằng 0, thì người vào hoặc ra đó đang đeo mặt nạ và chúng ta không biết họ là ai.

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). Nếu có khả năng không có lối ra vào nào khác ngoài cửa trước, thì y phải là số lượng người tối thiểu có thể ở trong Crime House vào cuối ngày. Nếu điều đó là không thể, y phải là "CRIME TIME".

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le id \le 2000\).

Phân nhóm

• Small dataset: \(1 \le N \le 15\).
• Large dataset: \(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ụ

5
3
E 5
L 0
E 5
2
L 1
L 1
4
L 1
E 0
E 0
L 1
7
L 2
E 0
E 1
E 2
E 0
E 3
L 4
13
L 4
L 1
L 2
E 0
L 1
E 0
L 2
E 0
L 2
E 0
E 0
L 1
L 4

Case #1: 1
Case #2: CRIME TIME
Case #3: 1
Case #4: 4
Case #5: 0

Nguồn

Google Code Jam 2014, Vòng 3, bài Crime House.

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

Diana cần bạn giúp tối đa hóa số vàng cô ấy nhận được khi chơi trò chơi yêu thích của mình. Cô ấy thường gặp phải tình huống đứng gần trụ của mình và đối mặt với \(N\) quái vật. Khi đó, Diana và trụ thay phiên nhau bắn các quái vật, và Diana được đi trước. Trong lượt của mình, Diana có thể chọn một quái vật để bắn (điều này có nghĩa là Diana có thể chọn bỏ qua một lượt). Trong lượt của nó, trụ sẽ bắn vào quái vật gần nó nhất. Diana và trụ không thể bắn vào những quái vật đã chết.

Nếu Diana bắn vào một con quái vật, lượng máu của nó sẽ giảm đi \(P\). Nếu trụ bắn vào một con quái vật, lượng máu của nó sẽ giảm đi \(Q\). Nếu máu của quái vật giảm xuống dưới \(1\), nó sẽ bị tiêu diệt. Con quái vật thứ \(i\) bắt đầu với \(H_i\) máu. Diana được thưởng \(G_i\) vàng nếu phát bắn của cô ấy tiêu diệt được con quái vật thứ \(i\), nhưng không nhận được gì nếu phát bắn của trụ tiêu diệt nó. Số vàng tối đa mà Diana có thể nhận được là bao nhiêu?

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 theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách đại diện cho \(P\), \(Q\) và \(N\). \(N\) dòng tiếp theo, với dòng thứ \(i\) chứa hai số nguyên cách nhau bởi dấu cách đại diện cho \(H_i\) và \(G_i\).

Các quái vật được cho theo thứ tự khoảng cách của chúng so với trụ. Nói cách khác, trụ sẽ chỉ bắn vào con quái vật thứ \(i\) nếu tất cả các quái vật \(< i\) đã chết.

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ố vàng tối đa mà Diana có thể nhận được.

Ràng buộc

• \(1 \le T \le 100\)
• \(20 \le P \le 200\)
• \(20 \le Q \le 200\)
• \(1 \le H_i \le 200\)
• \(0 \le G_i \le 10^6\)

Phân nhóm

• Small dataset: \(1 \le N \le 4\).
• Large dataset: \(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ụ

2
20 40 3
100 100
20 100
60 100
20 60 3
80 100
80 200
120 300

Case #1: 300
Case #2: 500

Nguồn

Google Code Jam 2014, Vòng 3, bài Last Hit.

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

Chủ sở hữu bí ẩn của một nhà máy điện tử đã quyết định thực hiện một điều rất thú vị. Cô ấy đã giấu những chiếc bóng bán dẫn vàng bên trong bảy thiết bị điện tử, và những người mua được những thiết bị đó sẽ được mời tham gia một chuyến tham quan kỳ diệu, tuyệt vời tại nhà máy.

Arnar và Solveig đã nhận được tin báo rằng có một chiếc bóng bán dẫn vàng được giấu bên trong một thiết bị tại cửa hàng điện tử địa phương của họ. Đầu tiên, họ góp tiền cùng nhau và mua tất cả các thiết bị, sau đó đặt chúng thành một hàng thẳng, đánh số các thiết bị từ \(0\) đến \(N-1\). Mỗi thiết bị có một số lượng bóng bán dẫn nhất định. Sau đó, họ đồng ý về một chiến thuật để quyết định ai sẽ nhận được bóng bán dẫn vàng:

Đầu tiên, Arnar sẽ chọn một phạm vi \([a, b]\) (bao gồm cả hai đầu) của các thiết bị, trong đó \(0 \le a \le b < N\). Tiếp theo, Solveig sẽ chọn một tập hợp các thiết bị mà cô ấy muốn lấy:

• Nếu \(a > 0\), cô ấy có thể lấy tất cả các thiết bị trong phạm vi \([0, a-1]\).
• Nếu \(b < N-1\), cô ấy có thể lấy tất cả các thiết bị trong phạm vi \([b+1, N-1]\).
• Cô ấy luôn có thể chọn lấy tất cả các thiết bị trong phạm vi \([a, b]\).

Sau khi Solveig đã chọn một trong các tập hợp thiết bị, Arnar sẽ lấy tất cả các thiết bị mà cô ấy không lấy.

Ví dụ, nếu có 3 thiết bị và Arnar chọn phạm vi \([1, 1]\), Solveig có thể chọn lấy phạm vi \([0, 0]\), phạm vi \([1, 1]\) hoặc phạm vi \([2, 2]\). Mặt khác, nếu Arnar chọn phạm vi \([1, 2]\), thì Solveig có thể chọn lấy phạm vi \([0, 0]\) hoặc phạm vi \([1, 2]\).

Cho biết số lượng bóng bán dẫn trong mỗi thiết bị, và biết rằng Arnar và Solveig mỗi người sẽ cố gắng tối đa hóa xác suất nhận được bóng bán dẫn vàng của mình (xác suất này được tối đa hóa bằng cách lấy các thiết bị điện tử có tổng số lượng bóng bán dẫn lớn nhất), xác suất Arnar nhận được bóng bán dẫn vàng và giành chiến thắng trong chuyến tham quan kỳ diệu, tuyệt vời là bao nhiêu?

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 năm số: \(N, p, q, r\) và \(s\). Điều này cho biết có \(N\) thiết bị, và thiết bị thứ \(i\) chứa \(((i \times p + q) \pmod r + s)\) bóng bán dẫn. Hãy nhớ rằng các thiết bị được đánh số từ \(0\) đến \(N-1\).

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à xác suất giành chiến thắng của Arnar.

y sẽ được coi là chính xác nếu nó nằm trong sai số tuyệt đối hoặc tương đối là \(10^{-9}\) so với đáp án chính xác.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le p \le 10^6\).
• \(1 \le q \le 10^6\).
• \(1 \le r \le 10^6\).
• \(1 \le s \le 10^6\).

Phân nhóm

• Small dataset: \(1 \le N \le 1000\).
• Large dataset: \(1 \le N \le 10^6\).

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

8
1 1 1 1 1
10 17 1 7 1
2 100 100 200 1
20 17 3 23 100
10 999999 999999 1000000 1000000
2 1 1 1 1
3 1 99 100 1
999999 1000000 999999 1000000 1000000

Case #1: 0.0000000000
Case #2: 0.6111111111
Case #3: 0.0098039216
Case #4: 0.6471920290
Case #5: 0.6000006000
Case #6: 0.5000000000
Case #7: 0.0291262136
Case #8: 0.6666666667

Nguồn

Google Code Jam 2014, Vòng 3, bài Magical, Marvelous Tour.

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

Hanaa và Sherine đang chơi Willow, một trò chơi trên một bảng gồm \(N\) thành phố. Thành phố thứ \(i\) chứa \(C_i\) đồng xu, và có \(N - 1\) con đường hai chiều chạy giữa các thành phố. Tất cả các thành phố đều có thể đi đến được với nhau. Trò chơi diễn ra như sau:

Đầu tiên, Hanaa chọn một trong các thành phố làm vị trí bắt đầu của mình, sau đó Sherine chọn một trong các thành phố (có thể trùng với thành phố Hanaa đã chọn) làm vị trí bắt đầu của mình. Sau đó, họ luân phiên thực hiện lượt chơi, Hanaa là người đi trước.

Trong lượt của một người chơi, người đó phải lấy tất cả các đồng xu tại thành phố mà họ đang đứng, nếu có; có thể không có đồng xu nào nếu thành phố ban đầu không có đồng xu, hoặc nếu một trong hai người chơi đã bắt đầu một lượt tại thành phố đó trước đó. Sau đó, nếu có thể, người chơi phải di chuyển đến một thành phố lân cận thông qua một con đường. Có thể không di chuyển được vì mỗi con đường chỉ được sử dụng tối đa một lần. Điều này có nghĩa là sau khi một người chơi đã sử dụng một con đường, không ai được phép sử dụng lại con đường đó nữa. Trò chơi kết thúc khi cả Hanaa và Sherine đều không thể thực hiện nước đi.

Sau khi trò chơi kết thúc, điểm của mỗi người chơi bằng hiệu số giữa số đồng xu người đó có và số đồng xu của đối thủ. Nếu đối thủ có nhiều đồng xu hơn, điểm của người đó sẽ là số âm. Cả hai người chơi đều cố gắng tối đa hóa điểm số của mình. Giả sử cả hai đều sử dụng chiến thuật tối ưu nhất để tối đa hóa điểm số, hãy tìm điểm số cao nhất mà Hanaa có thể đạt được.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), số lượng thành phố trên bảng. \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên \(C_i\), số lượng đồng xu trong thành phố \(i\).

Cuối cùng sẽ có thêm \(N - 1\) dòng, dòng thứ \(i\) (\(i\) bắt đầu từ 1) chứa một số nguyên duy nhất \(j\) (\(i < j \le N\)) cho biết có một con đường giữa thành phố \(i\) và thành phố \(j\). Tất cả các thành phố được đảm bảo có thể đi đến được với nhau khi bắt đầu trò chơi.

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à điểm số cao nhất mà Hanaa có thể đạt được.

Ràng buộc

• \(1 \le T \le 50\).
• \(0 \le C_i \le 10000\).

Phân nhóm

• Small dataset: \(2 \le N \le 80\).
• Large dataset: \(2 \le N \le 500\).

Đ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
3
1000
200
1000
2
3
8
8
0
8
0
0
0
0
10
2
5
4
5
6
7
8
10
150
200
0
5000
0
100
0
0
0
10000
10
3
8
5
8
7
8
9
10

Case #1: 200
Case #2: -2
Case #3: 5100

Nguồn

Google Code Jam 2014, Vòng 3, bài Willow.

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