Speed it up contest #4
Mê cung Praw
SubmitPoint: 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
- 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 để :
đều là số lẻ. : là số x làm tròn xuống. Vd: = 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
- Dòng thứ hai gồm n số nguyên dương không lớn hơn
, 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
.
Sample Input 1
4
1 3 3 1
Sample Output 1
5
Giải thích đáp án :
Đườ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
9
1 3 5 7 9 11 13 15 17
Sample Output 2
732
Task:
- Subtask 1 (10% số test) :
- Subtask 2 (40% số test) :
- Subtask 3 (50% số test) : Không ràng buộc gì thêm
Hiệu thuốc
SubmitPoint: 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
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
- Dòng thứ hai gồm A số nguyên
là giá của hộp khẩu trang loại i. - Dòng thứ ba gồm B số nguyên
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
Output
- Gồm 1 dòng duy nhất là kết quả bài toán.
Sample Input 1
2 3 1
3 3
3 3 3
1 2 1
Sample Output 1
5
Sample Input 2
1 1 2
10
10
1 1 5
1 1 10
Sample Output 2
10
Đoán Tổng
SubmitPoint: 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
Output
- In ra kết quả của bài toán.
Sample Input 1
1
Sample Output 1
2
Sample Input 2
2
Sample Output 2
1
Dãy số phan xi păng
SubmitPoint: 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
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
Tức là đếm số tập hợp B: gồm
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
. - Dòng tiếp theo chứa n số nguyên
.
Output
- Kết quả bài toán, chia dư cho
.
Sample Input 1
5
3 1 2 3 2
Sample Output 1
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) :
- Subtask 2 (40% số điểm) :
Cân bằng
SubmitPoint: 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
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
- Dòng đầu tiên của mỗi test chứa số n
- Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a :
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
2
4
1 2 1 1
4
1 2 3 4
Sample Output 1
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.