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

Xem PDF



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\)\(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)\)\(x\) \(\leq\) \(i\) \(\leq\) \(u\)\(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)\)\(x\) \(\leq\) \(i\) \(\leq\) \(u\)\(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\)\(n\leq 10.\)
  • Subtask #2 (\(20\%\) số điểm): \(m=1\)\(n\leq 10^3.\)
  • Subtask #3 (\(20\%\) số điểm): \(m=1;\) \(n\leq 10^9\)\(v−y\leq 10^7.\)
  • Subtask #4 (\(20\%\) số điểm): \(m=1\)\(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
102

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