یه المپیادی الآن چی کار می‌کنه؟!

سلام بچه‌ها ، خوبید؟!

به عنوان یه المپیادی الآن باید چی کار کنی؟!

اگه معلم داری از معلمت بپرس ، اگه نداری و نمی‌دونی واقعا چی کاری کنی به حرفهای من گوش کن

اگه اولی:
ورودت گل باران! کتاب الفبای المپیاد کامپیوتر کتاب خوبیه، کتاب ترکیبیات زرد هم خوبه همون کتابی که انتشارات فاطمی زده و نویسندش علی‌رضا علی‌پوره! خیلی مهمه که الآن به شمارش و استقرا و لانه کبوتری مسلط باشی! برای حل مسئله هم می‌تونی کتاب ترکیبیات خوشخوان رو بخونی که نویسندش عباس ثروتیِ ! اگه خیلی خوب این کتابا رو خوندی و مطمئن شدی که بلدی حالا برو کتاب استراتژی‌های حل مسئله رو بخون!

اگه دومی:
اول بگم که هر نتیجه‌ای که پارسال گرفتی رو فراموش کن؛ هست کسی که سال اول مرحله اول قبول نشده بعد طلا شده! اونطرف هم هستن کسانی که سال اول جز ۳۰ نفر شدند بعد رد شدند! شما الآن باید یه چیزایی از لانه کبوتری و استقرا بلد باشید! اگه احساس می‌کنید ضعیفید می‌تونید برید سوال حل کنید؛ از تو الفبای المپیاد کامپیوتر یا ترکیبیات خوشخوان! مقدار خوبی هم باید گراف یاد بگیرید که کتاب مقدمه‌ای بر تئوری گراف که نویسندش داگلاس ب. وست هست خوبه! یه مقدار کمی هم الگوریتم یاد بگیرید، نمی‌دونم از کجا یاد بگیرید خوبه! از علی‌رضا بپرسید

اگه سومی و تو دوره نیستی:
من سه بار زنگ زدم باشگاه؛ دفعه‌ی اول گفتند «آره پسرم می‌تونی شرکت کنی». دفعه‌ی دوم گفتند «نه پسر جان نمی‌تونی شرکت کنی». دفعه‌ی سوم گفتند «آره پسر گل می‌تونی شرکت کنی». تو تابستون هم یه بار به علی شریفی (یه نفر تو کمیته ملی المپیاد کامپیوتر) میل زدم، ایشون گفتند یه قانونی تصویب شده که طبق اون قانون سوم‌ها هم می‌تونن شرکت کنن. اما مشخص نیست که این قانون از امسال اجرا بشه یا نه،، ولی گفتند که به احتمال بالا از همین امسال شروع می‌شه! شما بخونین اگه نتونستید بدید هم ضرری نکردید؛ فقط اگه برای طلا می‌خونید باید به مقدار لازم برنامه نویسی و الگوریتم هم بخونید! چون نقره‌ها و برنزهای امسال هم با شما امتحان میدند دیگه!

اگه سومی و تو دوره‌ای:
اینو بدون که تهرانی‌ها کلاس دارن و الآن دارن کلی الگوریتم و سی پلاس پلاس و اینا یاد می‌گیرن! پس تو هم بشین بجای الافی اس‌جی‌یو و یوساکو بزن! می‌تونی یه سری از چیزها رو هم می‌تونی از تو سایت تاپ‌کدر یاد بگیری!

ولی کیه که به حرفه من گوش بده D:
دمه مرحله اول و مرحله دومی نشینید استراتژی یا علی‌پور و اینا بخونیدا! فقط سوال‌های سال قبل رو حل کنید!

چند نکته

سلام، خوبین؟ خوش می گذره؟!

می خواستم چند تا نکته بگم:

1- اگه یه نگاه به سمت راست صفحه بندازین ، یه کم پایین تر ، یه بخش وجود داره به نام "آرشیو موضوعی" ، همون طور که از اسمش پیداست، مطالب توی اونجا به صورت دسته بندیه. پس اگر خواستید در مورد هر موضوعی اطلاعات کسب کنین ، می تونید به راحتی از اونجا پیدا کنید.

2- من تقریبا مطالب قبلی رو توی این دسته بندی ها گذاشتم و اگه هر قسمت کامل نباشه ( مثلا توضیح در مورد مرحله 1 ) سعی می کنیم کاملش کنیم. 

3- لطفا بقیه نویسنده ها ( چه کسانی که الان هستن ، چه کسانی که بعدا میان) هم این موضوع رو رعایت کنن!

4- لطفا پیام خصوصی یا ایمل نزنید و بپرسید برای شروع چه کنم و ... اگر سوالی داشتید ، توی بخش نظرات بپرسید تا جوابش رو همه بگیرن. البته اول آرشیو موضوعی که مورد نظرتونه رو مطالعه کنید، اگه جواب سوالتون نبود بعد بپرسید! همین دیگه ، ممنون  D:

دوره نقره-طلا

به نام خدا

سلام به همه دوستان!

من علی باباییم. هم دوره‌ای علیرضا ذاکری و یکی از نویسنده ‌های دیگه این وبلاگ.
راستش چند روز پیش با یکی از بچه‌های دوره نقره-طلا در مورد دوره‌شون صحبت می‌کردیم، فکر کردم بد نباشه اینجا هم یه سری توضیحات بدم.
تو این دوره برای بچه‌ها ۲-۳ تا دوره‌ی دو هفته‌ای می‌ذارن که توش یه سری مباحث جدید می‌گن و آخرش امتحان‌های نهایی است که توش مدال طلاها و ۶ نفری که باید برای تیم رقابت کنند مشخص می‌شه. البته احتمال داره با طرح جدید کمیته این چیزها تغییر کنه.
مهمترین مباحثی که تدریس میشه این هاست:

flow , mincut

segment tree

kmp

matching, wmatching, vertex cover, ...

2connected vertex-edge component

2sat

eulerian tour

strongly connected components

convex hull

equation system

یاد گرفتن یه الگوریتم نیاز به این داره کهخودتونبخونیدش و کدش رو بزنید. منظورم اینه که خیلی رو کلاس‌های دوره برای یاد گرفتن این چیزها حساب نکنید و خودتون اون ها رو بخونید و تمرین کنید. مخصوصا اگه معلماتون نتونن خیلی خوب بهتون توضیح بدن (اتفاقی که سر دوره ما افتاد). واسه اینکه خودتون این ها رو بخونید منبع زیاده. از نوع کتابیش CLRS و creative و از نوع اینترنتیش رو هم خودتون سرچ کنید. مثلا اولین لینک تو قسمت پیوندهای همین وبلاگ ۳ تا از این درس ها رو توضیح داده.

یکی از کارهای مهمی که بچه ها تو این دوره انجام می‌دن حل مساله‌ تو سایت‌های اینترنتی است. مهمترینش (به نظر من) usaco است. تو این سایت یه سری سوال هست که باید به ترتیب (بخش به بخش) حلشون کنید و یه سری هم مطالب آموزشی داره که توش خیلی از الگوریتم ها رو یاد داده و خیلی مفیده. سایت های دیگه هم هست که اکثرا ACMای اند ولی برای تمرین کد زدن خیلی خوبند. بهترینش (بازم به نظر خودم) SGU است. اما اولویتتون تو این سایت ها USACO باشه بهتره. لینک این سایت ها تو قسمت پیوندهای همین وبلاگ هستش.

یک کار مهمه دیگه هم امتحان دادنه. امتحان‌های آنلاین اینترنتی فت و فراوونه. یکی از خوب‌هاش بازم مال سایت usaco است و یکی دیگه یه سایته برای المپیاد ملی کرواسی که آدرس‌هاشون به ترتیب اینهاست:

http://ace.delos.com/contestgate

http://hsin.hr/coci/

به جز امتحان‌های آنلاین خودتون هم می‌تونید سوال‌ها و testdata های امتحان های قدیمی رو پیدا کنید و از خودتون امتحان بگییرید. مثلا INOI و IOI و CEOI های سال‌های قبل خوبند.

امیدوارم حرف‌هایی که زدم به دردتون بخوره.

فعلا خداحافظ.

سلام!

سلام به همه ی خوانندگان این وبلاگ پر مسمی!!

همون طور که رامتین وعده داده بود، این وبلاگ از کار نخواهد ایستاد و من نویسنده ی جدید این وبلاگ هستم.

و همین طور که اینجا نوشته ، اسمم علیرضا ذاکری ه از دبیرستان شهید اژه ای اصفهان. امسال من پیش دانشگاهی هستم و سال گذشته ( دوره 18 )  مدال طلای المپیاد کامپیوتر گرفتم. و الان مثلا توی دوره ی انتخابی تیم ملی هستم. فک می کنم همینا واسه ی معارفه کافی باشه!

قبلا وبلاگ ejoi.blogfa.com رو داشتم که حالا که اومدم اینجا ، تصمیم دارم اونجا رو بدم به بچه هایی که الان دوره نقره-طلا هستن.

امیدوارم بتونم به شما علاقه مندان المپیاد کامپیوتر کمک کنم.

و این بود مراسم تودیع و معارفه و از این حرفا.

فعلا ، یا حق.

خداحافظ

سلام!

تقریبا یک سال میگذره از اولین پستى که زدم توشاززز و تمام سعیم رو کردم که به بچه ها کمک کنم که تو مسیرِالمپیادبیفتن.
براى آخرین بار هم من مراحلِالمپیادکامپیوتر رو میگم
1-مرحله اول که به صورتِ عمومى برگزار میشه و شامل۳۰یا۴۰سوالتستی۵گزینه ایهستش که کتابمرجعشهم پاسخى بهالمپیادکامپیوتر(مرحله۱)از آقاىفولادیهستش. لازمه ی شرکت دراین امتحان هم بودن نمرهِریاضیدبیرستان بالاى۱۶یا۱۷هستش.
و در خود امتحانمسا له هایشمارش و هوش خیلى رایج هستند. (اگر شمااین امتحان رو۱۰۰%بزنید در مرحله۲،۲۵نمره خواهید گرفت و خود مرحله۲هم۲۰۰نمره درِ که با هم جمع میشه و رتبه بندى میشه، اگر۵۰%بزنید۱۲.۵نمره میگیرید و ... )

2-مرحله دوم که فقط افرادى که مرحله۱قبول شدن حق دادن این امتحان رودارند که تقریبا۳۰۰یا۴۰۰نفر هستند. این مرحله به صورتِتشریحیدر۲روز بر گزار میشود. که در هر روز شما۴سوال دارین و۵ساعت وقت و تقریباامتحان داراى۱یا۲سوالالگوریتم،۱یا۲سوال گراف ، و بقیه سوال هاهم به هوش و قدرت استدلالِ شما بر مى گرده که این بخش رو اسمشو میذارنترکیبیات.کتابمرجعاین امتحان نیز پاسخى بهالمپیادکامپیوتر(مرحله۲)از آقاىفولادیهست و براى تمرین میتونید از کتاب هاىترکیبیات علیپور، تورنمنتشهرها ،مسأله هاىالمپیادشوروى، ترکیبیات ثروتی، استراتژیحل مسأله ، الفبا و غیره استفاده کنید. (پساز این مرحله نمره ها۰میشود)

 

3-مرحله سوم دیگه شما از لحظه دولت و مردمِ ایرانالمپیادی حساب میشین واز مزایاىالمپیادی بودن میتونید استفاده کنید و گرفتن مدال در اینمرحله تقریبا صد در صد هستش. در این مرحله که به دوره تابستان معروف هستش.شما به جایى میرین به اسم باشگاه دانشپژوهانجوان واقع در خیابانسردارجنگلتهران. در اینجا به شما درسِ گراف،الگوریتم،ترکیبیات وC++میدن.
صبح ها شما سر کلاستئوریمى شینینو بعد از ظهر ها سر کلاس عملى یعنى برنامهمی نویسیناون هم به زبانC++

در آخرِ تابستان افرادى کهبرنزمیشنمدالهایخودشون رو دریافتمیکنن و افرادى که در رتبه بندى در۲۰یا۲۱نفر اول بودن به مرحله۴راهپیدا میکنن که اسمش دورهنقرهطلا هستش. (در اینجا نمره ها۰میشود)

 

4-مرحله۴شما باید تقریبا۶،۷ماه را کدِ بزنید تادر اسفند یا فروردین آماده دادن امتحان نهایى باشین!(معروف به فاینال)

در دورهنقرهطلا امتحاناتِ تئوریاز بین میروند و شما چیزى را روى برگِنمی نویسیدو فقط باید کدِ بزنید والگوریتم کار کنید.
یعنى مسأله به۲بخشتقسیم میشه:
1-حل مسأله(الگوریتم ،تئوری)
2-کدِ زدنعملى(سی پلای پلاس,عملی)
که اگر شماتئوری مسأله را حل کنید اما به هر دلیلى کدِ آن سوالغلط باشد یا وقت نکنید,نمرهِ شما۰میشود ونمره ای دریافت نخواهید کرد.

5-پس از مشخص شدن افرادِ طلا، این افراد براى تیم رقابت میکنن که اسمش میشهدوره تیم که در نهایت۴نفر به مسابقاتِ جهانى راه پیدا میکنند.

اما اینمراحلممکنه همین امسال با تصویب شدن قانون سوم ها عوض بشه یا اینکه حتى باشگاه تصویب کُنه که دوره تابستان نداریم و هزار تا چیز مثل این ولىکلیتشدر۴سال اخیر همین بوده.

یک قانون هست که اگر تیماعزامیالمپیادایکس نفر باشدآنگاه دو ایکسنفر طلا میگیرند که چون تیمالمپیادکامپیوتر۴نفر هستش درالمپیادکامپیوتر۸تا طلا میدن.(دلیل مختلف بودن تعداد طلاهای المپیادهای متفاوت همین قانونه)

 

 

 

زندگیهالمپیادیه من از تابستانِ۸۴شروع شد که به ما معرفى شد و فقطتا تابستانِ۸۵شمارشمی خوندیمبه صورتِ بسیار آهسته جلو میرفتیم
تابستانِ۸۵تصمیم گرفتم کهالمپیادکامپیوتر بخونم و نه ریاضى پسهندسه وتئوریاعداد رو کنار گذاشتم و شروع کردمترکیبیات خوندن به صورتِبسیار زیاد
تابستانِ۸۶وارد دوره تابستان شدم
و اردیبهشتِ سال۸۷طلاىالمپیادرو گرفتم!!
تا تابستانِ۸۸هم براى تیم خوندم که متاسفانه۵امشدم که معروف به تیم داغ هستش!
الان هم که دانشگاه میرم و دیگه کارى باالمپیادنخواهم داشت واسههمین آخرینپستمرو زدم تا این وبلاگ رو به بچه هاى طلاى دیگه بدم که دردوره تیمهستن !
.
در آخر هم میخواستم از دوست ها ومعلم هایخوبم آقایان وحیدلیاقتو افشیننیکزادتشکر کنم که این وبلاگ رو به من دادند.

مرحله 2

خب, یه مرحله۲دیگه هم تموم شد.
تبریک میگم به اونایى که قبول شدن و به اونایى که قبول نشدن توصیه می کنم برید و اعتراض کنین
کافیه یک سوالتون رو بد خط نوشته باشین و 0  گرفته باشین اون موقع با اعتراض۲۵نمره مى گیرین و اوضاع فرق خواهد کرد
اصولا هر سال,۳یا۴نفر اعتراضى قبول میشن.
چنان چه اعتراض هم دادین و قبول نشدین خیلى ناراحت نباشین چون راه تازه ایجلوى پاتون هست و قرار نیست همه المپیاد قبول بشن، به این فرض بذارینکه صلاح نبوده که قبول شین
یه کم که بگذاره مى فهمین اینا همه بازی هاى بچهگونه بوده و دوامش تا دانشگاه هستش.  

به نظرِ مهم ترین چیزى که المپیاد کامپیوتر داره اون قدرت استدلالی هستکه به آدم میده و کلى چیز یاد گرفتین که خیلى از مردم نمى دونن در موردشبجاى اینکه برید بخونید هل=آیا و رضاشاه آدم بدی بوده و فلانی خوب و  ...

اونایى که مرحله۲قبول شدن خوبه که یک کمىCLRSوWESTبخونن که الگوریتم و گرافشون خوب شهچون تو دوره باید درس پاس کنین و اگر۲تا درسبیفتین برنز میشین.

البته نترسین آسون پاس کردن درس ها.

براى برنامه نویسى هم++Cجعفرنژاد قمى من خودم خوندم.

البته تو دوره درس میدن ولى اینکه بتونین یک برنامه قبل دوره بنویسین خیلى مهمِه.

براى برنامه نویسى هم از سایت هاى المپیاد آمریکا وACMروسیه استفاده کنین

acm.sgu.ru

ace.delos.com

یه کم بچرخید تو سایت ها یاد مى گیرین.

من همیشه  sguرو ترجیح می دادم ولی خیلی ها می گنusacoبهتره چون درس میده. البته به زبان انگیلیسی.

 

برنامه تایپ

سلام
من ۴، ۵ تا برنامه تایپ دانلود کردم چند تاشون که واقعا بد بودن فقط میگفتند این متن و تایپ کن و یاد نمی دادن
چند تا دیگش هم پولى بودن واسه همین رفتم به سراغِ محصولاتِ لینوکس تو ویندوز که مجانى باشن
الان این لینکى که گذشتم مالِ gtypist در ویندوز هستش!!
اگر میخواهید تایپ درست ۱۰ انگشتی یاد بگیرین حتما هر مرحله که  جلو می رین اون متن و بخونید که کلید رو با انگشتِ درست بزنید چون اگر اشتباه یاد بگیرین درست کردنش خیلى مشکل خواهد بود.

همین الان، من هنوز ۳، ۴ تا دکمهِ بالاى کیبورد رو اشتباه میزنم و همون باعث میشه سرعت تایپم بیاد پائین

http://www.vultaire.net/software/gtypist/index.php.en

وقتى این صفحه باز شد شما رو (EXE (recommendedکلیک کنید و دانلودتون شروع میشه
نیم MB هم بیشتر نیست پس همه میتونن دانلود کنن

Type

سلام

به عنوان یه موجودی (بالطبع 1 سر + 2 دست + 2 پا) که داره برای المپیاد کامپیوتر دست و پا می زنه خوبه که یه کمی هم به فکر یادگیری تایپ 10 انگشتی باشین.

کلا ضایعست که یه المپیاد کامپیوتری موقع تایپ کردن سرش توی کیبورد باشه.

برای اینکه سرعت تایپتون بالا بره , کافیه که روزی نیم ساعت از زمان بیکاریتون رو ( بجای بحث سیاسی ) تایپ تمرین کنین.

فعلا سایت زیر رو پیشنهاد میکنم.

www.typingcup.com/test/test.html

در آینده ی نزدیک هم یه برنامه ی تمرین تایپ (درست و حسابی) میزارم برای دانلود . هر چند اگه خودتون هم سرچ کنین چیزای خوبی گیر میارین.

در ضمن حتما حتما سعی کنین که تایپ رو بصورت اصولی (10 انگشتی) یاد بگیرین

سوال های دوره تابستان

مساله اول: مهره ها......................................................................................................... 30 نمره

دو مساله زیر را در نظر بگیرید:

مسالهA: گرافGو تعدادی مهره روی بعضی رأس های آن داده شده است. می خواهیم مهره ها را روی یال ها طوری حرکت دهیم که زیر گراف القایی رأس های که شامل حداقل یک مهره اند همبند شده و مجموع حرکات مهره ها نیز کمینه شود.

مسألهB :
گراف2بخشىHکهمجموعه ی دو بخش آنXوYمى باشند دادهشده است. میخواهیم کوچیکترین زیر مجموعۀXمانندSرا پیدا کنیم بهطورى کهN(S)=Y
ثابت کنید اگر براى مسألهA الگوریتمچندجمله ایوجود داشته باشد براى مسألهBنیزالگوریتمچندجمله ایوجود دارد.

 

مساله دوم: رنگ کردن مربع ها........................................................................................... 35 نمره

 

nمربح به ضلح واحد طوری در صفحه قرار گرفته اند که اضلاع شان موازی محور های مختصات بوده و مختصات طولی یا عرضی هیچ دو مربعی برابر نیست. یک عددkبه شما داده شده است و به شما گفته شده که هیچk+1مربعی وجود ندارد که هر دوتایشان با هم اشتراک داشته باشند.

ثابت کنید می توان این مربح ها را با حداکثر2k-1رنگ,طوری رنگ کرد که رنگ هرمربعی که با هم اشتراک دارند متفاوت باشد.

 

مساله سوم: مجموعه........................................................................................................15 نمره

 

ثابت کنید تعداد زیرمجموعه های مجموعه ی{1,2,…n}که دارای میانگین طبیعی هستند زوج تا هستند.

 

مساله چهار : شمارش........................................................................................................ 10 نمره

 

تعداد گراف های همبند بیشتر است یا نا همبند ؟

 

مساله پنجم : باز هم مساله!؟؟؟ ............................................................................................... 0 نمره

 

اگر 4 مساله قبل را حل کردید می توانید با خوشحالی جلسه را ترک کنید,در غیر این صورت سعی کنید آن ها را حل کنید !!!!

 

سوال های 1و2و5 امتحان دوره تابستان 85 هستش !!! سوال 3 حل مساله دوره ی ما(86)سوال 4 هم تمرین گراف سال 85 !!!

اگر مرحله 2 قبول شید 100% یک امتحان با این شکل خواهید دید !

مساله ها این جوری شماره دارند و نمرشون هم جلوش نوشته شده !

نوشته شده توسط رامتین رطبی(سابق) در سه شنبه ۵ خرداد۱۳۸۸ و ساعت 15:33 |

جواب ها

براى این سوالها یه سرىلمداریم که فرض میکنیم پذیرفتیم!1-یک گراف باnراس وn یالحتما یک دور دارد- 2گرافG یک زیر گرافدو بخشى دارد که بیش از نصفیالها را دارد!-3قضیهِ هال: درگراف۲بخشى که از دو بخشِAوBتشکیل شده و هرزیرمجموعهمثلXازAداراى شرط:

|X|

 آنگاه تطابقیوجود دارد کهAرا بپوشاند!

سری 1:

1 -طبقلم۲داریم که این گراف زیرگرافیبا بیش از نصفیالها دارد!!ما  2*nتایالرا در نظر میگیریم!!!فرض کنید بخش هاىگراف۲بخشى بالا و پائینبنامیم
حالا یک سرى ازیالها جهت دار به سمتِ پائین هستند و یک سرى به سمتِ بالا!یکى از این۲دستهیال,بیشتر ازnتا است!اینnتا را در نظر بگیرید!
nتا راس داریم وnتایالپس طبقلم۱یک دور وجود دارد کهیالهایشهمه به طرف یکبخشاست پسخاصیت مورد نظر را دارد

2-ماتریسی که در هر سطر وستونش kتا۱داریم راAبنامید

از روىAیک گراف 2بخشیمى سازیمبه ازاى هر سطر وستونش یک راس می گذاریم یعنى براىماتریس2*n, n*nتا راس داریم!حالا اگر A[i][j]=1آنگاه از رأس iبخشِسطربهjبخشِ ستون ها وصل میکنیم!حالا یکگراف۲بخشى داریم که درجهِ همه راس هاkاستبا استفاده ازلم۳میتوان اثبات کرد که هرگرافkَ منتظم۲بخشى داراىتطابق کامل استحالا هر بار یک تطابق بر میداریمو تبدیل به یک گراف می کنیمو اگریالiبهjرا بر داشتیم آنگاه درماتریسی که داریم مى سازیمدرایه یiو jرا۱میکنیم!!حالا یکگرافk-1 منتظم داریم و دوباره میتوانیم یک تطابق کم کنیمبه این ترتیب ماkتا جدول خواهیم داشت که جمعِ این جدول ها میشود A

  3-همواره نفر اول میبرد به غیر ازn=1 , m=1همیشه در حرکتِ اول خانهِ(0,0)خرده میشودفرض کنید نفر اول فقط خانهِ(0,0)را میخورد و در بهترین بازى می بازد
حرکتِ اولِ نفر دوم را در نظر بگیرید!!اگر زیرِ نقطه (X,Y) را خرده باشد آنگاه نفر اول میتوانند در حرکتِاول تا خانهِ(X,Y)رو بخورد و حالا تبدیل به نفر دوم شود یعنى در واقعجاى خود را با نفر دوم عوض میکند. حالا نفر اول حتما میبرد چرا که اگر نفردوم ببرد آنگاه در حالتى که نفر اول (0,0)را میخورد و نفر دوم(X,Y)را نفر اولمی توانستهبرنده شود

 

4 -جواب نه استفرض کنیدتوانستیماین کار را انجام بدهیم!!براى اینکه این کار را انجام بدهیم باید۴۰۰۴تا معادلa=bcداشته باشیم!!یکى ازbیاcباید از۲۰۰۳کمتر باشد چون اگر نباشدb*c>2002*2002میشودخوب اگرسطریوجود داشته باشد که اعداد هاى۱تا۲۰۰۲هیچ کدام رانداشته باشد وسطری وجودداشت که از۱تا۲۰۰۲را نداشت آنگاه تقاطع این سطر وستونجواب است!اما اگر یک سطر فقط وجود داشت که از۱تا۲۰۰۲را نداشت به این صورت عمل میکنیم!چون در همهستونها از عددِ۱تا۲۰۰۲داریم پس هرستوندقیقا یکى از اعداد هاى۱تا۲۰۰۲را داردستونیکه۲۰۰۲را دارد را در نظر بگیرید!خوب کوچیکترین عددِ این سطر وستون۲۰۰۲است!!پس اگرb=2002آنگاهc>2002 وb*c>2002*2002حالا اگر همهسطر هاوستونها یک عدد کوچکتر از۲۰۰۳داشتند آنگاه خانه اى که۲۰۰۲در ان قرار دارد خانه اى است که مشکل دارد

__________________________________________

سری 2:

1-اولین صحنهاى را در نظر بگیرید که یا همه سطر ها حداقل یک سفید دارند یا حداقل یکى از ستون ها یک سفید دارند (حتما هم وجود دارد(

در این زمانخاصیتمورد نظر وجود داردفرض کنید در هر سطر یک سفید داریمحالت اول:اگر در این مرحله همه ستون ها هم یک سفید داشتندفرض کنید در آخرین مرحله در خانهِ(i,j)سفید اضافه کردیم پس تا قبلاینحرکتستونjسفید نداشته و دیگرستونها همه سفید داشتند واینکه تمام سطر ها غیر ازiسفید داشتند!براى هر سطر یک خانهِ سفید را انتخاب میکنیم و به سمتِ ستونِjحرکتمیکنیم ، حتما یک خانهِ خالى پیدا میشود چون اگر از سفید به سیاه تبدیلشود که مسأله حال است و اینکه تا آخر نمى تواند سفید بمانند چون درستونjما سفید نداشتیم!!پس حداقل در همه سطر ها غیر ازiیک خانهِ خالى داریمخانهِ(i,j+1)و(i,j-1)حتما خالى هستند (حد اقل یکى از این دوخانه وجود دارد) چون با سیاه که پر نمى شوند چون در این حالت مسأله حالاست سفید هم نیستند چون اولین جایى است که سطرiخانهِ سفید دارد.پس۱۰خانهِ خالى داریم در صورتى که۹۱خانه از۱۰۰خانه پر است پس تناقص!حالت دوم:این است کهستونیوجود داشته باشد که سفید نداشته باشد!!مثلا ستونِtبگیرید!!اگر از سفیدِ هر سطر به سمتِستونtحرکتکنیم حتما یک خالى خواهیم دید (اثبات مانندِ بالا)

 

2- ابتدا ثابت میکنیم براىnهاى فرد نمى توانفرض کنید در مرحله ى اىامXiتا واحد حرکتداده ایم
 n-1مرحله داریم و بایدXiها متفاوت باشند

 n*(n-1)/2=سیگما(Xi) است و باید به هنگn مخالف 0 باشد(چرا که اگر0شودیعنى روى صندلىِ تکرارى خواهیم نشست) که این در حالتى رخ میدهد که nبه2 بخش پذیرباشد !! پسnباید زوج باشدبراىnهاى زوج همالگوریتموجود دارد:به ترتیب حرکت هاى زیر را انجام مى دهیم(تعداد چرخش ها)
n-1,2,n-3,4,n-5,6,....,1,n-2اگر رسم کنید میبیند که اینالگوریتمصحیح است و اثبات هم میشود!یعنى در واقع اگر از صندلىِ۱شروع کنیم به ترتیب روى1,n,2,n-1,3,n-2 ,… مى شنیم!

3-همیشه آرمین میبرد و در حق من ستم میشود

خوب فرض کنید در مرحله اول رامتین سکهXتومنى را انتخاب میکند وآرمین خودش این سکه را بر میدارد الان آرمینXتومان پول دارد و رامتین0تومان پول دارد پس نوبتِآرمین است که انتخاب کند!!اگر آرمین در ادامه ببرد که برده!!فرض کنید در ادامه ارمین هیچ راه بردى نداشته باشد!!ارمینسکه یX تومنى را به رامتین میدهد و حالا رامتینXتومانپول دارد وآرمین0تومان و نوبتِ رامتین است که بر دارد ،یعنى در واقعشرایط بده خودش را به رامتین میدهد!!!چون در این حالت کسى کهXتومان داشت می باختپس الانآرمین میبرد چونXتومان دست رامتین است

4-

فرض کنید درGمتغیر هاى زیر را تعریف میکنیم!!
x=تعداد۳راسى هایى که هیچیالیبین آنها نیست
y=تعداد۳راسى هایى که یک یال بین آنها وجود دارد
z=تعداد۳راسى هایى که دویال بین آنها قرار دارد
t=تعدادمثلثها(گرافK3)

معادله های زیر بر قرار است

x+y+z+t=(3 az n)

z+t=sigma(2 az di)

y+2*z+3*t=m*(n-2)

اگر 2 تا معادله اول را جمع کنیم و آخری را کم کنیمx+t به دست می آید که همان چیزی است که می خواهیم

5-تعدادمثلثهاى جهت در راxبگیریدومثلثهایى که یکیال در خلاف جهت دارد تاyبگیرید

y=sigma(2 az di)

x+y=(3 az n)

=>

x=(3 az n)- sigma(2 az di)

 

6-فرض کنید هیچ کس سر جاى خود نیستیکگرافجهت دار مى سازیم که به ازاى هر صندلى یک راس میگذاریماگر کسى که در خانهِ(x,y)نشسته وبلیطِ صندلىِ (z,t)را دارد (یاz=x یا y=t)از رأس(x,y)به رأس       (z,t)یال میکشیمحالا یک گراف داریم که درجه خروجیهر راس۱است.در این گراف حتما یک دوره جهت دار وجود دارد چون فرض کنید از رأس xشروع میکنیم و حرکت میکنیم ازیال خروجى این راس جلو میرویم بهyسپس ازyخارج میشویم تا به رأس تکرارى برسیم تا به رأس تکرارى نرسیدیم میتوانیمبه وسیلهیال خروجى از این راس خارج شویم!خوب حالا کافیست وقتى دوره جهت دار را پیدا کردیم اگر در دور از رأس (x,y)به(z,t)یال بود فردى که در  (x,y)نشسته را به مکان(z,t)ببریم و(z,t)را به سر جاى خودش و...

قسمت دو:حداکثر یک نفر!!مثال:فرض کنید به m+n-1نفر بلیطِ صندلىِ (۱،۱(رافروختیم
خوب سطر اول و ستون اول پر میشوندحالا به n-1نفر (2و1(رامی فروشیمو به n-1نفر (3و1(رامی فروشیم

...و به n-1نفر(1,m)رامی فروشیمولى هیچ کدام از این آدم هایى که بلیطِ(1,x)را دارندنمی توانندسر جاى خودبشینندچون سطر اول پر شده است!!فقط کسى که در(1و1)نشسته سر جاى خود است

 

 

نوشته شده توسط رامتین رطبی(سابق) در چهارشنبه ۲۶ فروردین۱۳۸۸ و ساعت 23:9 |