Mirror Olympic Miền Trung

Input

• Dòng thứ nhất chứa số \(A + B\).
• Dòng thứ hai chứa số \(A − B\).

Output

• Dòng thứ nhất ghi \(A\);
• Dòng thứ hai ghi \(B\).

Example

0
-200 

-100
100

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng: Mọi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố. Trong bài toán này bạn được cho một số tự nhiên chẵn \(n\), bạn hãy đếm số lượng cặp số nguyên tố \(a , b (a ≤ b)\) mà \(a + b = n\).

Input

• Gồm một dòng chứa một số tự nhiên chẵn \(n\).

Output

• Gồm dòng chứa một số là số lượng cặp số nguyên tố \(a , b\) mà \(a ≤ b\) và \(a + b = n\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^6\).

Example

10 

2

“Mẹ mua cho con heo đất, mẹ mua cho con heo đất í a í a, ngày hôm nay em vui lắm, cầm
heo trên tay em ngắm, í à í a, làm sao cho heo mau lớn làm sao cho heo mau lớn í à í a.
Heo không đòi ăn cơm, heo không đòi ăn cám, heo chỉ cần em bé trên tay ầu ơ, em không
thèm mua kem, em không thèm mua bánh, em để dành cho heo, em lì xì heo đất 200 mỗi ngày.
Này heo ơi! ngoan nhé! í a! này heo con ơi mau lớn í a”

Bắt đầu từ ngày hôm nay, mỗi ngày mẹ sẽ đưa cho em một số tờ tiền để nuôi heo. Cụ thể,
ngày thứ \(𝑖\) mẹ sẽ đưa cho em \(𝑠_𝑖\) tờ với các mệnh giá: \(𝑐_{𝑖,1}, 𝑐_{𝑖,2}, . . , 𝑐_{𝑖,𝑠_𝑖}\). Em sẽ lựa chọn (hoặc
không chọn) một tờ trong số các tờ mẹ đưa để “lì xì” cho heo với điều kiện: tờ tiền lựa chọn
của những ngày sau có mệnh giá không nhỏ hơn tờ tiền đã lựa chọn của những ngày trước.

Yêu cầu: Hãy lựa chọn tờ tiền để heo mau lớn nhất.

Input

• Dòng đầu chứa số \(𝑛\) là số ngày;
• \(𝑛\) dòng sau, mỗi dòng mô tả các tờ tiền mà mẹ cho. Dòng thứ \(𝑖\) mô tả ngày thứ \(𝑖\), số đầu tiên của dòng là \(𝑠_𝑖\), tiếp theo là các số \(𝑐_{𝑖,1}, 𝑐_{𝑖,2}, . . , 𝑐_{𝑖,𝑠_𝑖}\)
  (\(𝑐_{𝑖,𝑗} \leq 10^6\))

Output

• Gồm một dòng chứa tổng số tiền lớn nhất có thể chọn được để nuôi heo.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(𝑛 \leq 20\) và các \(𝑠_𝑖\) bằng 1;
• Subtask \(1\) (\(25\%\) số điểm): \(𝑛 \leq 10^5\) và các \(𝑠_𝑖\) bằng 1;
• Subtask \(1\) (\(25\%\) số điểm): \(𝑛 \leq 1000\) và \(𝑠_𝑖 \leq 50\);
• Subtask \(1\) (\(25\%\) số điểm): \(𝑛 \leq 1000\) và \(𝑠_1 + 𝑠_2 + ⋯ + 𝑠_𝑛 \leq 10^6\).

Example

 6
3 1 1 1
2 2 3
2 2 3
1 1
2 2 2
2 2 2 

9

Để phòng ngừa dịch cúm gia cầm mới, Bộ Nông nghiệp và phát triển nông thôn nghiên cứu,
tìm hiểu cách thức lây lan của một loại virus mới, làm cơ sở để lên phương án phòng chống.
Qua một thời gian nghiên cứu các nhà khoa học phát hiện ra cơ chế lây lan rất đơn giản sau
đây: Trước hết, vùng lãnh thổ khảo sát được biểu diễn bởi một bảng kích thước \(𝑛 × 𝑚\) được
chia thành lưới ô vuông đơn vị. Các cột của bảng được đánh số từ 1 tới \(𝑛\), từ trái qua phải và
các dòng của bảng được đánh số từ 1 tới \(𝑚\), từ dưới lên trên. Ô nằm trên giao của cột \(𝑖\) và
dòng \(𝑗\) được gọi là ô (\(𝑖,𝑗\)). Khi tại ô (\(𝑖,𝑗\)) có virus thì sau một đơn vị thời gian virus sẽ lây lan
sang các ô chung cạnh và chung đỉnh với ô đó.

Trên vùng lãnh thổ khảo sát, người ta quy hoạch \(𝑘\) khu đất để nuôi gia cầm. Mỗi khu là một
hình chữ nhật chiếm trọn một số ô của bảng và các cạnh song song với cạnh của bảng. Khu
thứ \(𝑖\) xác định bởi ô trái dưới (\(𝑎_𝑖, 𝑏_𝑖\)) và ô phải trên (\(𝑐_𝑖, 𝑑_𝑖\)). Các hình chữ nhật này không nhất
thiết rời nhau vì có một số gia cầm có thể sống chung trên một vùng đất.

Yêu cầu: Với cơ chế lây lan của virus đã biết và bản đồ các khu đất đã quy hoạch để nuôi các
gia cầm, hãy viết một chương trình để trả lời nhanh câu hỏi: Sau thời điểm \(𝑡\) tính từ lúc phát
hiện virus tại ô (\(𝑥_0, 𝑦_0\)) có bao nhiêu ô trong các khu quy hoạch bị lây virus. Giả thiết rằng ô
(\(𝑥_0, 𝑦_0\)) không nằm trong bất kỳ khu đất quy hoạch nào và thời điểm xuất hiện virus được
tính là 0.

Input

• Dòng đầu là 5 số \(𝑛, 𝑚, 𝑘, 𝑥_0\) và \(𝑦_0\) (\(1 \leq 𝑥_0 \leq 𝑛; 1 \leq 𝑦_0 \leq 𝑚\));
• Dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa 4 số \(𝑎_𝑖, 𝑏_𝑖, 𝑐_𝑖, 𝑑_𝑖\) (\(1 \leq 𝑎_𝑖 \leq 𝑐_𝑖 \leq 𝑛; 1 \leq 𝑏_𝑖 \leq 𝑑_𝑖 \leq 𝑚\));
• Dòng tiếp theo chứa số \(𝑞\) là số các câu hỏi cần trả lời (\(1 \leq 𝑞 \leq 𝑚𝑎𝑥(𝑛, 𝑚)\));
• Dòng cuối cùng chứa \(q\) số \(𝑡_1,𝑡_2, … ,𝑡_𝑞\) là thời điểm tương ứng với các câu hỏi, mỗi số có giá trị không lớn hơn \(10^6\).

Output

• Gồm một dòng chứa \(𝑞\) số lần lượt là kết quả trả lời của 𝑞 câu hỏi.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 1000; 1 \leq 𝑘 \leq 100; 1 \leq 𝑞 \leq 100\);
• Subtask \(2\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 10^6; 1 \leq 𝑘 \leq 400\);

Example

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

4 17 12

Trên lưới ô vuông gồm \(𝑚\) dòng và \(𝑛\) cột. Các dòng được đánh số từ 1 đến \(𝑚\) từ trên xuống dưới, các cột được đánh số từ 1 đến \(𝑛\) từ trái sang phải. Ô nằm giao giữa dòng \(𝑖\) và cột \(𝑗\) gọi là ô (\(𝑖,𝑗\)). Ban đầu, tại thời điểm 0, máy tính sẽ đặt \(𝑘\) robot trên lưới, robot thứ \(𝑟\) (\(𝑟 =1,2, … , 𝑘\)) được đặt ở ô (\(𝑥_𝑟, 𝑦_𝑟\)), các ô khác của lưới có thể đặt vật cản hoặc không. Mỗi đơn vị thời gian, người chơi phải điều khiển di chuyển một số con robot trong \(𝑘\) robot (có thể không điều khiển con nào). Robot chỉ thực hiện di chuyển sang một trong các ô kề cạnh hoặc kề đỉnh với ô robot đang đứng và ô đó không có vật cản, việc di chuyển này mất đúng một đơn vị thời gian.

Nhiệm vụ của người chơi là di chuyển để \(𝑘\) robot gặp nhau là sớm nhất, \(𝑘\) robot được gọi là gặp nhau nếu chúng cùng đứng trong một ô. Để trò chơi thêm thú vị, nếu ô (\(𝑖,𝑗\)) có vật cản thì ở thời điểm \(𝑑_{𝑖𝑗}\) vật cản sẽ biến mất và robot có thể đi vào ô (\(𝑖,𝑗\)) tính từ thời điểm \(𝑑_{𝑖j}\)

Input

• Dòng đầu tiên chứa 3 số \(𝑚, 𝑛, 𝑘\) (\(𝑚 \times 𝑛 \leq 5000\));
• Dòng thứ \(𝑖\) trong \(𝑚\) dòng tiếp theo chứa \(𝑛\) số nguyên, số thứ \(𝑗\) trong dòng nhận giá trị 0 mô tả ô (\(𝑖,𝑗\)) không có vật cản, hoặc -1 mô tả ô (\(𝑖,𝑗\)) có đặt robot, hoặc một số nguyên dương \(𝑑_{𝑖𝑗}\) mô tả ô (\(𝑖,𝑗\)) có vật cản và \(𝑑_{𝑖𝑗}\) là thời điểm vật cản ở ô đó biến mất (\(𝑑_{𝑖𝑗} \leq 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là thời điểm sớm nhất mà \(𝑘\) robot gặp nhau, nếu không tồn tại cách di chuyển ghi -1.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(𝑘 = 2\) và không có ô nào đặt vật cản;
• Subtask \(2\) (\(25\%\) số điểm): \(𝑘 \leq 5\) và không có ô nào đặt vật cản;
• Subtask \(3\) (\(25\%\) số điểm):\(𝑘 = 2\);
• Subtask \(4\) (\(25\%\) số điểm): \(𝑘 \leq 5\).

Example

3 4 2
-1 0 3 0
19 9 9 0
0 0 0 -1 

3