Phần thưởng (DHBB CT '19)

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

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

Test 1

Input

4 4 2 1 2 2 3

Output

Nguồn: 2019 chính thức

Bình luận

3
letangphuquy 9:38 a.m. 22 Tháng 5, 2020 ← chỉnh sửa 2 →
Đề có một lỗi hết sức nghiêm trọng ạ, ô ở cột i, hàng j mới nên được được kí hiệu là (i,j). Nếu em tuân theo đề thì truy vấn đầu tiên sẽ như sau :

Bảng :

1 16 256 \n 2 32 512 \n 4 64 .. \n 8 128 .. \n

Từ ô (hàng 1 cột 2) đến ô (hàng 2 cột 3) sẽ là truy vấn : \(16 + 256 + 32 + 512\)

HOẶC, có thể đề muốn yêu cầu trải các số như câu chuyện bàn cờ vua kể ở trên, như vậy thì phần mô tả phải là : "Điền lần lượt từng ô từ trái qua phải, từ trên xuống dưới" chứ không phải là "Điền lần lượt từng ô từ trên xuống dưới, từ trái qua phải"

Kính mong admin có thể xem xét và sửa đề lại gấp ạ, nó vô cùng ức chế và khó chịu với những ai đọc đề kĩ như em (mất 1 buổi học thêm không thể hiểu được test VD)

1

sky2001 12:35 p.m. 24 Tháng 8, 2020

Đề như thế là đúng rồi bạn.

Từ trên xuống dưới từ trái qua phải có nghĩa là các ô ở hàng trên sẽ được đánh số trước các ô ở hàng dưới (bất kể có cùng cột hay không), các ô cùng hàng thì được đánh số từ trái qua phải.

0

letangphuquy 4:57 p.m. 24 Tháng 8, 2020

ừm, dù sao thì mình cũng làm xong bài này cũng lâu rồi (dù sao thì em làm xong bài này cũng lâu rồi (hình như anh cùng khóa anh Hạnh nhỉ?))

3

Small 3:43 p.m. 22 Tháng 5, 2020

Đề chính thức của hội thi DHBB năm 2019 đó thanh niên letangphuquy

1 bình luận nữa