Contest Sinh nhật LQDOJ lần 2 - 2022 - Div.1

Một con ếch có thể nhảy theo bước với một trong hai kiểu sau: Bước ngắn có độ dài \(1\), bước dài có độ dài \(b\).

Con ếch muốn nhảy về phía trước theo đường thẳng, sao cho sau đúng \(t\) bước nhảy con ếch đi được quãng đường độ dài \(d\).

Hỏi con ếch có thể làm được điều này hay không.

Input

• Gồm một dòng duy nhất với ba số \(d\), \(t\) và \(b\) \((1 \leq d \leq 10^{18}, 1 \leq t, b \leq 10^9)\).

Output

• In ra ''Possible'' nếu con ếch có thể nhảy chính xác \(t\) bước để có được độ dài chính xác là \(d\), hoặc ''Impossible'' nếu con ếch không thể làm được điều này.

Example

10 6 3 

Possible

10 5 3

Impossible

Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối hai đỉnh \(a_i\) và \(b_i\), trên cạnh này có ghi một kí tự \(c_i\).

Một ''đường đi'' trên đồ thị có thể được biểu diễn bởi dãy số \(v_0, e_1, v_1, e_2, v_2, \ldots, v_{k-1}, e_k, v_k\), trong đó với mọi \(1 \leq i \leq k\), ta luôn có:

• \(1 \leq v_{i-1}, v_i \leq n\),
• \(1 \leq e_i \leq m\),
• Cạnh thứ \(e_i\) có hai đỉnh kề là \(v_{i-1}\) và \(v_i\).

Khi đó, đường đi này xuất phát ở đỉnh \(v_0\) và kết thúc ở đỉnh \(v_k\). Chú ý rằng các đỉnh \(v_0, v_1, \ldots, v_k\) hay các cạnh \(e_1, e_2, \ldots, e_k\) không nhất thiết phải đôi một phân biệt. Nói cách khác, một đường đi có thể đi qua một đỉnh hay một cạnh nhiều hơn một lần. Do mỗi cạnh của đồ thị có chứa một kí tự, ta viết lần lượt các chữ cái có trên các cạnh theo thứ tự của đường đi, và tạo ra xâu kí tự \(S = c_{e_1} c_{e_2} \ldots c_{e_k}\). Xâu kí tự này được gọi là ''xâu biểu diễn'' đường đi.

Cho đồ thị ở trên, bạn cần tìm ra đường đi ngắn nhất (chứa ít cạnh nhất) từ đỉnh \(1\) tới đỉnh \(2\), sao cho xâu biểu diễn của đường đi này là một xâu đối xứng.

Nhắc lại, xâu đối xứng là xâu kí tự mà khi đọc ngược hay xuôi đều như nhau. Ví dụ, a, ahiha hay abba là các xâu đối xứng; nhưng na, ahihi hay huhu thì không.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 20, 2 \leq 2 \cdot m \leq n \cdot (n - 1))\) lần lượt là số đỉnh và số cạnh của đồ thị.

• Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(a_i\), \(b_i\) \((1 \leq a_i, b_i \leq n)\) và một chữ cái Lattin in thường \(c_i\) thể hiện cạnh thứ \(i\) của đồ thị.

Output

• In ra một số nguyên duy nhất là độ dài (tính theo số cạnh) của đường đi ngắn nhất từ đỉnh \(1\) đến đỉnh \(2\) có xâu biểu diễn là xâu đối xứng. Nếu không tồn tại đường đi như vậy, in ra \(-1\).

Example

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 x 

3

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 z 

-1

Cho \(N\) điểm, đếm số cặp điểm thỏa mãn tồn tại một hình chữ nhật có cạnh song song với trục tọa độ
mà chứa cả hai điểm (có thể nằm trên cạnh) và không chứa bất kì điểm nào khác trong các điểm đã cho.

Input

• Dòng đầu chứa số \(N\) \((1 ≤ N ≤ 3·10^5)\)
• \(N\) dòng tiếp theo mỗi dòng chứa hai số \(x, y\) mô tả tọa độ của \(N\) điểm \((|x|, |y| \leq 10^9)\)

Output

• Đưa ra số cặp điểm thỏa mãn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 500\)
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 4000\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^4\)
• Subtask \(4\) (\(20\%\) số điểm): không có hai điểm nào nằm trên cùng một đường thẳng song song với một trong hai trục tọa độ
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

6
-1 -1
1 1
1 0
-1 0
-2 0
2 2 

5

Cho dãy số gồm \(N\) số nguyên không âm \(A_1,A_2,\ldots,A_N\). Ta có tổng AND của một dãy con gồm các phần tử \(A_{i_1},A_{i_2},\ldots,A_{i_k} (1\leq i_1<i_2<\ldots<i_k\leq N)\) là \(A_{i_1}\)&\(A_{i_2}\)&\(\ldots\)&\(A_{i_k}\).

Yêu cầu: Đếm số lượng dãy con có tổng AND bằng \(0\).

Input

• Dòng đầu chứa một số nguyên dương \(N (N \leq 10^6)\);
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1,A_2,…,A_N (A_i\leq 10^6)\).

Output

• In ra phần dư của số lượng dãy con có tổng AND bằng 0 trong phép chia cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(A_i \in [0,1]\).
• Subtask \(2\) (\(30\%\) số điểm): \(N,A_i \leq 1000\).
• Subtask \(3\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

3 
2 3 3 

0

4
0 1 2 3

10

6
5 2 0 5 2 1

53

Cho \(G\) là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ 1 đến \(n\). Tại đỉnh thứ \(i\) có một số nguyên dương \(a_i\). Tha và Thu chơi một trò chơi như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi, Tha đi trước
• Đến lượt mình, người chơi chọn một đỉnh \(i\) tùy ý, sau đó anh ta chia \(a_i\) cho một ước tùy ý (lớn hơn 1) của \(a_i\), sau đó với mỗi đỉnh \(j\) kề với \(i\) anh ta có thể tăng \(a_j\) lên một lượng là số nguyên không âm tùy ý (các đỉnh khác nhau có thể tăng một lượng khác nhau).
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa.
  Biết rằng hai người chơi đều rất thông minh, hãy xác định ai là người chiến thắng

Input

Dòng đầu tiên chứa \(T\) là số lượng testcase, với mỗi testcase:

• Dòng đầu tiên chứa \(n\) \(m\): số đỉnh và số cung của đồ thị
• Dòng tiếp theo chứa \(a_1\) \(a_2\) \(\ldots\) \(a_n\)
• \(m\) dòng tiếp theo mỗi dòng chứa một cung: \(u\) \(v\)

Output

• Với mỗi testcase, ghi ra trên một dòng 1/0 tương ứng là Tha/Thu chiến thắng

Scoring

• Trong tất cả các test: Tổng \(n\) và tổng \(m\) trong \(T\) testcase đều không quá \(10^5\), \(1\leq a_i \leq 10^9\)
• Subtask \(1\) (\(10\%\) số điểm): \(m=0\) và \(a_i \leq 10^5\)
• Subtask \(2\) (\(20\%\) số điểm): \(m=0\)
• Subtask \(3\) (\(30\%\) số điểm): \(a_i \leq 10^5\)
• Subtask \(4\) (\(40\%\) số điểm): không ràng buộc gì thêm

Example

2 
3 0
2 8 9
9 11
2 3 4 5 6 7 8 9 1
1 2
2 3
3 4
4 5
5 6
1 3
3 6
1 7
7 8
8 9
9 3 

0
1