المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۲:سوال ۹

Bacteria

همان طور که در شکل می بینید دو نوع باکتری داریم . یک نوع باکتری‌های چاق و یک نوع باکتری‌های لاغر. در ابتدا $m$‎ تا باکتری‌ لاغر داریم و ‎$n$‎ تا باکتری‌ چاق. حال این باکتری‌ها تقسیم می‌شوند. این طوری که هر باکتری لاغر پس از تقسیم به ‎$9$‎ تا باکتری لاغر و ‎$6$‎ تا باکتری چاق تقسیم خواهد شد. در ضمن یه قانون جالب دیگه هم وجود دارد و آن قانون این است که هر باکتری چاق پس از تقسیم به ‎$2$‎ تا باکتری لاغر و ‎$7$‎ تا باکتری چاق تقسیم خواهد شد. خوشبختانه عمل تقسیم به صورت هم‌زمان انجام می‌شود. یعنی همه‌ی باکتری‌ها کُلُهُم در آن واحد تقسیم می شوند‎.

حالا سوال چیست؟ سوال این است که کِی به وضعیت ‎$m'$‎ و ‎$n'$‎ می‌رسیم. یعنی چند بار باید عمل تقسیم انجام شود که ‎$m'$‎ تا باکتری لاغر و ‎$n'$‎ تا باکتری چاق بمانند. در ضمن هر وقت هر گروهی از باکتری‌ها تعدادشون بیش‌تر مساوی ‎$3000017$‎ شد، ‎$3000017$‎ تاشون می‌میرند. به عبارت ساده‌تر، کافیه همواره به پیمانه‌ی ‎$3000017$‎ کار کنید.‎

ورودی

  • در سطر اول فایل ورودی دو عدد ‎$m$‎ و ‎$n$ (تعداد باکتری‌های لاغر و چاق در وضعیت اولیه) نوشته شده است.‎
  • در سطر دوم فایل ورودی دو عدد ‎$m'$‎ و ‎$n'$ (تعداد باکتری‌ها در وضعیت نهایی) نوشته شده است.‎

خروجی

  • در تنها سطر فایل خروجی شما باید کمترین تعداد مراحل تقسیم را بنویسید.
  • در صورتی که نمی توان از وضعیت اولیه به وضعیت نهایی داده شده رسید در تنها سطر فایل خروجی عدد ‎$-1$‎ را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
1 2
13 20
1

ابزار صفحه