Cắt hình chữ nhật

Xem dạng PDF
Gửi bài giải
Điểm: 2,00 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Người ta dùng máy cắt để cắt một hình chữ nhật có kích thước ~M \times N~ ~(N~, ~M~ nguyên dương ~\leq 5000)~ thành một số ít nhất các hình vuông có kích thước nguyên dương và có các cạnh song song với cạnh hình chữ nhật ban đầu. Máy cắt khi cắt luôn cắt theo phương song song với một trong hai cạnh của hình chữ nhật và chia hình chữ nhật thành hai phần.

Input

Gồm ~2~ số là kích thước ~M~, ~N~ cách nhau bởi dấu cách.

Output

Ghi số ~k~ là số hình vuông được tạo ra

Sample Input

5 6

Sample Output

5

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    baotram1312  đã bình luận lúc 3, Tháng 11, 2024, 19:49

    test lớn thế thì qhd O(n^3) sao dc


  • 10
    Thanh_Do  đã bình luận lúc 27, Tháng 8, 2024, 16:59 ← sửa 4

    #goodluck #persist

    How to solve VNCUT

    Lưu ý: Comment này bao gồm thuật toán.

    Các gợi ý

    Bạn nên đọc từ trên xuống dưới.

    • Hint 0:

    Liệu ta có cần một thuật toán ~O(N \times M)~?

    • Hint 1:

    Hãy để ý số lượng biến cần input và số lượng bộ test

    • Hint 2:

    Hãy tưởng tượng đây là một bài interactive

    • Hint 3:

    Bài toán: Cho một số nguyên ~x~. Hãy đoán giá trị của ~x~.

    • Hint 4:

    Binary Search?

    Chúc bạn may mắn.

    Lời giải

    Note: Tuy mình không chắc chắn lắm, nhưng đây có thể là problem NP-hard và không thể giải theo cách thông thường. Vì vậy lời giải sau đây dùng một thuật hơi tà đạo một chút :>

    Giải thích ngắn gọn: Tìm kiếm nhị phân các giá trị của ~N~ và ~M~ trong mọi bộ test, sử dụng feedback WA/TLE/MLE/RE/~\dots~ như một hàm kiểm tra trong tìm kiếm nhị phân.

    Giải thích chi tiết:

    Với trường hợp ~N \times M \times (N + M) \le 10^7~, ta sử dụng thuật toán quy hoạch động. Cố gắng pass được nhiều test nhất có thể (mình sẽ giải thích sau). Ta có thể đúng từ ~7~ - ~15~ ~/~ ~20~ test tuỳ vào cách cài đặt.

    Với các trường hợp lớn, ta không thể sử dụng DP nữa. Lúc này, ta có một số nhận xét như sau:

    • Ta chỉ input hai số nguyên ~N~ và ~M~.
    • Trong trường hợp trung bình, ta sẽ đúng được ~\sim 14~ test (hãy làm mọi cách để đúng nhiều test nhất có thể, tốt nhất là từ 10 trở lên), có nghĩa là ta chỉ còn lại ~\sim 6~ test (từ đây sẽ gọi là những test còn lại).

    Vậy câu hỏi đặt ra là, liệu ta có thể biết được chính xác các giá trị của ~N~ và ~M~ trong những test còn lại hay không? Câu trả lời là chắc chắn là có thể!

    Từ hint 3, ta sẽ áp dụng tìm kiếm nhị phân giá trị của lần lượt ~N~ và ~M~ của những test còn lại, tương tự như problem Đoán số. Bài toán yêu cầu ta phải đoán một số chưa biết trước, cũng hệt như điều ta cần làm. Tuy nhiên, câu hỏi đặt ra là feedback < hay >= tương tự như trong bài đếm số thì ta phải lấy từ đâu?

    Ta có nhận xét quan trọng rằng, kết quả chấm phản ánh bản chất của bộ test (ví dụ thông thường, bạn TLE vì test lớn, WA do trường hợp đặc biệt, ... -> phản bản chất của bộ test là test lớn/trường hợp đặc biệt), đồng nghĩa với việc nó có khả năng cho ta biết được giá trị của ~N~ và ~M~. Ngoài ra, nó có đến 5 loại kết quả khác nhau bao gồm AC, WA, TLE, RE, MLE. Điều này có thể mường tượng như việc nếu <trình chấm> là một kiểu dữ liệu, nó có thể trả về 5 loại kết quả khác nhau.

    Nhìn lại problem Đoán số, bản chất hàm <bool> check(~mid~) của ta chỉ có thể trả về một trong hai giá trị: true và false (true tương ứng với ~mid~ < giá trị cần tìm, và false trong trường hợp ngược lại). Vậy thì ở đây, <trình chấm> cũng có thể trả về cho ta 2 loại kết quả! Lúc này, mỗi lần submit của ta có thể xem như một lần tìm kiếm nhị phân và gọi hàm gọi hàm <trình chấm> check(~mid~). Khi đó, nếu ~mid < N~, ta có thể cho test đó WA, còn nếu ~mid \ge N~, ta có thể cho test đó RE (Runtime Error). Do đây là tìm kiếm nhị phân nên số lượng thao tác (submit) tối đa cần dùng cho một test là ~\log(5000) \sim 12~ lần. Để làm cho một test WA, ta có thể output bừa một dãy kí tự gì đó, còn để RE thì ta có thể output ~s.top()~ của một stack ~s~ rỗng.

    Lúc này ta sẽ cần lặp đi lặp lại điều đó cho mọi test, với độ phức tạp (số lần submit) là ~O((numfail \times \log{5000}) \times 2)~ (do vậy nên ta cần cố gắng đúng nhiều test nhất có thể để đỡ đau lưng :<). Để tối ưu, ta có thể áp dụng tư tưởng tìm kiếm nhị phân song song (nhanh hơn một chút).

    Sau khi đã có giá trị ~N~ và ~M~ của mọi bộ test, ta chạy một chương trình duy nhất với giới hạn ~5000 \times 5000~ (~5 phút). Sau đó ta chia trường hợp, if else test và AC.

    Update 1: Đây không phải là thuật toán tối ưu, bạn có thể biến đổi dựa trên tư tưởng trên.


  • -13
    HotStepBroz  đã bình luận lúc 11, Tháng 6, 2023, 7:04

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    Eula_Simp_Lord  đã bình luận lúc 21, Tháng 3, 2022, 15:23

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 6
      kh0i  đã bình luận lúc 22, Tháng 3, 2022, 3:47

      Chia thành 2 hình 3x3 và 3 hình 2x2 bạn nhé :D


  • -16
    Rukashi  đã bình luận lúc 14, Tháng 10, 2021, 9:43

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 0
    ngkan  đã bình luận lúc 17, Tháng 5, 2021, 11:03

    Bài đã được thêm test.


    • -38
      stormgamming  đã bình luận lúc 1, Tháng 6, 2021, 13:39

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.