Google Code Jam 2017 - Round 1B

Năm 1860, Pony Express là hệ thống chuyển thư nhanh nhất nối bờ Đông và bờ Tây Hoa Kỳ. Hệ thống phục vụ \(N\) thành phố. Mỗi thành phố có đúng một con ngựa; mỗi con đi với một tốc độ không đổi nhất định và có tổng quãng đường tối đa mà nó có thể đi trước khi quá mệt để tiếp tục.

Người đưa thư Pony Express khởi hành bằng ngựa của thành phố xuất phát. Mỗi khi tới một thành phố, người đó có thể tiếp tục dùng con ngựa hiện tại hoặc đổi sang ngựa của thành phố ấy; việc đổi ngựa diễn ra tức thời. Ngựa không bao giờ có cơ hội nghỉ, nên một phần sức bền tối đa đã dùng thì mất vĩnh viễn. Khi người đưa thư tới thành phố đích, thư được giao.

Các tuyến giữa thành phố được thiết lập qua những cuộc thương lượng phức tạp giữa chủ công ty, nhà lập pháp, đại diện công đoàn và ông anh họ Pete. Vì vậy khoảng cách không nhất thiết tuân theo lẽ thường: chúng không nhất thiết thỏa bất đẳng thức tam giác, và khoảng cách từ A đến B có thể khác khoảng cách từ B đến A.

Bạn là một doanh nhân du hành thời gian và mang theo một máy tính nhanh từ tương lai. Một máy tính chưa đủ để lập dịch vụ thư điện tử khiến Pony Express lỗi thời, nhưng có thể dùng nó để lập tuyến tối ưu. Với toàn bộ dữ liệu về đường đi, ngựa ở từng thành phố và danh sách các cặp thành phố đầu-cuối, hãy tính nhanh thời gian tối thiểu cho mỗi chuyến giao thư. Mọi chuyến giao thư được xem là độc lập; dùng thành phố hay ngựa trong một chuyến không làm chúng mất đi ở chuyến khác.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm:

• Một dòng chứa \(N\), số thành phố có ngựa, và \(Q\), số cặp điểm dừng cần xét. Các thành phố được đánh số từ 1 đến \(N\).
• \(N\) dòng, dòng thứ \(i\) chứa \(E_i\), tổng quãng đường tối đa (km) ngựa ở thành phố \(i\) có thể đi, và \(S_i\), tốc độ không đổi (km/h) của nó.
• \(N\) dòng, mỗi dòng \(N\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\), \(D_{ij}\), bằng -1 nếu không có tuyến trực tiếp từ thành phố \(i\) đến \(j\), và bằng độ dài tuyến đó (km) nếu có.
• \(Q\) dòng, dòng thứ \(k\) chứa \(U_k,V_k\), lần lượt là điểm xuất phát và điểm đến của cặp thành phố thứ \(k\) cần xét.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y1 y2 ... yQ, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn \(y_k\) là thời gian tối thiểu theo giờ để giao thư từ \(U_k\) đến \(V_k\).

Mỗi \(y_k\) được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\); \(2\le N\le100\).
• \(1\le E_i\le10^9\) và \(1\le S_i\le1000\) với mọi \(i\).
• \(-1\le D_{ij}\le10^9\); \(D_{ii}=-1\); \(D_{ij}\ne0\) với mọi \(i,j\).
• \(U_k\ne V_k\) với mọi \(k\).
• Mọi chuyến từ \(U_k\) đến \(V_k\) đều được bảo đảm thực hiện được bằng các con ngựa đã cho.
• Không cặp có thứ tự nào bị lặp trong cùng một bộ test: với mọi \(l\ne m\), \(U_l\ne U_m\) và/hoặc \(V_l\ne V_m\).

Phân nhóm

• Test Set 1 (Visible): \(D_{ij}=-1\) với mọi \(i,j\) mà \(i+1\ne j\); các thành phố nằm trên một đường thẳng và mỗi tuyến chỉ đi từ một thành phố tới thành phố kế tiếp. \(Q=1\), \(U_1=1\), \(V_1=N\); chỉ cần tính chuyến từ thành phố đầu đến thành phố cuối.
• Test Set 2 (Hidden): \(1\le Q\le100\); \(1\le U_k,V_k\le N\) với mọi \(k\).

Đ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 1
2 3
2 4
4 4
-1 1 -1
-1 -1 1
-1 -1 -1
1 3
4 1
13 10
1 1000
10 8
5 5
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 10
-1 -1 -1 -1
1 4
4 3
30 60
10 1000
12 5
20 1
-1 10 -1 31
10 -1 10 -1
-1 -1 -1 10
15 6 -1 -1
2 4
3 1
3 2

Case #1: 0.583333333
Case #2: 1.2
Case #3: 0.51 8.01 8.0

Nguồn

Google Code Jam 2017, Vòng 1B, bài Pony Express.

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 may mắn sở hữu \(N\) chú kỳ lân. Bờm của mỗi chú có một hoặc hai trong ba loại lông: đỏ, vàng và xanh dương. Màu nhìn thấy của bờm phụ thuộc chính xác vào các loại lông có trong đó:

• Bờm chỉ có một màu lông sẽ mang chính màu ấy; chẳng hạn chỉ có lông xanh dương thì bờm xanh dương.
• Bờm có lông đỏ và vàng nhìn thành màu cam.
• Bờm có lông vàng và xanh dương nhìn thành màu xanh lá.
• Bờm có lông đỏ và xanh dương nhìn thành màu tím.

Bạn có lần lượt \(R,O,Y,G,B,V\) chú kỳ lân với bờm đỏ, cam, vàng, xanh lá, xanh dương và tím.

Bạn vừa xây một chuồng tròn gồm \(N\) ô xếp thành vòng, mỗi ô kề đúng hai ô khác. Bạn muốn đặt đúng một kỳ lân vào mỗi ô. Tuy nhiên, kỳ lân cần cảm thấy mình hiếm và đặc biệt, nên không chú nào được đứng cạnh một chú khác có chung ít nhất một màu lông trong bờm. Ví dụ, bờm cam không thể kề bờm tím vì cả hai đều có lông đỏ. Tương tự, bờm xanh lá không thể kề bờm vàng vì cả hai có lông vàng.

Có thể xếp tất cả kỳ lân hay không? Nếu có, hãy đưa ra một cách xếp.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm một dòng chứa bảy số nguyên \(N,R,O,Y,G,B,V\).

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). Nếu không thể xếp, y là IMPOSSIBLE; nếu có thể, y là chuỗi \(N\) ký tự mô tả các ô chuồng, bắt đầu ở một điểm tùy chọn và đọc theo chiều kim đồng hồ quanh vòng. Dùng R, O, Y, G, B, V để biểu diễn kỳ lân có bờm tương ứng. Cách xếp phải tuân thủ mọi quy tắc trên.

Nếu có nhiều cách xếp, có thể in bất kỳ cách nào.

Ràng buộc

• \(1\le T\le100\); \(3\le N\le1000\).
• \(R+O+Y+G+B+V=N\).
• \(0\le Z\) với mọi \(Z\in\{R,O,Y,G,B,V\}\).

Phân nhóm

• Test Set 1 (Visible): \(O=G=V=0\); mỗi kỳ lân chỉ có một màu lông trong bờm.
• Test Set 2 (Hidden): không có hạn chế thêm; mỗi kỳ lân có thể có một hoặc hai màu lông trong bờm.

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

Case #1: RYBRBY
Case #2: IMPOSSIBLE
Case #3: YBRGRB
Case #4: YVYV

Nguồn

Google Code Jam 2017, Vòng 1B, bài Stable Neigh-bors.

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

Annie là tài xế xe buýt với công việc đầy căng thẳng. Cô từng thử thư giãn bằng một chuyến du thuyền Caribe, nhưng chuyến đi đó cũng hóa ra căng thẳng, nên gần đây cô chuyển sang cưỡi ngựa.

Hôm nay, Annie cưỡi ngựa về phía đông trên một con đường một chiều dài và hẹp chạy từ tây sang đông. Hiện cô ở kilômét 0 và đích nằm tại kilômét \(D\); các cột kilômét được đánh số tăng dần từ tây sang đông.

Có \(N\) con ngựa khác đang đi về phía đông trên cùng con đường. Tất cả sẽ tiếp tục đi mãi mãi và hiện đều nằm giữa ngựa của Annie với đích. Con thứ \(i\) ban đầu ở kilômét \(K_i\) và đi với tốc độ tối đa \(S_i\) km/h.

Ngựa rất lịch sự: một con \(H_1\) sẽ không vượt (đi lên trước) con \(H_2\) vốn xuất phát phía trước nó. Hai hay nhiều con có thể ở cùng vị trí trong bất kỳ khoảng thời gian nào; có thể xem ngựa là các điểm. Những con ngựa khác Annie đi ở tốc độ tối đa, trừ khi một con nhanh \(H_1\) bắt kịp một con chậm \(H_2\) phía trước; khi đó \(H_1\) giảm tốc để bằng \(H_2\).

Ngựa của Annie không có tốc độ tối đa và có thể đi với bất kỳ tốc độ nào cô chọn, miễn là không vượt con ngựa khác. Để hành trình êm ái cho cả hai, Annie muốn chọn một tốc độ “ga tự động” không đổi duy nhất cho toàn bộ quãng đường từ vị trí hiện tại tới đích, sao cho ngựa của cô không vượt bất kỳ con nào. Tốc độ lớn nhất cô có thể chọn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(D,N\): vị trí đích chung của các con ngựa (km) và số ngựa khác trên đường. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(K_i,S_i\), vị trí ban đầu (km) và tốc độ tối đa (km/h) của con ngựa thứ \(i\).

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), còn y là tốc độ không đổi lớn nhất (km/h) Annie có thể dùng mà không vượt ngựa khác. y được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(0<K_i<D\le10^9\) với mọi \(i\).
• \(K_i\ne K_j\) với mọi \(i\ne j\); không hai con ngựa nào xuất phát cùng vị trí.
• \(1\le S_i\le10000\).

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le2\).
• Test Set 2 (Hidden): \(1\le N\le1000\).

Đ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
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

Nguồn

Google Code Jam 2017, Vòng 1B, bài Steed 2: Cruise Control.

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