Google Code Jam 2008 - Round 2

Trong bài toán này, chúng ta sẽ xem xét một loại cây nhị phân được gọi là cây boolean. Trong cây này, mọi hàng đều được lấp đầy hoàn toàn, ngoại trừ có thể là hàng cuối cùng (sâu nhất), và các nút ở hàng cuối cùng nằm xa nhất về bên trái có thể. Ngoài ra, mọi nút trong cây sẽ có 0 hoặc 2 con.

Điều làm cho cây boolean trở nên đặc biệt là mỗi nút có một giá trị boolean đi kèm, 1 hoặc 0. Ngoài ra, mỗi nút nội bộ (nút không phải lá) có một cổng "AND" hoặc "OR" đi kèm. Giá trị của một nút cổng "AND" được tính bằng phép AND logic của giá trị hai con của nó. Tương tự, giá trị của một nút cổng "OR" được tính bằng phép OR logic của giá trị hai con của nó. Giá trị của tất cả các nút lá sẽ được cho trong dữ liệu vào để giá trị của tất cả các nút có thể được tính toán ngược lên cây.

Gốc của cây là đối tượng chúng ta đặc biệt quan tâm. Chúng ta rất muốn gốc có giá trị \(V\), là 1 hoặc 0. Tuy nhiên, đây có thể không phải là giá trị thực tế của gốc. May mắn thay, chúng ta có thể gian lận và thay đổi loại cổng cho một số nút; chúng ta có thể đổi cổng AND thành cổng OR hoặc cổng OR thành cổng AND.

Cho mô tả về một cây boolean và những cổng nào có thể thay đổi được, hãy tìm số lượng cổng tối thiểu cần thay đổi để làm cho giá trị của nút gốc trở thành \(V\). Nếu điều này là không thể, hãy xuất "IMPOSSIBLE".

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.

Mỗi bộ test bắt đầu bằng \(M\) và \(V\). \(M\) đại diện cho số lượng nút trong cây và sẽ là số lẻ để đảm bảo tất cả các nút có 0 hoặc 2 con. \(V\) là giá trị mong muốn cho nút gốc, 0 hoặc 1.

\(M\) dòng tiếp theo mô tả từng nút của cây. Dòng thứ \(X\) sẽ mô tả nút \(X\), bắt đầu với nút 1 ở dòng đầu tiên.

\((M-1)/2\) dòng đầu tiên mô tả các nút nội bộ. Mỗi dòng chứa \(G\) và \(C\), mỗi giá trị là 0 hoặc 1. Nếu \(G\) là 1 thì cổng cho nút này là cổng AND, ngược lại là cổng OR. Nếu \(C\) là 1 thì cổng cho nút này có thể thay đổi được, ngược lại thì không. Nút nội bộ \(X\) có các nút \(2X\) và \(2X+1\) là con.

\((M+1)/2\) dòng tiếp theo mô tả các nút lá. Mỗi dòng chứa một giá trị \(I\), 0 hoặc 1, là giá trị của nút lá.

Để giúp hình dung, đây là hình ảnh của cây trong ví dụ đầu tiên.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là số lượng cổng tối thiểu phải thay đổi để làm cho đầu ra của nút gốc là \(V\), hoặc "IMPOSSIBLE" nếu điều này là không thể.

Case #X: Y

Ràng buộc

• \(1 < N \le 20\)

Phân nhóm

• Small dataset (Test set 1): \(2 < M < 30\)
• Large dataset (Test set 2): \(2 < M < 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
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
5 0
1 1
0 0
1
1
0

Case #1: 1
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2008, Vòng 2, bài Cheating a Boolean Tree.

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 vừa phát minh ra một phiên bản sửa đổi nhẹ của thuật toán nén run-length encoding (RLE), gọi là PermRLE.

Để nén một chuỗi, thuật toán này chọn một hoán vị của các số nguyên từ \(1\) đến \(k\), áp dụng hoán vị này cho \(k\) chữ cái đầu tiên của chuỗi đã cho, sau đó cho khối \(k\) chữ cái tiếp theo, và cứ tiếp tục như vậy. Độ dài của chuỗi phải chia hết cho \(k\). Sau khi hoán vị tất cả các khối, chuỗi mới được nén bằng RLE, được mô tả sau đây.

Việc áp dụng hoán vị \(p\) cho một khối \(k\) chữ cái có nghĩa là đặt chữ cái thứ \(p[1]\) của khối này vào vị trí đầu tiên, sau đó là chữ cái thứ \(p[2]\) vào vị trí thứ hai, và cứ tiếp tục như vậy. Ví dụ, áp dụng hoán vị \(\{3,1,4,2\}\) cho khối "abcd" sẽ thu được "cadb". Áp dụng nó cho chuỗi dài hơn "abcdefghijkl" theo từng khối sẽ thu được "cadbgehfkilj".

Chuỗi đã hoán vị sau đó được nén bằng run-length encoding. Để đơn giản, chúng ta sẽ coi kích thước nén của chuỗi là số lượng các nhóm chữ cái bằng nhau liên tiếp. Ví dụ, kích thước nén của "aabcaaaa" là 4; nhóm đầu tiên trong bốn nhóm là một nhóm gồm hai chữ cái "a", sau đó là hai nhóm "b" và "c" mỗi nhóm chỉ chứa một chữ cái, và cuối cùng là một nhóm chữ cái "a" dài hơn.

Rõ ràng, kích thước nén có thể phụ thuộc vào hoán vị được chọn. Vì mục tiêu của các thuật toán nén là giảm thiểu kích thước của văn bản nén, nhiệm vụ của bạn là chọn hoán vị mang lại kích thước nén nhỏ nhất có thể và xuất ra kích thước đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test sẽ chứa \(k\). Dòng thứ hai sẽ chứa \(S\), chuỗi cần được nén.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất ra một dòng chứa "Case #\(X\): \(Y\)" (dấu ngoặc kép để rõ ràng) trong đó \(X\) là số thứ tự của bộ test và \(Y\) là kích thước nén tối thiểu của \(S\).

Ràng buộc

• \(N = 20\)
• \(S\) sẽ chỉ chứa các chữ cái tiếng Anh viết thường từ 'a' đến 'z'
• Độ dài của \(S\) sẽ chia hết cho \(k\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(2 \le k \le 5\)
• \(1 \le \text{length of } S \le 1000\)
• Large dataset (Test set 2 - Hidden):
• \(2 \le k \le 16\)
• \(1 \le \text{length of } S \le 50000\)

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

Case #1: 7
Case #2: 12

Nguồn

Google Code Jam 2008, Vòng 2, bài PermRLE.

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

Gần hành tinh Hỏa, trong một thiên hà xa xôi kỳ lạ rất giống với thiên hà của chúng ta, đang diễn ra một cuộc chiến sinh tử giữa lực lượng đế chế và quân phiến loạn. Quân đội phiến loạn có \(N\) con tàu, chúng ta sẽ coi chúng là các điểm \((x_i, y_i, z_i)\). Mỗi con tàu có một bộ thu với công suất \(p_i\). Quân phiến loạn cần có khả năng gửi thông điệp từ tàu tuần dương trung tâm đến tất cả các con tàu, nhưng họ đang eo hẹp về tài chính nên không thể trang bị một bộ phát quá mạnh.

Nếu tàu tuần dương được đặt tại \((x, y, z)\), và một trong các con tàu khác ở \((x_i, y_i, z_i)\) có bộ thu công suất \(p_i\), thì công suất bộ phát của tàu tuần dương cần ít nhất là:

(|xi - x| + |yi - y| + |zi - z|) / pi

Nhiệm vụ của bạn là tìm vị trí đặt tàu tuần dương sao cho cực tiểu hóa công suất cần thiết cho bộ phát của nó, và in ra công suất đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test nối tiếp theo sau.

Mỗi bộ test chứa số nguyên \(N\) ở dòng đầu tiên, là số lượng con tàu trong bộ test đó.

\(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_i, y_i, z_i\) và \(p_i\), cách nhau bởi các khoảng trắng đơn. Đây là tọa độ của con tàu thứ \(i\) và công suất bộ thu của nó. Có thể có nhiều hơn một con tàu ở cùng một tọa độ.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất ra:

Case #X: Y

trong đó X là số thứ tự của bộ test và Y là công suất tối thiểu đủ để tiếp cận tất cả các con tàu trong hạm đội. Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le T \le 10\)
• \(0 \le x_i, y_i, z_i \le 10^6\)
• \(1 \le p_i \le 10^6\)

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le N \le 10\)
• Large dataset (Test set 2 - Hidden): \(1 \le N \le 1000\)

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

Case #1: 3.50000000
Case #2: 0.00000000
Case #3: 2.33333333

Nguồn

Google Code Jam 2008, Vòng 2, bài Star Wars.

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

Tangor, cậu bé mười tuổi, vừa khám phá ra cách tính diện tích của một hình tam giác. Là một cậu bé thông minh, cậu ngạc nhiên trước việc có rất nhiều cách khác nhau để tính diện tích. Cậu cũng tự thuyết phục bản thân rằng, nếu tất cả các đỉnh của tam giác đều có tọa độ nguyên, thì diện tích của tam giác đó luôn là một số nguyên hoặc một nửa của một số nguyên! Thật thú vị phải không?

Nhưng hôm nay Tangor đang cố gắng làm điều ngược lại. Thay vì lấy một hình tam giác và tính diện tích của nó, cậu ấy lấy một số nguyên \(A\) và cố gắng vẽ một hình tam giác có diện tích là \(A/2\). Cậu ấy tự giới hạn mình chỉ sử dụng các điểm nguyên trên giấy kẻ ô vuông để làm các đỉnh của tam giác.

Chính xác hơn, tờ giấy kẻ ô vuông được chia thành một lưới các ô vuông kích thước \(N \times M\). Các đỉnh của tam giác chỉ có thể được đặt tại các góc của các ô đó. Nếu bạn tưởng tượng một hệ tọa độ trên tờ giấy, thì các điểm này có dạng \((x, y)\), trong đó \(x\) và \(y\) là các số nguyên sao cho \(0 \le x \le N\) và \(0 \le y \le M\).

Cho số nguyên \(A\), hãy giúp Tangor tìm ba điểm nguyên trên tờ giấy kẻ ô vuông sao cho diện tích của tam giác tạo bởi các điểm đó đúng bằng \(A/2\), nếu có thể. Trong trường hợp có nhiều cách để thực hiện việc này, bất kỳ giải pháp nào cũng sẽ làm cậu ấy hài lòng.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(C\), số lượng bộ dữ liệu trong tệp đầu vào.
• \(C\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(N, M\), và \(A\) như mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng. Nếu không có cách nào thỏa mãn điều kiện, in ra:

Case #k: IMPOSSIBLE

Case #k: x1 y1 x2 y2 x3 y3

Ràng buộc

• \(0 \le C \le 1000\)
• \(1 \le A \le 10^8\)

Phân nhóm

• Small dataset (Tập kiểm tra 1 - Công khai): \(1 \le N \le 50, 1 \le M \le 50\).
• Large dataset (Tập kiểm tra 2 - Ẩn): \(1 \le N \le 10000, 1 \le M \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ụ

3
1 1 1
1 2 64
10 10 1

Case #1: 0 0 0 1 1 1
Case #2: IMPOSSIBLE
Case #3: 1 1 2 3 5 8

Nguồn

Google Code Jam 2008, Vòng 2, bài Triangle Areas.

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