Mê cung Praw

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/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 2301. 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 ab lần lượt là xy. Khi đó phải tồn tại số tự nhiên k để :

    x2k,y2k đề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 (1N105)
  • Dòng thứ hai gồm n số nguyên dương không lớn hơn 109, 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 109+7.

Sample Input 1

Copy
4
1 3 3 1

Sample Output 1

Copy
5

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
732

Task:

  • Subtask 1 (10% số test) : n8
  • Subtask 2 (40% số test) : n103
  • 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 (1iA) có giá ai, dung dịch sát khuẩn loại j (1jB) có giá bj. Để 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 ci đồng nếu bạn mua một hộp khẩu trang loại xi cùng với một dung dịch sát khuẩn loại yi.

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 (1A,B,M105)
  • Dòng thứ hai gồm A số nguyên ai (1ai105) là giá của hộp khẩu trang loại i.
  • Dòng thứ ba gồm B số nguyên bj (1bj105) 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 xi,yi,ci (1xiA,1yiB,ciaxi+byi)

Output

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

Sample Input 1

Copy
2 3 1
3 3
3 3 3
1 2 1

Sample Output 1

Copy
5

Sample Input 2

Copy
1 1 2
10
10
1 1 5
1 1 10

Sample Output 2

Copy
10

Đ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 (1N100)

Output

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

Sample Input 1

Copy
1

Sample Output 1

Copy
2

Sample Input 2

Copy
2

Sample Output 2

Copy
1

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 i,2ix:Xi1<Xi.

Cho một dãy A có độ dài n. Một tập hợp Bb 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 AB1,AB2,AB3,...,ABb 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 1bin, sao cho từ tập hợp b ta có một dãy(là tập con của A) tương ứng Ab1,Ab2,Ab3,... 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 (1N105).
  • Dòng tiếp theo chứa n số nguyên Ai.

Output

  • Kết quả bài toán, chia dư cho 109+7.

Sample Input 1

Copy
5
3 1 2 3 2

Sample Output 1

Copy
18

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) : n20
  • Subtask 2 (40% số điểm) : n2.105

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 (ai=aj). 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 an 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 (1T100)
  • Dòng đầu tiên của mỗi test chứa số n (1n104)
  • Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a : a1,a2,a3,...,an(1ai109)

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
2 
4
1 2 1 1
4
1 2 3 4

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.