Nguồn: Học sinh Giỏi THPT Hà Nội năm 2021 - 2022

Cho bốn số thực \(A, B, C, D\). Hỏi tích của bốn số đó là số dương, số âm hay số \(0\)?

Input

Dữ liệu vào từ tệp văn bản TBS.INP:

• Gồm bốn dòng, mỗi dòng chứa một số thực lần lượt là \(A\), \(B\), \(C\), \(D\).
• Các số thực này thỏa mãn \(-10^{18} \le A, B, C, D \le 10^{18}\).

Output

Kết quả ra tệp văn bản TBS.OUT:

• Một số nguyên duy nhất là:
• \(1\) nếu tích bốn số là số dương;
• \(-1\) nếu tích bốn số là số âm;
• \(0\) nếu tích bốn số là số \(0\).

Examples

20.21
-1.2
-2.3
1.0

1

5.0
-8.9
0.0
123.456

0

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2021 - 2022

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ \('𝐴'\) đến \('𝑍'\) và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ \(1\) có tên là \('𝐴'\) và nhảy đến các ô tiếp theo quy luật: lần \(1\) nhảy \(1\) ô, lần \(2\) nhảy \(2\) ô, lần \(3\) nhảy \(3\) ô, \(…\), lần \(𝑁\) nhảy \(𝑁\) ô. Vậy sau \(𝑁\) lần nhảy thì robot đang ở ô nào?

Input

Dữ liệu vào từ tệp văn bản DKT.INP:

• Gồm một số nguyên dương \(N\) là số lần nhảy của robot \((N \le 10^9)\).

Output

Kết quả ra tệp văn bản DKT.OUT:

• Một kí tự duy nhất là tên của ô sau \(N\) lần robot nhảy.

Example

1

B

Note

• Sau \(1\) lần nhảy, robot ở ô thứ \(2\), có tên là kí tự \(B\).

4

K

Note

• Sau \(4\) lần nhảy, robot ở ô thứ \(11\), có tên là kí tự \(K\).

7

C

Note

• Sau \(7\) lần nhảy, robot ở ô thứ \(29\), có tên là kí tự \(C\).

Constraint

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài thoả mãn: \(𝑁 ≤ 10^3;\)
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: \(𝑁 ≤ 10^6;\)
• \(20\%\) số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2021 - 2022

Trên trục số \(Ox\), cho \(𝑁\) đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm \(𝑀\) được gọi là nằm trong đoạn thẳng \(𝐴𝐵\) nếu \(𝐴 \leq 𝑀 \leq 𝐵\).

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng \(𝐾\) đoạn thẳng.

Input

Dữ liệu vào từ tệp văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên \(𝑁\) và \(𝐾\) \((1 \leq 𝐾 \leq 𝑁 \leq 10^5);\)
• \(𝑁\) 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 \((1 \leq 𝑎 \leq 𝑏 \leq 10^{18})\).

Output

Kết quả ra tệp 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 \(𝐾\) đoạn thẳng.

Example

3 2
1 5
2 8
3 7

3

Note

• Toạ độ của \(3\) điểm nằm trong đúng \(2\) đoạn thẳng là: \(2, 6, 7\).
• Điểm có toạ độ \(2\) nằm trong \(2\) đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ \(6, 7\) nằm trong \(2\) đoạn thẳng: thứ hai và thứ ba.

3 1
1 5
2 8
3 7

2

Note

• Toạ độ của \(2\) điểm nằm trong đúng \(1\) đoạn thẳng là: \(1, 8\).
• Điểm có toạ độ \(1\) chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ \(8\) chỉ nằm trong đoạn thẳng thứ ba.

3 3
1 5
2 8
3 7

3

Note

• Toạ độ của \(3\) điểm nằm trong cả \(3\) đoạn thẳng là: \(3,4,5\).

Constraint

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(a,b \leq 10^3;\)
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(K = N;\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2021 - 2022

Trong một đất nước có \(N\) thành phố được đánh số từ \(1\) đến \(N\), các thành phố được nối với nhau bởi \(N - 1\) con đường hai chiều, đảm bảo hai thành phố bất kì có thể đi được đến nhau. Có \(M\) thành phố đang có dịch bệnh. Người ta muốn chọn thành phố để xây dựng bệnh viện dã chiến sao cho: chỉ số an toàn từ thành phố đó đến thành phố đang có dịch bệnh bất kì đều không lớn hơn \(K\) \((K\) là một số cho trước và chỉ số an toàn giữa hai thành phố \(X\) và \(Y\) được tính bằng tổng số con đường trên đường đi từ \(X\) đến \(Y)\).

Yêu cầu: Em hãy lập trình để tính xem có thể xây dựng bệnh viện dã chiến ở bao nhiêu thành phố?

Input

Dữ liệu vào từ tệp văn bản BV.INP:

• Dòng đầu tiên gồm ba số nguyên dương \(N, M, K\) \((1 \leq K \leq M \leq N \leq 10^5)\) mô tả số lượng thành phố, số lượng thành phố đang có dịch bệnh và số \(K;\)
• \(N - 1\) dòng sau gồm hai số nguyên \(u\) và \(v\) mô tả có con đường nối hai thành phố thứ \(u\) và thứ \(v\) \((1 \leq u, v \leq N);\)
• Dòng tiếp theo gồm \(M\) số nguyên \(x\) mô tả những thành phố đang có dịch bệnh \((1 \leq x \leq N)\).

Output

Kết quả ra tệp văn bản BV.OUT:

• Gồm một số nguyên duy nhất là số thành phố có thể thoả mãn để xây dựng bệnh viện dã chiến (thành phố đang có dịch bệnh cũng có thể xây dựng bệnh viện dã chiến).

Example

6 2 2
1 2
3 2
3 5
4 2
5 6
1 3

4

Note

• Có \(4\) thành phố có thể xây dựng bệnh viện dã chiến: \(1, 2, 3, 4\).

6 3 2
1 2
3 2
3 5
4 1
5 6
1 3 5

2

Note

• Có \(2\) thành phố có thể xây dựng bệnh viện dã chiến: \(2, 3\). Thành phố \(4\) không xây dựng được bệnh viện dã chiến vì chỉ số an toàn từ thành phố \(4\) đến thành phố đang dịch bệnh \(5\) là \(4\).

Constraint

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thoả mãn: \(N \leq 500;\)
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: \(N \leq 10^4;\)
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: mỗi thành phố chỉ có đường đi trực tiếp đến tối đa hai thành phố khác\(;\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2021 - 2022

Cuối ngày làm việc của một công ty giao hàng, nhân viên tranh thủ giao đơn hàng cuối trước khi trở về nhà. Công ty có \(N\) nhân viên giao hàng và \(T\) yêu cầu chở hàng, mỗi nhân viên giao hàng thực hiện không quá một yêu cầu chở hàng. Có hai kho hàng, nhân viên giao hàng cần đến một trong hai kho này lấy hàng rồi di chuyển đến địa điểm cần giao. Cho biết khoảng cách từ \(N\) nhân viên đến hai kho hàng và khoảng cách từ hai kho hàng đến \(T\) địa điểm nhận hàng. Tìm tổng khoảng cách nhỏ nhất để thực hiện được toàn bộ \(𝑇\) yêu cầu chở hàng.

Yêu cầu: Em hãy tìm cách sắp xếp các nhân viên giao hàng sao cho tổng khoảng cách nhân viên phải di chuyển là nhỏ nhất để thực hiện được toàn bộ \(T\) yêu cầu chở hàng.

Input

Dữ liệu vào từ tệp văn bản GH.INP:

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(T\) \((1 \leq T \leq N \leq 10^5);\)
• Dòng thứ hai gồm \(N\) số nguyên \(a1_i\) là khoảng cách của nhân viên thứ \(i\) đến kho \(1\) \((1 \leq i \leq N, \ 0 \leq a1_i \leq 10^9);\)
• Dòng thứ ba gồm \(N\) số nguyên \(a2_i\) là khoảng cách của nhân viên thứ \(i\) đến kho \(2\) \((1 \leq i \leq N, \ 0 \leq a2_i \leq 10^9);\)
• Dòng thứ bốn gồm \(T\) số nguyên \(b1_j\) là khoảng cách từ kho \(1\) đến địa điểm nhận hàng thứ \(j\) \((1 \leq j \leq T, \ 0 \leq b1_j \leq 10^9);\)
• Dòng thứ năm gồm \(T\) số nguyên \(b2_j\) là khoảng cách từ kho \(2\) đến địa điểm nhận hàng thứ \(j\) \((1 \leq j \leq T, \ 0 \leq b2_j \leq 10^9).\)

Output

Kết quả ra tệp văn bản GH.OUT:

• Gồm một số nguyên duy nhất là tổng khoảng cách nhỏ nhất để thực hiện được toàn bộ \(T\) yêu cầu chở hàng.

Example

3 2
1 2 2
7 5 3
3 5
2 3

10

Note

• Nhân viên giao hàng thứ \(1\), đến kho \(1\), giao hàng đến địa điểm thứ \(1\). Khoảng cách là \(1 + 3 = 4\).
• Nhân viên giao hàng thứ \(3\), đến kho \(2\), giao hàng đến địa điểm thứ \(2\). Khoảng cách là \(3 + 3 = 6\).
• Tổng khoảng cách là \(10\).

Constraint

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thoả mãn: khoảng cách từ nhân viên giao hàng đến các kho bằng nhau và khoảng cách từ các kho đến địa điểm giao hàng bằng nhau, tức là:
  \(a1_1 = a2_1, \ a1_2 = a2_2, \ldots, \ a1_N = a2_N;\)
  \(b1_1 = b2_1, \ b1_2 = b2_2, \ldots, \ b1_T = b2_T;\)
• \(10\%\) số test khác ứng với \(10\%\) số điểm của bài thoả mãn: khoảng cách từ nhân viên giao hàng đến các kho bằng nhau.
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: \(T \leq 2;\)
• \(10\%\) số test khác ứng với \(10\%\) số điểm của bài thoả mãn: \(N \leq 10;\)
• \(10\%\) số test khác ứng với \(10\%\) số điểm của bài thoả mãn: \(N \leq 100;\)
• \(10\%\) số test khác ứng với \(10\%\) số điểm của bài thoả mãn: \(T \leq 100;\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.