شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

بایگانی

مرحله ۲ روز اول

چهارشنبه, ۱۳ ارديبهشت ۱۳۸۵، ۰۱:۵۷ ب.ظ
۱) الف) با خودتون ب) تابلویه که جواب بصورت مجموعی از اعدادمون هستن که هر کی ضریب -۱ یا ۱ داره. البته حتما یه نفر با ضریب مثبت وجود داره(با استقرا تابلوئه). پس جواب بصورت (جمع چند تا) منهای (جمع بقیه) هست. حالا ما جواب مینیمم رو در نظر میگیریم. میایم اول قسمت مثبت رو جمع می‌زنیم و بعد قسمت منفی رو جمع میزنیم و آخر این دو عدد رو از هم کم می‌کنیم.

۲) نقش رو تعریف میکنیم خطی که مینیمم مسیر رو از گوشه‌ی بالا سمت چپ به پایین سمت راست رو طی میکنه و البته از روی محیط قالیها میگذره. حالا فرض استقرا اینه که ما هر نقشی که کمتر از k تا قالی توشه میتونیم درست کنیم. حالا واسه k قالی میایم اون قالی رو در نظر میگیریم که بالا و سمت راستش خالیه ( مثلا میتونید از روی نقش اولین حرکت سمت راستمون رو دنبال کنید و به محض اینکه حرکت سمت پایین کردید این جا همون قالین). خوب حالا این قالیه رو حذف کنید و طبق استقرا بقیه رو بسازید و بعد هم اینو اضافه کنید.

۳) اول همه‌ی لامپ‌ها رو رندوم میبندیم به کلیدها. حالا دو حالت پیش میاد:
الف) یدونه لامپ روشن بشه: که بدیهیه: با ۱۰۰ حرکت خرابها رو درمیاریم و هر کلیدی رو با لامپ سالمه چک میکنیم اگر روشن شد که میفهمیم کلید درسته و لامپه نظیرش خراب بوده. اگر هم روشن نشه فقط میفهمیم که کلید خرابه. از این دومی ۵۰ بار اتفاق میفته که لامپ‌های نظیرشونرو میتونیم با اون کلید درسته چک کنیم و حله.
ب)هیچکی روشن نشه: که خوب ‍پس یار هر کس دقیقا برعکسه خودش بوده. پس ۵۰ تای اول رو در خودشون یکی شیفت میدیم جلو(یعنی ۱ به ۲, ۲ به ۳, ... , تا ۵۰ به ۱). اگه کسی روشن نشد که تابلویه وگرنه یه دونه روشن میشه. حالا بوسیله‌ی این و شبیه به بالا حل میکنیم البته توجه داشته باشید که با تعیین هرکس وضعیت اون یار قبلیش هم معلوم میشه.
اینکه چرا میشه ۲۵۰ تا حداکثر, خودتون چک کنید.

۴) سوال هم ارزه با اینکه بگیم: دو رشته اگر حداکثر در ۲ بیت تفاوت داشته باشند باید کد متفاوتی براشون خرج بشه. که این اگر کدمون حداکثر k باشه غیر ممکن و اگر k+1 باشه حتما ممکنه. که مسئله مورد اول رو می‌خواد. کافیه بیاین یدونه رشته رو با همه‌ی کسانی که باهاش تو یه بیت تفاوت دارند رو در نظر بگیرید. این دو به توان k بعلاوه‌ی ۱ رشته میشه. که چون با k بیت کد حداکثر دو به توان k حالت میشه پوشوند لذا دو تا از این رشته‌ها کد یکسان دارند و نمیتوان بینشان تفاوت گذاشت.(در حقیقت نمی‌فهمیم که کدامیک از این‌ها منظور فرستنده بودند.)

اینها هم تقریبا حل-راهنمایی بودند و مقداریش رو باید خودتون ثابت کنید.
  • ۸۵/۰۲/۱۳
  • شااززز منگولیا

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی