JOI 2007 Representative Selection - Ngày 3

Một anagram của một xâu là xâu thu được bằng cách sắp xếp lại các ký tự của xâu đó. Xâu ban đầu cũng được tính là một anagram của chính nó. Chẳng hạn, EARTH và HEART đều là anagram của HEART.

Một xâu có thể có nhiều anagram khác nhau. Ví dụ, các anagram phân biệt của IOI, theo thứ tự từ điển tăng dần, là IIO, IOI, OII.

Cho một xâu, hãy xác định vị trí của nó trong danh sách tất cả các anagram phân biệt của chính nó, sắp theo thứ tự từ điển tăng dần. Các vị trí được đánh số bắt đầu từ \(1\). Chẳng hạn, EARTH đứng thứ \(28\), còn HEART đứng thứ \(55\) trong danh sách anagram tương ứng.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa xâu cần xét.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: vị trí của xâu đã cho trong danh sách các anagram phân biệt theo thứ tự từ điển.

Ràng buộc

• Xâu chỉ gồm các chữ cái tiếng Anh in hoa và có không quá \(20\) ký tự.
• Chú ý tránh tràn số: \(2^{32}<20!<2^{63}\).

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(05\): \(20\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

HEART

55

IOI

2

Một người bạn của bạn làm nghề quản tượng được lệnh đưa voi tới cung điện. Các con đường tới cung điện đều thu phí và người quản tượng phải tự trả tiền. Hãy giúp người ấy tìm một hành trình có tổng phí nhỏ nhất.

Bản đồ gồm các trạm thu phí và các con đường. Cần tuân theo các quy tắc sau:

• Mỗi con đường là một đoạn thẳng nối hai trạm thu phí và có thể đi theo cả hai chiều. Giữa một cặp trạm có nhiều nhất một con đường.
• Phải đi hết một con đường từ đầu này tới đầu kia. Không được chuyển sang đường khác ở giữa đường, kể cả tại giao điểm của hai đường.
• Tại một trạm, voi không thể chuyển giữa hai đoạn đường tạo thành một góc nhọn. Cụ thể, khi đi từ \(p\) tới \(q\) rồi tới \(r\), góc \(\angle pqr\) giữa hai tia \(qp\) và \(qr\) phải lớn hơn hoặc bằng \(90^\circ\). Góc vuông và góc tù đều được phép.

Voi bắt đầu ở trạm \(1\). Cung điện nằm ngay cạnh trạm \(2\); mục tiêu là tới trạm \(2\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(n,m\): số trạm thu phí và số con đường.
• Dòng thứ \(i+1\) (\(1\le i\le n\)) chứa hai số nguyên \(x_i,y_i\), là tọa độ trạm \(i\).
• Dòng thứ \(j+n+1\) (\(1\le j\le m\)) chứa ba số nguyên \(a_j,b_j,c_j\), cho biết có một con đường nối trạm \(a_j\) với trạm \(b_j\), với phí đi qua là \(c_j\).

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn tổng phí nhỏ nhất để đi từ trạm \(1\) tới trạm \(2\) theo các quy tắc trên. Nếu không thể tới được trạm \(2\), ghi -1.

Ràng buộc

• \(2\le n\le100\).
• \(-10\,000\le x_i,y_i\le10\,000\) (\(1\le i\le n\)).
• \(1\le a_j<b_j\le n\) (\(1\le j\le m\)).
• \(0\le c_j\le10\,000\) (\(1\le j\le m\)).
• Giữa một cặp trạm có nhiều nhất một con đường.

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(10\): \(10\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

5 6
0 0
10 10
0 10
10 0
2 -6
1 2 30
1 3 4
1 4 5
1 5 1
2 4 3
2 5 1

8

Xét một vi mạch (IC) có \(n\) đầu vào ở phía trên và \(n\) đầu ra ở phía dưới. Ở mỗi phía, các đầu được đánh số \(1,2,\ldots,n\) từ trái sang phải. Mỗi đầu vào được nối tới đúng một đầu ra và mỗi đầu ra nhận tín hiệu từ đúng một đầu vào.

Ta mô tả một IC bằng dãy \((a_1,\ldots,a_n)\), trong đó \(a_i\) là số thứ tự của đầu vào nối tới đầu ra \(i\). Chẳng hạn, IC \((2,3,1)\) nối đầu vào \(2\) tới đầu ra \(1\), đầu vào \(3\) tới đầu ra \(2\), và đầu vào \(1\) tới đầu ra \(3\).

Với \(n=3\), có sáu loại IC: \((1,2,3)\), \((1,3,2)\), \((2,1,3)\), \((2,3,1)\), \((3,1,2)\) và \((3,2,1)\).

Khi mắc các IC nối tiếp, đầu ra \(i\) của IC trước được nối với đầu vào \(i\) của IC sau. Ví dụ, mắc nối tiếp năm IC đều có dạng \((2,3,1)\) sẽ có tác dụng giống IC \((3,1,2)\): các đầu ra cuối cùng \(1,2,3\) lần lượt nhận tín hiệu từ các đầu vào ban đầu \(3,1,2\).

Cho \(n\), \(k\) và hoán vị \((a_1,\ldots,a_n)\) của các số từ \(1\) đến \(n\). Hãy xác định có thể mắc nối tiếp \(k\) IC cùng loại để có tác dụng giống IC \((a_1,\ldots,a_n)\) hay không. Nếu có, hãy đưa ra một loại IC thỏa mãn. Nếu có nhiều đáp án, được phép đưa ra bất kỳ đáp án nào.

Dữ liệu vào

Đọc từ đầu vào chuẩn, gồm \(n+1\) dòng:

• Dòng đầu chứa hai số nguyên \(n,k\), phân cách bằng dấu cách.
• Dòng thứ \(i+1\) (\(1\le i\le n\)) chứa số nguyên \(a_i\).

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn.

Nếu có loại IC thỏa mãn, ghi \(n\) dòng mô tả IC đó. Dòng thứ \(i\) (\(1\le i\le n\)) chứa số thứ tự của đầu vào nối tới đầu ra \(i\) của IC cần tìm. Dãy được ghi ra phải là một hoán vị của các số từ \(1\) đến \(n\).

Nếu không tồn tại loại IC thỏa mãn, chỉ ghi một dòng chứa 0.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le k\le10\,000\).
• \(1\le a_i\le n\) (\(1\le i\le n\)); các \(a_i\) đôi một khác nhau.

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(05\): \(20\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

3 5
3
1
2

2
3
1

4 4
2
1
4
3

0