Quy Hoạch Động Bitmask

Sau khi làm nhiệm vụ cho nhóm C.R.A.S.H, thì giờ đây CJ đã không còn làm được gì, cả không thể về lại nơi cũ vì sẽ bị nhóm này truy sát. Trong lúc CJ đang đi quanh quẩn nơi đây thì vô tình gặp Catalina và cô gái này rất là hám tiền. CJ và Catalina bắt tay với nhau, và Catalina nhờ CJ giúp một công việc: Cướp hết ngân hàng nhỏ ở các khu vực nông thôn.

Ở vùng nông thôn San Andreas có \(N\) địa điểm, trong đó có \(K\) địa điểm là ngân hàng, đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, đánh số từ \(1\) tới \(M\), con đường thứ \(i\) có độ dài là \(L_{i}\). Catalina muốn CJ tìm đường đi sao cho xuất phát từ một ngân hàng, cướp hết tất cả \(K\) ngân hàng, mỗi con đường và một địa điểm có thể được đi qua nhiều lần, và độ dài đường đi là ngắn nhất có thể. Đảm bảo hai ngân hàng khác nhau bất kì đều có đường đi.

Yêu cầu: Hãy tìm ra cho CJ và Catalina độ dài đường đi ngắn nhất trên.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N,M,K\) thể hiện số địa điểm, số con đường hai chiều, số ngân hàng.
• Dòng tiếp theo chứa \(K\) số \(a_{1},a_{2},…,a_{K}\) là số hiệu của các địa điểm là ngân hàng.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_{i},v_{i}, L_{i}\) thể hiện có đường nối trực tiếp \(u_{i},v_{i}\) và độ dài là \(L_{i}\).

Output

• Ghi ra độ dài đường đi ngắn nhất.

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 2.10^{5}\)
• \(1 \leq K \leq 18\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{3}\), \(M \leq 2.10^{3}\), \(K \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{5}\), \(M \leq 2.10^{5}\), \(K \leq 10\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 6 2
1 4 
3 2 1
5 4 3
5 1 1
1 2 7
3 5 3
6 1 1 

4

SPyofgame là một điệp viên của tổ chức O.W.C.A với bí danh H (H là gì thì chắc ai cũng nhận ra). Mỗi tháng, anh ta nhận được một danh sách nhiệm vụ của mình. Dù là thành viên lâu năm nhưng SPyofgame khá lười biếng, suốt ngày chỉ lo chơi surviv và nhắn tin cho bạn gái, anh ta không thể tính toán được xác suất để hoàn thành được \(N\) nhiệm vụ cụ thể được giao nên thường bị phạt tiền. Lần này, bạn hãy giúp anh ấy tính xác suất để anh ấy có thể hoàn thành được nhiệm vụ.

Input

Dòng đầu tiên là số nguyên dương \(N\), số lượng nhiệm vụ được giao \((1 \leq N \leq 20)\)
\(N\) dòng tiếp theo, mỗi dòng bao gồm \(N\) số nguyên dương \(x\) là xác xuất(%) để hoàn thành được nhiệm vụ con thứ \(i\) \((1 \leq i \leq N, 0 \leq x \leq 100)\)

Output

1 dòng duy nhất là xác suất để SPyofgame có thể hoàn thành \(N\) nhiệm vụ, đáp án được chấp nhận nếu sai số không quá \(10^{-6}\)

Example

3
10 6 4
4 2 10
25 12 7 

0.150000000000

Một bàn cờ vua đặc biệt có \(n \times n\) ô vuông. Ô vuông ở hàng \(i\) cột \(j\) có giá trị nguyên dương là \(a[i][j]\).

Hãy tìm cách xếp \(n\) quân xe lên bàn cờ sao cho không có hai quân xe nào "ăn nhau" và tổng giá trị của các ô vuông có đặt quân xe là lớn nhất.

Input

• Số nguyên dương \(t\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), và ma trận \(a\)

Output

• Với mỗi câu hỏi, in ra một dòng có dạng Case k: x trong đó \(k\) là số thứ tự câu hỏi và \(x\) là tổng giá trị lớn nhất ở các ô vuông có đặt quân xe

Constraints

• \(t \leq 100\)
• \(n \leq 16\)
• \(1 \leq a[i][j] \leq 10^5\)

Example

2
2
1 5
2 1
3
1 2 3
6 5 4
8 1 2

Case 1: 7
Case 2: 16

Scoring

• \(40\%\) số điểm thỏa mãn \(n \leq 10\)

Trên hệ tọa độ \(Oxy\) có \(n\) điểm, hãy tìm cách vẽ lên số đường thẳng ít nhất, sao cho mỗi điểm trong \(n\) điểm này đều thuộc ít nhất một đường thẳng.

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), và tọa độ \(x_i\), \(y_i\) của \(n\) điểm

Constraints

• \(q \leq 500\)
• \(n \leq 16\)
• \(-10^5 \leq x_i, y_i \leq 10^5\)

Output

• Với mỗi test case, in ra một dòng dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số đường thẳng ít nhất cần vẽ

Example

2
3
0 0
1 1
2 2
3
0 0
1 1
2 3

Case 1: 1
Case 2: 2

Tham khảo: LightOJ

Cho một số \(n\) được biểu diễn theo cơ số \(b\). Các chữ số của số này đều khác nhau đôi một.

Hãy đếm số hoán vị của số này theo cơ số \(b\) sao cho hoán vị này có giá trị theo cơ số \(10\) chia hết cho \(k\).

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa hai số nguyên dương \(b\), \(k\) và số \(n\) được biểu diễn theo cơ số \(b\)

Constraints

• \(q \leq 100\)
• \(2 \leq b \leq 16\)
• \(1 \leq k \leq 20\)

Output

• Với mỗi test case, in ra một dòng dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số hoán vị thỏa mãn đề bài

Example

3
2 2
10
10 2
5681
16 1
ABCDEF0123456789

Case 1: 1
Case 2: 12
Case 3: 20922789888000

Tham khảo: LightOJ

Trong tựa game Yasuo, có \(n\) con boss, mỗi con boss có lượng máu riêng của chúng. Con boss thứ \(i\) có lượng máu là \(h_i\).

Ban đầu, khi chưa tiêu diệt được con boss nào, nhân vật chính sẽ có thanh katana "Trăn Trối". Với mỗi nhát chém, thanh gươm gây \(1\) sát thương cho mỗi con boss bất kỳ.

Sau khi tiêu diệt được con boss thứ \(i\) bạn sẽ nhận "THÊM" một thanh katana mới, thanh gươm này sẽ gây \(a[i][j]\) sát thương một nhát chém đối với con boss thứ \(j\).

Lưu ý: các thanh gươm trước đó không bị mất đi, vẫn có thể được sử dụng tiếp.

Hãy tìm số nhát chém tối thiểu để "phá đảo" trò chơi.

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), máu của \(n\) boss \(h_1, h_2, ..., h_n\) và ma trận \(a\)

Constraints

• \(q \leq 40\)
• \(n \leq 15\)
• \(1 \leq h_i \leq 10^6\)
• \(0 \leq a[i][j] \leq 9\)

Output

• Với mỗi test case, in ra một dòng theo định dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số nhát chém tối thiểu

Example

2
3
10 10 10
010
100 
111
3
3 5 7
030
500
007

Case 1: 30
Case 2: 12

Tham khảo: LightOJ

Cho dãy số nguyên dương \(a\) gồm \(n\) phần tử. Nhiệm vụ của bạn là hãy hoán đổi các phần tử liền kề sao cho các số có cùng giá trị đứng cạnh nhau thành một đoạn liên tiếp.

Input

• Số nguyên dương \(t\) --- số câu hỏi
• Mỗi câu hỏi, chứa hai số nguyên dương \(n\), \(m\) và dãy \(a\)
• Các phần tử trong dãy \(a\) có giá trị không quá \(m\)

Constraints

• \(t \leq 15\)
• \(n \leq 10^5\)
• \(m \leq 16\)

Output

• Số lần hoán đổi tối thiểu để hoàn thành

Example

3
4 2 
1 2 1 2
6 4
2 1 4 3 1 2
8 6
1 3 2 5 5 4 5 2

Case 1: 1
Case 2: 6
Case 3: 5

Tham khảo: LightOJ

Có \(n\) thành phố và \(m\) chuyến bay kết nối giữa chúng. Bạn muốn đi từ Syrjälä đến Lehmälä để bạn đến thăm mỗi thành phố đúng một lần. Có bao nhiêu tuyến đường khả thi?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(m\): số thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots,n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay đều là chuyến bay một chiều.

Output

• In ra một số nguyên: số tuyến đường theo modulo \(10^9 + 7\).

Constraints

• \(2 \le n \le 20\)
• \(1 \le m \le n^2\)
• \(1 \le a, b \le n\)

Example

4 6
1 2
1 3
2 3
3 2
2 4
3 4

2

Có \(n\) người muốn lên đến đỉnh của một tòa nhà mà chỉ có một thang máy. Bạn biết trọng lượng của mỗi người và trọng lượng tối đa cho phép trong thang máy. Số lần đi thang máy tối thiểu là bao nhiêu?

Input

• Dòng đầu tiên có hai số nguyên \(n\) và \(x\): số lượng người và trọng lượng tối đa cho phép trong thang máy
• Dòng thứ hai chứa \(n\) số nguyên \(w_1,w_2,\ldots,w_n\): trọng lượng của mỗi người

Constraints

• \(1 \leq n \leq 20\)
• \(1 \leq x \leq 10^9\)
• \(1 \leq w_i \leq x\)

Output

• In một số nguyên: số lần đi tối thiểu

Example

4 10
4 8 6 1

2