Google Code Jam 2013 - Round 1C

Trong tiếng Anh, có 26 chữ cái được chia thành nguyên âm hoặc phụ âm. Trong bài toán này, chúng ta coi a, e, i, o, và u là các nguyên âm, và 21 chữ cái còn lại là các phụ âm.

Một bộ lạc sống trong Khu rừng Đầy màu sắc Vĩ đại có truyền thống đặt tên cho các thành viên bằng các chữ cái tiếng Anh. Tuy nhiên, việc đặt một cái tên hay cho thành viên mới không hề dễ dàng vì nó phản ánh địa vị xã hội của thành viên đó trong bộ lạc. Người ta tin rằng tên càng ít phổ biến thì người sở hữu nó càng có nhiều đặc quyền xã hội.

Tộc trưởng của bộ lạc là một nhà ngôn ngữ học chuyên nghiệp. Ông nhận thấy rằng những cái tên khó phát âm thường ít phổ biến, và lý do là chúng có quá nhiều phụ âm liên tiếp. Do đó, ông thông báo rằng địa vị xã hội của một thành viên trong bộ lạc được xác định bởi giá trị \(n\) của cái tên đó, chính là số lượng chuỗi con có ít nhất \(n\) phụ âm liên tiếp trong tên. Ví dụ, khi \(n = 3\), cái tên "quartz" có giá trị \(n\) là 4 vì các chuỗi con quartz, uartz, artz, và rtz mỗi chuỗi đều có ít nhất 3 phụ âm liên tiếp. Giá trị \(n\) càng lớn nghĩa là địa vị xã hội trong bộ lạc càng cao. Hai chuỗi con được coi là khác nhau nếu chúng bắt đầu hoặc kết thúc ở các vị trí khác nhau (ngay cả khi chúng bao gồm các chữ cái giống nhau), ví dụ "tsetse" chứa 11 chuỗi con có hai phụ âm liên tiếp, mặc dù một số chuỗi trong đó (như "tsetse" và "tsetse") chứa các chữ cái giống nhau.

Tất cả các thành viên trong bộ lạc phải được tộc trưởng đặt tên và cho trước giá trị \(n\). Mặc dù tộc trưởng là một nhà ngôn ngữ học và có thể đảm bảo rằng các cái tên được đặt đều có ý nghĩa, nhưng ông không giỏi tính toán giá trị \(n\). Hãy giúp tộc trưởng xác định giá trị \(n\) của mỗi cái tên. Lưu ý rằng các cái tên khác nhau có thể có các giá trị \(n\) khác nhau đi kèm.

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\). Tiếp theo là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test cho biết tên của một thành viên dưới dạng một chuỗi có độ dài \(L\), và một số nguyên \(n\). Mỗi tên bao gồm một hoặc nhiều chữ cái tiếng Anh viết thường.

Dữ liệu ra

Với mỗi bộ test, hãy 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à giá trị \(n\) của tên thành viên đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 < n \le L\).

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le L \le 100\).
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le L \le 10^6\). Kích thước tệp đầu vào không lớn hơn 6MB.

Đ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
quartz 3
straight 3
gcj 2
tsetse 2

Case #1: 4
Case #2: 11
Case #3: 3
Case #4: 11

Nguồn

Google Code Jam 2013, Vòng 1C, bài Consonants.

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 nhận được món quà tuyệt vời nhất từ trước đến nay: một chiếc gậy Pogo. Gậy pogo là dụng cụ dùng để nhảy lên khỏi mặt đất khi bạn đang đứng trên đó.

Chiếc gậy Pogo này rất đặc biệt: cú nhảy thứ nhất sẽ đưa bạn đi một khoảng cách \(1\) đơn vị, cú nhảy thứ hai sẽ đưa bạn đi \(2\) đơn vị, cú nhảy thứ ba là \(3\) đơn vị, và cứ tiếp tục như vậy. Bạn chỉ có thể nhảy theo bốn hướng bằng chiếc gậy này: bắc (tăng \(y\)), nam (giảm \(y\)), đông (tăng \(x\)) hoặc tây (giảm \(x\)).

Bây giờ bạn muốn chơi một trò chơi trong sân sau của mình, nơi được mô hình hóa như một mặt phẳng vô hạn. Bạn đang đứng với chiếc gậy tại điểm \((0, 0)\) và bạn muốn đi đến điểm \((X, Y)\).

Điểm \((X, Y)\) sẽ không bao giờ là \((0, 0)\), và nó luôn có thể đạt được từ điểm xuất phát của bạn.

Hãy kiểm tra kỹ phần dữ liệu ra, vì yêu cầu đầu ra cho tập dữ liệu nhỏ (Small) và tập dữ liệu lớn (Large) là không giống nhau.

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ộ trên một dòng. Mỗi dòng gồm \(2\) số nguyên cách nhau bởi một khoảng trắng, \(X\) và \(Y\), là tọa độ của điểm bạn muốn đến.

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 chuỗi đại diện cho các hướng di chuyển. Ví dụ, nếu bạn di chuyển theo hướng bắc, sau đó nam, sau đó đông, rồi tây, chuỗi này sẽ là NSEW.

• Đối với tập dữ liệu nhỏ (Small), đầu ra được coi là đúng nếu nó không mất quá \(500\) bước nhảy để đến đích trong mỗi bộ thử nghiệm.
• Đối với tập dữ liệu lớn (Large), đầu ra được coi là đúng nếu nó đến được điểm đích với số bước nhảy ít nhất có thể.

Nếu có nhiều giải pháp đúng, hãy in ra bất kỳ giải pháp nào.

Ràng buộc

• \(1 \le T \le 50\) (Small).
• \(0 \le |X|, |Y| \le 100\) (Small).
• \(1 \le T \le 100\) (Large).
• \(0 \le |X|, |Y| \le 10^6\) (Large).

Phân nhóm

Các giới hạn của từng tập dữ liệu được nêu trong mục Ràng buộc.

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

Case #1: ENWSEN
Case #2: ENSWN

Nguồn

Google Code Jam 2013, Vòng 1C, bài Pogo.

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 nghiên cứu lịch sử của Vạn Lý Trường Thành, được xây dựng để chống lại các cuộc xâm lược quân sự từ phương Bắc. Trong bài toán này, ta giả định Vạn Lý Trường Thành kéo dài từ vô tận ở phía Đông đến âm vô tận ở phía Tây. Vì khoảng cách quá lớn, bức tường không được xây dựng cùng một lúc. Thay vào đó, người xây dựng sử dụng chiến lược phản ứng: bất cứ khi nào một phần biên giới bị tấn công thành công, bức tường ở phần đó sẽ được nâng lên độ cao đủ để ngăn chặn một cuộc tấn công tương tự trong tương lai.

Biên giới phía Bắc thường xuyên bị các bộ lạc du mục tấn công. Mỗi bộ lạc tấn công biên giới trên một đoạn nhất định với cường độ \(S\). Để đẩy lùi cuộc tấn công, bức tường phải có độ cao ít nhất là \(S\) trên toàn bộ đoạn bị tấn công. Nếu chỉ cần một đoạn nhỏ của bức tường thấp hơn mức cần thiết, cuộc tấn công sẽ xuyên thủng bức tường tại điểm đó và thành công. Lưu ý rằng ngay cả một cuộc tấn công thành công cũng không làm hỏng bức tường. Sau cuộc tấn công, mọi đoạn tường bị tấn công có độ cao thấp hơn \(S\) sẽ được nâng lên độ cao \(S\) — nói cách khác, bức tường được nâng lên theo cách tối thiểu để có thể ngăn chặn cuộc tấn công đó. Nếu hai hoặc nhiều cuộc tấn công xảy ra trong cùng một ngày, bức tường chỉ được nâng lên sau khi tất cả các cuộc tấn công đó đã kết thúc, và được nâng lên theo cách tối thiểu để có thể ngăn chặn tất cả chúng.

Các bộ lạc du mục không nhất thiết chỉ tấn công một lần. Họ có xu hướng di chuyển (sang phía Đông hoặc phía Tây) và định kỳ tấn công bức tường. Để đơn giản hóa, ta giả định họ di chuyển với tốc độ không đổi và tấn công bức tường theo các khoảng thời gian đều đặn; hơn nữa, cường độ tấn công của một bộ lạc thay đổi một lượng không đổi sau mỗi lần tấn công (giảm do tiêu hao hoặc tăng do kinh nghiệm).

Giả sử ban đầu (năm 250 TCN) bức tường chưa tồn tại (độ cao bằng 0 ở mọi nơi), và cho biết mô tả đầy đủ về tất cả các bộ lạc du mục, hãy xác định có bao nhiêu cuộc tấn công đã thành công.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ bắt đầu bằng một dòng chứa một số nguyên \(N\): số lượng bộ lạc tấn công bức tường. \(N\) dòng tiếp theo, mỗi dòng mô tả một bộ lạc. Dòng thứ \(i\) chứa tám số nguyên \(d_i, n_i, w_i, e_i, s_i, delta\_d_i, delta\_p_i\) và \(delta\_s_i\) cách nhau bởi dấu cách:

• \(d_i\) – ngày diễn ra cuộc tấn công đầu tiên của bộ lạc (ngày 1 tháng 1 năm 250 TCN được coi là ngày 0).
• \(n_i\) – số lần tấn công của bộ lạc này.
• \(w_i, e_i\) – điểm cực Tây và cực Đông của đoạn tường bị tấn công trong lần đầu tiên.
• \(s_i\) – cường độ của cuộc tấn công đầu tiên.
• \(delta\_d_i\) – số ngày giữa các cuộc tấn công liên tiếp của bộ lạc này.
• \(delta\_p_i\) – khoảng cách bộ lạc di chuyển về phía Đông giữa các cuộc tấn công liên tiếp (nếu âm, bộ lạc di chuyển về phía Tây).
• \(delta\_s_i\) – sự thay đổi cường độ giữa các cuộc tấn công liên tiếp.

Dữ liệu ra

Với mỗi bộ test, in ra 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à số cuộc tấn công thành công.

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le d_i\).
• \(1 \le delta\_d_i \le 676060\).
• \(d_i + (n_i - 1) \times delta\_d_i \le 676060\).
• \(1 \le s_i \le 10^6\).
• \(-10^5 \le delta\_s_i \le 10^5\).
• \(s_i + (n_i - 1) \times delta\_s_i \ge 1\).

Phân nhóm

• Small dataset (Test set 1):
  • \(1 \le N \le 10\).
  • \(1 \le n_i \le 10\).
  • \(-100 \le w_i < e_i \le 100\).
  • \(-10 \le delta\_p_i \le 10\).
• Large dataset (Test set 2):
  • \(1 \le N \le 1000\).
  • \(1 \le n_i \le 1000\).
  • \(-10^6 \le w_i < e_i \le 10^6\).
  • \(-10^5 \le delta\_p_i \le 10^5\).

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

Case #1: 5
Case #2: 6

Nguồn

Google Code Jam 2013, Vòng 1C, bài The Great Wall.

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