Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2019 - Tin học - Khối 10

Theo truyền thuyết, vua Sêram rất khâm phục và đã tặng thưởng cho nhà thông thái Sêta vì đã sáng tạo ra cờ vua. Phần thưởng mà Sêta mong muốn là tất cả các hạt lúa mì đặt trên bàn cờ theo quy tắc sau: Ô thứ nhất đặt một hạt, ô thứ hai đặt \(2\) hạt, ô thứ ba đặt \(4\) hạt, …, tiếp tục theo quy luật ô sau có số hạt gấp đôi số hạt của ô trước, cho tới khi đặt đến ô thứ \(64\) trên bàn cờ vua. Rất thích thú với truyền thuyết này, Long và Vân cùng nhau giải quyết bài toán sau:

Xét một bảng số kích thước \(m\) x \(n,\) các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm giao giữa hàng \(i\) và cột \(j\) được gọi là ô \((i,\) \(j).\) Với một số nguyên dương \(k\) \((k\) \(\leq\) \(10)\), lần lượt điền các số vào các ô của bảng theo nguyên tắc sau:

• Bắt đầu điền từ ô \((1,\) \(1)\) ghi số \(1.\)
• Điền lần lượt từng ô từ trên xuống dưới, từ trái qua phải. Ô tiếp theo điền giá trị gấp \(k\) lần giá trị điền ô trước.

Với bộ \(4\) số nguyên dương \((x,\) \(y,\) \(u,\) \(v)\) thỏa mãn \(1\) \(\leq\) \(x\) \(\leq\) \(u\) \(\leq\) \(m\) và \(1\) \(\leq\) \(y\) \(\leq\) \(v\) \(\leq\) \(n,\) hai bạn Long và Vân muốn tính tổng các số nằm trong các ô \((i,\) \(j)\) mà \(x\) \(\leq\) \(i\) \(\leq\) \(u\) và \(y\) \(\leq\) \(j\) \(\leq\) \(v.\)

Yêu cầu: Cho \(7\) số nguyên dương \(m,\) \(n,\) \(k,\) \(x,\) \(y,\) \(u,\) \(v,\) hãy tính tổng các số nằm trong các ô \((i,\) \(j)\) mà \(x\) \(\leq\) \(i\) \(\leq\) \(u\) và \(y\) \(\leq\) \(j\) \(\leq\) \(v\) của bảng số được điền theo quy tắc trên.

Input

• Một dòng chứa 7 số nguyên dương \(m,\) \(n,\) \(k,\) \(x,\) \(y,\) \(u,\) \(v.\)

Output

• Một dòng chứa một số là phần dư của phép chia tổng các số được tính chia cho \(111539768.\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(m=1\) và \(n\leq 10.\)
• Subtask #2 (\(20\%\) số điểm): \(m=1\) và \(n\leq 10^3.\)
• Subtask #3 (\(20\%\) số điểm): \(m=1;\) \(n\leq 10^9\) và \(v−y\leq 10^7.\)
• Subtask #4 (\(20\%\) số điểm): \(m=1\) và \(n\leq 10^9\)
• Subtask #5 (\(10\%\) số điểm): \(m,n\leq 10^9.\)

Example

4 4 2 1 2 2 3

102

Nguồn: 2019 chính thức

Long và Vân cùng nhau chơi trò chơi trên dãy số như sau: Long sẽ chọn một dãy gồm \(n\) số \(a_1, a_2,\dots , a_n\). Sau đó, Vân sẽ tìm cách biến đổi dãy số nguyên \(a_1, a_2,\dots , a_n\) về dãy đẹp bậc \(d\) bằng dãy các bước biến đổi như sau: Mỗi bước, chọn một số trong dãy, tăng hoặc giảm số đó đi một đơn vị. Một dãy \(b_1, b_2,\dots , b_n\) được gọi là dãy đẹp bậc \(d\) nếu \(b_i = b_{i−1} + d\) với \(i = 2, 3,\dots , n\). Cụ thể, dãy \(b_1, b_2 = b_1 + d, … , b_n = b_{n−1} + d\) là dãy đẹp bậc \(d\).

Ví dụ, dãy (\(3, 2, 2\)) với \(d = 1\) mất ít nhất \(3\) phép biến đổi để đưa về dãy (\(1, 2, 3\)) là một dãy đẹp bậc \(1\).

Yêu cầu: Cho dãy số nguyên \(a_1, a_2,\dots , a_n\) và số nguyên dương \(d\), hãy tính số bước ít nhất cần dùng để biến đổi dãy \(a_1, a_2,\dots , a_n\) thành một dãy đẹp bậc \(d\).

Input

• Dòng đầu chứa số nguyên \(n\) (\(n \leq 1000\)) và \(d\);
• Dòng thứ hai chứa \(n\) số nguyên mô tả dãy \(a_1, a_2,\dots , a_𝑛\).

Output

• Một dòng, chứa một số nguyên là số bước ít nhất cần dùng để biến đổi dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) thành một dãy đẹp bậc \(𝑑\).

Scoring

• Subtask #1 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^3\)
• Subtask #2 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^9\)
• Subtask #3 (\(25\%\) số điểm): \(d = 1\) và \(|a_i| \leq 10^3\)
• Subtask #4 (\(25\%\) số điểm): \(d \leq 10^9\) và \(|a_i| \leq 10^9\)

Example

3 1 
3 2 2

3

Nguồn: 2019 chính thức

Công ty Long Vân đang sản xuất robot vận chuyển hàng hóa tự động. Để làm việc đó, công ty tiến hành huấn luyện các robot trên một địa hình được chia thành một lưới các ô vuông gồm \(𝑚\) dòng (đánh số từ 1 đến \(𝑚\) theo chiều từ trên xuống dưới) và \(𝑛\) cột (đánh số từ 1 đến \(n\) theo chiều từ trái sang phải). Ô giao giữa dòng \(i\), cột \(j\) được gọi là ô (\(i, j\)), có độ cao là \(ℎ_{𝑖𝑗}\ (|ℎ_{𝑖𝑗}| \le 10^9)\) và có điểm thưởng là \(𝑠_{𝑖𝑗}\ (|𝑠_{𝑖𝑗}| \le 10^9)\).

Một thử nghiệm cho robot như sau: Đặt robot ở một ô nào đó, điểm thưởng của robot bằng điểm thưởng tại ô được đặt, mỗi bước robot được phép dừng lại hoặc di chuyển sang ô chung cạnh có độ cao cao hơn độ cao của ô hiện tại. Khi robot di chuyển sang ô nào đó, điểm thưởng của robot được cộng một lượng là điểm thưởng tại ô đó.

Yêu cầu: Cho địa hình thử nghiệm robot, hãy tìm vị trí đặt robot và cách di chuyển của robot để khi robot dừng lại, tổng điểm thưởng của robot là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(𝑚, 𝑛\);
• Tiếp theo là \(𝑚\) dòng mô tả độ cao của các ô trên địa hình, dòng thứ \(𝑖\) chứa \(𝑛\) số \(ℎ_{𝑖1}, ℎ_{𝑖2}, … , ℎ_{𝑖𝑛}\);
• Tiếp theo là \(𝑚\) dòng mô tả điểm thưởng của các ô trên địa hình, dòng thứ \(𝑖\) chứa \(𝑛\) số \(𝑠_{𝑖1}, 𝑠_{𝑖2}, … , 𝑠_{𝑖𝑛}\).

Output

• Một dòng chứa một số là tổng điểm nhiều nhất mà robot có thể đạt được.

Scoring

• Subtask #1 (\(20\%\) số điểm): \(𝑚 = 1; 𝑛 \leq 10^3\)
• Subtask #2 (\(20\%\) số điểm): \(𝑚 = 1; 𝑛 \leq 10^5\);
• Subtask #3 (\(20\%\) số điểm): \(𝑚 \times 𝑛 \leq 10^3\) và \(𝑠_{𝑖𝑗} = 1\);
• Subtask #4 (\(20\%\) số điểm): \(𝑚 \times 𝑛 \leq 10^5\) và \(𝑠_{𝑖𝑗} = 1\);
• Subtask #5 (\(20\%\) số điểm): \(𝑚 \times 𝑛 \leq 10^5\)

Example

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

7