Cắt hình chữ nhật

View as PDF
Submit solution
Points: 2.00 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -3
    baotram1312  commented on Nov. 3, 2024, 7:49 p.m.

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


  • 6
    Thanh_Do  commented on Aug. 27, 2024, 4:59 p.m. ← edit 3

    #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 :>

    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  commented on June 11, 2023, 7:04 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -8
    Eula_Simp_Lord  commented on March 21, 2022, 3:23 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 4
      kh0i  commented on March 22, 2022, 3:47 a.m.

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


  • -16
    Rukashi  commented on Oct. 14, 2021, 9:43 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    ngkan  commented on May 17, 2021, 11:03 a.m.

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