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

شروع موضوع توسط armita ‏2009/4/30 در انجمن المپیاد كامپيوتر

  1. مهدی

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,598 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

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

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,036 / -77
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    Dark Eagle کاربر حرفه ای

    ارسال‌ها:
    404
    امتیازات:
    +679 / -34
    نام مرکز سمپاد:
    helli 2
    شهر:
    Tehran
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

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

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

    meli کاربر خاک انجمن خورده

    ارسال‌ها:
    2,017
    امتیازات:
    +8,686 / -142
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1 تهران
    شهر:
    تهران
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,598 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

    Phanntom کاربر فوق فعال

    ارسال‌ها:
    115
    امتیازات:
    +379 / -15
    نام مرکز سمپاد:
    helli
    شهر:
    تهران
    دانشگاه:
    light massage(پیام نور)
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,598 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : آرشیو سوالات از گذشته تا کنون

    همه دو جفتی های اعداد اول aوb را بیابید به طوریکه aکوچکتر مساوی b و مجموع آنها نیز یک عدد اول باشد و از n بیشتر نشود
     
    • لایک لایک x 1
  8. مهدی

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,598 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

    حالا رو این سوال فکر کنید :د
     
    • لایک لایک x 1
  9. The Smith

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

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

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

    meli کاربر خاک انجمن خورده

    ارسال‌ها:
    2,017
    امتیازات:
    +8,686 / -142
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1 تهران
    شهر:
    تهران
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    من اکسپت گرفتم ولی اصلا راه حلّم خوشگل و خاص نبود :))
     
    • لایک لایک x 2
  11. The Smith

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    meli کاربر خاک انجمن خورده

    ارسال‌ها:
    2,017
    امتیازات:
    +8,686 / -142
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1 تهران
    شهر:
    تهران
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

    most wanted کاربر نیمه حرفه ای

    ارسال‌ها:
    215
    امتیازات:
    +691 / -25
    نام مرکز سمپاد:
    علامه حلی2
    شهر:
    تهران
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    meli کاربر خاک انجمن خورده

    ارسال‌ها:
    2,017
    امتیازات:
    +8,686 / -142
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1 تهران
    شهر:
    تهران
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

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

    informatic کاربر فوق فعال

    ارسال‌ها:
    109
    امتیازات:
    +1,185 / -10
    نام مرکز سمپاد:
    شهيد سلطانی
    شهر:
    کرج
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    informatic کاربر فوق فعال

    ارسال‌ها:
    109
    امتیازات:
    +1,185 / -10
    نام مرکز سمپاد:
    شهيد سلطانی
    شهر:
    کرج
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : آرشیو سوالات از گذشته تا کنون

    کل حالات میشه ماکسیموم 17! دیگه
     
  19. informatic

    informatic کاربر فوق فعال

    ارسال‌ها:
    109
    امتیازات:
    +1,185 / -10
    نام مرکز سمپاد:
    شهيد سلطانی
    شهر:
    کرج
    پاسخ : آرشیو سوالات از گذشته تا کنون

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

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : آرشیو سوالات از گذشته تا کنون

    اثباتش از طریق ‌birthday attackه. :)