Đan Phượng
Bnumber
Nộp bàiPoint: 100
Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong hai số:
Ví dụ về dãy các số đẹp:
Hãy tìm số đẹp thứ
Input
- Gồm một dòng chứa số nguyên dương
.
Output
- In ra kết quả của bài toán.
Giới hạn:
- Subtask 1 (
số điểm): - Subtask 2 (
số điểm):
Sample Input 1
2
Sample Output 1
5
Sample Input 2
10
Sample Output 2
21
BSCOUNTK
Nộp bàiPoint: 100
Cho một dãy
Input
- Dòng đầu chứa
số nguyên dương và . - Dòng thứ hai gồm
phần tử nguyên dương miêu tả dãy .
Output
- In ra kết quả của bài toán.
Giới hạn:
- Subtask 1 (
số điểm): - Subtask 2 (
số điểm):
Sample Input 1
4 6
1 3 5 6
Sample Output 1
2
Sample Input 2
6 8
1 2 5 3 4 8
Sample Output 2
9
KSum
Nộp bàiPoint: 100
Cho
Sắp xếp mảng
Input
- Dòng đầu gồm
số nguyên dương và . - Dòng tiếp theo gồm
số nguyên dương mô tả dãy . - Dòng cuối cùng gồm
số nguyên dương mô tả dãy .
Output
- In ra kết quả của bài toán.
Constraints
, . .
Subtask
số điểm có . còn lại không có giới hạn gì thêm.
Sample Input 1
5 10
4 2 6 4 8
7 3 1 9 5
Sample Output 1
9
abc
Nộp bàiPoint: 100
Cho một xâu
Hãy in ra độ dài đoạn tốt lớn nhất.
Input
- Dòng đầu gồm số nguyên dương
miêu tả độ dài xâu. - Dòng thứ hai miêu tả xâu
. Xâu chỉ bao gồm các kí tự và có độ dài . Ouput
In ra độ dài đoạn tốt lớn nhất.
Sample Test
Input
7
aabbbcc
Output
5
Giải thích: Chọn đoạn
Điểm chung
Nộp bàiPoint: 100
Trên trục số
Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng
Dữ liệu nhập vào từ file văn bản DC.INP
:
- Dòng đầu tiên gồm hai số nguyên
và dòng sau, mỗi dòng gồm hai số nguyên mô tả hai điểm đầu và cuối của đoạn thẳng .
Kết quả ghi ra file văn bản DC.OUT
:
Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng
Ràng buộc
- Có
số test ứng với số điểm của bài thoả mãn: số test khác ứng với số điểm của bài thoả mãn: số test còn lại ứng với số điểm của bài không có ràng buộc gì thêm.
Ví dụ
Input
3 2
1 5
2 8
3 7
Output
3
Giải thích: Toạ độ của
- Điểm có toạ độ
nằm trong đoạn thẳng: đầu tiên và thứ hai. - Điểm có toạ độ
nằm trong đoạn thẳng: thứ hai và thứ ba.
Input
3 1
1 5
2 8
3 7
Output
2
Giải thích: Toạ độ của
- Điểm có toạ độ
chỉ nằm trong đoạn thẳng đầu tiên. - Điểm có toạ độ
chỉ nằm trong đoạn thẳng thứ ba.
Input
3 3
1 5
2 8
3 7
Output
3
Giải thích: Toạ độ của
SEQ
Nộp bàiPoint: 100
Cho dãy số gồm
Yêu cầu: Đếm số cặp
Input
- Dòng đầu tiên chứa
số nguyên - Dòng thứ hai chứa
số nguyên
Output
- Một số nguyên duy nhất là số lượng cặp
đếm được.
Subtask
- Subtask 1 (
số điểm): . - Subtask 2 (
số điểm): và . - Subtask 3 (
số điểm): Không có giới hạn gì thêm.
Sample Test
Input
3 0 1
1 -1 2
Output
4
Mảng cộng dồn - Cơ bản
Nộp bàiPoint: 100
Cho một dãy số nguyên
Input
5 4
1 2 3 4 5
1 2
2 3
1 5
3 4
Output
3
5
15
7
Xâu Đầy Đủ
Nộp bàiPoint: 100
Bạn được nhận
Input
- Dòng đầu tiên gồm số nguyên dương
miêu tả số lượng xâu. dòng tiếp theo, mỗi dòng bao gồm một xâu kí tự gồm các chữ cái tiếng Anh in thường.
Output
- In ra một số nguyên là kết quả bài toán.
Sample Test
Input1:
8
the
quick
brown
fox
jumps
over
lazy
dog
Output1:
1
Input2:
3
a
b
abcdefghijklmnopqrstuvwxyz
Output2:
4
Turtle Graph
Nộp bàiPoint: 100
Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.
Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.
Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.
Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.
Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.
Cho đồ thị vô hướng gồm
Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương
Thỏ đố Rùa có thể đếm số cách để điền các số
Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.
Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi
Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!
Input
- Dòng đầu tiên gồm số nguyên dương
miêu tả số câu hỏi. - Đối với mỗi câu hỏi:
- Dòng đầu tiên
số nguyên dương miêu tả số đỉnh và cạnh của đồ thị. dòng tiếp theo, mỗi dòng gồm số nguyên dương miêu tả cạnh thứ .
- Dòng đầu tiên
Output
- Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho
.
Điều kiện
. .- Dữ liệu đảo bảo rằng tổng
trong tất cả các câu hỏi không vượt quá , tương tự với tổng .
Subtask
số điểm: . số điểm: Trong mọi câu hỏi, đồ thị có dạng cây. số điểm: Không có ràng buộc gì thêm.
Ví dụ
Input:
2
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
2 1
2 1
Output:
0
4
Giải thích:
Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.
Ở câu hỏi thứ hai, có
- Điền số
vào đỉnh , số vào đỉnh . - Điền số
vào đỉnh , số vào đỉnh . - Điền số
vào đỉnh , số vào đỉnh . - Điền số
vào đỉnh , số vào đỉnh .
MaxMod
Nộp bàiPoint: 100
Cho dãy số gồm
Yêu cầu: Hãy in ra giá trị lớn nhất tìm được.
Input
- Dòng đầu tiên chứa
số nguyên duyên - Dòng thứ hai chứa dãy
gồm phần tử.
Output
- Một số nguyên duy nhất là giá trị lớn nhất tìm được.
Constraints
Subtask
- Có
số test ứng với . - Có
số test ứng với .
Sample Input 1
4 4
5 2 4 1
Sample Output 1
3
Sample Input 2
3 20
199 41 299
Sample Output 2
19
CApp
Nộp bàiPoint: 100
Cho một dãy
Ta có hàm
Hãy tìm một đoạn con có độ dài bằng
Input
- Dòng thứ nhất chứa
số nguyên dương . - Dòng thứ hai gồm
số nguyên dương miêu tả dãy .
Output
- In ra giá trị của
lớn nhất với .
Constraints
. .
Subtasks
- Subtask
: - Subtask
: Không có ràng buộc gì thêm
Sample Input 1:
6 4 2
1 2 2 1 3 4
Sample Output 1:
2
Explanation 1:
Chọn đoạn
Sample Input 2:
7 5 3
1 1 2 2 1 1 2 3
Sample Output 2:
1
Explanation 2:
Chọn đoạn
ckn
Nộp bàiPoint: 100
Cho
Subtask
- Sub
: , . (30%) - Sub
: , . (30%) - Sub
: , , . (40%)
Input
- Dòng đầu tiên gồm một số nguyên dương
miêu tả subtask mà test này tương ứng. ( ) - Dòng thứ hai gồm hai số nguyên dương
và . dòng sau, mỗi dòng gồm hai số nguyên dương , ( ) miêu tả truy vấn tương ứng.
Output
- In ra
dòng, mỗi dòng là kết quả của truy vấn tương ứng.
Sample Test
Input:
1
3 2345
6 4
8 4
15 8
Output:
15
70
1745
Cây
Nộp bàiPoint: 100
Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình.
Cho một đồ thị vô hướng gồm
Input:
- Dòng đầu gồm 2 số
và . dòng sau, mỗi dòng gồm 2 số chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.
Output:
- Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".
Sample Test 1
Input:
3 2
1 2
2 3
Output:
Yes
Sample Test 2
Input:
3 3
1 2
2 3
3 1
Output:
No
Cây mèo
Nộp bàiPoint: 100
Cho một cây vô hướng gồm
Input:
Dòng đầu gồm
Dòng sau gồm
Output:
In ra số lá mà Thinkies có thể đi vào
Mẫu:
Input:
4 1
1 1 0 0
1 2
1 3
1 4
Output:
2
Cây chẵn
Nộp bàiPoint: 100
Cho một cây có
Input
- Dòng đầu tiên chứa số nguyên dương
. dòng tiếp theo chứa 2 số là các cạnh của cây.
Output
- In ra một số nguyên số cạnh có thể xóa
- Nếu không thể có cách cắt thỏa mãn, in ra -1.
Sample Test 1
Input:
4
2 4
4 1
3 1
Output:
1
Sample Test 2
Input:
10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5
Output:
4
Cây tiền thưởng
Nộp bàiPoint: 100
Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có
Input
- Dòng đầu tiên là số nguyên dương
là số đỉnh của cây. dòng tiếp theo mỗi dòng gồm 2 số là chỉ số của đỉnh thứ . dòng tiếp theo mỗi dòng là 2 số là cạnh của cây.
Output
- In ra một số là số tiền lớn nhất bạn có thể được thưởng.
Subtasks
- Subtask 1:
. - Subtask 2: Với mỗi
, tồn tại một cạnh với . - Subtask 3: Không có điều kiện gì thêm.
Sample Test
Input:
3
1 3
4 6
7 9
1 2
2 3
Output:
8
Đỉnh tốt
Nộp bàiPoint: 100
Cho một cây vô hướng gồm
Input:
- Dòng đầu gồm 3 số
dòng sau mỗi dòng gồm 2 số là cạnh nối từ đỉnh tới .- Dòng cuối gồm
số miêu tả các đỉnh đặc biệt.
Output:
- Số đỉnh tốt.
Sample Test
Input:
6 2 3
1 5
2 3
3 4
4 5
5 6
1 2
Output:
3
Giải thích:
- 3 đỉnh tốt là đỉnh 3,4,5.
Ràng buộc
- Subtask 1:
(50%) - Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
- Subtask 3: Không giới hạn gì thêm. (20%).
Dọn tuyết
Nộp bàiPoint: 100
Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra
Input
- Dòng đầu tiên gồm 2 số tự nhiên
- Dòng tiếp theo gồm
số tự nhiên là số lượng búp bê của từng thùng. ( )
Output
- Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo
Sample Test
Input:
3 2
1 2 1
Output:
5
Giải thích:
- Có 5 cách chọn là:
với là con búp bê thứ của thùng thứ
seqk
Nộp bàiPoint: 100
Cho dãy số gồm
Tìm dãy con liên tiếp dài nhất có tổng đúng bằng
Input
- Dòng đầu nhập số nguyên dương
và . - Dòng thứ
nhập số nguyên .
Output
- In ra kết quả là độ dài dãy con thỏa mãn yêu cầu
Sample test
Input
7 7
4 3 2 1 1 1 6
Output
4
Đếm Đoạn
Nộp bàiPoint: 100
Cho số nguyên dương
Input
- Gồm một dòng duy nhất chứa số nguyên dương
.
Output
- Gồm một dòng duy nhất là kết quả bài toán.
Subtask
- Subtask
( số điểm): - Subtask
( số điểm): - Subtask
( số điểm):
Sample Input 1
9
Sample Output 1
3
Explanation 1
qsum
Nộp bàiPoint: 100
Cho dãy
Có
Input
- Dòng đầu gồm 2 số nguyên dương
và . - Dòng thứ hai gồm
số nguyên dương miêu tả dãy . . dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương , miêu tả các truy vấn.
Ouput
- In ra
dòng, mỗi dòng là kết quả của một truy vấn tương ứng.
Subtask
- Subtask
: - Subtask
: Trong tất cả các truy vấn, . - Subtask
: Không giới hạn gì thêm .
Sample Test
Input
4 3
1 2 3 4
1 2
2 3
1 4
Output
5
8
30
Tích 3 số
Nộp bàiPoint: 100
Cho số tự nhiên
Input
- Gồm số tự nhiên
.
Output
- Số bộ số thỏa mãn.
Sample Test
Input:
3
Output:
7
TPLT
Nộp bàiPoint: 100
Cho đồ thị vô hướng không có trọng số gồm
Input
- Dòng đầu tiên chứa hai số nguyên dương
. dòng sau, mỗi dòng gồm số nguyên dương và miêu tả cạnh .
Output
- In ra số thành phần liên thông của đồ thị.
Điều kiện
.
Ví dụ
Input 1:
4 3
1 2
2 3
3 4
Output 1:
1
Input 2:
5 5
1 2
2 3
3 1
4 5
5 4
Output 2:
2
MinPath
Nộp bàiPoint: 100
Đất nước
Input
- Dòng đầu tiên chứa hai số nguyên dương
. dòng sau, mỗi dòng gồm số nguyên dương và miêu tả con đường .- Dòng tiếp theo gồm
số nguyên dương miêu tả thành phố mà vị khách thứ đang ở. - Dòng cuối cùng chứa số nguyên dương
- thành phố nơi diễn ra sự kiện.
Output
- Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.
Điều kiện
.
Subtask
số điểm: . số điểm: Không giới hạn gì thêm.
Ví dụ
Input 1:
4 3 3
1 2
2 3
3 4
1 2 3
4
Output 1:
3 2 1
Input 2:
5 4 3
1 2
2 3
3 1
4 5
1 2 5
3
Output 2:
1 1 -1
MPT
Nộp bàiPoint: 100
Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận
Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang
, nếu đây là một ô bình thường có thể đi. , đây là vùng nguy hiểm tuyệt đối không được đi vào. , đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện. , đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.
Input
- Dòng đầu tiên gồm
số nguyên , miêu tả kích thước bảng. dòng sau, mỗi dòng gồm kí tự miêu tả vùng đất.
Output
- In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra
.
Điều kiện
Ví dụ
Input 1:
3 4
S...
....
...T
Output 1:
5
Input 2:
3 4
S.*T
*.*.
*...
Output 2:
7
Biocoloring
Nộp bàiPoint: 100
Năm
Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.
Đồ thị được cho có một vài điều kiện như sau:
- Không có khuyên.
- Đồ thị vô hướng.
- Đồ thị liên thông.
Input
- Dòng thứ nhất gồm số nguyên dương
miêu tả số test case. - Đối với mỗi test case:
- Dòng thứ nhất chứa số nguyên dương
miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ tới . - Dòng thứ hai gồm số nguyên dương
miêu tả số cạnh của đồ thị. dòng tiếp theo, mỗi dòng gồm hai số nguyên dương miêu tả cạnh .
- Dòng thứ nhất chứa số nguyên dương
Output
- Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".
Constraints
Sample Input 1:
3
3
3
0 1
1 2
2 0
3
2
0 1
1 2
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
Sample Output 1:
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
ThreeMove
Nộp bàiPoint: 100
Cho một đồ thị có hướng không trọng số gồm
Cho đỉnh
Input
- Dòng đầu tiên gồm
số nguyên , miêu tả số đỉnh và số cạnh. dòng sau, mỗi dòng gồm số nguyên dương miêu tả cạnh một chiều .- Dòng cuối gồm
số nguyên dương và miêu tả đỉnh xuất phát và đỉnh đích.
Output
- In ra một số là số bước ít nhất để đi từ
tới , nếu không có cách đi nào thì in ra .
Điều kiện
Ví dụ
Input 1:
5 5
1 2
2 3
3 4
4 5
5 4
1 5
Output 1:
2
Input 2:
5 4
1 2
2 3
3 4
4 5
1 5
Output 2:
-1
Mua vé
Nộp bàiPoint: 100
Có
Hãy xác định thời gian mua vé nhỏ nhất.
Input
- Dòng đầu chứa số nguyên dương
- Dòng thứ hai chứa
số nguyên dương miêu tả dãy . - Dòng thứ ba chứa
số nguyên dương miêu tả dãy .
Output
- In ra thời gian ít nhất để mua vé cho
người.
Sample Test
Input
5
2 5 7 8 4
4 9 10 10
Output
18
Bộ Năm Số
Nộp bàiPoint: 100
Trên dãy số nguyên
Ví dụ, trên dãy gồm
Yêu cầu: Cho dãy số
Input
- Dòng đầu chứa ba số nguyên
- Dòng thứ hai gồm
số nguyên .
Output
- Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.
Subtask
- Có
số test ứng với - Có
số test ứng với - Có
số test ứng với - Có
số test ứng với - Có
số test còn lại không có giới hạn gì thêm.
Sample Input 1
7 1 -1
2 8 1 9 1 -1 8
Sample Output 1
25
Sample Input 2
7 0 0
2 8 1 9 1 -1 8
Sample Output 2
9
lcmax
Nộp bàiPoint: 100
Cho một số nguyên dương
Input
- Gồm một số nguyên dương
,
Output
- In ra bội chung nhỏ nhất tìm được.
Sample Test
Input:
10
Output:
30
Giải thích: Số
Nghiện điện tử
Nộp bàiPoint: 100
Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng
nếu tổng các số từ đến lớn hơn hẳn 0.- 0 nếu tổng các số từ
đến bằng 0. nếu tổng các số từ đến nhỏ hơn hẳn 0.
Gọi
Input
- Dòng đầu tiên gồm số
- Dòng tiếp theo gồm
số của mảng
Output
- In ra một số là giá trị
lớn nhất tìm được.
Sample Test
Input:
5
-1 -2 3 -1 -1
Output
1
Sample Test 2
Input:
6
-1 2 -3 4 -5 6
Output
6
Sample Test 3
7
1 -1 -1 1 -1 -1 1
Output
-1
Giải thích:
- Test 1 chia thành (-1 -2 ) (3 -1 -1)
- Test 2 chia thành (-1 2 -3 4 -5 6)
- Test 3 chia thành (1 -1 -1 1 -1) (-1 1)
Ràng buộc:
- Subtask 1:
(30%) - Subtask 2:
(40%) - Subtask 3:
(30%)