Google Code Jam 2015 - Round 3

Đất nước Fairland có những luật rất nghiêm ngặt về cách các công ty tổ chức và trả lương cho nhân viên:

1. Mỗi công ty phải có đúng một CEO, người không có quản lý.
2. Mọi nhân viên trừ CEO phải có đúng một quản lý. Vì thế sơ đồ tổ chức gồm toàn bộ nhân viên là một cây, không có chu trình.
3. Trong suốt thời gian một nhân viên còn làm việc cho công ty, quản lý của họ không bao giờ được thay đổi. Do đó, nếu một quản lý rời công ty thì tất cả nhân viên báo cáo cho người đó cũng phải rời công ty.
4. CEO không bao giờ được rời công ty.
5. Mỗi nhân viên nhận một mức lương, tức một số đô-la Fairland mỗi năm. Lương của một nhân viên không bao giờ được thay đổi.
6. Các nhân viên khác nhau có thể có mức lương khác nhau, và lương của một nhân viên không nhất thiết liên quan đến vị trí của họ trong sơ đồ tổ chức.

Chính phủ Fairland vừa thông qua thêm một luật:

1. Chênh lệch giữa mức lương lớn nhất và nhỏ nhất trong toàn công ty không được vượt quá \(D\) đô-la Fairland.

Marie là CEO của Fairland General Stuff Corporation và phải bảo đảm công ty tuân thủ luật mới. Điều này có thể buộc cô phải cho một số nhân viên nghỉ việc. Marie có danh sách nhân viên, quản lý và mức lương của họ. Hãy tìm số nhân viên lớn nhất cô có thể giữ lại, tính cả chính cô.

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 gồm hai số nguyên \(N\) (số nhân viên) và \(D\) (chênh lệch lương tối đa được phép). Tiếp theo là một dòng chứa bốn số nguyên \(S_0,A_s,C_s,R_s\), rồi một dòng chứa bốn số nguyên \(M_0,A_m,C_m,R_m\). Tám số cuối xác định hai dãy:

Marie có ID 0; các nhân viên còn lại có ID từ 1 đến \(N-1\). Lương của nhân viên \(i\) là \(S_i\). Với mọi nhân viên \(i\) khác Marie, quản lý của họ là \(M_i\bmod i\). Lưu ý rằng \(M_0\) không ảnh hưởng đến quản lý của Marie vì cô không có quản lý.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số nhân viên lớn nhất Marie có thể giữ lại trong công ty, tính cả cô, sao cho cả bảy luật đều được tuân thủ.

Ràng buộc

• \(1\le T\le100\).
• \(0\le S_0<R_s\).
• \(0\le M_0<R_m\).
• \(0\le A_s,A_m\le1000\).
• \(0\le C_s,C_m\le10^9\).

Phân nhóm

• Tập nhỏ: \(1\le N\le1000\); \(1\le D\le1000\); \(1\le R_s,R_m\le1000\).
• Tập lớn: \(1\le N\le10^6\); \(1\le D\le10^6\); \(1\le R_s,R_m\le10^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ụ

3
1 395
18 246 615815 60
73 228 14618 195
6 5
10 1 3 17
5 2 7 19
10 13
28 931 601463 36
231 539 556432 258

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

Nguồn

Google Code Jam 2015, Vòng 3, bài Fairland.

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

Tập lũy thừa của một tập \(S\) là tập hợp tất cả các tập con của \(S\), bao gồm tập rỗng và chính \(S\). Đi từ một tập đến tập lũy thừa của nó thì dễ, nhưng trong bài này ta sẽ đi theo chiều ngược lại!

Ta bắt đầu với một tập các số nguyên \(S\) mà các phần tử không nhất thiết phân biệt, tìm tập lũy thừa của nó, rồi thay mỗi phần tử của tập lũy thừa (tức mỗi tập con) bằng tổng các phần tử trong tập con đó để tạo ra một tập mới \(S'\). Ví dụ, nếu \(S=\{-1,1\}\) thì tập lũy thừa là \(\{\{\},\{-1\},\{1\},\{-1,1\}\}\), nên \(S'=\{0,-1,1,0\}\). \(S'\) được phép chứa phần tử trùng nhau; vì vậy nếu \(S\) có \(N\) phần tử thì \(S'\) luôn có đúng \(2^N\) phần tử.

Cho mô tả các phần tử của \(S'\) và tần suất của chúng, hãy xác định tập \(S\) ban đầu. Đề bảo đảm tồn tại \(S\). Nếu có nhiều tập \(S\) có thể tạo ra \(S'\), đề bảo đảm tập ban đầu là tập sớm nhất trong số đó. Để so sánh hai tập khác nhau \(S_1\) và \(S_2\) có cùng số phần tử, hãy sắp xếp mỗi tập theo thứ tự không giảm rồi xét vị trí đầu tiên từ trái sang mà chúng khác nhau. \(S_1\) sớm hơn khi và chỉ khi phần tử tại vị trí đó trong \(S_1\) nhỏ hơn phần tử tương ứng trong \(S_2\).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(P\), sau đó là hai dòng, mỗi dòng chứa \(P\) số nguyên cách nhau bởi dấu cách. Dòng đầu trong hai dòng này chứa tất cả các giá trị khác nhau \(E_1,E_2,\ldots,E_P\) xuất hiện trong \(S'\), được sắp xếp tăng dần. Dòng thứ hai chứa các tần suất \(F_1,F_2,\ldots,F_P\). Nói cách khác, với mọi \(i\), giá trị \(E_i\) xuất hiện đúng \(F_i\) lần trong \(S'\).

Dữ liệu ra

Với mỗi bộ test, in một dòng bắt đầu bằng Case #x:, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), rồi in các phần tử của tập \(S\) ban đầu, cách nhau bởi dấu cách và theo thứ tự không giảm. Bạn phải liệt kê trực tiếp các phần tử của \(S\), không dùng hai danh sách giá trị và tần suất như cách dữ liệu vào mô tả \(S'\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le P\le10000\).
• \(F_i\ge1\).

Phân nhóm

• Tập nhỏ: \(S\) có từ 1 đến 20 phần tử; \(0\le E_i\le10^8\).
• Tập lớn: \(S\) có từ 1 đến 60 phần tử; \(-10^{10}\le E_i\le10^{10}\).

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

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

Nguồn

Google Code Jam 2015, Vòng 3, bài Log Set.

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

Thành phố nơi bạn sống nằm bên bờ dòng sông Binary kỳ vĩ. Nước sông đến từ một số phụ lưu bắt nguồn tận trên núi. Không may cho thành phố, những người nông dân sống trên núi cần dùng một phần nước trong các phụ lưu để tưới cây.

Từ lâu, thành phố đã thỏa thuận cho nông dân canh tác mà vẫn duy trì dòng sông: mỗi nông dân được dùng nước cho ruộng đúng một nửa thời gian. Họ luân phiên chuyển nước vào ruộng trong một ngày rồi để nước chảy xuống sông trong một ngày. Kết quả lại là thảm họa! Vì việc dùng nước của tất cả nông dân đồng bộ, ai cũng cùng chuyển nước hoặc cùng không chuyển nước, nên cứ một ngày sông lại cạn, ngày kế tiếp thành phố lại ngập lụt.

Để giải quyết vấn đề, thành phố yêu cầu mỗi nông dân chọn một lũy thừa nguyên nào đó của 2 (dù sao đây cũng là sông Binary) trong đoạn từ 1 đến \(D\), rồi cứ mỗi khi số ngày ấy trôi qua lại đổi trạng thái sử dụng nước: bắt đầu hoặc dừng lấy nước. Không nhất thiết mọi lũy thừa của 2 từ 1 đến \(D\) đều được chọn, và nhiều nông dân có thể chọn cùng một số. Số 1 cũng được tính là một lũy thừa của 2. Ý tưởng là làm tổng lượng nước sử dụng đều hơn để hạn hán và lũ lụt ít xảy ra hơn.

Chuyện đó đã diễn ra từ lâu. Gần đây, bạn và những người dân khác bắt đầu nghi ngờ rằng nông dân không tuân thủ thỏa thuận; thậm chí bạn còn không biết hiện có bao nhiêu nông dân. Dữ liệu duy nhất là lịch sử lưu lượng nước qua thành phố trong \(N\) ngày. Bạn có thể xác định họ có trung thực không?

Mỗi phụ lưu có lưu lượng 1, và lưu lượng sông chính bằng tổng lưu lượng của mọi phụ lưu không bị chuyển nước sang ruộng. Trước khi xem bản ghi, bạn không biết có bao nhiêu phụ lưu. Mỗi phụ lưu bị nhiều nhất một nông dân chuyển nước, nhưng có thể có những phụ lưu không bao giờ bị ai chuyển nước. Các chu kỳ chuyển nước đã bắt đầu từ rất lâu trước khi thành phố ghi nhận lưu lượng, và không có gì bảo đảm chúng cùng bắt đầu vào một ngày.

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\), \(D\) cách nhau bởi dấu cách. Dòng tiếp theo chứa \(N\) số nguyên; số thứ \(i\), ký hiệu \(d_i\), là lưu lượng sông trong ngày thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: M, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(M\) là số nông dân nhỏ nhất có thể đang chuyển nước khỏi các phụ lưu theo đúng mô hình đã mô tả và phù hợp với lưu lượng quan sát được.

Nếu chắc chắn có ít nhất một nông dân đang hoạt động nhưng dữ liệu đã cho không thể được giải thích bởi các nông dân tuân thủ quy tắc, in CHEATERS! thay cho một số.

Ràng buộc

• \(1\le T\le50\).
• \(D\) là một lũy thừa của 2.
• \(1\le D\le\lfloor N/2\rfloor\).

Phân nhóm

• Tập nhỏ: \(1\le N\le50\); \(0\le d_i\le5\).
• Tập lớn: \(1\le N\le5000\); \(0\le d_i\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ụ

4
5 2
2 2 2 2 2
6 2
1 1 1 0 0 0
8 4
2 1 1 0 0 1 1 2
8 4
0 1 1 3 1 2 2 2

Case #1: 0
Case #2: CHEATERS!
Case #3: 2
Case #4: 3

Nguồn

Google Code Jam 2015, Vòng 3, bài River Flow.

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

Ôi không — cả \(N\) con chim cút nuôi của bạn đều đã sổng mất! Hiện bạn ở vị trí 0 trên một đường thẳng. Con chim thứ \(i\) bắt đầu tại vị trí nguyên khác 0 là \(P_i\) mét trên đường thẳng đó và liên tục chạy ra xa bạn với vận tốc nguyên không đổi \(S_i\) mét mỗi giây. Bạn có thể chạy với vận tốc nguyên không đổi \(Y\) mét mỗi giây và đổi hướng tức thời bất cứ lúc nào. Lưu ý rằng chim cút luôn chạy ra xa bạn, kể cả khi lúc đó bạn không chạy về phía chúng. Bất cứ khi nào bạn và một con chim ở cùng một điểm, con chim ấy được bắt mà không tốn thêm thời gian.

Hãy tìm số giây nhỏ nhất cần để bắt tất cả chim cút.

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 gồm hai số nguyên \(Y\) (vận tốc của bạn) và \(N\) (số chim cút), rồi đến hai dòng, mỗi dòng chứa \(N\) số nguyên cách nhau bởi dấu cách. Dòng đầu trong hai dòng này chứa các vị trí \(P_i\) của chim; dòng thứ hai chứa các vận tốc \(S_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số giây nhỏ nhất cần để bắt hết chim.

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

Ràng buộc

• \(1\le T\le100\).
• \(2\le Y\le1000\).
• \(-10^7\le P_i\le10^7\) và không có \(P_i\) nào bằng 0.
• \(1\le S_i<Y\).

Phân nhóm

• Tập nhỏ: \(1\le N\le25\).
• Tập lớn: \(1\le N\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ụ

2
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1

Case #1: 3.000000
Case #2: 5.000000

Nguồn

Google Code Jam 2015, Vòng 3, bài Runaway Quail.

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

Adamma là một nhà khoa học khí hậu quan tâm đến nhiệt độ. Mỗi phút, cô ghi lại nhiệt độ hiện tại dưới dạng số nguyên, tạo thành một danh sách dài \(x_1,x_2,\ldots,x_N\). Adamma dùng thang nhiệt độ riêng thay vì những thang quen thuộc như Celsius hay Kelvin, nên các giá trị có thể rất lớn và âm. Cô thường vẽ đồ thị các nhiệt độ này trên màn hình máy tính.

Sáng nay, Adamma quyết định tính trung bình trượt của danh sách để có một đồ thị mượt hơn. Cô dùng cửa sổ làm mượt kích thước \(K\), nghĩa là biến dãy \(N\) nhiệt độ thành dãy \(N-K+1\) nhiệt độ trung bình \(s_1,s_2,\ldots,s_{N-K+1}\). Mỗi \(s_i\) là trung bình của \(x_i,x_{i+1},\ldots,x_{i+K-1}\). Các giá trị \(x_i\) ban đầu đều là số nguyên, nhưng một số \(s_i\) có thể là phân số.

Không may, Adamma quên lưu dãy nhiệt độ ban đầu! Bây giờ cô muốn trả lời một câu hỏi khác: chênh lệch giữa nhiệt độ lớn nhất và nhỏ nhất là bao nhiêu? Nói cách khác, cô cần tính

Nhưng cô chỉ còn \(N\), \(K\) và dãy đã làm mượt.

Sau khi suy nghĩ, Adamma nhận ra có thể không xác định được duy nhất vì có nhiều dãy ban đầu hợp lệ. Trong trường hợp đó, cô muốn biết đáp án nhỏ nhất trong tất cả các dãy ban đầu có thể tạo ra dãy làm mượt với \(N\) và \(K\) đã cho.

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\), \(K\) cách nhau bởi dấu cách. Dòng thứ hai chứa các số nguyên \(\mathrm{sum}_1,\mathrm{sum}_2,\ldots,\mathrm{sum}_{N-K+1}\) cách nhau bởi dấu cách, trong đó \(s_i=\mathrm{sum}_i/K\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là chênh lệch nhỏ nhất có thể giữa nhiệt độ lớn nhất và nhỏ nhất.

Ràng buộc

• \(1\le T\le100\).
• \(2\le K\le N\).
• Mỗi \(\mathrm{sum}_i\) là một số nguyên trong đoạn \([-10000,10000]\).

Phân nhóm

• Tập nhỏ: \(2\le N\le100\).
• Tập lớn: \(2\le N\le1000\); \(2\le K\le100\).

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

Case #1: 5
Case #2: 0
Case #3: 12

Nguồn

Google Code Jam 2015, Vòng 3, bài Smoothing Window.

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