Mysterious Road Signs

Thị trấn Signfield nằm trên một con đường thẳng hoàn hảo và dài vô hạn chạy từ tây sang đông. Dọc theo con đường có một dãy \(S\) biển báo bí ẩn với các con số ở cả hai mặt. Biển thứ \(i\) (được đánh số theo thứ tự từ tây sang đông) nằm tại một điểm cách Signfield \(D_i\) kilômét về phía đông, có số \(A_i\) ở mặt quay về phía tây và số \(B_i\) ở mặt quay về phía đông.

Không ai ở Signfield biết những biển báo này muốn nói gì. Bạn cho rằng các số ở mặt phía tây dành cho tài xế đi về hướng đông và biểu thị khoảng cách đến một địa điểm cụ thể nào đó. Tương tự, bạn cho rằng các số ở mặt phía đông dành cho tài xế đi về hướng tây và biểu thị khoảng cách đến một địa điểm cụ thể nào đó. Tuy nhiên, bạn nghi ngờ rằng không phải tất cả biển báo đều nhất quán với giả thuyết này.

Để bắt đầu kiểm chứng giả thuyết, bạn muốn tìm các tập biển báo hợp lệ tuân theo những quy tắc sau:

• Tập đó là một dãy con liên tiếp của toàn bộ dãy biển báo. (Cả toàn bộ dãy cũng được tính là một dãy con liên tiếp.)
• Tồn tại hai vị trí \(M\) và \(N\) kilômét về phía đông Signfield, trong đó \(M\) và \(N\) là các số không nhất thiết dương và không nhất thiết phân biệt, sao cho với mỗi biển trong tập, ít nhất một trong hai điều sau đúng:
  • \(D_i+A_i=M\).
  • \(D_i-B_i=N\).

Số biển lớn nhất có thể có trong một tập hợp lệ như mô tả ở trên là bao nhiêu, và có bao nhiêu tập hợp lệ khác nhau có kích thước đó?

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ộ bắt đầu bằng một dòng chứa số nguyên \(S\): số biển báo. Sau đó có thêm \(S\) dòng. Dòng thứ \(i\) mô tả biển thứ \(i\) (theo thứ tự từ tây sang đông) và chứa ba số nguyên \(D_i\), \(A_i\), \(B_i\): khoảng cách của biển về phía đông Signfield (tính bằng kilômét), số trên mặt phía tây và số trên mặt phía đông.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y và z lần lượt là số biển lớn nhất có thể có trong một tập hợp lệ và số tập hợp lệ có kích thước đó, như mô tả trong đề bài.

Ràng buộc

• \(1\le T\le60\).
• \(1\le D_i\le10^6\) với mọi \(i\).
• \(D_i<D_j\) với mọi \(i<j\).
• \(1\le A_i\le10^6\) với mọi \(i\).
• \(1\le B_i\le10^6\) với mọi \(i\).

Phân nhóm

Test Set 1 (Hiển thị): \(1\le S\le100\) trong mọi bộ test.

Test Set 2 (Ẩn): \(1\le S\le100\) trong tất cả trừ 3 bộ test; trong 3 bộ test còn lại, \(S=10^5\).

Đ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 1 1
5
2 7 12
6 3 11
8 10 1
11 11 12
13 9 14
5
1 3 3
2 2 2
3 1 1
4 2 2
5 3 3

Case #1: 1 1
Case #2: 3 2
Case #3: 5 1

Nguồn

Google Code Jam 2018, Vòng 1B, bài Mysterious Road Signs.

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 quyết dứt điểm câu hỏi muôn thuở rằng ngôn ngữ lập trình nào là tốt nhất, bạn hỏi tổng cộng \(N\) người về ngôn ngữ yêu thích của họ. Đây là câu hỏi mở: mỗi người được tự do nêu bất kỳ ngôn ngữ nào, và trên thế giới có vô hạn ngôn ngữ.

Một số người đã trả lời, và bạn đã tổng hợp thông tin thành một danh sách số lượng. Chẳng hạn, 1 2 có nghĩa là cho đến lúc này bạn đã hỏi 3 người: một người chọn một ngôn ngữ nào đó, còn hai người kia chọn một ngôn ngữ khác.

Bạn định công bố kết quả dưới dạng bảng liệt kê từng ngôn ngữ và tỷ lệ phần trăm số người chọn nó. Mỗi tỷ lệ được làm tròn tới số nguyên gần nhất; nếu phần thập phân lớn hơn hoặc bằng 0,5 thì làm tròn lên. Ví dụ, 12,5% được làm tròn thành 13%, 99,5% thành 100%, còn 12,4999% thành 12%.

Trong những khảo sát như vậy, đôi khi tổng các tỷ lệ đã làm tròn không đúng bằng 100. Sau khi bạn khảo sát xong những người còn lại, tổng lớn nhất có thể của các tỷ lệ đã làm tròn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\) và \(L\): tổng số người trong khảo sát và số ngôn ngữ khác nhau đã xuất hiện trong câu trả lời của những người đã trả lời. Dòng thứ hai chứa \(L\) số nguyên \(C_i\); số thứ \(i\) là số người đã chọn ngôn ngữ thứ \(i\) trong số các ngôn ngữ đã xuất hiện.

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, và \(y\) là tổng lớn nhất có thể của các tỷ lệ phần trăm đã làm tròn như mô tả trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le L < N\).
• \(1 \le C_i\) với mọi \(i\).
• \(\sum_i C_i < N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2 \le N \le 25\).
• Test Set 2 (Hiển thị): \(2 \le N \le 250\).
• Test Set 3 (Ẩn): \(2 \le N \le 10^5\).

Đ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
1 1
10 3
1 3 2
6 2
3 1
9 8
1 1 1 1 1 1 1 1

Case #1: 100
Case #2: 100
Case #3: 101
Case #4: 99

Nguồn

Google Code Jam 2018, Vòng 1B, bài Rounding Error.

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

Bạn là nhà giả kim tài giỏi nhất của một đất nước coi những kim loại như vàng, bạch kim và bạc là tẻ nhạt, nhưng lại đặc biệt quý trọng chì. Thế giới biết đến \(M\) kim loại; chì là kim loại số 1 trong bảng tuần hoàn của bạn. Nhà lãnh đạo yêu cầu bạn dùng số kim loại trong kho bạc để tạo ra nhiều chì nhất có thể.

Với mỗi kim loại, kể cả chì, bạn biết đúng một công thức tạo một gram kim loại đó bằng cách phá hủy một gram của mỗi loại trong hai kim loại nguyên liệu. Nếu thắc mắc về định luật bảo toàn khối lượng, gram còn lại bị mất vào các phế phẩm vô dụng. Công thức không hoạt động với phần lẻ của một gram. Tuy nhiên, bạn có thể dùng mỗi công thức bao nhiêu lần tùy ý, hoặc không dùng lần nào, miễn là mỗi lần đều có đủ nguyên liệu.

Nếu lựa chọn tối ưu, tổng lượng chì lớn nhất mà bạn có thể thu được là bao nhiêu? Lưu ý rằng sau khi hoàn tất, một số kim loại khác chì có thể vẫn còn dư.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(M\), số kim loại được biết đến. Tiếp theo là \(M\) dòng, mỗi dòng chứa hai số nguyên \(R_{i1}\) và \(R_{i2}\); dòng thứ \(i\) cho biết có thể tạo một gram kim loại \(i\) bằng cách phá hủy một gram kim loại \(R_{i1}\) và một gram kim loại \(R_{i2}\). Cuối cùng là một dòng chứa \(M\) số nguyên \(G_1,G_2,\ldots,G_M\), trong đó \(G_i\) là số gram kim loại \(i\) trong kho bạc. Chì là kim loại 1.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là lượng chì lớn nhất, tính bằng gram, mà bạn có thể thu được.

Ràng buộc

• \(1\le T\le100\).
• \(1\le R_{i1}<R_{i2}\le M\) với mọi \(i\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2\le M\le8\); \(0\le G_i\le8\) với mọi \(i\).
• Test Set 2 (Ẩn): \(2\le M\le100\); \(0\le G_i\le100\) với mọi \(i\).
• Test Set 3 (Ẩn): \(2\le M\le100\); \(0\le G_i\le10^9\) với mọi \(i\).

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

Case #1: 7
Case #2: 4
Case #3: 0

Nguồn

Google Code Jam 2018, Vòng 1B, bài Transmutation.

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