صفحه ۳۴
پاسخ مرحله ۱ سال ۸۷
کد 1:
1) ه
۲) ج
۳) ا
۴) ه
۵) ج
۶) ج
۷) د
۸) د
۹) ا
۱۰) د
۱۱) ا
۱۲) ه
۱۳) ب
۱۴) د
۱۵) ه
۱۶) د
۱۷) ا
۱۸) ه
۱۹) ا
۲۰) د
۲۱) د
۲۲) ج
۲۳) ب
۲۴) ج
۲۵) ه
۲۶) حذف (۱۶ میشه جواب)
۲۷) ا
۲۸) ج
۲۹) ب
۳۰) ب
کد 2:
1- ه
۲- ه
۳- ج
۴- الف
۵- ج
۶- الف
۷- ج
۸- د
۹- د
۱۰- ب
۱۱- د
۱۲- الف
۱۳- ه
۱۴- د
۱۵- د
۱۶- ه
۱۷- الف
۱۸- د
۱۹- ه
۲۰- الف
۲۱- ج
۲۲- د
۲۳- ج
۲۴- ب
۲۵- ه
۲۶- الف
۲۷- ج
۲۸- ب
۲۹- ب
۳۰- حذف
با تشکر از حسام و رکسانا !!!!
حالا copyright رو بیخیال بشم ملت من و سرویس می کنن !!!!!
البته اگه سوال ها رو داشتم به اینا اطمینان نمى کردم و خودم حل می کردم ولى چى کار کنم دیگه باید به بچه ها اعتماد کرد !!!
;)
۱۳۸۷/۱۱/۰۵ · ۱۸:۱۴
مسابقات
با عرض سلام به همگی!
من یکی از اعضای کمیته‌ی برگزاری مسابقه دانش‌آموزی هستم.
تیم
برگزار کننده مسابقه امسال امکانی برای تامین محل اقامت تیم‌های شهرستانی
در اختیار ندارد، بنابراین برگزاری مسابقه به تیم‌های تهرانی محدود شده
است.
اگر شهرستانی هستید و می‌توانید محل اقامت‌تان در تهران را
تامین کنند با ما تماس بگیرید. در صورت امکان تیم شما را در مسابقه ثبت
نام میکنیم. شماره تلفن ما در صفحه «تماس با ما» در سایت مسابقه هست
(آدرس زیر)
http://ispc.schoolnet.ir/contact.html
موفق باشید
۱۳۸۷/۱۱/۰۲ · ۱۹:۳۱
+
دومین مسابقه‌ی دانش‌آموزی ایران۱۶-۱۷بهمن برگزار میشه.
شرکت‌کنندگان در رده‌ی سنی اول تا سوم دبیرستان هستند
این آدرسِ سایتش هست:http://ispc.schoolnet.ir.
برای ثبت نام به بعضی مدارس بخشنامه امده. اگر نیومده زنگ بزنید به شماره‌ای که توی بخش «تماس با ما» توی سایت گذاشته شده.
ما رو که راه ندادن بقیه بران از المپیاد کامپیوتر دفاع کنن و نذارن ربوکاپی ها چیزى بشن !!!
سال پیش که زیرِ دست و پاى المپیادی ها خورد شدن.
حتى پائین تر از المپیادی هاى سال دومى.
۱۳۸۷/۱۰/۲۷ · ۱۹:۳۱
+
کلا بد نیست به اونجا هم سر بزنید
۱۳۸۷/۱۰/۰۲ · ۰۹:۲۷
جواب های قشنگ!!!
ابتدا به خانه ها وزن مى دهیم وزن خانهِ اى برابر (F(i است(که (F(i تابع فیبوناچی هست)
متغیر W را مجموع وزن ها تعریف میکنم !
ثابت میکنم که W همواره ثابت است و برابرِ سیگما F(i) i=0 تا i=n
در حرکتِ نوع اول که بدیهى است که ثابت میماند چون تعریف فیبوناچی است
F(i)=F(i-1)+F(i-2)l
در حرکتِ دوم کافیست ثابت کنیم که
2F(i)=F(i-2)+F(i+1)l
از طرف چپ شروع میکنیم !
2F(i)=F(i)+F(i)=[F(i+1)-F(i-1)]+[F(i-1)+F(i-2)]=F(i+1)+F(i-2) :D
خوب پس W همواره ثابت است !
حالا که ثابت کردیم W ثابت است کافیست ثابت کنیم که
sigma F(i)i=0 ta i=n
استقرا میزنیم روى n براى n=۰ که بدیهى است !
حالا از t=>t+1
میدانیم
sigma F(i) i=0 ta i=t
به طرفین معادله (F(t+۱ اضافه میکنیم و اثبات می شود!
پس هیچ وقت مهره ای در خانهِ n+۲ قرار نمیگیرد چون مجموع تغییر خواهد کرد !
۲-------------------->
اگر گراف لوپ (یالی که دو سر آن یک راس باشد ، یا دوری به طول یک) یا یالهای موازی(دو یال که دو راس های مجاور مشترک دارند یا دوری به طول 2) داشته باشد که دوری که طول آن بر 3 بخشپذیر نباشد را یافته ایم ، پس فرض کنیم گراف ساده است.مسیر ماکسیمالی در گراف که راسaیک انتهای آن است را در نظر می گیریم.aباید حداقل با دو راس دیگر به جز راس مجاورش در مسیر ماکسیمال همسایه باشد زیرا مسیر ماکسیمال است و مسیر نمی تواند از طرفaبزرگ شود ، این دو راس را به ترتیب از طرفaبه انتهای دیگر گراف ،xوyمی نامیم . سه دور را در نظر می گیریم، دوری که شامل مسیرaxویالaxمی باشد ، دوری که شامل مسیرxy و دو یالay وaxاست .و دوری که شامل مسیرayو یالayاست. فرض کنیم که طول دور اولی بر 3 بخشپذیر باشد پس طول مسیرaxبرابر3k-1است.همچنین فرض کنیم طول دور سوم نیز برابر3k*است ، پس طول مسیرxy برابر3k*-2است . طول مسیرayبرابر است با مجموع طول این دو مسیر ، پس بر 3 بخشپذیر است ، پس طول دوری که شامل مسیر و یالayاست بر 3 بخشپذیر نیست (برابر3i+1است )پس چنین دوری در گراف وجود دارد.
۳----------------->
به صورتِ دلخواه یال ها را جهت دار می کنیم چون زوج یال داریم میتوانیم بگوییم که زوج راس داریم که درجهِ خروجی آنها فرد است چون سیگما درجه خروجی انها برابرِ تعداد یال هاست
حالا ۲ راس را در نظر میگیریم که درجهِ خروجی ان ها فرد است چون گراف همبند است پس مسیرى بین این ۲ راس وجود دارد (نه لزوما جهت دار)
تمام جهت هاى یال های این مسیر را بر عکس میکنیم !
راس هایی که در وسط مسیر هستند که زوجیت درجه خروجی شان تغییر نمى کند(بدیهى است خود تون اثبات کنین)
۲ رأس انتهایی هم تغییر می کند یعنى از فرد تبدیل به زوج میشوند !
پس هر مرحله ۲ تا از راس هاى بد تبدیل به خوب می شوند و چون تعداد آنها زوج تا است زمانى تعداد راس های بد ۰ میشود.
۴--------------------->
ثابت میکنم که یک بازه سفید وجود درِ که همه سیاه ها را در بر می گیرد و براى سیاه ها هم به طورِ مشابه است (فقط جاى سیاه و سفید عوض میشود)
اولین بازه ی سیاه که بسته میشود و آخرین بازه ی سیاهى که شروع میشود را در نظر بگیرین!
چون این ۲ تا بازه هر کدام با k تا بازه ی سفید اشتراک دارند پس یک بازه هست که با جفت بازه هاى در نظر گرفته شده اشتراک دارد(این را انتخاب میکنیم). اگر همچین بازه ای نباشه باید حداقل 2*k بازه سفید داشته باشیم !
ثابت میکنیم بازه ای که انتخاب کردیم با همه بازه هاى سیاه اشتراک دارد!
بدیهى است که همه بازه ها یک نقطه بین اولین پایان و آخرین شروع را دارد اگر نداشته باشد این ۲ نقطه تغییر میکند !(اثباتش به عهدۀ خود تون دیگه خیلى بدیهیه)
۵------------------>
الف)
جعبه با بزرگترین سیب را بر میداریم و سپس بر اساسِ تعداد سیب ها جعبه ها را مرتب میکنیم !
حالا فرض کنید جعبه ی شماره ۱ کمترین سیب را دارد و به ترتیب تا ۹۸ تعداد سیب ها افزایش مى یابد !
جعبه ها را دست بندى میکنیم و جعبه ی 2*i و1+ ( 2*i) را در یک بسته میگذریم !
حالا ۴۹ بسته داریم و میخواهیم ۴۹ جعبه انتخاب کنیم!
از هر بسته جعبه ای را انتخاب میکنم که بیشترین پرتقال را دارد!
این یک جعبه بر داشتن خوب هستش چون بدیهى است بیشتر از نصف پرتقال ها را dadad و در بد ترین حالت جعبه ۱،۳،۵،۹۷ انتخاب شده به همراه 99!
که چون ۹۹ بیشتر از ۹۸ ، سیب دارد و ۹۷>۹۶ ،۹۵>۹۴ ،….. ۳>۲ و ۱>=1
پس نصف سیب ها برداشتِ شده’اند!
ب) به شکل بالا بر میداریم اما این بر بعد از بر داشتن جعبه با بیشترین سیب دست ها را ۳ تایى در نظر میگیریم و در هسته جعبه با بیشترین پرتقال را بر میداریم !
باز هم درست میشود!
J)ابتدا جعبه با بیشترین سیب را بر میدارم و سپس جعبه با بیشترین پرتقال !
حالا ۹۸ جعبه دارم و میخواهم ۴۹ جعبه بر دارم!
A=بیش ترین سیب B=بیش ترین پرتقال !
خوب میام میگم اگه من بتونم جعبه ها رو ۲ دسته بکنم که اختلافِ سیب هاى ۲ طرف کوچیک تر مساوىِAباشد و اختلافِ پرتقال این دست کم تر مساوىِ Bباشد مسأله حل است!
چون اون دسته با بیشترین موز رو بر میداریم و با اون ۲ تا جعبه !
موز ها که بیشترن و سیب ها هم بیشترن چون در بد ترین حالت ما کمترین سیب رو بر میداریم که چون اختلافشون از A کمترِه با اون آمدنِ جعبه با بیشترین سیب جبران میشه و براى پرتقال ها هم همین طور!
از این به بعد a_i میشه سیب جعبه i و b_i میشه پرتقال جعبه i.
پس کافیه ثابت کنیم اگر 2x جعبه داشته باشیم و میخواهیم x جعبه انتخاب کنیم که همه a_i ها ازA کوچیکترند وb_i ها از B کوچیکترند میتوان دستi ها را به ۲ قسمت تقسیم کرد که اختلافِ سیب ها حد اکثر A باشد و پرتقال ها B باشد !
این حکم را با استقرا ثابت میکنیم
استقرا میزنیم روى که. از که به k+۲ میرسیم!
همین !
استقرا به عهدۀ خودتون( خیلى هم بدیهى نیست پس یه کم فکر کنید ،نگید چون نگفته خیلى بدیهیه )
۶----------------------------->
مسأله را با استقرا روى تعداد یال ها حل میکنیم
پایه استقرا( m=2 تعداد یالها)
چون گراف همبند است پس میتوانیم بگوییم که خود گراف حداکثر ۳ راس دارد و کمتر هم ندارد! خود گراف P-۳ است
فرض استقرا :گرافی با زوج یال و همبند را میتوان به P-۳ افراز کرد!
گام استقرا:m==>m+2
مسیرِ ماکسیمم را در نظر میگیریم !
فرض کنید که راس ها به ترتیب در مسیر a1,a2،….،ax باشد (به بدیهیت x>=۳ است زیرا اگر کمتر باشد آنگاه بزرگترین مسیر به طول ۱ است و چون گراف همبند است پس گراف حداکثر ۲ راس دارد و گراف میتوانند حداکثر ۱ یال داشته باشد !)
1)اگر a2 همسایه به غیر از a1 و a3 داشته باشد آنگاه اون راس را u مینامیم
ثابت میکنم اگر ما یال (a1-a2) و (a2- u) را بر داریم گراف هنوز همبند خواهد ماند!( در اینجا تعریف از همبندی بدون در نظر گرفتن راس های درجه ۰ است)
اگر درجهِ a1 صفر شود که مشکلى نیست و با تعریف همبندى تناقص ندارد!
اما اگر درجه یه a1 بیشتر از صفر باشد آنگاه میدانیم تمام همسایه هاى a1 در مسیر هستند چون اگر همسایه ای بیرون از مسیر داشته باشد میتوانیم طول مسیر را افزایش بدیم که با ماکسیمم بودنش تناقص دارد!
پس هنوز a1 به a2 مسیر دارد چون اگر a1 به یک راسى مثل at برود و سپس به a_t-1 سپس به a_t-2 ...
به a2 میرسد.
براى رأس u هم همین اثبات کافیست چون رأس u اگر ۰ شود که با تعریف همبندی تناقص ندارد اگر هم همسایه داشته باشد باز هم همسایه هایش در مسیر هستند چون اگر نباشند آنگاه مسیر ماکسیمم نبوده !
2)اگر a2 همسایه ای به غیر از a1 و a3 نداشته باشد مسیر a1-a2-a3 را حذف میکنیم. a2 که درجه ۰ میگیرد ،a3 هم که به مسیر وصل است.
فقط مى ماند a1:
اگر درجهِ a1 صفر شود که حله
اگر هم ۰ نشود آنگاه همسایه در مسیر دارد که باز هم گراف همبند مى ماند!
پس گراف هم چنان همبند است و m یال دارد ! (طبق فرض استقرا مسأله حل است)
۱۳۸۷/۰۸/۱۷ · ۰۶:۵۹
سوالهاى قشنگ!!!
دوباره سلام!
ببینید من یه سرى سوال در اوردم که به درد مرحله ۲ میخوره. فکر کنم هر کدومش ایده هاى خوبى داره.
هر کس که مى خواهد میتونه به من میل بزنه و این سؤالات رو بگیره بعد هر کدوم رو که حل کرد به من میل کنه تا واسش صحیح کنم !!
میل:
۱۳۸۷/۰۷/۰۷ · ۲۴:۰۳
خلاصه
احتمالا کسایى که میان اینجا من را مى شناسند ولى حالا براى معرفى میگم که من رامتین رطبی هستم!
این هم خلاصه ای از گردهمایی!
خوب جلسه برای دفعه‌ی اول خوب پیش رفت و سه نفر از بچه‌هایی که هنوز المپیاد ندادن توش شرکت کردن.
جلسه این جوری شروع شد که یکی می‌خواست کلن بدونه المپیاد کامپیوتر چی هست. بچه‌ها براش توضیح دادن که کلن 4 مرحله‌ی کلی داریم، که اولیش مرحله اول هست که تقریبن همه‌ی کشور میتونه ثبت‌نام کنه. از این مرحله اول نفراتی برگزیده می‌شن واسه مرحله 2؛ که حدود 300 نفر هستش. این 300 نفر تو مرحله دوم شرکت می‌کنن و 40 نفر برگزیده شده به دوره‌ی تابستون دعوت می‌شن (که تو تهران برگزار میشه.).
در این مرحله حدود 35 نفر حضور دارن که 15 نفر برنز می‌شن (بعد از یک سری امتحان) و بقیه هم میرن در دوره‌ی نقره-طلا.
تو جلسه گفته شد که برای هر مرحله چه چیزی لازم هست.
مرحله اول: ترکیبیات استفاده میشه. که بهترین کتاب‌ها برای این مرحله کتاب ترکیبیات دکتر علی‌پور و پاسخی بر المپیاد کامپیوتر (مرحله 1) هستن.
مرحله‌ی اول شامل 30 تا 40 تست با 5 ساعت وقت.
مرحله دوم: ترکیبیات و کمی هم الگوریتم و گراف استفاده میشه. که برای مرحله دوم هم کتاب دکتر علی‌پور، پاسخی بر المپیاد کامپیوتر (مرحله 2)، استراتژی حل مسئله و ترکیبیات آقای ثروتی به همراه کلیه کتاب‌هایی که مسئله‌های تئوری دارن مثل شوروی، تورنمنت شهرها، لنینگراد،... (البته فقط مسئله‌های ترکیبیات.)
مرحله دوم شامل 2 امتحان 5 ساعته هستش که هر امتحان 4 سؤال داره و 100 نمره.
از این به بعد که میشه دوره‌ی تابستون و مرحله 3 نقش ترکیبیات کم رنگ میشه و بیشتر به الگوریتم و گراف بها داده میشه. همچنین به برنامه‌نویسی در این مرحله هم اشاره کرد که زبان C++ یاد می‌دن.
بعد از این که برنزها از جمع کامپیوتری‌ها جدا می‌شن، میشه دوره‌ی نقره-طلا که اینجا گراف کم استفاده میشه و حل مسائل 2 قسمت میشه؛
1. به دست آوردن الگوریتم
2. نوشتن الگوریتم به زبان C++
بعد از این که در مورد دوره‌ها صحبت شد، بچه‌ها از ترکیبیات و مقدار درس خوندن بزرگتر‌ها می‌پرسیدن که تقریبن به این نتیجه رسیدیم که هر کس بیشتر درس بخونه نتیجه‌ی بهتری می‌گیره (البته موردهای استثنا هستن).
۱۳۸۷/۰۶/۲۵ · ۰۷:۴۳
گردهمایی!
یه کاری هست که خیلی وقته می‌خوام انجام بدم، اما به دلایل گوناگون نشد! مسئله اینه که من فکر کردم که شاید خوب باشه هر چند وقت یک‌بار ما یه کسی را دعوت کنیم، که بیاد تو شاززز on بشه و به سوال‌های آدم‌ها جواب بده(اسما برای شازززirc channelدرست کرده.) این گردهمایی‌ها(!) بیشتر برای اینه که آدم‌ها با المپیاد کامپیوتر آشنا بشن و اگر راهنمایی لازم دارن، کسی باشه که بهشون کمک کنه، مستقل از این که کجا زندگی می‌کنن. خوب یه سری مشکلاتی هم هست. مثل این که اگه تعداد این گردهمایی‌ها زیاد باشه، ما (من و نیلوفر و اسما ) نمی‌تونیم تو همه‌شون باشیم. یا اینکه فقط کسایی بیان که خودشون به اندازه‌ی کافی می‌دونن (مثل اکثر کسایی که تو شاززز نظر می‌دن) و خیلی چیزهای دیگه. حالا من همه این‌ها را نوشتم که بقیه هم رو این موضوع فکر کنند و ابعادمختلفش را بررسی کنن! ببینیم کلن کارِ خوبی هست یا نه.
پ.ن. به نظر من ماهی یک‌بار کافیه!
نظرتون با برگزاری اولین گردهمایی در پنج‌شنبه، 21 شهریور، ساعت 3 تا 6 چیه؟
(اگه تاریخ دیگه‌ای هم به نظرتون خوبه بگید!)
دقیقا نمی دونم ولی فک می کنم پایان دوره امسال روز قبل از این جمعه است. شاید هم برای برنزها, هم برای نقره طلاها خوب باشه که بیان. تو رای دادن به این هم دقت کنین!
زمان برگزاری همین جمعه ساعت 3 تا 6 بعد از ظهر می باشد.
بچه ها irc channel نیاز به java داره، ما فکر می کنیم که اکثر شما
java ندارید، برای همین احتمالا برنامه رو تا حدی تغییر می دیم، کسایی
که می خوان در گرد همایی شرکت کنند، ID یه yahoo شون و اینکه
در چه مرحله ای از المپیاد هستن رو به آدرس sh44zzz@yahoo.com ایمیل کنند.
تا دقایقی دیگر گرد همایی برگزار خواهد شد
۱۳۸۷/۰۶/۰۲ · ۱۹:۳۰