Google Code Jam 2011 - Round 1C

Jeff là thành viên của dàn nhạc giao hưởng Atlantis vĩ đại. Mỗi nhạc công trong dàn nhạc đã quyết định âm thanh mà họ sẽ chơi (để đơn giản, chúng ta giả định mỗi nhạc công chỉ chơi một âm duy nhất). Chúng ta nói hai âm thanh là hòa hợp nếu tần số của bất kỳ âm nào trong số chúng chia hết cho tần số của âm còn lại (đây là một quan niệm về sự hòa hợp khá khắt khe, nhưng người Atlantis nổi tiếng là rất bảo thủ trong âm nhạc). Jeff biết rằng các nốt nhạc mà những người chơi khác chơi không nhất thiết phải hòa hợp với nhau. Anh ấy muốn nốt nhạc của mình cải thiện bản giao hưởng, vì vậy anh ấy muốn chọn nốt nhạc của mình sao cho nó hòa hợp với nốt nhạc của tất cả các nhạc công khác.

Bây giờ, điều này nghe có vẻ đơn giản (vì tất cả các tần số đều là số nguyên dương, Jeff chỉ cần chơi nốt có tần số 1, hoặc ngược lại, Bội chung nhỏ nhất của tất cả các nốt khác), nhưng không may là nhạc cụ của Jeff chỉ có một phạm vi nốt nhạc giới hạn. Hãy giúp Jeff tìm xem liệu có thể chơi một nốt nhạc hòa hợp với tất cả những người khác hay không.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm được mô tả bởi hai dòng. Dòng đầu tiên chứa ba số: N, L và H, biểu thị số lượng nhạc công khác, nốt thấp nhất và nốt cao nhất mà nhạc cụ của Jeff có thể chơi. Dòng thứ hai chứa N số nguyên biểu thị tần số các nốt nhạc được chơi bởi những nhạc công khác.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là chuỗi "NO" (nếu Jeff không thể chơi một nốt nhạc thích hợp), hoặc một tần số khả thi. Nếu có nhiều tần số Jeff có thể chơi, hãy xuất tần số thấp nhất.

Ràng buộc

• \(1 \le \mathbf{T} \le 40\).

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le \mathbf{N} \le 100\).
  • \(1 \le L \le H \le 10000\).
  • Tất cả các tần số không lớn hơn 10000.

• Large dataset (Test set 2 - Hidden):

  • \(1 \le \mathbf{N} \le 10^4\).
  • \(1 \le \mathbf{L} \le \mathbf{H} \le 10^{16}\).
  • Tất cả các tần số không lớn hơn \(10^{16}\).

Đ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 2 100
3 5 7
4 8 16
1 20 5 2

Case #1: NO
Case #2: 10

Nguồn

Google Code Jam 2011, Vòng 1C, bài Perfect Harmony.

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ó một tình huống khẩn cấp trong không gian! Bạn cần điều động soái hạm của hạm đội đi từ ngôi sao \(0\) đến ngôi sao \(N\) càng nhanh càng tốt, đi qua các ngôi sao khác theo thứ tự số tăng dần (\(0 \to 1 \to \dots \to N\)). Soái hạm của bạn bình thường di chuyển với tốc độ \(0,5\) parsec mỗi giờ.

Ngoài việc điều động soái hạm, bạn có thể ra lệnh cho các kỹ sư xây dựng tối đa \(L\) trạm tăng tốc tại các ngôi sao khác nhau. Việc xây dựng một trạm tăng tốc mất \(t\) giờ và tất cả \(L\) trạm tăng tốc có thể được xây dựng song song. Trong khi soái hạm di chuyển từ một ngôi sao đã hoàn thành trạm tăng tốc đến ngôi sao tiếp theo, tốc độ của nó là \(1\) parsec mỗi giờ.

Nếu một trạm tăng tốc được hoàn thành tại một ngôi sao trong khi soái hạm đang di chuyển từ ngôi sao đó đến ngôi sao tiếp theo, soái hạm sẽ bắt đầu di chuyển nhanh hơn ngay khi trạm tăng tốc được hoàn thành.

Hỏi mất bao nhiêu giờ để soái hạm của bạn đến được ngôi sao \(N\) nếu bạn xây dựng các trạm tăng tốc để nó đến nơi sớm nhất có thể?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa các số nguyên \(L, t, N\) và \(C\), theo sau là \(C\) số nguyên \(a_i\), tất cả cách nhau bởi dấu cách. \(a_i\) là số parsec giữa ngôi sao \(k \times C + i\) và ngôi sao \(k \times C + i + 1\), với mọi giá trị nguyên của \(k\).

Ví dụ, với \(N=8, C=3, a_0=3, a_1=5\) và \(a_2=4\), khoảng cách giữa các ngôi sao là \([3, 5, 4, 3, 5, 4, 3, 5]\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một số nguyên duy nhất: số giờ cần thiết để đến được ngôi sao \(N\). Đáp án được đảm bảo luôn là một số nguyên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le C \le 1000\).
• \(C \le N\).
• \(1 \le a_i \le 10^4\).
• \(0 \le t \le 10^{11}\).
• \(t\) là số chẵn.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 1000\); \(0 \le L \le 2\).
• Large dataset (Test set 2): \(1 \le N \le 10^6\); \(0 \le L \le N\).

Đ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 20 8 2 3 5
1 4 2 2 10 4

Case #1: 54
Case #2: 20

Lưu ý: Bài toán này diễn ra trong một vũ trụ nơi tốc độ ánh sáng cao hơn nhiều so với 1 parsec mỗi giờ, vì vậy chúng ta không cần lo lắng về các hiệu ứng thuyết tương đối hẹp.

Nguồn

Google Code Jam 2011, Vòng 1C, bài Space Emergency.

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 bán những bức tranh hình học tuyệt đẹp. Mỗi bức tranh bao gồm các ô vuông kích thước \(1 \times 1\) được sắp xếp thành một lưới không chồng chéo. Ví dụ:

    .##..
    .####
    .####
    .##..

Các ô màu xanh lam được đại diện bởi ký tự #, và các ô màu trắng được đại diện bởi ký tự .. Bạn không sử dụng các màu khác.

Tuy nhiên, không phải ai cũng thích màu xanh lam, và một số khách hàng muốn bạn thay thế tất cả các ô màu xanh trong tranh bằng các ô màu đỏ. Ngặt nỗi, các ô màu đỏ chỉ có kích thước lớn hơn là \(2 \times 2\), điều này khiến việc thay thế trở nên khó khăn.

Bạn có thể che bất kỳ khối ô vuông xanh \(2 \times 2\) nào bằng một ô màu đỏ duy nhất, và lặp lại cho đến khi hoàn tất. Một ô màu đỏ không được đè lên ô màu đỏ khác, không được che các ô màu trắng và không được nằm ngoài phạm vi bức tranh. Ví dụ, bạn có thể thêm các ô màu đỏ vào bức tranh trước đó như sau:

    ./\..
    .\//\
    ./\\/
    .\/..

Mỗi ô màu đỏ ở đây được đại diện bởi một cặp ký tự / ở góc trên bên trái và góc dưới bên phải, và một cặp ký tự \ ở hai góc còn lại.

Cho một bức tranh xanh và trắng, liệu bạn có thể biến nó thành một bức tranh đỏ và trắng theo cách này không?

Dữ liệu vào

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

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa \(R\) và \(C\), số hàng và số cột trong bức tranh. \(R\) dòng tiếp theo, mỗi dòng chứa đúng \(C\) ký tự, mô tả bức tranh. Như đã nêu trên, ký tự # đại diện cho ô màu xanh, và ký tự . đại diện cho ô màu trắng.

Dữ liệu ra

Với mỗi bộ thử nghiệm, đầu tiên in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1).

Nếu có thể che các ô màu xanh bằng các ô màu đỏ không chồng chéo, hãy in ra \(R\) dòng, mỗi dòng chứa \(C\) ký tự, mô tả bức tranh đỏ và trắng thu được. Như trên, các ô màu đỏ nên được đại diện bởi các ký tự / và \, trong khi các ô màu trắng được đại diện bởi ký tự .. Nếu có nhiều giải pháp khả thi, bạn có thể in ra bất kỳ giải pháp nào.

Nếu nhiệm vụ là bất khả thi, hãy in ra một dòng duy nhất chứa văn bản "Impossible".

Ràng buộc

Phân nhóm

• Small dataset (Test set 1): \(1 \le T \le 20\); \(1 \le R \le 6\); \(1 \le C \le 6\).
• Large dataset (Test set 2): \(1 \le T \le 50\); \(1 \le R \le 50\); \(1 \le C \le 50\).

Đ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 3
###
###
1 1
.
4 5
.##..
.####
.####
.##..

Case #1:
Impossible
Case #2:
.
Case #3:
./\..
.\//\
./\\/
.\/..

Nguồn

Google Code Jam 2011, Vòng 1C, bài Square Tiles.

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