Đại học Vinh - TS10 - 2025
[Đại học Vinh - TS10 - 2025] Bài 1: Tam giác vuông
Nộp bàiPoint: 6
Ba số nguyên dương ~a, b, c~ (~a \le b < c~) là các cạnh của một tam giác vuông nếu thỏa mãn ~a^2 + b^2 = c^2~.
Yêu cầu: Cho trước một số nguyên dương ~N~, viết chương trình đếm số tam giác vuông tạo bởi ba số nguyên dương ~a, b, c~ với điều kiện ~1 \le a \le b < c \le N~
INPUT
Một dòng gồm một số nguyên dương ~N~ với ~1 < N \le 10^4~
OUTPUT
In ra số lượng số tam giác vuông tìm được
SAMPLE INPUT 1
10
SAMPLE OUTPUT 1
2
Giải thích: Có 2 tam giác vuông được tạo bởi bộ 3 số là:
- ~a = 3,~ ~b = 4,~ ~c = 5~
- ~a = 6,~ ~b = 8,~ ~c = 10~
SAMPLE INPUT 2
15
SAMPLE OUTPUT 2
4
Giải thích: Có 2 tam giác vuông được tạo bởi bộ 3 số là:
- ~a = 3,~ ~b = 4,~ ~c = 5~
- ~a = 6,~ ~b = 8,~ ~c = 10~
- ~a = 5,~ ~b = 12,~ ~c = 13~
- ~a = 9,~ ~b = 12,~ ~c = 15~
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | ~1 < N \le 10^3~ |
2 | ~34\%~ | ~10^3 < N \le 5 \times 10^3~ |
3 | ~16\%~ | Không có ràng buộc gì thêm. |
[Đại học Vinh - TS10 - 2025] Bài 2: Xâu tương tự
Nộp bàiPoint: 5
Để phát hiện mức độ trùng lặp giữa các văn bản, người ta thường kiểm tra mức độ tương tự của các đoạn văn bản được biểu diễn theo dạng các xâu ký tự. Cho hai xâu ký tự st1
và st2
có thể chứa các chữ cái thường (~a, b, ..., z~), các chữ cái hoa (~A, B, ..., Z~) và dấu cách trắng. Để tính mức độ tương tự của hai xâu st1
và st2
, ta chuyển các xâu về dạng chữ cái thường hoặc chữ cái hoa sau đó tính độ tương tự theo công thức ~k = \frac{x}{y}~, trong đó:
- ~x~: số lượng chữ cái khác nhau có xuất hiện đồng thời trong cả 2 xâu
st1
vàst2
nhưng không tính dấu cách.
- ~y~: số lượng chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
nhưng không tính dấu cách.
Yêu cầu: Viết chương trình tính độ tương tự ~k~ của hai xâu st1
và st2
.
INPUT
Gồm hai dòng, mỗi dòng chứa một xâu không quá ~20000~ ký tự.
OUTPUT
In ra một dòng chứa phần nguyên của giá trị ~100 \times k~.
SAMPLE INPUT 1
The eyes
They see
SAMPLE OUTPUT 1
100
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1
vàst2
làt
,h
,e
,y
,s
, vì vậy ~x = 5~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
làt
,h
,e
,y
,s
, vì vậy ~y = 5~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{5}{5} = 1~, vì vậy phần nguyên của giá trị ~100 \times k = 100~.
SAMPLE INPUT 2
Form
Formal
SAMPLE OUTPUT 2
66
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1
vàst2
làf
,o
,r
,m
, vì vậy ~x = 4~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
làf
,o
,r
,m
,a
,l
, vì vậy ~y = 6~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{4}{6} = 0.6666~, vì vậy phần nguyên của giá trị ~100 \times k = 66~.
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | Chiều dài các xâu bé hơn ~1000~ ký tự |
2 | ~30\%~ | Chiều dài các xâu từ ~1000~ đến ~10000~ ký tự |
3 | ~20\%~ | Chiều dài các xâu từ ~10001~ đến ~20000~ ký tự |
[Đại học Vinh - TS10 - 2025] Bài 3: Quà cứu trợ
Nộp bàiPoint: 5
Trong một vùng bị thiên tai, có ~n~ gia đình khó khăn cần được hỗ trợ. Mỗi gia đình có một mức nhu cầu hỗ trợ riêng được biểu diễn bằng một số nguyên dương ~a_i~ (~i = 1, 2, ..., n~). Một tổ chức cứu trợ chuẩn bị ~m~ gói quà với giá trị của mỗi gói quà được biểu diễn bằng một số nguyên dương ~b_j~ (~j = 1, 2, ..., m~) để hỗ trợ các gia đình khó khăn. Tổ chức cứu trợ sẽ phát các gói quà theo nguyên tắc: nếu mỗi gia đình có nhu cầu mong muốn là ~a_i~ thì gia đình đó sẽ nhận được chỉ một gói quà có giá trị thuộc đoạn ~[a_i - k; a_i + k]~ với ~k~ là một số nguyên không âm.
Yêu cầu: Viết chương trình giúp tổ chức cứu trợ phân chia các gói quà để phát được cho nhiều gia đình nhất.
INPUT
Dòng 1 gồm ~3~ số nguyên dương ~n, m, k~ (~1 \le n \le 2 \times 10^5;~ ~1 \le m \le n;~ ~0 \le k \le 10^5~), mỗi số cách nhau ít nhất một dấu cách.
Dòng 2 gồm ~n~ số nguyên dương ~a_i~ (~10^5 \le a_i \le 10^8; 1 \le i \le n~), mỗi số cách nhau ít nhất một dấu cách.
Dòng 3 gồm ~m~ số nguyên dương ~b_j~ (~10^5 \le b_j \le 10^8;~ ~1 \le j \le m~), mỗi số cách nhau ít nhất một dấu cách.
OUTPUT
Gồm một dòng chứa số lượng gia đình nhiều nhất nhận được các gói quà.
SAMPLE INPUT 1
4 3 5
60 45 80 90
30 60 75
SAMPLE OUTPUT 1
2
Giải thích: Vì ~k = 5~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:
- ~01~ gia đình có nhu cầu cần hỗ trợ ~60~, giá trị gói quà ~60~
- ~01~ gia đình có nhu cầu cần hỗ trợ ~80~, giá trị gói quà ~75~
SAMPLE INPUT 2
5 2 3
21 15 35 10 40
32 16
SAMPLE OUTPUT 2
2
Giải thích: Vì ~k = 3~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:
- ~01~ gia đình có nhu cầu cần hỗ trợ ~35~, giá trị gói quà ~32~
- ~01~ gia đình có nhu cầu cần hỗ trợ ~15~, giá trị gói quà ~16~
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | ~1 \le n \le 10^4;~ ~1 \le m \le n~ |
2 | ~30\%~ | ~10^4 < n \le 10^5;~ ~10^4 < m \le n~ |
3 | ~20\%~ | ~10^5 < n \le 2 \times 10^5;~ ~10^5 < m \le n~ |
[Đại học Vinh - TS10 - 2025] Bài 4: Vùng sáng ảnh
Nộp bàiPoint: 4
Khi ảnh được chụp vào ban đêm, phần lớn bức ảnh sẽ tối và có thể có một số vùng sáng nhỏ được tạo ra bởi các đối tượng phát sáng. Để tìm các vùng sáng nhỏ, người ta thường chuyển ảnh cần xử lý thành một loại ảnh gọi là ảnh đa mức xám.
Ảnh đa mức xám được biểu diễn bằng một bảng gồm ~n~ hàng và ~m~ cột, trong đó các hàng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~m~, từ trái qua phải. Mỗi ô (~i~, ~j~) trong bảng chứa một số nguyên thuộc đoạn [~0~; ~255~] để biểu diễn mức độ sáng của một điểm ảnh tại hàng ~i~ và cột ~j~ (~1~ ≤ ~i~ ≤ ~n~; ~1~ ≤ ~j~ ≤ ~m~). Giá trị tại ô (~i~, ~j~) càng lớn thì mức sáng của điểm ảnh càng cao (~0~: đen; ~255~: trắng). Một điểm ảnh ở ô (~i~, ~j~) được gọi là điểm sáng nổi bật nếu nó là điểm trung tâm và có giá trị mức sáng lớn nhất trong một bảng con hình vuông có chiều dài cạnh là ~2k + 1~, bảng này là một vùng sáng ảnh. Một vùng sáng nổi bật nhất trong ảnh là một vùng sáng ảnh có tổng giá trị mức sáng của các điểm ảnh lớn nhất so với các vùng sáng khác.
Yêu cầu: Viết chương trình tìm một vùng sáng nổi bật nhất trong ảnh.
INPUT
Dòng ~1~ gồm ~3~ số nguyên dương ~n~, ~m~, ~k~ (~10^2~ ≤ ~n~, ~m~ ≤ ~5~ × ~10^3~; ~1~ ≤ ~k~ ≤ ~20~), mỗi số cách nhau ít nhất một dấu cách;
Dòng thứ ~i~ (~i~ = ~1~, ~2~, ..., ~n~) trong ~n~ dòng tiếp theo, mỗi dòng ghi ~m~ số nguyên thuộc đoạn [~0~; ~255~], mỗi số cách nhau ít nhất một dấu cách.
OUTPUT
Một dòng chứa tổng giá trị mức sáng của các điểm ảnh trong vùng sáng nổi bật nhất, nếu không có vùng sáng nổi bật thì ghi số ~0~.
SAMPLE INPUT 1
4 5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
SAMPLE OUTPUT 1
0
Giải thích: Với ~k = 1~, ảnh không có vùng sáng nổi bật nhất.
SAMPLE INPUT 2
5 5 1
1 2 1 3 1
1 1 9 1 1
1 2 3 6 4
1 1 5 7 5
2 3 4 6 5
SAMPLE OUTPUT 2
45
Giải thích:
- Với ~k~ = ~1~, ảnh có ~2~ điểm sáng nổi bật ở các ô (~2~,~3~) và (~4~,~4~).
- Vùng sáng nổi bật nhất có tổng giá trị mức sáng các điểm ảnh là ~45~.
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | ~10^2 < n, m \le 10^3~ và ~1 \le k \le 5~ |
2 | ~25\%~ | ~10^3 < n, m \le 3 \times 10^3~ và ~5 < k \le 10~ |
3 | ~25\%~ | ~3 \times 10^3 < n, m \le 5 \times 10^3~ và ~10 < k \le 20~ |