[Đại học Vinh - TS10 - 2025] Bài 1: Tam giác vuông

Nộp bài
Time limit: 1.0 / Memory limit: 1G

Point: 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ài
Time limit: 1.0 / Memory limit: 1G

Point: 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ự st1st2 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 st1st2, 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 st1st2 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 st1st2 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 st1st2.

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 st1st2t, 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 st1st2t, 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 st1st2f, 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 st1st2f, 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ài
Time limit: 1.0 / Memory limit: 1G

Point: 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ài
Time limit: 1.0 / Memory limit: 1G

Point: 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~