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

Cho hai số nguyên dương \(L\) và \(R\).

Yêu cầu: Tìm số nguyên dương \(M\) \((L \leq M < R)\) để chênh lệch giữa tổng các số nguyên liên tiếp từ \(L\) đến \(M\) và tổng các số nguyên liên tiếp từ \(M + 1\) đến \(R\) là nhỏ nhất.

Input

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

• Gồm hai số nguyên dương \(L\) và \(R\) \((L < R \leq 10^9)\).

Output

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

• Gồm một số nguyên duy nhất là số \(M\) thoả mãn.

Example

2 7

5

Note

• Tổng từ \(2\) đến \(5\) là: \(14\). Tổng từ \(6\) đến \(7\) là: \(13\)
• Chênh lệch là: \(1\)

Constraint

• Có \(60\%\) số test: \(L < R \leq 10^3\);
• Có \(40\%\) số test còn lại: \(L < R \leq 10^9\).

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

Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số \(30\). Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó: hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của \(30\).

Yêu cầu: Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ẩn đó.

Input

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

• Gồm một dòng duy nhất chứa số nguyên dương \(N\), với \(N\) có tối đa \(10^7\) chữ số là số cần giải mã.

Output

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

• Gồm một số nguyên duy nhất là số lớn nhất chia hết cho \(30\) tìm được bằng cách hoán vị các chữ số của \(N\). Nếu không tìm thấy thì đưa ra -1.

Example

1002

2100

Note

• Số \(2100\) là hoán vị lớn nhất của số \(1002\) và chia hết cho \(30\).

12498567859

-1

Note

• Không tồn tại số hoán vị nào chia hết cho \(30\).

Constraint

• Có \(50\%\) số test: \(N \leq 10^7\);
• Có \(50\%\) số test còn lại: \(N\) có tối đa \(10^9\) chữ số.

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

Trong một trò chơi, có N người chơi xếp thành một vòng tròn và được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có \(M\) lượt phát đồng xu cho người chơi với nguyên tắc như sau: mỗi lượt, chọn ngẫu nhiên hai số nguyên dương \(L\) và \(R\) \((L \leq N, R \leq N)\), phát một đồng xu cho những người chơi từ số \(L\) đến số \(R\) theo chiều kim đồng hồ.

Yêu cầu: Cho trước \(N, M\) và các cặp số \(L, R\). Tìm số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số đồng xu như vậy.

Input

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

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) là số lượng người chơi và số lượt phát đồng xu.
• \(M\) dòng sau, mỗi dòng gồm hai số nguyên dương \(L\) và \(R\) mô tả lượt phát đồng xu.

Output

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

• Gồm hai số nguyên dương là số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số đồng xu như vậy.

Example

5 2
1 5
4 2

2 4

Note

• Số đồng xu của mỗi người ở mỗi lượt phát đồng xu:
• Ban đầu: 0 0 0 0 0
• Lượt thứ nhất: 1 1 1 1 1
• Lượt thứ hai: 2 2 1 2 2
• Vậy số lượng đồng xu lớn nhất là \(2\) và có \(4\) người được \(2\) đồng xu.

Constraint

• Có \(60\%\) số test: \(N, M \leq 10^3\);
• Có \(20\%\) số test khác: \(N, M \leq 10^5\);
• Có \(20\%\) số test còn lại: \(N \leq 10^9, M \leq 10^5\).

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

Trong một trò chơi di chuyển trên bảng số có quy tắc như sau:

• Bảng số gồm có \(N\) dòng và \(M\) cột; các dòng được đánh số từ \(1\) đến \(N\), từ trên xuống dưới; các cột được đánh số từ \(1\) đến \(M\), từ trái sang phải. Ô ở dòng thứ \(u\) giao với cột thứ \(v\) được gọi là ô \((u, v)\). Ô \((u, v)\) chứa một số nguyên \(A_{uv}\) không âm.

• Từ ô \((u, v)\), người chơi có thể di chuyển sang một ô có chung cạnh: \((u - 1, v)\), \((u + 1, v)\), \((u, v - 1)\), \((u, v + 1)\) hoặc di chuyển sang một ô khác có cùng giá trị và không thể di chuyển vào ô có giá trị bằng 0. Mỗi lần di chuyển tốn một đơn vị thời gian.

Yêu cầu: Cho vị trí ô xuất phát và ô đích, tìm thời gian nhỏ nhất đi từ ô xuất phát về ô đích theo luật của trò chơi.

Input

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

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) là số dòng và số cột của bảng.
• Dòng thứ hai gồm bốn số \(x, y, z, t\) mô tả xuất phát ở ô \((x, y)\) và đích ở ô \((z, t)\).
• \(N\) dòng sau, mỗi dòng gồm \(M\) số nguyên không âm mô tả bảng số.
• Lưu ý: Mỗi số nguyên cách nhau một dấu cách. Dữ liệu đảm bảo luôn có đường đi từ ô xuất phát đến đích.

Output

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

• Gồm một số nguyên dương là số đơn vị thời gian nhỏ nhất để đi từ ô xuất phát đến ô đích thỏa mãn yêu cầu.

Example

5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 9
0 0 10 0
11 12 13 14

9

Note

• Có thể đi như các đỉnh được tô đậm: 1, 2, 3, 4, 6, 9, 8, 10, 13, 14.
  

5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 6
0 0 6 0
3 4 7 9

4

Note

• Có thể đi như các đỉnh được tô đậm: \(1, 5, 7, 7, 9.\)
  

Constraint

• Có \(40\%\) số test: \(N, M \leq 100\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng phân biệt;
• Có \(20\%\) số test khác: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng phân biệt;
• Có \(20\%\) số test khác: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng lặp lại không quá hai lần;
• Có \(20\%\) số test còn lại: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số trong bảng có thể lặp lại nhiều lần.