trang chủ / đề bài / rectcut

Cắt Hình Chữ Nhật

Đề bài

Mô tả

Cho hình chữ nhật kích thước a×b. Nhiệm vụ là cắt nó thành các hình vuông. Mỗi lần cắt, bạn chọn một hình chữ nhật và cắt thành hai hình chữ nhật sao cho tất cả các cạnh đều có độ dài nguyên. Tìm số lần cắt ít nhất cần thực hiện.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên a và b.

Dữ liệu ra

In ra số lần cắt ít nhất.

Ràng buộc

  • 1≤a,b≤500

Ví dụ

Input Output Giải thích
2 8 3 Cắt 2×8 thành 2×4 + 2×4, rồi mỗi 2×4 thành 2×2 + 2×2: tổng 3 lần cắt
4 4 0 Đã là hình vuông, không cần cắt

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0