1. Google Code Jam 2015 - Dijkstra
Nhà khoa học máy tính người Hà Lan Edsger Dijkstra có nhiều đóng góp quan trọng, trong đó có thuật toán tìm đường đi ngắn mang tên ông. Bài này không nói về thuật toán đó.
Bạn bị trừ một điểm trong bài thi thuật toán vì viết sai “Dijkstra”: giữa D và stra, bạn viết một số ký tự, mỗi ký tự là i, j hoặc k. Bạn định tranh luận để lấy lại điểm bằng quaternion, một hệ số có thật (mở rộng từ số phức) với cấu trúc phép nhân sau:
Muốn nhân hai quaternion, tra hàng của số thứ nhất và cột của số thứ hai. Ví dụ \(i\times j=k\), còn \(j\times i=-k\).
Như các ví dụ cho thấy, phép nhân quaternion không giao hoán: tồn tại \(a,b\) sao cho \(a\times b\ne b\times a\). Tuy nhiên nó có tính kết hợp: với mọi \(a,b,c\), \(a\times(b\times c)=(a\times b)\times c\).
Dấu âm tuân theo quy tắc thông thường: \((-a)\times(-b)=a\times b\) và \((-a)\times b=a\times(-b)=-(a\times b)\).
Bạn muốn chứng minh phần viết sai tương đương với ijk bằng cách cắt chuỗi tại hai vị trí thành ba chuỗi con không rỗng, sao cho chuỗi trái rút gọn bằng phép nhân quaternion thành \(i\), chuỗi giữa thành \(j\), chuỗi phải thành \(k\). Ví dụ, jij được hiểu là \(j\times i\times j\); \(j\times i=-k\) và \((-k)\times j=i\), nên jij rút gọn thành \(i\). Nếu làm được, bạn sẽ lấy lại điểm. Hãy xác định có thể cắt như vậy hay không.
Dữ liệu vào
Dòng đầu chứa số bộ test \(T\).
Mỗi test gồm một dòng chứa hai số nguyên \(L,X\), rồi một dòng chứa \(L\) ký tự, tất cả đều là i, j hoặc k. Chuỗi không chứa dấu âm, 1 hay ký tự nào khác. Chuỗi cần xét là chuỗi \(L\) ký tự đã cho lặp lại \(X\) lần. Chẳng hạn, với \(L=4\), \(X=3\) và chuỗi kiij, chuỗi đầy đủ là kiijkiijkiij.
Dữ liệu ra
Với mỗi test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là YES hoặc NO tùy chuỗi có thể chia thành ba phần cho tích lần lượt \(i,j,k\) hay không.
Ràng buộc
- \(1\le T\le100\).
- \(1\le L\le10000\).
Phân nhóm
- Nhỏ: \(1\le X\le10000\), \(1\le L X\le10000\).
- Lớn: \(1\le X\le10^{12}\), \(1\le L X\le10^{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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 11/28 | 39,29% |
| Test Set 2 | 17/28 | 60,71% |
Ví dụ
Ví dụ 1
Input
5
2 1
ik
3 1
ijk
3 1
kji
2 6
ji
1 10000
iOutput
Case #1: NO
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: NONote
Test 1 quá ngắn để chia thành ba chuỗi con.
Test 2 chỉ cần chia thành i, j, k.
Test 3 chỉ có thể chia thành k, j, i, không thỏa yêu cầu.
Test 4 có chuỗi jijijijijiji; có thể chia thành jij (rút gọn thành \(i\)), iji (thành \(j\)), và jijiji (thành \(k\)).
Ở test 5, dù chọn các đoạn thế nào, không đoạn nào có thể rút gọn thành \(j\) hoặc \(k\).
Nguồn
Google Code Jam 2015, Vòng loại, bài Dijkstra.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
