Google Code Jam 2017 - World Finals

Bạn có một bộ đặc biệt gồm \(N\) xúc xắc sáu mặt; trên sáu mặt của mỗi con là sáu số nguyên dương khác nhau. Các xúc xắc khác nhau có thể được đánh số khác nhau.

Bạn muốn xếp một số hoặc toàn bộ xúc xắc thành một hàng sao cho các mặt trên tạo thành một dãy thẳng, tức là hiển thị các số nguyên liên tiếp. Với mỗi xúc xắc, bạn được chọn mặt nào nằm trên.

Dãy thẳng dài nhất có thể tạo theo cách này dài 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 một dòng chứa \(N\), số xúc xắc. Tiếp theo là \(N\) dòng, mỗi dòng gồm sáu số nguyên dương \(D_{ij}\); số thứ \(j\) trên dòng thứ \(i\) là giá trị ở mặt thứ \(j\) của xúc xắc 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, và y là độ dài dãy thẳng dài nhất.

Ràng buộc

• \(1\le T\le100\).
• \(1\le D_{ij}\le10^6\) với mọi \(i,j\).

Phân nhóm

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

\(1\le N\le100\).

Test Set 2 (Large, ẩn)

• \(1\le N\le50000\).
• Tổng \(N\) trên mọi bộ test không quá 200000.

Đ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
4 8 15 16 23 42
8 6 7 5 30 9
1 2 3 4 55 6
2 10 18 36 54 86
2
1 2 3 4 5 6
60 50 40 30 20 10
3
1 2 3 4 5 6
1 2 3 4 5 6
1 4 2 6 5 3

Case #1: 4
Case #2: 1
Case #3: 3

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Dice Straight.

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

Nhà du hành quả cảm K, có thể là tác giả bài này hoặc không, gần đây đi lại rất nhiều. Trong một chuyến đi, cô bay từ San Francisco tới Frankfurt, Johannesburg, Abu Dhabi, Singapore, Tokyo rồi trở về San Francisco. Cô đã đi vòng quanh Trái Đất theo một đường khép kín chạm mọi kinh tuyến: với mỗi kinh độ có thể có, đường đi có ít nhất một điểm ở kinh độ đó.

Tuy nhiên, K không chắc chuyến ấy đủ “siêu tuyệt vời”, vì người ta cũng có thể đi vòng quanh Trái Đất bằng cách bay tới Bắc Cực rồi đi bộ một vòng quanh đó; ngoài việc bay tới Bắc Cực, việc này không có vẻ khó. Vì vậy cô đưa ra khái niệm tổng quát hơn: omnicircumnavigation — một đường khép kín quanh Trái Đất, coi Trái Đất là mặt cầu, vẫn là một hành trình vòng quanh bất kể đặt hai cực ở đâu. Nói cách khác, đó là đường khép kín trên mặt cầu chạm mọi bán cầu có thể chọn; chạm biên bán cầu là đủ. Tương đương, đường ấy cắt mọi đại vòng, tức mọi đường tròn có đường kính lớn nhất trên mặt cầu.

Bạn được cho một dãy \(N\) điểm trên mặt cầu bán kính 1. Hãy kiểm tra đường nối chúng theo thứ tự có phải omnicircumnavigation hay không. Đường đi nối mỗi cặp điểm liên tiếp bằng tuyến ngắn nhất trên bề mặt, rồi nối điểm cuối về điểm đầu theo cùng cách. Không có hai điểm liên tiếp nào, kể cả cặp cuối–đầu, thẳng hàng với gốc tọa độ: chúng không đối cực và cũng không phải cùng một điểm trên mặt cầu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng \(N\), số thành phố K ghé thăm. \(N\) dòng sau chứa ba số nguyên \(X_i,Y_i,Z_i\). Điểm thứ \(i\) trên mặt cầu có tọa độ

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test và y là YES nếu hành trình là omnicircumnavigation, ngược lại là NO.

Ràng buộc

• \(1\le T\le200\).
• \(-10^6\le X_i,Y_i,Z_i\le10^6\) với mọi \(i\).
• Ít nhất một trong \(X_i,Y_i,Z_i\) khác 0 với mọi \(i\).
• Với mọi cặp liên tiếp \(i,j\), gồm cả \(i=N-1,j=0\), không vectơ nguyên nào trong hai vectơ \((X_i,Y_i,Z_i)\) và \((X_j,Y_j,Z_j)\) là bội nguyên của vectơ kia. Do đó hai điểm không trùng nhau và không đối cực trên mặt cầu.

Phân nhóm

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

\(3\le N\le50\).

Test Set 2 (Large, ẩn)

\(3\le N\le5000\).

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

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Omnicircumnavigation.

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

Ở Code Jam có một trò chơi mang tên “Operation” (không liên quan gì đến phẫu thuật). Mỗi lá bài ghi một phép toán số học cơ bản \(O_i\) — cộng, trừ, nhân hoặc chia — cùng một toán hạng nguyên bên phải \(V_i\). Chẳng hạn, một lá có thể ghi + 0, - -2 hoặc / -4. Toán hạng có thể âm hoặc bằng 0, nhưng toán hạng của phép chia không bao giờ bằng 0.

Trong mỗi ván, ta chọn một giá trị nguyên ban đầu \(S\) và bày ra \(C\) lá bài. Người chơi phải sắp thứ tự các lá, dùng mỗi lá đúng một lần; sau đó áp dụng lần lượt các phép toán lên \(S\) để thu được kết quả cuối cùng.

Dù các toán hạng đều nguyên, mọi phép tính được thực hiện trên số hữu tỉ. Ví dụ, với \(S=5\) và các lá + 1, - 2, * 3, / -2, nếu dùng theo thứ tự vừa nêu thì kết quả là \((5+1-2)\times3/(-2)=-6\). Các phép toán luôn được thực hiện theo thứ tự lá bài, không xét độ ưu tiên toán tử. Nếu dùng thứ tự - 2, / -2, + 1, * 3, kết quả là \(((5-2)/(-2)+1)\times3=-3/2\); đây chính là giá trị lớn nhất có thể đạt với bộ bài ấy.

Hãy tìm giá trị cuối cùng lớn nhất có thể và biểu diễn nó dưới dạng phân số tối giản có mẫu số dương.

Dữ liệu vào

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

Mỗi test bắt đầu bằng hai số nguyên \(S\) và \(C\): giá trị ban đầu và số lá bài. Tiếp theo là \(C\) dòng; dòng thứ \(i\) chứa một ký tự \(O_i\) thuộc +, -, *, / và số nguyên \(V_i\), mô tả lá bài thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, còn \(y,z\) là các số nguyên sao cho \(y/z\) là kết quả lớn nhất. Hai số \(y,z\) không có ước chung nào ngoài \(1\) và \(-1\), và \(z>0\).

Ràng buộc

• \(1\le T\le100\).
• \(-1000\le S\le1000\).
• \(O_i\) luôn thuộc +, -, *, /.
• \(-1000\le V_i\le1000\).
• Nếu \(O_i\) là / thì \(V_i\ne0\).

Phân nhóm

• Test Set 1 (Visible): \(1\le C\le15\).
• Test Set 2 (Hidden): \(1\le C\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ụ

5
1 2

- 3
* 2
5 4
+ 1
- 2
* 3
/ -2
1000 7
* -1000
* -1000
* 1000
* 1000
* 1000
* 1000
* 1000
-1 3
- -1
* 0
/ -1
0 1
+ 0

Case #1: -1 1
Case #2: -3 2
Case #3: 1000000000000000000000000 1
Case #4: 1 1
Case #5: 0 1

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Operation.

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

Cây khung của một đồ thị vô hướng có \(N\) đỉnh là một cây gồm \(N-1\) cạnh, chỉ sử dụng các cạnh của đồ thị và chứa đủ cả \(N\) đỉnh.

Hãy xây dựng một đồ thị có ít nhất 2 và không quá 22 đỉnh sao cho đồ thị có đúng \(K\) cây khung khác nhau. Hai cây khung được coi là khác nhau khi và chỉ khi tập cạnh của chúng khác nhau.

Đồ thị phải là đồ thị đơn: giữa mỗi cặp đỉnh có nhiều nhất một cạnh và không được có khuyên, tức cạnh nối một đỉnh với chính nó.

Với mọi \(K\) trong giới hạn bên dưới, đề bài bảo đảm tồn tại ít nhất một đồ thị thỏa mãn.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\).

Mỗi test gồm một dòng chứa số nguyên \(K\): số cây khung mong muốn.

Dữ liệu ra

Với mỗi test, trước tiên in một dòng có dạng Case #x: y, trong đó x là số thứ tự test, bắt đầu từ 1, và \(y\) là số đỉnh của đồ thị được xây dựng. Giá trị \(y\) phải nằm trong đoạn từ 2 đến 22, kể cả hai đầu.

Sau đó, in thêm \(y\) dòng. Dòng thứ \(i\) trong số này biểu diễn đỉnh thứ \(i\) và phải chứa đúng \(y\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) phải là:

• 1 nếu đỉnh thứ \(i\) và đỉnh thứ \(j\) được nối bởi một cạnh;
• 0 nếu không có cạnh như vậy.

Ma trận này phải đối xứng và mọi phần tử trên đường chéo chính phải là 0.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào. Đề bài bảo đảm tồn tại đáp án cho mọi \(K\) thuộc giới hạn.

Ràng buộc

• \(1 \le T \le 300\).
• \(3 \le K \le 10000\).
• Bài chỉ có một Test Set và không có Test Set lớn.
• Có thể nộp lại Test Set này; mỗi lần thử lại chịu hình phạt thời gian theo quy định của cuộc thi gốc.

Phân nhóm

• Test Set 1 (Visible): \(3 \le K \le 10000\).

Đ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
3
8

Case #1: 3
011
101
110
Case #2: 4
0111
1001
1001
1110

1-2, 1-3, 1-4
1-2, 1-3, 2-4
1-2, 1-3, 3-4
1-2, 1-4, 3-4
1-2, 2-4, 3-4
1-3, 1-4, 2-4
1-3, 2-4, 3-4
1-4, 2-4, 3-4

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Spanning Planning.

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 chơi một trò solitaire với \(N\) chồng bài ngửa, ban đầu mỗi chồng có \(C\) lá. Mỗi lá có một giá trị và một chất; không có hai lá nào trong cùng ván mang cùng cặp giá trị/chất.

Trong một nước đi, bạn được làm đúng một trong hai việc:

• Nếu trên đỉnh các chồng khác nhau có ít nhất hai lá cùng chất, bỏ khỏi ván lá có giá trị nhỏ nhất trong số các lá ấy. Khi bỏ lá cuối cùng, chồng vẫn tồn tại nhưng trở thành chồng rỗng.
• Nếu có một chồng rỗng, lấy lá trên đỉnh của một chồng không rỗng bất kỳ và đặt nó lên chồng rỗng (khi đó nó là lá duy nhất trong chồng ấy).

Bạn thắng nếu có thể thực hiện một dãy nước đi để cuối cùng mỗi chồng chứa nhiều nhất một lá. Hãy xác định có thể thắng từ cách xếp ban đầu hay không.

Dữ liệu vào

Dòng đầu chứa số chồng dựng sẵn \(P\) dùng trong các test. Sau đó là \(P\) dòng. Dòng thứ \(i\) bắt đầu bằng \(C_i\), số lá của chồng dựng sẵn thứ \(i\), rồi đến \(C_i\) cặp số \((V_{ij},S_{ij})\). Cặp thứ \(j\) cho giá trị và chất của lá thứ \(j\) tính từ đỉnh xuống.

Tiếp theo là một dòng chứa số test \(T\). Mỗi test bắt đầu bằng \(N,C\), lần lượt là số chồng và số lá trong mỗi chồng của test. Dòng sau chứa \(N\) chỉ số \(P_i\) (đánh số từ 0), chỉ ra các chồng dựng sẵn được dùng.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1 và y là POSSIBLE nếu có thể thắng, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

• \(1\le T\le100\).
• \(2\le P\le60000\).
• \(0\le P_i<P\).
• Chồng dựng sẵn thứ \(P_i\) có đúng \(C\) lá.
• Không có hai lá trong một test mang cùng cặp giá trị/chất.

Phân nhóm

• Test Set 1 (Visible): \(2\le N\le4\); \(2\le C_i\le13\); \(2\le C\le13\); \(1\le V_{ij}\le13\); \(1\le S_{ij}\le4\).
• Test Set 2 (Hidden): \(2\le N\le50000\); \(2\le C_i\le50000\); \(2\le C\le50000\); \(4\le N\times C\le10^5\); \(1\le V_{ij},S_{ij}\le50000\).

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

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Stack Management.

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

Trong một tương lai rất gần, ở một thiên hà lân cận, bạn muốn tạm rời trách nhiệm là nhà sản xuất sợi duy nhất của hành tinh Thundera để du lịch tới Care-a-Lot, hành tinh thư giãn nhất. Phương tiện duy nhất là mạng máy dịch chuyển liên sao.

Một máy dịch chuyển là thiết bị nhỏ trôi ở một điểm trong không gian. Bạn có thể kích hoạt nó từ xa tại bất kỳ điểm nào, nhưng theo nguyên lý bảo toàn khoảng cách dịch chuyển, nó chỉ có thể đưa bạn tới một điểm khác có đúng cùng khoảng cách \(L_1\) đến máy như trước khi dịch chuyển. Với hai điểm \((x_0,y_0,z_0)\) và \((x_1,y_1,z_1)\), khoảng cách ấy là

Ba lô phản lực đã hỏng nên bạn không thể tự di chuyển. Bạn bắt đầu ở Thundera, có thể dùng một máy để tới \(p_1\), dùng một máy khác (hoặc lại máy cũ) để tới \(p_2\), v.v.; lần dịch chuyển cuối phải đưa bạn tới chính xác Care-a-Lot.

Biết tọa độ hai hành tinh và mọi máy dịch chuyển, hãy xác định chuyến đi có thể thực hiện hay không; nếu có, tìm số lần dịch chuyển ít nhất. Hai lần dùng cùng một máy vẫn được tính là hai lần dịch chuyển riêng biệt.

Mọi tọa độ trong input là số nguyên thuộc phạm vi cho trước. Tuy nhiên, các điểm trung gian được phép có tọa độ nguyên hoặc không nguyên và không bị giới hạn phạm vi.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng số nguyên \(N\), số máy dịch chuyển. Tiếp theo là \(N+2\) dòng, mỗi dòng chứa ba số nguyên \(X_i,Y_i,Z_i\). Dòng đầu trong số này là tọa độ Thundera, dòng thứ hai là tọa độ Care-a-Lot, và \(N\) dòng còn lại lần lượt là tọa độ các máy.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1. Nếu không thể tới Care-a-Lot thì y là IMPOSSIBLE; nếu có thể thì y là số lần dịch chuyển ít nhất.

Ràng buộc

• \(1\le T\le100\).
• \((X_i,Y_i,Z_i) e(X_j,Y_j,Z_j)\) với mọi \(i e j\); không có hai vật thể được mô tả ở cùng tọa độ.

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le100\) và \(-10^3\le X_i,Y_i,Z_i\le10^3\).
• Test Set 2 (Hidden): \(1\le N\le150\) và \(-10^{12}\le X_i,Y_i,Z_i\le10^{12}\).

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

Case #1: IMPOSSIBLE
Case #2: 3
Case #3: 2

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Teleporters.

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