• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

آرشیو سوالات از گذشته تا کنون

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : آرشیو سوالات از گذشته تا کنون

آره .
تو دلیلی برای نقض کردن و ناقص و غلط بودن اثبات من بیار.
من این سوال رو تو اصول و فنون دیدم (ptc)
به شخصه سوالی ندیدم که جواب غلط داده باشه تو این کتاب

تا فردا میرم از معلم ترکیبیات می‌پرسم.

ببین دوست من،من میگم اگه همه امتیازاتشون برابر باشه از کجا معلوم ده نفر اخر همین ده نفر آخر که تو فرض مسئله هستش باشن؟
اگه یه جدول ببینی،متوجه میشی منظورمو.
(امروز دبیر ترکیبیات نیومده بود)
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : آرشیو سوالات از گذشته تا کنون

راه نیما رو یکم عوض میکنم ، راحت تر بفهمید !
فرض کنید 19 نفر داریم ،همه ی بازی های تورنمنت هم مساوی شدن !
حالا هر کی 18 امتیاز داره و ده نفره آخر ، دقیقا 9 امتیاز رو از خودشون بدست آوردن :‌)
 

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
657
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : آرشیو سوالات از گذشته تا کنون

دوست خوب من .... نفر 20 ام خیاره .... :-?

نفر 20 امی هم هست که اون 10 نفر رو برده و به اون 9 نفر دیگه باخته ....

امتیاز این یارو اِه و اون 9 نفر میشه 20 .... بقیه هم 18 .... و در ضمن اون 10 نفر نصف امتیازشون رو از خودشون گرفتن ....

رضا => این مقاومتش از منم بیشتره ... :-"
 

meli

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,014
امتیاز
8,478
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
شهر
تهران
مدال المپیاد
برنز کشوری کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : آرشیو سوالات از گذشته تا کنون

میگه یه سری گل داریم، یه سری گلدون، تعداد گل ها هم کمتر مساویه گلدوناس، بعد گل i اگه تو گلدون j قرار بگیره a i , j زیبایی داره.
بعد میخوایم گل ها رو یه جوری تو این گلدونا قرار بدیم که مجموع زیبایی ها ماکزیمم بشه، حالا تو خروجی باید بگین حداکثر مجموع زیبایی ها چقدره، و تو خط بعدم بگین هر گل تو کدوم گلدون باید باشه که جمع زیبایی ها حداکثر شه!

+ بازم برین خودتون یه بار بخونین من چون قبلا اینُ خونده بودم، ممکنه چیزی رو جا انداخته باشم.
 

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : آرشیو سوالات از گذشته تا کنون

خب، خیلی وقته که سوالات الگوریتمی گذاشته نشده اینجا
من یه سوال میذارم رو این سوال فکر کنید

ستاره یمشهور در بین n نفر کسی است که همه او را می شناسند،اما او هیچ گس را نمیشناسد.
هدف مسئله این است که اگر ستاره ی مشهوری در بین n نفر وجود دارد،با پرسش هایی در قالب((منو ببخشید!آیا شما کسی که آنجاست را می شناسید؟))
ستاره ی مشهور را بیابیم
(فرض بر این است که همگی پاسخ ها درست هستند و همه حتی فرد مشهور،به ما پاسخ خواهند داد)
میخواهیم پاسخ را با کم ترین تعداد پرسش ممکن بیابیم.از آنجا که در بین nعنصر می توان n(n-1)/2 زوج را برگزید؛ اگر پرسش ها را بدون هیچ طرح یا برنامه ای بپرسیم،در بدترین حالت ممکن،ممکن استn*n-1 پرسش لازم باشد
آیا میتوان الگوریتمی یافت که در بدترین حالت ممکن،عملکرد بهتری داشته باشد یا نه ؟
[nb]اگه سوال رو یه جا خوندید(که میدونم کجاست :-" )بذارید بقیه هم قکر کنن تا ایده سوال به ذهنشون برسه بعدش...[/nb]
 

Phanntom

کاربر فوق‌فعال
ارسال‌ها
115
امتیاز
364
نام مرکز سمپاد
helli
شهر
تهران
مدال المپیاد
سابقه دارم!
دانشگاه
light massage(پیام نور)
پاسخ : آرشیو سوالات از گذشته تا کنون

دوستان اگه میشه سوال 231رو هم یه عنایتی :D
 

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از Wilson :
دوستان اگه میشه سوال 231 رو هم یه عنایتی :D
همه دو جفتی های اعداد اول aوb را بیابید به طوریکه aکوچکتر مساوی b و مجموع آنها نیز یک عدد اول باشد و از n بیشتر نشود
 

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : آرشیو سوالات از گذشته تا کنون

من یادم رفت بیام سوالو اصلاح کنم
ساری :D

سوال رو با دوستان رفتیم دوباره چک کردیم بعد دیدیم که تو کتاب اشتباه ترجمه شده بودش
سوال اصلی که ترجمه کردیم به این صورت در اومد که ؛ هر کدوم از افردا نصف امتیازهاشون رو از ده نفر آخر به دست آوردن
در غیر این صورت جواب یکتا نخواهد داشت

حالا رو این سوال فکر کنید :د
 

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,544
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : آرشیو سوالات از گذشته تا کنون

یه سوال از SGU بگم خیلی قشنگ بودش !

سوال 502 : http://acm.sgu.ru/problem.php?contest=0&problem=502

میگه یه عدد n بهتون میدیم که کوچکتر مساوی 17^10 هست. باید اولین جایگشتی از این عدد رو بگین که بر ۱۷ بخشپذیر باشه.

کسی حل کرد راهشو نگه و سعی کن acc بگیره. آخر سر هم من کدشو میزارم خودم
 

meli

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,014
امتیاز
8,478
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
شهر
تهران
مدال المپیاد
برنز کشوری کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : آرشیو سوالات از گذشته تا کنون

راه حل خوشگلم داره این سوال؟ :-"

من اکسپت گرفتم ولی اصلا راه حلّم خوشگل و خاص نبود :))
 

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,544
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از MeLi :
راه حل خوشگلم داره این سوال؟ :-"

من اکسپت گرفتم ولی اصلا راه حلّم خوشگل و خاص نبود :))
فک نکنم :-" ولی راه حل بازگشتی داره :-? ، من بازگشتی زدم :D
فقط راه قشنگش اینه که با O (Leng(n)!)x نباشه :D
 

meli

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,014
امتیاز
8,478
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
شهر
تهران
مدال المپیاد
برنز کشوری کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : آرشیو سوالات از گذشته تا کنون

وقتی خیلی راحت تر اکسپت میشه چه کاریه ایده بزنی :-"

حالا بعدا خواستین کدمُ میزارم ببینین که اصنم ایده نمیخواست :D
 

most wanted

کاربر نیمه‌حرفه‌ای
ارسال‌ها
215
امتیاز
669
نام مرکز سمپاد
علامه حلی2
شهر
تهران
پاسخ : آرشیو سوالات از گذشته تا کنون

من یه چیزی رو نمیفهمم این 502 چرا با !(length n) اکسپت میشه :|
اونم تو 15 ms :|
 

meli

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,014
امتیاز
8,478
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
شهر
تهران
مدال المپیاد
برنز کشوری کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : آرشیو سوالات از گذشته تا کنون

من هم الان نمیفهمم چرا اکسپت میشد ولی اون موقع دیفالتِ ذهنم این بود که خب باید جایگشت ها رو چک کرد مگه ایده دیگه ای هم هست؟ :-"

همین کد برا این سوال به طرزِ عجیبی اکسپت میشه :-? اصن اینقدر شک کرده بودم به کدم دوبار دیگه ئم سابمیت کردم ببینم باگِ اس جی یو نباشه
 

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : آرشیو سوالات از گذشته تا کنون

اِ این سواله !!! :D حتی یادمه میشد مثلا چند تا جایگشت رندوم انتخاب کنی ، اگه یکیش بخشپذیر بود که هیچی ، اگه هم نبود یعنی نبود !!!!!! :D
 

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,544
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از |H|3$4|M| :
اِ این سواله !!! :D حتی یادمه میشد مثلا چند تا جایگشت رندوم انتخاب کنی ، اگه یکیش بخشپذیر بود که هیچی ، اگه هم نبود یعنی نبود !!!!!! :D
خو آره ولی 17! خیلی عدد بزرگی میشه فک کنم :-"
 

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از sobh :
خو آره ولی 17! خیلی عدد بزرگی میشه فک کنم :-"

منظورت چی بود ؟! چه ربطی به حرف من داشت ؟!
 

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,544
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از |H|3$4|M| :
منظورت چی بود ؟! چه ربطی به حرف من داشت ؟!
کل حالات میشه ماکسیموم 17! دیگه
 

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از sobh :
کل حالات میشه ماکسیموم 17! دیگه

من گفتم رندوم انتخاب میکنم ، قرار نیست همه رو چک کنیم !!! مثلاً 1 میلیون جایگشت رندوم انتخاب میکنیم ، اگه بخشپذیر بود که همون جایگشت رو میدیم ، اگر هم نبود یعنی کلا نبوده ! دلیل علمی هم نداره ولی اکسپت میشد !
 

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,544
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : آرشیو سوالات از گذشته تا کنون

به نقل از |H|3$4|M| :
من گفتم رندوم انتخاب میکنم ، قرار نیست همه رو چک کنیم !!! مثلاً 1 میلیون جایگشت رندوم انتخاب میکنیم ، اگه بخشپذیر بود که همون جایگشت رو میدیم ، اگر هم نبود یعنی کلا نبوده ! دلیل علمی هم نداره ولی اکسپت میشد !
اثباتش از طریق ‌birthday attackه. :)
 
بالا