Google Code Jam 2010 - Round 1A

Bạn có một mảng một chiều gồm \(N\) điểm ảnh (pixel). Mỗi điểm ảnh có một giá trị, được biểu diễn bằng một số nguyên từ \(0\) đến \(255\). Khoảng cách giữa hai điểm ảnh là giá trị tuyệt đối của hiệu giữa hai giá trị của chúng.

Bạn có thể thực hiện mỗi thao tác sau đây không giới hạn số lần:

1. Với chi phí \(D\), xóa bất kỳ điểm ảnh nào, khi đó các điểm ảnh lân cận ban đầu của nó sẽ trở thành lân cận của nhau.
2. Với chi phí \(I\), chèn một điểm ảnh có giá trị bất kỳ vào bất kỳ vị trí nào — giữa hai điểm ảnh hiện có, trước điểm ảnh đầu tiên, hoặc sau điểm ảnh cuối cùng.
3. Bạn có thể thay đổi giá trị của bất kỳ điểm ảnh nào. Chi phí là giá trị tuyệt đối của hiệu giữa giá trị cũ và giá trị mới của điểm ảnh đó.

Mảng được gọi là mượt (smooth) nếu bất kỳ hai điểm ảnh lân cận nào cũng có khoảng cách tối đa là \(M\). Hãy tìm chi phí tối thiểu để thực hiện một chuỗi các thao tác làm cho mảng trở nên mượt.

Lưu ý: Mảng rỗng — mảng không chứa điểm ảnh nào — được coi là mượ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 theo sau, mỗi bộ gồm hai dòng. Dòng đầu tiên có dạng "\(D\) \(I\) \(M\) \(N\)", dòng tiếp theo chứa \(N\) số \(a_i\): giá trị của các điểm ảnh từ trái sang phải.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là chi phí tối thiểu để làm cho mảng đầu vào trở nên mượt.

Ràng buộc

• Tất cả các số trong dữ liệu vào là số nguyên.
• \(1 \le T \le 100\)
• \(0 \le D, I, M, a_i \le 255\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 3\).
• Large dataset (Test set 2): \(1 \le N \le 100\).

Đ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
6 6 2 3
1 7 5
100 1 5 3
1 50 7

Case #1: 4
Case #2: 17

Nguồn

Google Code Jam 2010, Vòng 1A, bài Make it Smooth.

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

Arya và Bran chơi với hai số nguyên dương \(A,B\) trên bảng, Arya đi trước. Mỗi lượt, người chơi thay \(A\) bằng \(A-kB\), hoặc \(B\) bằng \(B-kA\), với số nguyên dương \(k\). Người đầu tiên làm một số giảm xuống 0 hoặc âm sẽ thua.

Ví dụ từ \((12,51)\): Arya đổi 51 thành \(51-3\cdot12=15\); Bran đổi 15 thành 3; Arya đổi 12 thành 3; Bran buộc đổi một số 3 thành 0 và thua.

Gọi \((A,B)\) là thế thắng nếu Arya có thể chắc chắn thắng bất kể Bran chơi thế nào. Cho \(A_1,A_2,B_1,B_2\), hãy đếm số thế thắng với \(A_1\le A\le A_2\) và \(B_1\le B\le B_2\).

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm bốn số \(A_1,A_2,B_1,B_2\).

Dữ liệu ra

In Case #x: y, với \(y\) là số thế thắng trong hình chữ nhật đã cho.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_1\le A_2\le10^6\), \(1\le B_1\le B_2\le10^6\).
• Bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(A_2-A_1\le30\), \(B_2-B_1\le30\).
• Lớn: các hiệu không quá 999999.

Đ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
5 5 8 8
11 11 2 2
1 6 1 6

Case #1: 0
Case #2: 1
Case #3: 20

Nguồn

Google Code Jam 2010, Vòng 1A, bài Number Game.

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 trò Join-\(K\), quân đỏ và xanh rơi vào bảng \(N\times N\) dựng đứng, tới ô trống thấp nhất trong cột.

    - Legal Position -

          .......
          .......
          .......
          ....R..
          ...RB..
          ..BRB..
          .RBBR..

   - Illegal Position -

          .......
          .......
          .......
          .......
   Bad -> ..BR...
          ...R...
          .RBBR..

. là ô trống, R đỏ, B xanh. Hình trái hợp lệ; hình phải không hợp lệ vì quân được đánh dấu chưa rơi xuống ô trống bên dưới.

Người chơi thắng nếu có ít nhất \(K\) quân cùng màu liên tiếp theo ngang, dọc hoặc chéo:

      - Four in a row -

     R   RRRR    R   R
     R          R     R
     R         R       R
     R        R         R

Bạn bí mật xoay bảng 90 độ theo chiều kim đồng hồ. Sau khi xoay hoàn toàn, trọng lực làm quân rơi xuống:

    - Start -

     .......
     .......
     .......
     ...R...
     ...RB..
     ..BRB..
     .RBBR..

   - Rotate -

     .......
     R......
     BB.....
     BRRR...
     RBB....
     .......
     .......

   - Gravity -

     .......
     .......
     .......
     R......
     BB.....
     BRR....
     RBBR...

Chỉ được xoay một lần; trọng lực chỉ tác dụng sau khi xoay xong; chỉ xét người thắng sau khi quân rơi xong. Hãy xác định màu nào tạo được \(K\) quân liên tiếp.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,K\), rồi \(N\) dòng dài đúng \(N\) mô tả một thế hợp lệ; ban đầu chưa màu nào có \(K\) quân liên tiếp.

Dữ liệu ra

In Case #x: y, với y là Red, Blue, Neither hoặc Both.

Ràng buộc

• \(1\le T\le100\), \(3\le K\le N\); thời gian 30 giây; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(3\le N\le7\).
• Lớn: \(3\le N\le50\).

Đ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
7 3
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
6 4
......
......
.R...R
.R..BB
.R.RBR
RB.BBB
4 4
R...
BR..
BR..
BR..
3 3
B..
RB.
RB.

Case #1: Neither
Case #2: Both
Case #3: Red
Case #4: Blue

Nguồn

Google Code Jam 2010, Vòng 1A, bài Rotate.

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