المپدیا

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

ابزار کاربر

ابزار سایت


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

فهرست مندرجات

رقص مگس‌ها

$N$ مگس بر روی صفحه‌ای در نقاطی با شماره‌های ۱، ۲، … و $N$ نشسته‌اند. ساعتی روی میز قرار دارد که ثانیه‌شمار آن با صدای مشخصی حرکت می‌کند. از زمان شروع به کار ساعت و دقیقا در ابتدای هر ثانیه، کلیه‌ی مگس‌ها از نقطه‌ای که در آن قرار دارند بلند شده، در مکان قبلی یکی دیگر از مگس‌ها بر روی صفحه می‌نشینند. زمان پرواز هر مگس از یک ثانیه کم‌تر است و هیچ دو مگسی در یک نقطه نمی‌نشینند. می‌دانیم که مگسی که در نقطه‌ای مانند $i$ است در ابتدای ثانیه‌ی بعدی به نقطه‌ی دیگری مانند $j$‌می‌رود. با تکرار این حرکت‌ها، به نظر می‌رسد که مگس‌ها به طور دسته جمعی می‌رقصند. این رقص ادامه می‌یابد تا لحظه‌ای که تمامی مگس‌ها در آن لحظه به مکان‌های اولیه‌ی خود بازگردند.

برنامه‌ای بنویسید که با دریافت $N$، نحوه‌ی حرکت مگس‌ها (شماره‌ی نقطه‌ای که یک مگس از یک نقطه‌ی مشخص به آن‌جا پرواز می‌کند) را طوری تعیین کند که رقص مگس‌ها بیش‌ترین زمان ممکن طول بکشد.

ورودي

ورودی برنامه $N$ است که از صفحه کلید خوانده می‌شود. فرض کنید $n\leq 100$.

خروجي

در فایل خروجی در سطر اول مقدار $N$ و در $N$ سطر بعدی $i$ و $j$ را بنویسید، به این معنی که مگس واقع در نقطه‌ی $i$ ام در ابتدای ثانیه‌ی بعد به نقطه‌ی $j$ ام می‌رود. ( $i$ و $j$ ممکن است با هم برابر باشند.) در آخرین سطر، مقدار زمانی را که رقص مگس‌ها طول می‌کشد بنویسید.


ابزار صفحه