DeMen contest (Div 1)

DeMen100ms là 1 con người đang ở tận cùng của sự cô đơn. Và cậu luôn ghét nhìn thấy người khác đi chơi với nhau. Một hôm, leanhduy123 rủ cậu đi ngồi cafe vỉa hè. Vì thấy mọi người ngoài đường đi chơi cùng nhau nên DeMen100ms rất cay cú.

• Ở ngoài đường đang có \(N\) người được đánh số từ \(1\) đến \(N\).
• Người thứ i có điểm hạnh phúc là \(HP[i]\).
• Tổng số điểm hạnh phúc là : tổng của các tích \(HP[i] * HP[j]\) \((1 \leq i < j \leq n)\)

Yêu cầu: In ra tổng số điểm hạnh phúc có thể đạt được từ \(N\) người đó.

Input

• Dòng đầu nhập \(N\) là người trên đường.
• Dòng thứ 2 là \(N\) số điểm hạnh phúc của \(N\) người.

Output

• In ra tổng điểm hạnh phúc của \(N\) người đó, vì kết quả có thể rất lớn nên lấy kết quả modulo cho \(10^9 + 7\)

Constraints

• \(N \leq 5*10^6\)
• \(0 < HP[i] \leq 3*10^4\)

Scoring

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

Example

3
1 2 3 

11

Trong bài tập này nhiệm vụ của bạn là tìm số nguyên dương \(x\) tối thiểu và bạn được cung cấp một danh sách tất cả các ước của \(x\), trừ 1 và \(x\). Nếu không thể tìm được \(x\) thỏa mãn danh sách ước thì có thể coi danh sách là mâu thuẫn.

Nói cách khác, gọi \(S(x)\) là tập hợp các ước khác \(1\) và \(x\) của \(x\). Bạn được cho tập \(D\), hãy tìm số \(x\) nhỏ nhất có \(S(x) = D\) là tập đã cho.

Input

• Dòng đầu tiên chứa số \(T\) \((T \leq 25)\) là số lượng truy vấn. Sau đó \(T\) dòng tiếp theo.
• Dòng đầu tiên của mỗi truy vấn chứa số nguyên \(n\) \((n \leq 300)\) là số lượng của danh sách.
• Dòng thứ hai của mỗi truy vấn chứa \(n\) số nguyên \(d_1, d_2, ... d_n\), với \(d_i\) \((d_i \leq 10^6)\) là một trong những ước của số đang đoán và tất cả \(d_i\) là khác biệt. Nói cách khác \(D = \{d_1, d_2, ..., d_n\}\)

Output

• Gồm \(T\) dòng mỗi dòng in ra \(-1\) nếu danh sách là mâu thuẫn, ngược lại in ra \(x\) tối thiểu.

Example

2
8
8 2 12 6 4 24 16 3
2
4 7

48
-1

Có một số vấn đề xảy ra trong phòng tin học. Do đó, người ta đã kiểm tra lại hệ thống dây cáp của phòng học.

Biết rằng:

• Máy chủ luôn kết nối với máy số 1
• Mỗi sợi dây cáp chỉ kết nối giữa hai máy bất kỳ với nhau. Đồng nghĩa, thông tin có thể chuyển qua lại giữa 2 máy này
• Máy chủ có thể gửi thông tin đến các máy khác nếu máy chủ kết nối với máy đó hoặc kết nối trung gian qua 1 số máy khác.

** Quan trọng nhất : Đường dây liên thông khi và chỉ khi máy chủ có thể chuyển thông tin đến tất cả các máy còn lại (Bằng cách trực tiếp hoặc gián tiếp)**

Vì DeMen100ms là học sinh chuyên Tin, người ta đã nhờ anh thiết lập một chương trình trả lời câu hỏi :

• Nếu đường dây liên thông thì có thể cắt tối đa bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “-“ trước đáp án) (\(-0\) cũng là một đáp án có thể xảy ra)
• Ngược lại, thì phải gắn tối thiểu bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “+” trước đáp án)

Các bạn hãy giúp anh làm việc này nhé !

Input

• Dòng đầu là 2 số nguyên dương \(n\) và \(k\) lần lượt là số máy và số dây cáp của phòng học \((n, k \leq 10^6)\)
• \(k\) dòng tiếp theo, dòng thứ \(i\) là \(2\) số nguyên dương \(a_i, b_i\) : Dây cáp thứ \(i\) nối 2 máy \(a_i\) và \(b_i\). \((a_i, b_i \leq n, a_i \neq b_i)\)

Output

• In ra kết quả của câu hỏi trên

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5, k \leq 10\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, k \leq 10^3\)
• Subtask \(1\) (\(40\%\) số điểm): \(n, k \leq 10^6\)

Example

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

-1

4 3
1 2
2 3
3 1

1

Sau khi sửa máy tính xong, giờ học lại được tiếp tục. Và thế là các học sinh phải thực hiện những phép tính trên máy tính của mình. Thế nhưng, thật thiếu công bằng khi mỗi máy tính có khả năng tính toán khác nhau.

Máy tính có số hiệu \(a\) có thể thực hiện \(1 + 2 + ... + (a - 1) + a\) phép tính/giây.

Có thể coi phòng học có vô hạn máy tính.

Yêu cầu : Với mỗi truy vấn \([L, R]\), gọi \(f(a)\) là tổng số phép tính/giây của máy có số hiệu \(a\) trong \(K\) giây. Hãy tính \(f(L) + f(L+1) + ... + f(R)\).

Input

• Dòng đầu tiên là \(T\) tương ứng với số truy vấn cần hỏi \((T \leq 5*10^5)\)
• \(T\) dòng tiếp theo, mỗi dòng là \(3\) số nguyên dương \(L, R, K\) tương ứng với truy vấn và thời gian cần hỏi và (\(L, R, K \leq 10^{18}, L \leq R)\)

Output

• In ra \(T\) dòng tương ứng với câu trả lời cho \(T\) truy vấn (Vì số có thể rất lớn nên hãy in kết quả modulo \(10^9+7\))

Scoring

• \(K <= 10^{18}\)
• Subtask \(1\) (\(20\%\) số điểm): \(T = 1; \ L, R \leq 10^5\)
• Subtask \(2\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}, R - L \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}, R - L \leq 10\)
• Subtask \(4\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}\)
• Subtask \(5\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}\)

Example

3
1 2 23
2 4 2
1 4 3

92
38
60

Trong toán học, tam giác Pascal là một mảng tam giác của các hệ số nhị thức. Các hàng của tam giác Pascal được liệt kê theo quy ước bắt đầu bằng hàng \(n = 0\) ở trên cùng (hàng \(0\)). Các mục trong mỗi hàng được đánh số từ đầu bên trái với \(k = 0\) và thường được đặt so le so với các số trong các hàng liền kề. Tam giác có thể được xây dựng theo cách sau: Trong hàng \(0\) (hàng trên cùng), có một số \(1\) duy nhất. Mỗi số của mỗi hàng tiếp theo được xây dựng bằng cách thêm số ở trên và bên trái với số ở trên và sang bên phải, coi các mục trống là \(0\). Ví dụ: số ban đầu trong hàng đầu tiên (hoặc bất kỳ số nào khác) là \(1\) (tổng của \(0\) và \(1\)), trong khi các số \(1\) và \(3\) trong hàng thứ ba được thêm vào để tạo ra số \(4\) ở hàng thứ tư.

Ta gọi \(P(n)=A[0,n-1]+A[1,n-2]+...+A[C(n/2)-1,n-C(n/2)]\)

Trong đó :

• \(n\) là số nhập trong input
• \(A[i,j]\) là số thứ \(i\) của hàng thứ \(j\) (Tính từ trái qua phải, số đầu tiên là số thứ 0)
• \(C(x)\) = Giá trị của \(x\) khi làm tròn lên. Ví dụ \(C(2.5) = 3\).
• \(A[i,j]\) = \(A[j,i]\)

Yêu cầu : Nhập số \(n\). Hãy xuất \(P(n)\). Bạn phải trả lời \(t\) câu hỏi

Input

• Dòng đầu nhập số \(t\) là số truy vấn \((t \leq 10^5)\)
• \(t\) dòng tiếp theo, mỗi dòng là mỗi số nguyên dương \(n\) \((n \leq 10^{18})\)

Output

• Xuất ra \(t\) dòng, mỗi dòng là kết quả \(P(n)\) tìm được. Vì \(P(n)\) có thể rất lớn nên hãy in ra \(P(n)\) chia lấy dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(T = 1\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)
• Subtask \(2\) (\(60\%\) số điểm): \(T \leq 10^5\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)

Example

2
1
2

1
1

DeMen100ms là một người đam mê lập trình. Và hôm nay, DeMen100ms đã tạo ra một trò để chơi với Monarchuwu: DeMen100ms sẽ dùng máy tính để tạo ngẫu nhiên 1 dãy bit nhị phân trên đường tròn với độ dài \(k\) không quá \(1000\), và DeMen100ms luôn là người đi trước.

Sẽ có \(k\) lượt tương ứng với độ dài của dãy :

• Lượt đầu tiên, DeMen100ms có thể chọn và xóa \(1\) số bất kì trong dãy bit
• \(k - 1\) lượt tiếp theo, mỗi bên sẽ chọn xóa số liền kề trên đường tròn (trái hoặc phải) so với số mà đối phương lựa chọn ở lượt trước.

Các lưu ý :

• Bên thắng là bên xóa được nhiều bit số \(1\) hơn
• Sau khi xóa, dãy sẽ tự động lại gần với nhau. Ví dụ : Xóa ký tự thứ \(2\) của '010' -> '00'
• 2 bên luôn chơi tối ưu.

Nhưng sau khi đọc luật chơi, Monarchuwu cho rằng trò chơi quá OP nên anh ta đã đề nghị ở lượt đầu, DeMen100ms phải chọn một vị trí ngẫu nhiên để trò chơi trở lại vị trí cân bằng. Và nhiệm vụ của bạn (với vai trò là cộng sự của DeMen100ms) là hãy tính giúp DeMen100ms tỉ lệ phần trăm mà DeMen100ms có thể thắng Monarchuwu (Biết sau lượt thứ nhất, cả hai người đều chơi tối ưu)

Input

• Nhập 1 dòng duy nhất là dãy bit được tạo ngẫu nhiên bởi máy tính (Độ dài của dãy bit không vượt quá \(1000\))

Output

• Đáp án của bài toán (Làm tròn đến \(2\) chữ số thập phân)

Example

1010

50.00