Độ khó: Dễ (1/4 điểm)

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 chứa một số nguyên dương ~N~ với ~1 < N \le 10^4~.

Output

Một dòng chứa số lượng tam giác vuông đếm được.

Ràng buộc

• 50% số test có ~N~ thỏa mãn ~1 < N \le 10^3~.
• 34% số test có ~N~ thỏa mãn ~10^3 < N \le 5 \cdot 10^3~.
• 16% số test có ~N~ thỏa mãn ~5 \cdot 10^3 < N \le 10^4~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

10

Sample Output 1

2

Giải thích 1

Có 2 tam giác vuông tạo bởi các bộ 3 số: ~(a, b, c) = (3, 4, 5)~ và ~(6, 8, 10)~.

Sample Input 2

15

Sample Output 2

4

Giải thích 2

Có 4 tam giác vuông tạo bởi các bộ 3 số: 1) ~a = 3, b = 4, c = 5~. 2) ~a = 6, b = 8, c = 10~. 3) ~a = 5, b = 12, c = 13~. 4) ~a = 9, b = 12, c = 15~.

Độ khó: Trung bình (2/4 điểm)

Để 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 dưới 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 và sau đó tính độ tương tự theo công thức ~k = x / y~, trong đó:

• ~x~ là số lượng các 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~ là số lượng các chữ cái khác nhau có xuất hiện ở một trong hai xâu ~st1~ hoặc ~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 2 dòng, mỗi dòng chứa một xâu không vượt quá 20000 ký tự.

Output

Một dòng chứa phần nguyên của giá trị ~100 \times k~.

Ràng buộc

• 50% số test có chiều dài các xâu bé hơn 1000 ký tự.
• 30% số test có chiều dài các xâu từ 1000 ký tự đến 10000 ký tự.
• 20% số test có chiều dài các xâu từ 10001 ký tự đến 20000 ký tự.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

The eyes
They see

Sample Output 1

100

Giải thích 1

• Các chữ cái khác nhau có xuất hiện đồng thời trong cả hai xâu là ~\{t, h, e, y, s\}~, vì vậy ~x = 5~.
• Các chữ cái khác nhau có xuất hiện ở một trong hai xâu là ~\{t, h, e, y, s\}~, vì vậy ~y = 5~.
• Độ tương tự của 2 xâu là ~k = x / y = 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 2

• Các chữ cái khác nhau có xuất hiện đồng thời trong cả hai xâu là ~\{f, o, r, m\}~, vì vậy ~x = 4~.
• Các chữ cái khác nhau có xuất hiện ở một trong hai xâu là ~\{f, o, r, m, a, l\}~, vì vậy ~y = 6~.
• Độ tương tự của 2 xâu là ~k = x / y = 4 / 6 = 0.6666~, vì vậy phần nguyên của giá trị ~100 \times k = 66~.

Độ khó: Trung bình (2/4 điểm)

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, \ldots, 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, \ldots, 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ột 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 \cdot 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

Một dòng chứa số lượng gia đình nhiều nhất nhận được các gói quà.

Ràng buộc

• 50% số test có ~n~ và ~m~ thỏa mãn ~1 \le n \le 10^4~ và ~1 \le m \le n~.
• 30% số test có ~n~ và ~m~ thỏa mãn ~10^4 < n \le 10^5~ và ~10^4 < m \le n~.
• 20% số test có ~n~ và ~m~ thỏa mãn ~10^5 < n \le 2 \cdot 10^5~ và ~10^5 < m \le n~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

4 3 5
60 45 80 90
30 60 75

Sample Output 1

2

Giải thích 1

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 2

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.

(Các ví dụ minh họa cho ~n, m, k~ nhỏ.)

Độ khó: Trung bình (2/4 điểm)

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 \le i \le n~; ~1 \le j \le 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.

(Lưu ý theo ví dụ 1: điểm trung tâm phải lớn hơn hẳn mọi điểm ảnh còn lại trong bảng con; bảng con phải nằm trọn trong ảnh.)

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 \le n, m \le 5 \cdot 10^3~; ~1 \le k \le 20~), mỗi số cách nhau ít nhất một dấu cách.
• Dòng thứ ~i~ (~i = 1, 2, \ldots, 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 ảnh không có vùng sáng nổi bật thì ghi số 0.

Ràng buộc

• 50% số test có ~n, m~ và ~k~ thỏa mãn ~10^2 \le n, m \le 10^3~ và ~1 \le k \le 5~.
• 25% số test có ~n, m~ và ~k~ thỏa mãn ~10^3 < n, m \le 3 \cdot 10^3~ và ~5 < k \le 10~.
• 25% số test có ~n, m~ và ~k~ thỏa mãn ~3 \cdot 10^3 < n, m \le 5 \cdot 10^3~ và ~10 < k \le 20~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

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 1

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 2

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.

(Các ví dụ minh họa cho ~n, m, k~ nhỏ.)