Xếp hình vuông (THTA Vòng Chung kết)

Xem PDF



Thời gian:
Scratch 10.0s

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một khung hình chữ nhật kích thước \(A \times B\), em được phép chọn \(K\) là số nguyên bất kì từ \(10\) đến \(20\) và tiến hành xếp các mảnh hình vuông có kích thước \(K \times K\) lên khung hình \(A \times B\) với yêu cầu:

  • Các cạnh của các mảnh hình vuông khi xếp cạnh phải song song với cạnh của khung hình;
  • Không có hình nào thừa ra ngoài hoặc chồng lên nhau;
  • Diện tích còn thừa là ít nhất.

Hãy tìm cách xếp và in ra phần diện tích còn thừa nhỏ nhất.

Input

  • Dữ liệu nhập vào từ bàn phím gồm hai dòng lần lượt là hai số tự nhiên \(A, B\) (\(20 \leq A, B \leq 10^7\)).

Output

  • In ra màn hình một số duy nhất là diện tích còn thừa nhỏ nhất thoả mãn yêu cầu đề bài.

Example

Test 1

Input
55
56
Output
55
Note

Chọn \(K = 11\) và xếp được \(25\) mảnh hình \(11 \times 11\), phần diện tích còn thừa là \(55 \cdot 56 - 25 \cdot (11 \cdot 11) = 3080 - 3025 = 55\).

Test 2

Input
21
22
Output
62
Note

Chọn \(K = 20\) và xếp được \(1\) mảnh hình \(20 \times 20\), phần diện tích còn thừa là \(21 \cdot 22 - 1 \cdot (20 \cdot 20) = 462 - 400 = 62\).

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: