آزمون شاز تشریحی 1 المپیاد کامپیوتر سال 1391

از shaazzz
پرش به ناوبری پرش به جستجو

سوالات[ویرایش]

  • سوال ۱
  • سوال ۲: زورو و اسبش دارن با هم بازی می‌کنن. اول کار یه رشته‌ی خالی داریم. توی هر دور از بازی اسب زورو یه حرف Z یا H به انتهای رشته اضافه می‌کنه. بعدش زورو می‌تونه دو تا از حرف‌های رشته رو انتخاب کنه و جاشون رو با هم عوض کنه، می‌تونه هم تصمیم بگیره که هیچ کار نکنه. حالا زورو می‌خواد طوری بازی کنه که در پایان دور‌های فرد‌ (دور یکم، سوم، پنجم...) رشته‌ای که به وجود اومده قرینه باشه. رشته‌ی قرینه هم رشته‌ای هست که خودش و وارونش با هم برابر هستن. ثابت کنید زورو می‌تونه!
  • سوال ۳: سوال می‌گه که یه آقای پستچی توی گوشه بالا سمت چپ یه جدول بزرگ هست که مختصاتاش از (۱, ۱) تا (n, n) هست. این آقا می‌خواد به n تا خونه نامه برسونه. مختصات خونه i ام (ai, bi) هست. ترتیب رسوندن نامه‌ها مهم نیست. هر مرحله می‌تونه یک واحد به یکی از چهار جهت اصلی بره. یه الگوریتم بدید که بتونه با تعداد O(n√n) حرکت یه مسیری رو طی کنه که از همه‌ی خونه‌ها رد بشه و به خونه‌ی اصلیش برگرده.