شاززز

شاززز

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

بایگانی

۲ مطلب در شهریور ۱۳۸۹ ثبت شده است

۲۵
شهریور
اسامی رو طوری نوشتم که نام خانودگی‌ها به ترتیب حروف الفبا باشه!

نام نام خانوادگی توضیحات
سجاد جلالی شام بچه‌های شاززز فراموش نشود
محمد حسین سخاوت
پارسا سعادت پناه
حسین شایسته شام بچه‌های شاززز فراموش نشود
حامد صالح دوم دبیرستان
کسری عدالت نژاد شام بچه‌های شاززز فراموش نشود
محمدرضا کسنوی شام بچه‌های شاززز فراموش نشود
محمدرضا ملکی دوم دبیرستان

طلاهاتون مبارکتون باشه!

نتایج تغییر کرد:
دوستان باید عرض کنم که این نتایج، نتایج اصلی نیست! و تغییر پذیره
من یک معذرت خواهیه گنده بهتون بدهکارم.. امیدوارم که ببخشیم!
من فکر می‌کردم این نتایج نهایی هستند! راستش این نتایج رو پای تلفن رو از یکی از بچه‌ها پرسیدم.. ولی اون بهم نگفت که ممکنه تغییر کنه
اگر می‌دونستم نتایج نهایی نیست هرگز نمی‌زدم! همگی ببخشید
الآن لیست بالا لیست درست نتایج شده هستش! (یعنی امیدوارم درست باشه این دیگه (اینم پایه تلفن از یکی پرسیدم D:))
اون موقعی که نتایج رو زده بودم اعتراض‌ها بررسی نشده بوده ظاهرا! ولی الآن دیگه بررسی شده مثکه

  • شااززز منگولیا
۰۶
شهریور

یا حق

سلام به همه رفقا.

شرمنده به خاطر تاخیر تو پست زدن. این جواب سوال‌های پست قبلیه:

۱- برای اینکه ببینیم چندتا جایگشت رو می‌شه مرتب کرد،‌ تعداد جایگشت‌هایی که از جایگشت مرتب شده می‌شه به اون‌ها رفت رو می‌شماریم. اگه جایگاه‌های 1 تا n رو به عنوان راس و هر کارت رو به عنوان یک یال در نظر بگیریم، به یک گراف می‌رسیم. حالا تو این گراف هر دو راسی که تو یک مولفه باشند رو می‌شه جابجا کرد، بدون اینکه بقیه رئوس رو به هم بریزیم. پس در واقع هر مولفه از این گراف رو می‌تونیم به هر شکلی جایگشت بدیم. پس اگه این گراف k تا مولفه با اندازه‌های a1تا akداشته باشه، جواب مسئله می‌شه:

a1! * a2! * ... * ak!) % 1000007)

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

۲- فرض کنید با تعدادی حرکت دنباله رو مرتب کردیم. عناصری رو در نظر بگیرید که در هیچ مرحله‌ای حرکت داده نشده‌اند. این عناصر باید تشکیل یک زیردنباله‌ی صعودی بدهند. از طرفی اگر یک زیر دنباله‌ی صعودی را در نظر بگیریم، با جابجا کردن بقیه عناصر می‌شه دنباله رو مرتب کرد. پس مساله تبدیل می‌شه به پیدا کردن طولانی‌ترین زیردنباله‌ی صعودی که اختصارا بهش می‌گنLIS. برای این مساله یه راه‌حل داینمایک از (O(n^2 وجود داره که با یه ایده‌ی جالب می‌شه به (O(n * log n کاهشش داد.

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

----------------------------------------------------------------------------------

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

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

(پی نوشت: دمه افطاره. از همه دوستان التماس دعا)

  • شااززز منگولیا