123Code...

Nội dung Bài tập

Mã:: OLP30.4.PHOMAI

Tên:: Chia phô mai (OLP 30/4 năm 2021)

Dạng thi:: oi

Thang điểm:: 10 điểm

Giới hạn thời gian:: 1 giây

Giới hạn bộ nhớ:: 256 MB

Được tạo bởi:: phucnq

: Share

Hai chú gấu con đã tìm được trong rừng hai miếng phô mai có khối lượng tương ứng là a và b gam (g), với a và b là hai số nguyên. Hai chú gấu tham lam đến nỗi muốn chuẩn bị đánh nhau để tranh phần miếng phô mai nhiều hơn. Một con cáo đi đến và nói: "Các chú hãy đợi đấy, tôi sẽ giúp các chú chia các miếng phô mai bằng nhau!", "Đồng ý, nhưng làm sao chia được?" - một chú gấu hào hứng nói. "Rất đơn giản, nếu khối lượng miếng phô mai nào đó được chia đều thành hai phần thì thôi sẽ ăn một phần. Nếu khối lượng miếng phô mai được chia đều làm ba thì tôi sẽ ăn hai phần ba, còn nếu chia đều làm năm thì tôi sẽ ăn bốn phần năm. Như vậy tôi sẽ ăn một ít và hai miếng phô mai sẽ bằng nhau" - con cáo nói. Hai chú gấu nghi ngờ con cáo chơi khăm mình nhưng lúc này chúng không thể tự chia hai miếng phô mai bằng nhau được nên đành phải đồng ý với lời đề nghị của cáo nhưng với một điều kiện: Cáo phải chia sao cho hai miếng phô mai bằng nhau nhanh nhất và khối lượng của chúng phải luôn là số nguyên. Yêu cầu: Bạn hãy tìm số ít nhất các thao tác đã mô tả ở trên sao cho cáo có thể chia thành hai miếng phô mai bằng nhau. Dữ liệu: Vào từ tập tin văn bản PHOMAI.INP, gồm một dòng duy nhất ghi hai số nguyên a và b cách nhau một khoảng trắng (1 <= a, b <= 10^9). Kết quả: Ra tập tin văn bản PHOMAI.OUT, gồm một dòng duy nhất ghi một số cho biết: - Trường hợp con cáo nói dối và không thể chia đều được, ghi số -1 - Ngược lại, ghi số thao tác ít nhất. Trong trường hợp hai miếng phô mai ban đầu bằng nhau thì ghi số 0. Ví dụ: PHOMAI.INP PHOMAI.OUT 15 20 3 Giải thích: Lần 1: Cáo chia miếng 15g thành 3 phần, mỗi phần 5g. Cáo ăn 2 phần, miếng còn lại bằng 5g. Lần 2: Cáo chia miếng 20g thành 2 phần, mỗi phần 10g. Cáo ăn 1 phần, miếng còn lại bằng 10g. Lần 3: Cáo chia tiếp miếng 10g thành 2 phần, mỗi phần 5g. Cáo ăn 1 phần, miếng còn lại bằng 5g. Kết quả sau 3 lần chia Cáo có 2 miếng bằng nhau và bằng 5g. Không có cách chia nào khác nhanh hơn 3 lần chia nên kết quả là 3. PHOMAI.INP PHOMAI.OUT 14 8 -1 PHOMAI.INP PHOMAI.OUT 4 4 0
Quảng cáo