Speed it up contest #4

Mê cung Praw

Time limit: 2.0 / Memory limit: 512M

Point: 100

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/181C1ZLuJW-n0Ln4Y221uAbShnJOAnLIB/view

*Lời giải: * https://drive.google.com/file/d/1IXafO_AxmNyrrDYVg2yeGIzvBKGKP3nh/view

Cho một mê cung gồm n phòng xếp thành 1 hàng, các phòng đánh số từ 1 đến n. Mỗi phòng được mã hóa bằng một số tự nhiên từ 0 đến $2^{30} - 1$ . Hải đang ở phòng số 1. Hải có thể di chuyển từ phòng a đến phòng b khi và chỉ khi:

a < b
Gọi số mã hóa của phòng a và b lần lượt là x và y. Khi đó phải tồn tại số tự nhiên k để :

$⌊ \frac{x}{2^{k}} ⌋, ⌊ \frac{y}{2^{k}} ⌋$ đều là số lẻ.

$⌊ x ⌋$ : là số x làm tròn xuống. Vd: $⌊ 1.6 ⌋$ = 1

Đồng thời, số cách di chuyển từ phòng a *đến phòng *b bằng số lượng k thỏa mãn yêu cầu trên.

Hải biết rằng mình cần đến được phòng n để thoát khỏi mê cung. Hỏi Hải có bao nhiêu cách để di chuyển từ phòng 1 đến phòng n? Hai cách di chuyển được gọi là khác nhau nếu Hải đi qua một phòng trong một cách nhưng không đi qua trong cách kia, hoặc Hải dùng 2 cách khác nhau để di chuyển giữa hai phòng. Đáp án có thể rất lớn hãy đưa ra đáp án chia dư cho 10^9 + 7.

Input

Dòng đầu tiên chứa N $(1 \leq N \leq 10^{5})$
Dòng thứ hai gồm n số nguyên dương không lớn hơn $10^{9}$ , trong đó số thứ i là số mã hóa của phòng thứ i.

Output

In ra một số nguyên duy nhất là số cách di chuyển từ phòng 1 đến phòng n, modulo $10^{9} + 7$ .

Sample Input 1

Copy

4
1 3 3 1

Sample Output 1

Copy

Giải thích đáp án :

Copy

Đường đi 1 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 0
    phòng 3 - 4 : k = 0

Đường đi 2 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 1
    phòng 3 - 4 : k = 0

Đường đi 3 :
    phòng 1 - 4 : k = 0

Đường đi 4 :
    phòng 1 - 2 : k = 0
    phòng 2 - 4 : k = 0

Đường đi 5 :
    phòng 1 - 3 : k = 0
    phòng 3 - 4 : k = 0

Sample Input 2

Copy

9
1 3 5 7 9 11 13 15 17

Sample Output 2

Copy

Task:

Subtask 1 (10% số test) : $n \leq 8$
Subtask 2 (40% số test) : $n \leq 10^{3}$
Subtask 3 (50% số test) : Không ràng buộc gì thêm

Hiệu thuốc

Submit

Time limit: 1.0 / Memory limit: 512M

Point: 100

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/1N2USUPOOdO7rEyskmAhBYtLcg2fCoaDG/view

*Lời giải: * https://drive.google.com/file/d/1jEnIuv8geT9aYUwzc5CPV4CNl7RW9QRz/view

Một hiệu thuốc bán A loại khẩu trang và B loại dung dịch sát khuẩn. Hộp khẩu trang loại i $(1 \leq i \leq A)$ có giá $a_{i}$ , dung dịch sát khuẩn loại j $(1 \leq j \leq B)$ có giá $b_{j}$ . Để khuyến khích mọi người đeo khẩu trang và sử dụng dung dịch sát khuẩn để phòng ngừa, ngăn chặn lây lan dịch bệnh Covid-19, cửa hàng quyết định tặng M loại phiếu giảm giá cho khách hàng. Phiếu thứ i sẽ giảm $c_{i}$ đồng nếu bạn mua một hộp khẩu trang loại $x_{i}$ cùng với một dung dịch sát khuẩn loại $y_{i}$ .

Hỏi bạn cần ít nhất bao nhiêu để mua một hộp khẩu trang và một dung dịch sát khuẩn. Biết rằng mỗi phiếu giảm giá chỉ sử dụng một lần.

Input

Dòng đầu tiên gồm ba số nguyên A, B, M $(1 \leq A, B, M \leq 10^{5})$
Dòng thứ hai gồm A số nguyên $a_{i}$ $(1 \leq a_{i} \leq 10^{5})$ là giá của hộp khẩu trang loại i.
Dòng thứ ba gồm B số nguyên $b_{j}$ $(1 \leq b_{j} \leq 10^{5})$ là giá của dung dịch sát khuẩn loại i.
M dòng tiếp theo, dòng thứ i gồm 3 số nguyên $x_{i}, y_{i}, c_{i}$ $(1 \leq x_{i} \leq A, 1 \leq y_{i} \leq B, c_{i} \leq a_{x_{i}} + b_{y_{i}})$

Output

Gồm 1 dòng duy nhất là kết quả bài toán.

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Đoán Tổng

Submit

Time limit: 1.0 / Memory limit: 512M

Point: 100

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/14jGaBgQ77dVgKT3jZwUgyxmMBniIJZu-/view

*Lời giải: * https://drive.google.com/file/d/1pTVSSpee2tyMRrSphdLOJGVhVPysCqKV/view

Hải chọn ra N số nguyên liên tiếp trong khoảng từ 1 đến 100. Sau đó Hải đố bạn biết tổng các số mà Hải đã chọn là chẵn hay lẻ. Hãy viết chương trình để trả lời câu đố của Hải. Nếu tổng chắc chắn là một số chẵn in ra "0", nếu tổng chắc chắn là số lẻ in ra "1", nếu tổng có thể là số chẵn hoặc lẻ in ra "2".

Input

Dòng đầu tiên gồm một số nguyên N $(1 \leq N \leq 100)$

Output

In ra kết quả của bài toán.

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Dãy số phan xi păng

Submit

Time limit: 2.0 / Memory limit: 512M

Point: 100

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/15y5cnDohfBpU4AOM1QgwDZJnui_YPp6z/view

*Lời giải: * https://drive.google.com/file/d/161OduQZ7Pnaa6kjBuAZ-2xcn5hCsaYhE/view

Một dãy X độ dài x được gọi là dãy số phan xi păng nếu $\forall i, 2 \leq i \leq x : X_{i - 1} < X_{i} .$

Cho một dãy A có độ dài n. Một tập hợp B có b phần tử có giá trị nằm trong đoạn [1,n] được gọi là tập hợp phan xi păng nếu có thể thay đổi vị trí các phần tử của dãy sau $A_{B_{1}}, A_{B_{2}}, A_{B_{3}}, . . ., A_{B_{b}}$ sao cho dãy này trở thành dãy phan xi păng.

Tức là đếm số tập hợp B: gồm $1 \leq b_{i} \leq n$ , sao cho từ tập hợp b ta có một dãy(là tập con của A) tương ứng $A_{b_{1}}, A_{b_{2}}, A_{b_{3}}, . . .$ thỏa mãn sao cho tồn tại 1 cách sắp xếp dãy này thành một dãy phan xi păng.

Vd dãy :

A : 3 1 2 3 2
Tập B có thể là {1,2} => A[1] = 3 , A[2] = 1 => ta có dãy 3,1 sắp xếp lại ta có dãy 1,3 là dãy phan xi păng
Lưu ý {1,2} = {2,1} "tập hợp"

Hãy đếm số tập hợp B là tập hợp phan xi păng.

Input

Dòng đầu tiên gồm một số nguyên N $(1 \leq N \leq 10^{5})$ .
Dòng tiếp theo chứa n số nguyên $A_{i}$ .

Output

Kết quả bài toán, chia dư cho $10^{9} + 7$ .

Sample Input 1

Copy

5
3 1 2 3 2

Sample Output 1

Copy

Giải thích

Các tập hợp thỏa mãn đó là {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}, {1,2,3}, {1,2,5}, {2,3,4}, {2,4,5}.

Task:

Subtask 1 (60% số điểm) : $n \leq 20$
Subtask 2 (40% số điểm) : $n \leq 2 . 10^{5}$

Cân bằng

Submit

Time limit: 2.0 / Memory limit: 512M

Point: 100

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/14mUwz9rvb78k4IL-GTDSkNR7PSbS4xPq/view

*Lời giải: * https://drive.google.com/file/d/1ACRIlL6TB5QrfL3eMzycZG9Ww33kVKcY/view

Cân bằng của một mảng được định nghĩa là số cặp chỉ số (i,j) (i < j) với giá trị bằng nhau $(a_{i} = a_{j})$ . Ví dụ cân bằng của mảng a = [1,1,2,2,1] là 4. Số cặp chỉ số với giá trị bằng nhau là (1,2), (1,5), (2,5) và (3,4).

Cho một mảng a có n phần tử, in ra tổng cân bằng của tất cả các mảng con của a.

Một mảng b được định nghĩa là mảng con của mảng a nếu ta có thể thu được mảng b sau khi xóa một vài phần tử (có thể là không hoặc tất cả phần tử) ở đầu và cuối của mảng a.

Input

Dòng đầu tiên gồm một số nguyên T số test $(1 \leq T \leq 100)$
Dòng đầu tiên của mỗi test chứa số n $(1 \leq n \leq 10^{4})$
Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a : $a_{1}, a_{2}, a_{3}, . . ., a_{n} (1 \leq a_{i} \leq 10^{9})$

Output

Với mỗi test, in ra một số là tổng cân bằng của tất cả mảng con của a

Sample Input 1

Copy

Sample Output 1

Copy

6
0

Giải thích

Test 1 : [1,2] cân bằng là 0, [1,1] cân bằng là 1, [1,2,1] cân bằng là 1, [2,1,1] cân bằng là 1, [1,2,1,1] cân bằng là 3. Đáp án là 6.