VOI Training 2024-10-16

Cho đồ thị vô hướng đầy đủ có \(N\) đỉnh (được đánh số từ \(1\) đến \(N\)). Cạnh nối đỉnh \(i\) và đỉnh \(j\) sẽ có trọng số bằng \(D_{i,j}\). Lưu ý rằng \(D_{i,j}=D_{j,i}\) với mọi cặp \(i \ne j\).

Hãy tìm cách chọn ra một tập cạnh sao cho tổng trọng số của chúng là lớn nhất và các đầu mút của chúng không trùng nhau (nói cách khác, hai cạnh \((u,v)\) và \((p,q)\) khác nhau bất kỳ trong tập được chọn ra phải thỏa mãn \(u\), \(v\), \(p\), \(q\) là bốn số nguyên phân biệt).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \(\left(2\le N\le 16\right)\).
• Dòng tiếp theo chứa \(N-1\) số nguyên dương \(D_{1,2}\), \(D_{1,3}\), \(D_{1,4}\),..., \(D_{1,N}\).
• Dòng tiếp theo chứa \(N-2\) số nguyên dương \(D_{2,3}\), \(D_{2,4}\), \(D_{2,5}\),..., \(D_{2,N}\).
• Dòng tiếp theo chứa \(N-3\) số nguyên dương \(D_{3,4}\), \(D_{3,5}\), \(D_{3,6}\),..., \(D_{3,N}\).
• ...
• Dòng cuối cùng chứa một số nguyên dương \(D_{N-1,N}\).
• Dữ liệu đảm bảo \(2\le D_{i,j}\le 10^9\) với mọi \(i\ne j\).

Output

• In ra tổng trọng số lớn nhất của tập cạnh tìm được.

Example

Test 1

Input

4
1 5 4
7 9
6

Output

14

Note

Ta có thể chọn các cạnh \((1,3)\) và \((2,4)\) để được tổng trọng số \(5+9=14\).

3
1 2
4

4

Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Với mỗi đỉnh \(i\) \((2\le i\le N)\) tồn tại đúng một cạnh nối \(i\) và \(\left\lfloor\dfrac{i}{2}\right\rfloor\). Ta định nghĩa khoảng cách từ đỉnh \(u\) đến đỉnh \(v\) trên cây (và ngược lại) bằng đúng số lượng cạnh xuất hiện trên đường đi duy nhất từ \(u\) đến \(v\).

Cho biết hai số nguyên \(X\) và \(K\) \((1\le X\le N, 0\le K\le N-1)\), bạn hãy viết chương trình xác định có bao nhiêu đỉnh trên cây có khoảng cách đến \(X\) đúng bằng \(K\).

Input

• Dòng đầu chứa số nguyên dương \(T\) thể hiện số lượng câu hỏi \(\left(T\le 10^5\right)\).
• Trong \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(N\), \(X\), \(K\) \(\left(1\le N\le 10^{18}, 1\le X\le N, 0\le K\le N-1\right)\).

Output

• Gồm \(T\) dòng là câu trả lời cho từng câu hỏi tương ứng.

Example

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

1
3
4
2
0

Cho trước giá trị \(C\) và \(N\) thao tác bit, thao tác thứ \(i\) có dạng \(T \ A\), trong đó:

• \(T=1\) biểu thị cho phép gán \(M = M \ \text{and} \ A\).
• \(T=2\) biểu thị cho phép gán \(M = M \ \text{or} \ A\).
• \(T=3\) biểu thị cho phép gán \(M = M \ \text{xor} \ A\).

Đức có một biến số nguyên \(X\). Ban đầu, Đức gán \(X=C\) và tiến hành \(N\) bước tính toán:

• Bước \(1\): Áp dụng thao tác bit thứ \(1\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• Bước \(2\): Lần lượt áp dụng thao tác bit thứ \(1\) và thứ \(2\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• Bước \(3\): Lần lượt áp dụng thao tác bit thứ \(1\), thứ \(2\), và thứ \(3\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• ...
• Bước \(N\): Lần lượt áp dụng thao tác bit thứ \(1\), thứ \(2\), thứ \(3\),..., thứ \(N\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.

Bạn hãy giúp Đức viết chương trình thực hiện \(N\) bước tính toán trên nhé!

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(C\) \(\left(1\le N\le 2\times 10^5, 0\le C < 2^{30}\right)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo có dạng \(1 \ A_i\), \(2 \ A_i\), hoặc \(3 \ A_i\) thể hiện thao tác bit thứ \(i\) \(\left(0\le A_i < 2^{30} \right)\).

Output

• In ra \(N\) dòng là kết quả của \(N\) bước tính toán.

Example

3 19
3 10
2 13
1 6

25
31
4

Đất nước Byteland có \(N\) thành phố, \(M\) trạm phát điện, và \(E\) đường dây nối hai chiều. Mỗi đường dây sẽ nối hai thành phố với nhau, hoặc hai trạm phát điện với nhau, hoặc một trạm phát điện với một thành phố. Để dễ hình dung, ta có thể biểu diễn Byteland dưới dạng mô hình đồ thị vô hướng gồm \(N+M\) đỉnh và \(E\) cạnh. Các thành phố tương ứng với các đỉnh \(1\), \(2\),..., \(N\) và các trạm phát điện tương ứng với các đỉnh \(N+1\), \(N+2\),..., \(N+M\). Cạnh thứ \(i\) \((1\le i\le E)\) nối hai đỉnh \(U_i\) và \(V_i\).

Một thành phố được xem là đã hòa lưới điện nếu tồn tại một đường đi từ nó đến một trạm phát điện nào đó. Bạn hãy lập trình xử lý \(Q\) sự kiện giả lập, tại sự kiện \(i\) ta tiến hành phá hủy đường dây (cạnh) thứ \(X_i\) và cho biết số lượng thành phố hòa lưới điện còn lại là bao nhiêu. Lưu ý rằng một khi một đường dây bị phá hủy, nó sẽ không bao giờ được nối lại.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N\), \(M\) và \(E\) \(\left(2\le N+M\le 2\times 10^5, 1\le E\le 5\times 10^5\right)\).
• Dòng thứ \(i\) trong \(E\) dòng tiếp theo chứa hai số nguyên dương \(U_i\), \(V_i\) \((1\le U_i < V_i \le N+M)\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) \(\left(1\le Q\le \min\left(E, 5\times 10^5\right)\right)\).
• Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa số nguyên dương \(X_i\) \(\left(1\le X_i\le E\right)\). Dữ liệu đảm bảo tất cả các giá trị \(X_i\) đều không trùng nhau.

Output

• Gồm \(Q\) dòng. Dòng thứ \(i\) ghi một số nguyên là số lượng thành phố hòa lưới điện còn lại.

Example

5 5 10
2 3
4 10
5 10
6 9
2 9
4 8
1 7
3 6
8 10
1 8
6
3
5
8
10
2
7

4
4
2
2
2
1

Xét bài toán sau: Cho dãy số gồm \(N\) số nguyên dương, hãy cho biết bội số chung nhỏ nhất (LCM) của toàn dãy nếu ta biến đổi một phần tử của nó về giá trị \(1\).

Nhận thấy đề bài chưa đủ khó, Đức quyết định nâng cấp nó lên:

• Các phần tử trong dãy thay vì được cho trực tiếp sẽ được biểu diễn dưới dạng tích của các thừa số nguyên tố. Cụ thể, phần tử thứ \(i\) sẽ gồm \(m_i\) thừa số nguyên tố \(p_1\), \(p_2\),..., \(p_{m_i}\), với số mũ tương ứng là \(e_{1,i}\), \(e_{2,i}\),..., \(e_{m_i,i}\). Nói cách khác, giá trị của nó sẽ bằng \(p_1^{e_1,i}\times p_2^{e_2,i}\times p_3^{e_3,i}\times ... \times p_{m_i}^{e_{m_i},i}\).
• Ta lần lượt thử biến đổi từng phần tử thứ \(1\), \(2\), \(3\),..., \(N\) về giá trị \(1\), và tính xem có tổng số bao nhiêu giá trị LCM khác nhau có thể thu được (mỗi lần thử chỉ biến đổi đúng một phần tử).

Input

• Dòng đầu chứa số nguyên dương \(N\) \(\left(1\le N\le 2\times 10^5\right)\).
• Nhóm dòng thứ \(i\) trong \(N\) nhóm dòng tiếp theo bắt đầu bởi một dòng chứa số nguyên dương \(m_i\). Theo sau là \(m_i\) dòng, dòng thứ \(j\) chứa thừa số nguyên tố \(p_j\) và số mũ \(e_j\) \(\left(1\le p_j, e_j\le 10^9\right)\).
• Dữ liệu đảm bảo tổng tất cả giá trị \(m_i\) không vượt quá \(2\times 10^5\). Đồng thời, tất cả các giá trị \(p\) đều là số nguyên tố.

Output

• In ra một số nguyên là số lượng giá trị LCM khác nhau ta có thể thu được sau \(N\) lần thử nghiệm.

Example

4
1
3 2
2
2 2
5 1
1
5 1
2
2 1
3 1

3

Cho \(1\) xâu \(S\) gồm \(n\) ký tự, ta sinh ra \(n\) xâu con của \(S\) là: \(T_1=S_{1..n}\), \(T_2=S_{2..n}\), \(T_3=S_{3..n}\),..., \(T_n=S_{n..n}\).

Sau đó ta sẽ sắp xếp \(n\) xâu \(T\) lại theo thứ tự từ điển tăng dần, \(1\) xâu \(A\) được xem là có thứ tự từ điển nhỏ hơn \(B\) nếu tồn tại \(1\) vị trí \(k\) sao cho \(A_{1..k-1}=B_{1..k-1}\) và \(A_k < B_k\).

Cuối cùng ta sẽ xây dựng mảng \(a_1\), \(a_2\),..., \(a_n\) với \(a_i=x\) nếu xâu \(T_x\) nằm ở vị trí \(i\) sau khi đã được sắp xếp tăng dần. Mảng \(a\) được gọi là Suffix Array của xâu \(S\).

Ví dụ:

• Cho xâu \(S=\)bcab.
• Ta có \(4\) xâu con:
  • \(T_1=\)bcab
  • \(T_2=\)cab
  • \(T_3=\)ab
  • \(T_4=\)b
• Mảng \(T\) sau khi sắp xếp lại theo thứ tự tăng dần là: \(T_3\), \(T_4\), \(T_1\), \(T_2\).
• Vậy ta có suffix array là \(3\), \(4\), \(1\), \(2\).

Yêu cầu:

• Cho trước Suffix Array \(a\) và số \(K\). Trong những xâu có Suffix Array \(a\), hãy tìm xâu \(S\) có thứ tự từ điển nhỏ thứ \(K\).
• Để đơn giản các xâu chỉ bao gồm các kí tự từ a đến z.

Input:

• Dòng đầu tiên có \(2\) số: \(N\), \(K\) lần lượt là số kí tự và thứ tự từ điển của xâu cần in ra \(\left(N\le 1000, K\le 10^{12}\right)\).
• Dòng thứ \(2\) chứa \(N\) số nguyên phân biệt là dãy \(a_1\), \(a_2\),..., \(a_N\).

Output:

• Gồm xâu kết quả in trên \(1\) dòng duy nhất, chỉ gồm các chữ cái thường từ a đến z, trường hợp không có kết quả thì in ra \(-1\).

4 2
3 4 1 2

bdab

Nguồn bài: VOS Round 23 - Lê Ðôn Khuê