آمار پرسش:
- پرسیده شده: 2022-05-10 03:32:47 -0500
- مشاهده شده: 244 بار
- بروز شده: 2022-05-10 03:40:44 -0500
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
جفت کردن قله ها و دره ها در اعداد قرینه شده - سوال سوم سال 1401 - دوره 32
تعدادی عدد متمایز دور یک دایره داریم که در ابتدا همه ی آنها سفید هستند. یک عدد را دره میگوییم، اگر از هر دو عدد مجاورش کوچکتر باشد. همچنین یک عدد را قله مینامیم، اگر از هر دو عدد مجاورش بزرگتر باشد.
روی اعداد به ترتیب از کوچک به بزرگ، عملیات زیر را انجام میدهیم:
● اگر دره است ، آن را سیاه میکنیم.
● اگر قله است، از این عدد به دو جهت حرکت میکنیم تا به اولین دره ی سیاه برسیم و از میان این دو دره ی سیاه عدد بزرگتر را انتخاب کرده و با قله ی مذکور جفت میکنیم و دره های که جفت شده را قرمز میکنیم. (اگر از دو جهت به یک دره ی سیاه یکسان رسیدیم، همان را انتخاب میکنیم. )
● در غیر این صورت ، کاری انجام نمیدهیم. به این ترتیب، در نهایت دره ها و قله ها به جفتهایی افراز میشوند. در شکل زیر، افراز حاصل از اجرای الگوریتم در یک نمونه آمده است.
حال، هر عدد را با قرینه اش جایگزین کرده و الگوریتم گفته شده را با اعداد جدید اجرا میکنیم. ثابت کنید دو عدد در اجرای دوم الگوریتم جفت میشوند، اگر و تنها اگر اعداد متناظرشان (قرینه هایشان) در اجرای اول الگوریتم جفت شده باشند
