Google Code Jam 2008 - Round 1C

Bạn đang lái xe trên đường cao tốc thì bị cảnh sát giao thông bắt vì chạy quá tốc độ. Hóa ra họ đã theo dõi bạn, và họ ngạc nhiên trước thực tế là bạn đã tăng tốc suốt thời gian qua mà không hề sử dụng phanh! Và bây giờ bạn tuyệt vọng tìm một lý do để giải thích điều đó.

Bạn quyết định rằng sẽ hợp lý nếu nói "tất cả các biển báo giới hạn tốc độ mà tôi nhìn thấy đều theo thứ tự tăng dần, đó là lý do tại sao tôi liên tục tăng tốc". Viên cảnh sát cười đáp lại, và cho bạn biết tất cả các biển báo được đặt dọc theo đoạn đường cao tốc bạn đã đi, và nói rằng khó có khả năng bạn may mắn đến mức chỉ nhìn thấy một phần của những biển báo này theo thứ tự tăng dần.

Bây giờ bạn cần ước tính khả năng đó, hay nói cách khác, tìm xem có bao nhiêu dãy con khác nhau của dãy đã cho là tăng nghiêm ngặt. Dãy con rỗng không được tính vì điều đó ngụ ý rằng bạn đã không nhìn vào bất kỳ biển báo giới hạn tốc độ nào cả!

Ví dụ, \((1, 2, 5)\) là một dãy con tăng của \((1, 4, 2, 3, 5, 5)\), và chúng ta đếm nó hai lần vì có hai cách để chọn \((1, 2, 5)\) từ danh sách.

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 theo sau. Dòng đầu tiên của mỗi bộ test chứa n, m, X, Y và Z cách nhau bởi một dấu cách. n sẽ là độ dài của dãy giới hạn tốc độ. m sẽ là độ dài của mảng tạo \(A\). m dòng tiếp theo sẽ chứa m phần tử của \(A\), mỗi dòng một số nguyên (từ \(A[0]\) đến \(A[m-1]\)).

Sử dụng \(A\), X, Y và Z, đoạn mã giả sau đây sẽ in ra dãy giới hạn tốc độ theo thứ tự. mod biểu thị phép toán lấy số dư.

for i = 0 to n-1
  print A[i mod m]
  A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

Lưu ý: Cách tạo dữ liệu vào không liên quan đến thuật toán tối ưu và chỉ tồn tại để giữ cho kích thước của các tệp dữ liệu vào ở mức thấp.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất một dòng chứa "Case #T: S" (ngoặc kép để cho rõ ràng) trong đó T là số thứ tự của bộ test và S là số lượng dãy con tăng nghiêm ngặt khác rỗng lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 20\)
• \(1 \le m \le 100\)
• \(0 \le X \le 10^9\)
• \(0 \le Y \le 10^9\)
• \(1 \le Z \le 10^9\)
• \(0 \le A[i] < Z\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le m \le n \le 1000\)
• Large dataset (Test set 2): \(1 \le m \le n \le 500000\)

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

Case #1: 15
Case #2: 13

Nguồn

Google Code Jam 2008, Vòng 1C, bài Increasing Speed Limits.

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âu chuyện

Giáo sư Loony, một người bạn thân của tôi, xông vào văn phòng tôi với khuôn mặt đỏ bừng và trông rất giận dữ. Điều đầu tiên ông ấy thốt ra là "Thật là tệ hại cho mấy tay sản xuất điện thoại. Tôi đã cố gắng gửi một tin nhắn văn bản, và tôi mất hơn mười phút để gõ một dòng tin nhắn duy nhất." Tôi cố gắng trấn an ông ấy: "Nhưng có chuyện gì vậy? Tại sao ông lại mất nhiều thời gian đến thế?" Ông ấy tiếp tục: "Anh không thấy sao?! Cách họ sắp xếp các chữ cái thật là lộn xộn! Tại sao 's' lại là chữ cái thứ 4 trên phím của nó? Còn 'e' nữa? Tại sao nó không phải là chữ cái đầu tiên trên phím? Tôi phải nhấn phím '7' BỐN lần để gõ một chữ 's'? Thật là điên rồ!"

"Bình tĩnh đi bạn tôi," tôi nói, "Sơ đồ này đã được sử dụng từ rất lâu rồi, ngay cả trước khi tin nhắn văn bản được phát minh. Họ phải giữ nó như vậy."

"Đó không phải là lý do," mặt ông ấy càng lúc càng đỏ hơn. "Đã đến lúc phải thay đổi tất cả những thứ này. Ngay từ đầu nó đã là một ý tưởng ngớ ngẩn rồi. Và nhân tiện, tại sao họ chỉ đặt các chữ cái trên 8 phím? Tại sao không dùng cả 12 phím? Và tại sao chúng phải liên tiếp nhau?"

"Ừm... tôi... không... biết," tôi trả lời.

"Được rồi, thế là đủ rồi. Những người đó rõ ràng là kém năng lực. Tôi chắc chắn rằng ai đó có thể nghĩ ra một sơ đồ tốt hơn."

Tôi có thể thấy ông ấy là một trong những người như vậy. Những người phàn nàn về vấn đề, nhưng không bao giờ thực sự cố gắng giải quyết nó.

Trong bài toán này, bạn được yêu cầu đưa ra cách sắp xếp các chữ cái lên các phím tốt nhất để tối thiểu hóa số lần nhấn phím cần thiết để gõ một tin nhắn. Bạn sẽ được cho số lượng phím, số lượng chữ cái tối đa có thể đặt trên mỗi phím, tổng số chữ cái trong bảng chữ cái và tần suất của mỗi chữ cái trong tin nhắn. Các chữ cái có thể được đặt ở bất kỳ đâu trên các phím và theo bất kỳ thứ tự nào. Mỗi chữ cái chỉ có thể xuất hiện trên một phím. Ngoài ra, bảng chữ cái có thể có nhiều hơn 26 chữ cái (đây không phải là tiếng Anh).

Để tham khảo, bàn phím điện thoại hiện tại trông như thế này:

key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz

Lần nhấn đầu tiên của một phím sẽ gõ chữ cái đầu tiên. Mỗi lần nhấn tiếp theo sẽ chuyển sang chữ cái kế tiếp. Ví dụ, để gõ từ "snow", bạn cần nhấn "7" bốn lần, tiếp theo là "6" hai lần, tiếp theo là "6" ba lần, và cuối cùng là "9" một lần. Tổng số lần nhấn phím là 10.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ thử nghiệm \(N\). Tiếp theo là \(N\) trường hợp. Mỗi trường hợp gồm hai dòng. Trên dòng đầu tiên, chúng ta có số lượng chữ cái tối đa có thể đặt trên một phím (\(P\)), số lượng phím khả dụng (\(K\)) và số lượng chữ cái trong bảng chữ cái của chúng ta (\(L\)), tất cả cách nhau bởi dấu cách đơn. Dòng thứ hai có \(L\) số nguyên không âm. Mỗi số đại diện cho tần suất của một chữ cái nhất định. Số đầu tiên là số lần chữ cái thứ nhất được sử dụng, số thứ hai là số lần chữ cái thứ hai được sử dụng, và cứ tiếp tục như vậy.

Dữ liệu ra

Với mỗi trường hợp, bạn nên xuất ra dòng sau:

Case #x: [minimum number of keypad presses]

cho biết số lần nhấn bàn phím để gõ tin nhắn cho cách sắp xếp tối ưu.

Ràng buộc

• \(P \times K \ge L\)
• \(0 \le\) Tần suất của mỗi chữ cái \(\le 1000000\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N \le 10\)
• \(1 \le P \le 10\)
• \(1 \le K \le 12\)
• \(1 \le L \le 100\)
• Large dataset (Test set 2 - Hidden):
• \(1 \le N \le 100\)
• \(1 \le P \le 1000\)
• \(1 \le K \le 1000\)
• \(1 \le L \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ụ

2
3 2 6
8 2 5 2 4 9
3 9 26
1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

Case #1: 47
Case #2: 397

Nguồn

Google Code Jam 2008, Vòng 1C, bài Text Messaging Outrage.

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

Ngày xửa ngày xưa trong một tình huống kỳ lạ, người ta gọi một số là xấu xí (ugly) nếu nó chia hết cho bất kỳ số nguyên tố có một chữ số nào (\(2, 3, 5\) hoặc \(7\)). Vì vậy, \(14\) là số xấu xí, nhưng \(13\) thì không. \(39\) là số xấu xí, nhưng \(121\) thì không. Lưu ý rằng \(0\) là số xấu xí. Ngoài ra, các số âm cũng có thể là số xấu xí; \(-14\) và \(-39\) là những ví dụ về các số như vậy.

Vào một ngày rảnh rỗi, bạn đang ngắm nhìn một chuỗi các chữ số, chẳng hạn như:

123456

Bạn cảm thấy thú vị bởi có bao nhiêu khả năng xảy ra nếu bạn được phép chèn các dấu cộng (\(+\)) hoặc trừ (\(-\)) vào giữa các chữ số. Ví dụ, bạn có thể tạo ra:

1 + 234 - 5 + 6 = 236

là một số xấu xí. Hoặc:

123 + 4 - 56 = 71

không phải là một số xấu xí.

Rất dễ để đếm số cách khác nhau mà bạn có thể chơi với các chữ số: Giữa mỗi hai chữ số liền kề, bạn có thể chọn đặt một dấu cộng, một dấu trừ hoặc không đặt gì cả. Do đó, nếu bạn bắt đầu với \(D\) chữ số, có \(3^{D-1}\) biểu thức bạn có thể tạo ra.

Lưu ý rằng việc có các số không ở đầu là hoàn toàn hợp lệ. Nếu chuỗi là "01023", thì "01023", "0+1-02+3" và "01-023" đều là các biểu thức hợp lệ.

Nhiệm vụ của bạn rất đơn giản: Trong số \(3^{D-1}\) biểu thức đó, hãy đếm xem có bao nhiêu biểu thức có giá trị là một số xấu xí.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ dữ liệu, \(N\). Mỗi bộ dữ liệu sẽ là một dòng duy nhất chứa một chuỗi các chữ số thập phân không rỗng.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, bạn nên xuất ra một dòng:

Case #X: Y

trong đó \(X\) là số thứ tự bộ dữ liệu, bắt đầu từ 1, và \(Y\) là số lượng biểu thức có giá trị là một số xấu xí.

Ràng buộc

• \(0 \le N \le 100\).
• Chuỗi trong mỗi bộ dữ liệu sẽ không rỗng và chỉ chứa các ký tự từ '0' đến '9'.

Phân nhóm

• Small dataset (Test set 1 - Visible): Mỗi chuỗi dài không quá 13 ký tự.
• Large dataset (Test set 2 - Hidden): Mỗi chuỗi dài không quá 40 ký tự.

Đ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
1
9
011
12345

Case #1: 0
Case #2: 1
Case #3: 6
Case #4: 64

Nguồn

Google Code Jam 2008, Vòng 1C, bài Ugly Numbers.

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