De-Evolution Tam Giác

Đề bài

Mô tả

Cho một tam giác đều có độ dài cạnh là x. Ta muốn biến nó thành một tam giác đều có độ dài cạnh là y.

Trong mỗi giây, ta được phép thay đổi độ dài của đúng một cạnh của tam giác hiện tại, với hai điều kiện:

  • Sau khi thay đổi, ba cạnh vẫn tạo thành một tam giác không suy biến (có diện tích dương).
  • Tại mọi thời điểm, độ dài mỗi cạnh luôn là số nguyên dương.

Hãy tìm số giây ít nhất để biến tam giác đều cạnh x thành tam giác đều cạnh y.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên xy (3y<x100000), lần lượt là độ dài cạnh của tam giác đều ban đầu và tam giác đều cần đạt được.

Dữ liệu ra

In ra một số nguyên duy nhất là số giây ít nhất cần thiết.

Ràng buộc

  • 3y<x100000

Ví dụ

Input Output Giải thích
6 3 4 Một cách: (6,6,6)(6,6,5)(6,5,3)(5,3,3)(3,3,3), mỗi bước đều là tam giác hợp lệ. Cần 4 bước.
8 5 3 (8,8,8)(8,8,5)(8,5,5)(5,5,5). Cần 3 bước.
22 4 6 Cần 6 bước để đưa tam giác đều cạnh 22 về tam giác đều cạnh 4.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0