Problem A.
Merging arrays 1
Problem B. Number of smaller 1
Problem C. Number of Equal 2
Problem D. Segment With Small Sum 2
Problem E. Segment With big Sum 3
Problem F. Number of Segments with small sum 3
Problem G. Number of Segments with big sum 3
Problem H. Segments with small set 4
@andr
ew280
4
1
-----------------------------------------------------------------------------------------------------
Mọi thắc mắc và góp ý về đề bài các bạn liên hệ với mình qua địa chỉ email:
andrew168545824@[Link] hoặc Zalo/Telegram : 0965303260
Các bạn có thể tham khảo video lời giải của mình tại
[Link]
-----------------------------------------------------------------------------------------------------
TWO POINTERS
Problem A. Merging arrays
array.
Input
The first line contains
5
@andr
ew280
You are given two arrays, sorted in non-decreasing order. Merge them into one sorted
4
integersnandm, the sizes of the arrays (1n,m10
). The second line containsnintegersai, elements of the first array, the third line contains
9 9
ai,bi10 ).
Output
Print n+m integers, the merged array.
Example
Input Output
67 1 2 3 6 8 9 13 13 15 18 18 21 25
1 6 9 13 18 18
2 3 8 13 15 21 25
Source code tham khảo : [Link]
Problem B. Number of smaller
2
You are given two arrays, sorted in non-decreasing order. For each element of the second
array, find the number of elements in the first array strictly less than it.
Input
The first line contains
5 integersnnandmm, the sizes of the arrays (1n,m10
). The second line containsnintegersai, elements of the first array, the third line contains
9 9
ai,bi10 ).
Output
Print m numbers, the number of elements of the first array less than each of the elements
of the second array.
Example
Input Output
67 1123466
1 6 9 13 18 18
2 3 8 13 15 21 25
@andr
ew280
4
Source code tham khảo : [Link]
Problem C. Number of Equal
You are given two arrays aa and bb, sorted in non-decreasing order. Find the number of
pairs (i,j) for which ai=bj.
Input
The first line contains
5 integersnnandmm, the sizes of the arrays (1n,m10
). The second line containsnintegersai, elements of the first array, the third line contains
9 9
ai,bi10 ).
Output
Print one number, the answer to the problem.
Example
Input Output
87 11
3
11333588
1334555
Source code tham khảo : [Link]
Problem D. Segment With Small Sum
Given an array ofnintegersai. Let's say that the segment of this arraya[l..r](1lrn) is good if the sum of
5 18
Input The first line contains integersnnands(1n10 ,1s10
9). The second line contains integersai(1ai10
).
Output
@andr
Print one integer, the length of the longest good segment. If there are no such segments,
ew280
print -1.
Example
Input
7 20
4 Output
4
2643689
Source code tham khảo : [Link]
Problem E. Segment With big Sum
Given an array ofnintegersaiai. Let's say that the segment of this arraya[l..r](1lrn) is good if the sum o
Input
5 18
The first line contains integersnands(1n10 ,1s10
9). The second line contains integersai(1ai10
).
Output
Print one integer, the length of the shortest good segment. If there are no such segments, print1.
4
Example
Input Output
7 20 3
2643689
Source code tham khảo : [Link]
Problem F. Number of Segments with small sum
Given an array of n integers ai. Let's say that the segment of this array a[l..r] (1lrn) is good if the sum
Input
@andr
5 18
ew280
The first line contains integers n and s (1n10 , 1s10
). The second line contains integers ai (1ai10
4
9
).
Output
Print one integer, the number of good segments.
Example
Input Output
7 20 19
2643689
Source code tham khảo : [Link]
Problem G. Number of Segments with big sum
Given an array of n integers ai. Let's say that the segment of this array a[l..r] (1lrn) is good if the sum
Input
5 18
The first line contains integers n and s (1n10 , 1s10
9). The second line contains integers ai (1ai10
).
5
Output
Print one integer, the number of good segments.
Example
Input Output
7 20 9
2643689
Source code tham khảo : [Link]
Problem H. Segments with small set
@andr
Given an array of n integers ai. Let's say that a segment of this array a[l..r] (1lrn) is good if there are n
Input
ew280
4
The first line contains integers n and k (1n10 5
,5 0kn). The second line contains integers ai (1ai10
).
Output
Print one integer, the number of good segments.
Example
Input Output
73 20
2643683
Source code tham khảo : [Link]
Problem I. Segment with small Spread
Given an array of n integers ai. Let's say that a segment of this array a[l..r] (1lrn) is good if the differe
6
Input
5 18
The first line contains integers n and k (1n10 , 0k10
). The second line contains integers ai (1ai10
18
).
Output
Print the number of good segments.
Example
Input Output
73 16
2643689
@andr
ew280
Source code tham khảo : [Link]
4
Độ phức tạp của code trên là O(nlogn), dễ tiếp cận hơn, các bạn có thể tham khảo cách sử
dụng minimum queue để độ phức tạp là O(n).
Link tham khảo Minimum Stack/ Minimum Queue :
[Link]
