Google Code Jam 2016 - Round 3

Đại học Forest cung cấp \(N\) môn học và sinh viên phải hoàn thành tất cả để lấy bằng. Các môn chỉ được học lần lượt: phải hoàn thành một môn rồi mới bắt đầu môn khác. Mỗi môn hoặc là cơ bản, có thể học mà không cần kiến thức trước, hoặc là nâng cao, có đúng một môn khác làm tiên quyết.

Sinh viên phải học môn tiên quyết trước môn phụ thuộc, nhưng hai môn không nhất thiết liền nhau. Một môn có thể là tiên quyết của nhiều môn khác. Không có chu trình tiên quyết. Mọi thứ tự gồm đủ \(N\) môn và tuân thủ các quan hệ tiên quyết đều hợp lệ để lấy bằng.

Khi bạn tốt nghiệp, trường kỷ niệm thứ tự môn học bằng cách in bản viết tắt lên mũ tốt nghiệp: đó là chuỗi gồm chữ cái đầu tên từng môn, theo đúng thứ tự bạn đã học. Ví dụ, học Coding rồi Jamming sẽ tạo chuỗi CJ. Việc có một số từ ngầu xuất hiện làm chuỗi con trên mũ được coi là hợp thời.

Xét tất cả các thứ tự học hợp lệ. Với mỗi từ ngầu, hãy tìm tỉ lệ các thứ tự mà từ đó xuất hiện ít nhất một lần làm chuỗi con của chuỗi trên mũ. Cần lưu ý ta lấy tỉ lệ trên các thứ tự môn học, không phải trên các chuỗi mũ khác nhau. Nhiều môn có thể bắt đầu bằng cùng một chữ cái, nên số chuỗi phân biệt có thể ít hơn số thứ tự môn.

Khác thường so với Code Jam, bài này chỉ yêu cầu đáp án xấp xỉ; hãy đặc biệt chú ý định dạng đầu ra.

Cách thi bài này

Bài chỉ có một bộ Small và không có bộ Large. Bạn có thể thử lại input, nhưng sẽ chịu phạt thời gian.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm năm dòng theo thứ tự:

1. Số môn học \(N\).
2. \(N\) số nguyên; số thứ \(i\) là chỉ số môn tiên quyết của môn \(i\), hoặc 0 nếu môn \(i\) là môn cơ bản. Các môn được đánh số từ 1 đến \(N\).
3. Một chuỗi gồm \(N\) chữ cái tiếng Anh in hoa, không có khoảng trắng; ký tự thứ \(i\) là chữ cái đầu tên môn \(i\).
4. Số từ ngầu \(M\).
5. \(M\) từ ngầu, mỗi từ chỉ gồm các chữ cái tiếng Anh in hoa.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y1 y2 ... yM, trong đó x là số thứ tự bộ test, bắt đầu từ 1, và \(y_i\) là tỉ lệ các thứ tự môn hợp lệ mà từ ngầu thứ \(i\) xuất hiện làm chuỗi con trên mũ tốt nghiệp.

\(y_i\) được coi là đúng nếu sai số tuyệt đối so với đáp án không quá \(0.03\).

Ràng buộc

Phân nhóm

Test Set 1 (Small, hiển thị)

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le M\le5\).
• Độ dài mỗi từ ngầu từ 1 đến 20.
• Mỗi từ ngầu chỉ gồm chữ cái tiếng Anh in hoa.
• Không có chu trình do các quan hệ tiên quyết tạo thành.

Đ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
2
0 1
CJ
4
CJ C D JC
3
0 1 0
BAA
3
AA AAB ABA

Case #1: 1.0 1.0 0.0 0.0
Case #2: 0.67 0.0 0.33

Nguồn

Google Code Jam 2016, Vòng 3, bài Forest University.

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

Ngôn ngữ Go được thiết kế với API đơn giản và hỗ trợ đa luồng. Đội Code Jam muốn đẩy hai mục tiêu này tới giới hạn nên đề xuất một ngôn ngữ mới: Go++.

Go++ có một thanh ghi lưu một giá trị Boolean, 0 hoặc 1, ban đầu bằng 0. Ngôn ngữ có ba lệnh:

• 0: đặt thanh ghi thành 0.
• 1: đặt thanh ghi thành 1.
• ?: in giá trị hiện tại của thanh ghi.

Đơn giản phải không? Để hỗ trợ đa luồng, hai chương trình Go++ khác nhau có thể chạy đồng thời và dùng chung thanh ghi. Mỗi lệnh được thực thi nguyên tử, nghĩa là một lệnh phải kết thúc hoàn toàn trước khi lệnh tiếp theo bắt đầu. Hai chương trình có thể được xen kẽ theo bất kỳ cách nào miễn là thứ tự tương đối của các lệnh trong từng chương trình được giữ nguyên.

Ví dụ, hai chương trình 1? và ?0 chỉ có sáu cách xen kẽ sau; ở đây ký hiệu các lệnh của chương trình thứ hai bằng phần gạch chân trong bản gốc để phân biệt:

• <u>?0</u>1? in 01 vì thanh ghi ban đầu là 0.
• <u>?</u>1<u>0</u>? in 00.
• <u>?</u>1?<u>0</u> in 01.
• 1<u>?0</u>? in 10.
• 1<u>?</u>?<u>0</u> in 11.
• 1?<u>?0</u> in 11.

Chuỗi đầu ra luôn chỉ gồm 0 và 1, không bao giờ có ?, vì ? không phải một trạng thái của thanh ghi.

Thông thường, lập trình viên viết chương trình để tạo đầu ra mong muốn; ở đây bạn phải viết hai chương trình không thể tạo ra một đầu ra không mong muốn. Bạn được cho chuỗi “xấu” \(B\) độ dài \(L\) và tập \(G\) gồm \(N\) chuỗi “tốt”, tất cả đều dài \(L\). Hãy tạo hai chương trình Go++ (không nhất thiết cùng độ dài) sao cho khi chạy như trên, chúng có thể tạo ra mọi chuỗi trong \(G\), nhưng không thể tạo ra \(B\). Chúng có thể tạo thêm các chuỗi không thuộc \(G\) và khác \(B\). Tổng cộng hai chương trình phải có đúng \(L\) lệnh ?, và tổng số lệnh không được vượt quá 200.

Ví dụ, với \(B=\) 11 và \(G=\{\) 10, 00 \(\}\), hai chương trình ? và 10?1 là một đáp án hợp lệ: chúng sinh được mọi chuỗi trong \(G\) nhưng không thể sinh \(B\) với bất kỳ cách xen kẽ nào. Chúng cũng có thể sinh 01, nhưng điều đó được phép. Hai chương trình 1? và ?0 không hợp lệ vì có thể sinh \(B\) như ví dụ sáu cách ở trên. Hai chương trình 00 và ?? cũng không hợp lệ vì không sinh được mọi chuỗi trong \(G\).

Hãy tạo hai chương trình thỏa mãn, hoặc xác định rằng nhiệm vụ là IMPOSSIBLE.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa \(N,L\): số chuỗi trong \(G\) và độ dài của \(B\) cũng như mọi chuỗi trong \(G\). Dòng thứ hai chứa \(N\) chuỗi phân biệt độ dài \(L\) thuộc \(G\). Dòng thứ ba chứa chuỗi xấu \(B\) độ dài \(L\). Tất cả các chuỗi chỉ gồm 0 và 1.

Dữ liệu ra

Với mỗi bộ test, in Case #x: IMPOSSIBLE nếu không có hai chương trình thỏa mãn. Nếu có, in Case #x: y z, trong đó y,z là hai chương trình. Tổng số lệnh không vượt quá 200; mỗi chương trình có ít nhất một lệnh; tổng cộng phải có đúng \(L\) lệnh ?.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le L\le50\).
• Các chuỗi trong \(G\) đôi một khác nhau.

Phân nhóm

Test Set 1 (Small, hiển thị)

\(B\) chỉ gồm các ký tự 1.

Test Set 2 (Large, ẩn)

\(B\) có thể là chuỗi 0 và 1 bất 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
2 2
10 00
11
3 2
11 10 00
01
4 2
00 01 10 11
11

Case #1: ? 10?1
Case #2: 1?? 0
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2016, Vòng 3, bài Go++.

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à một chiến binh nổi dậy chống lại Đế chế Thiên hà độc ác, và đang chạy trốn!

Bạn vừa phá hoại Nhà máy Tội ác của Đế chế, và lực lượng an ninh sắp truy đuổi. Nhà máy nằm trên tiểu hành tinh 0 trong một hệ gồm \(N\) tiểu hành tinh được đánh số. Tàu trốn thoát Century Quail nằm trên tiểu hành tinh 1; nếu tới được đó, bạn sẽ bay đi an toàn.

Mỗi tiểu hành tinh là một điểm trong không gian và có vận tốc; bạn chuyển động cùng tiểu hành tinh đang đứng. Thiết bị Asteroid Jumper cho phép nhảy tức thời giữa hai tiểu hành tinh bất kỳ. Cú nhảy dài đáng sợ hơn cú nhảy ngắn, nên bạn muốn tối thiểu hóa khoảng cách lớn nhất phải nhảy. Tuy nhiên, tính từ lúc này, nếu có bất kỳ khoảng thời gian liên tục nào dài quá \(S\) giây mà bạn không nhảy, lực lượng an ninh sẽ bắt được bạn. Khoảng từ lúc bắt đầu đến cú nhảy đầu và mọi khoảng giữa hai cú nhảy liên tiếp đều không quá \(S\). Có thể nhảy ở bất kỳ thời điểm thực nào, không cần chờ số giây nguyên. Bạn thoát ngay khi nhảy tới tiểu hành tinh 1.

Tiểu hành tinh \(i\) bắt đầu tại \((x_i,y_i,z_i)\) và mỗi giây dịch chuyển thêm vectơ \((V_{xi},V_{yi},V_{zi})\). Chuyển động diễn ra liên tục, không cập nhật rời rạc từng giây; một tiểu hành tinh cũng có thể đứng yên. Hai tiểu hành tinh trùng vị trí không gây ra điều gì: bạn vẫn chỉ có thể đi giữa chúng bằng một cú nhảy, kể cả khi khoảng cách đúng bằng 0 ở thời điểm ấy.

Trong kế hoạch trốn thoát tối ưu, khoảng cách của cú nhảy dài nhất là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N,S\): số tiểu hành tinh và thời gian tối đa được phép không nhảy. Tiếp theo là \(N\) dòng, đánh số từ 0; dòng thứ \(i\) chứa sáu số nguyên: vị trí ban đầu \((x_i,y_i,z_i)\) và vectơ dịch chuyển trong một giây \((V_{xi},V_{yi},V_{zi})\).

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à khoảng cách cú nhảy dài nhất cần thực hiện. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-4}\).

Ràng buộc

• \(1\le T\le20\).
• \(2\le N\le1000\).
• \(1\le S\le100\).
• \(-500\le x_i,y_i,z_i\le500\).

Phân nhóm

Test Set 1 (Small, hiển thị)

\(V_{xi}=V_{yi}=V_{zi}=0\).

Test Set 2 (Large, ẩn)

\(-500\le V_{xi},V_{yi},V_{zi}\le500\).

Đ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 7
0 0 0 0 0 0
1 2 2 0 0 0
1 1 1 0 0 0
5 10
0 0 0 0 0 0
35 0 0 -1 0 0
1 54 0 0 -2 0
2 -150 0 0 10 0
4 0 0 -1 0 0
3 1
-10 2 0 1 0 0
0 0 10 0 0 -1
-10 -2 0 1 0 0

Case #1: 1.7320508
Case #2: 2.0000000
Case #3: 4.0000000

Nguồn

Google Code Jam 2016, Vòng 3, bài Rebel Against The Empire.

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 đang học một khóa lập trình được chấm bằng các bộ bài tập thuộc nhiều loại. Khóa học kéo dài một số ngày chẵn dương. Ban đầu bạn không có bộ bài nào. Mỗi ngày, bạn phải làm đúng một việc:

• Yêu cầu một bộ bài “Coding”.
• Yêu cầu một bộ bài “Jamming”.
• Nộp một bộ bài để chấm. Chỉ được chọn việc này nếu đang giữ ít nhất một bộ. Nếu có nhiều bộ, bắt buộc phải nộp bộ được yêu cầu gần đây nhất, bất kể loại nào.

Mọi bộ bài đều khác nhau. Không có yêu cầu về số bộ từng loại phải nộp. Sau khi nộp, bạn không còn giữ bộ đó. Mọi bộ chưa nộp khi khóa học kết thúc đều không đem lại điểm.

Bạn yêu cầu và nộp bài cho một trợ giảng trí tuệ nhân tạo. Kỳ lạ thay, mỗi ngày trợ giảng có một trong hai tâm trạng: “Coding” hoặc “Jamming”.

Khi yêu cầu một bộ bài:

• Nếu chủ đề yêu cầu trùng tâm trạng, trợ giảng giao bộ có điểm tối đa 10.
• Nếu không trùng, trợ giảng giao bộ có điểm tối đa 5.

Khi nộp một bộ bài:

• Nếu chủ đề bộ bài trùng tâm trạng ngày nộp, bạn nhận điểm tối đa của bộ đó.
• Nếu không trùng, bạn nhận ít hơn điểm tối đa 5 điểm.

Ví dụ, nếu xin bộ Coding vào ngày trợ giảng có tâm trạng Coding và nộp vào ngày tâm trạng Jamming, bộ có tối đa 10 nhưng bị trừ 5, nên bạn nhận 5 điểm. Nếu xin bộ Jamming vào ngày tâm trạng Coding rồi nộp vào ngày tâm trạng Jamming, bộ chỉ có tối đa 5 nhưng được nhận trọn 5 điểm.

Nhờ một đồng nghiệp khóa trên hiểu trợ giảng, bạn biết trước tâm trạng mỗi ngày. Tổng điểm lớn nhất có thể đạt là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng là chuỗi \(S\) chỉ gồm C và J. Ký tự thứ \(i\) mô tả tâm trạng ngày thứ \(i\): C là Coding và J là Jamming.

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à số điểm tối đa.

Ràng buộc

• \(1\le T\le100\).
• Độ dài \(S\) là số chẵn.

Phân nhóm

Test Set 1 (Small, hiển thị)

\(2\le |S|\le50\).

Test Set 2 (Large, ẩn)

• \(2\le |S|\le20000\).
• Tổng độ dài mọi chuỗi \(S\) trong bộ dữ liệu không quá 150000.

Đ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
CCJJ
CJCJ
CJJC
CJJJ
CCCCCC

Case #1: 20
Case #2: 10
Case #3: 20
Case #4: 15
Case #5: 30

Nguồn

Google Code Jam 2016, Vòng 3, bài Teaching Assistant.

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