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

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

  1. Fliqpy

    Fliqpy کاربر نیمه حرفه ای

    ارسال‌ها:
    184
    امتیازات:
    +308 / -5
    نام مرکز سمپاد:
    غیر انتفاعی علامه حلی 3
    شهر:
    تهران
    دانشگاه:
    شريف
    رشته دانشگاه:
    نرم افزار
    پاسخ : آرشیو سوالات از گذشته تا کنون

    نمیدونم درسته یا نه ولی فکر کنم با 3n-logn-3 بشه
    الگوریتم ما این طوریه که در هر مرحله ثابت میکنیم یه نفر ستاره مشهور نیست
    دو نفر رو که نمیدونیم ممکنه باشن یا نه رو انتخاب میکنیم و از یکی در مورد اون یکی میپرسیم.اگه جواب بله بود پس اونی که ازش پرسیدیم ستاره نیست و اگه "نه" بود اونی که راجع بهش پرسیدیم.(هر مرحله دو نفری رو انتخاب میکنیم کمترین تعداد پرسش ازشون صورت گرفته شده باشه)پس بعد از n-1 مرحله یه نفر میمونه. حالا برای اینکه بفهمیم اون ستاره هست یا نه،باید حداکثر 2n-2 تا سوال بپرسیم (اون راجع به هر کدوم از افراد دیگه و هر کدوم از افراد دیگه راجع به اون)اما قبلاً logn تا از این سوالا رو پرسیدیم پس میشه 3n-logn-3.
     
  2. Phanntom

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

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

    سوال خوب دارید معرفی کنید
    +
    این سوال 180 sgu هستش
    ایراد این کد چیه؟


    کد:
    #include <iostream>
    using namespace std;
    const int MAXN = 1000*100+10;
    int n,a[MAXN],tmp [MAXN];
    long long ans=0;
    void merge(int s,int e)
    {
         int mid = (s+e)/2,cou=s;
         int p1=s,p2=mid ;
         while (p1!= mid && p2!= e)
         {
         if (a[p1] <= a[p2])
            tmp[cou++]=a[p1++];
         else
         {
             ans+=mid-p1;
            tmp[cou++]=a[p2++];
         }
         }
         while(p2!=e)
                     tmp[cou++]=a[p2++];
         while(p1!=mid)
                       tmp[cou++]=a[p1++];
         for ( int i=s;i<e;i++)
             a[i]=tmp[i];
    }
    void sorT(int s, int e)
    {
         if(e-s<=1)
              return;
         int mid=(s+e)/2;
          sorT(s,mid);
         sorT(mid,e);
         merge (s,e);
    }
         
    int main ()
    {
        cin >> n;
        for(int i=0;i<n;i++)
                cin >> a[i];
        sorT (0,n);
        for(int i=0;i<n;i++)
                cout << a[i] << " ";
        cout << endl;
        cout << ans << endl;
        cin >> n;
        return 0; 
    
    }
     
  3. kagali

    kagali کاربر نیمه فعال

    ارسال‌ها:
    8
    امتیازات:
    +8 / -0
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    سبزوار
    پاسخ : آرشیو سوالات از گذشته تا کنون

    میشه یه لطفی بکنی خودت جوابشو بدی؟؟!!البته اگه اشکال نداره با توضیح...
     
  4. miladaghajohari

    miladaghajohari کاربر نیمه فعال

    ارسال‌ها:
    5
    امتیازات:
    +4 / -0
    نام مرکز سمپاد:
    شهید اژه ای 2
    شهر:
    اصفهان
    پاسخ : آرشیو سوالات از گذشته تا کنون

    دوستان این سوال 190 اس جی یو ایده حلش چیه؟یه مربع میده یه تیکه هاییش نیست .میگه میشه با دومینو چیدش؟اگر میشه یه راه حل چاپ کن.
    http://acm.sgu.ru/problem.php?contest=0&problem=190
    من کد زیر رو استفاده کردم که رو 21 wrong خورد.راه حل این بود که اگر یه مربع داریم که یه چیز بش وضصل خوب دومینورو میزاریم روش اگر نبود کلا اختیاری یکی رو میزاریم و این اعمال رو تا آخر انجام می دهیم.
    اگر اشکالم رو بگید متشکر میشم.
    http://paste.ubuntu.com/7023077/
     
  5. rezaezio

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

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

    راهت غلط ! تبدیلش کن به گراف دوبخشی، ماکسیمم مچینگ رو پیدا کن !
     
  6. miladaghajohari

    miladaghajohari کاربر نیمه فعال

    ارسال‌ها:
    5
    امتیازات:
    +4 / -0
    نام مرکز سمپاد:
    شهید اژه ای 2
    شهر:
    اصفهان
    پاسخ : آرشیو سوالات از گذشته تا کنون

    متشکرم از پاسخ شما.ولی اگر یه مثال نقض برای راهم بگید عالی میشه.
    راستی این ماکسیمم مچینگ رو میگن که توی دوره و اینا نمیاد(شنیدم دقیق نمیدونم).شما نمیدونید که لازمه یا نه؟
     
  7. rezaezio

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

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

    مثال نقض که نمی تونم بزنم ! ولی درست شنیدی، تو دوره درس نمیدن !
     
    • لایک لایک x 1
  8. senator77

    senator77 کاربر نیمه حرفه ای

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

    بچه ها یک سوال جالب
    سخت ترین کار دنیا ترجمه کردن سوالات sgu هست خب منم که انگلیسی قوی دارم :)) :)) :)) :)) :))هزار ماشالا
    میشه بگید جایی هست که ترجمه سوالات رو گذاشته باشه؟حداقل 20 تا سوال رو ترجمه کرده باشه ها ی چند جایی رفتم ولی همشون معمولا سه تا سوال اول رو ترجمه کرده بودن :D :D :D
    اگه جایی هست بگید
     
  9. The Smith

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

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

    یه سری جاها هست ولی خب اگه باشه یا خیلی سخته یا خیلی آبکی .
    خودت ترجمه کن تا قوی شی. :‌|
    سر کانتست کسی نیست برات ترجمه کنه :‌|
     
  10. senator77

    senator77 کاربر نیمه حرفه ای

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

    آغا کلا از سر ترجمه گذشتم :-\ :-\ :-\ :-\
    کسی ترجمه ی سوال های sgu رو داره جون من بگه منم بهره ببرم [-o< [-o< [-o< [-o<
    بعدشم رفت سر یوساکو خیر سرم که ترجمه شدست فصل اول بخش اولشو 4 تا سوالشو حل کردم بعد رسیدم بخش دو سر سوال اول گیر کردم هر کی میتونه درباره ی اون سوال ی راهنمایی هم کنه 8-> 8-> 8-> 8-> 8->
    مر30 :x :x :x
     
  11. most wanted

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

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

    :-"
    سوال واسه ترجمه یا راهنمایی میخوای سوالو بگو ! :-"
    اینجا داره یه تعدادی !
    http://challenger.blog.ir/category/SGU/
     
    • لایک لایک x 2
  12. mhnp

    mhnp کاربر فعال

    ارسال‌ها:
    69
    امتیازات:
    +182 / -21
    نام مرکز سمپاد:
    علامه حلی
    شهر:
    کرمان
    دانشگاه:
    شهید باهنر
    رشته دانشگاه:
    مهندسی نرم افزار
    پاسخ : آرشیو سوالات از گذشته تا کنون

    اینو چند روز پیش دوستم گفت جالب بود .
    یه برنامه بنویسید که بدون دستور شرطی از بین چند عدد بزرگ ترینشونو معلوم کنه .
     
    • لایک لایک x 1
  13. sara.speed

    sara.speed کاربر فعال

    ارسال‌ها:
    34
    امتیازات:
    +39 / -3
    نام مرکز سمپاد:
    فرزانگان 10
    شهر:
    تهران
    دانشگاه:
    نرفتم هنو خو
    رشته دانشگاه:
    خو اینم نمیدونم
    پاسخ : آرشیو سوالات از گذشته تا کنون

    اگه منظورت اینه که چطوری بدون مقایسه ما بیایم و پیدا کنیم http://paste.ubuntu.com/7527671/ این کدی که نوشتم یک آرایه رو بدون مقایسه مرتب میکنه
     
  14. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,913 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

    این سوال رو خب توی تاپیک مرتبطش میگفتید (اصلا به من چه؟)

    من این کد رو نوشتم ولی قبل از کامپایل باید محدوده ی اعداد ورودی رو بهش بگید و تا زمانی اعداد رو از ورودی میگیره که ورودی برابر 1- نباشه

    http://paste.ubuntu.com/7528448/
     
  15. The Smith

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

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

    اگه لیمیت اعدادمون تا ۱۰ به توان ۱۸ باشه کد هیچکدمتون جواب نمیده :|
     
    • لایک لایک x 1
  16. Dark Eagle

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

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

    مثلا الآن اگه از تابع max اِ cpp استفاده کنیم چه مشکلی داره ... دستور شرطی هم نداره :-"

    میشه string گرفت ... یه تابع chek هم نوشت 2 تا string بگیره بگه کدوم بزرگ تره ... واسه هر عددی هم کار میکنه ...

    اما فک نکنم منظور سواله این باشه .... الآن منظور از بدون دستور شرطی چیه ؟
     
    • لایک لایک x 2
  17. مهسا.ق

    مهسا.ق کاربر فوق حرفه ای

    ارسال‌ها:
    1,104
    امتیازات:
    +3,293 / -94
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران
    رشته دانشگاه:
    نرم افزار
    پاسخ : آرشیو سوالات از گذشته تا کنون

    خوب مثلما منظورش فقط دستور if نیست خوب!
    وگرنه یه جا این روشی که شما می گید خود تابع sort هم جواب می ده چه کاریه اصلا :-""
    کسی که سوالو گفته یه تعریفی از دستور شرطی بیا ارائه بده! از یه زاویه ای بخوای نگاه کنی حتی for , while هم شرطین :-? :D

    یه چیزی این 2 تا کد هر دوتاشون از if استفاده کردید که
     
  18. sara.speed

    sara.speed کاربر فعال

    ارسال‌ها:
    34
    امتیازات:
    +39 / -3
    نام مرکز سمپاد:
    فرزانگان 10
    شهر:
    تهران
    دانشگاه:
    نرفتم هنو خو
    رشته دانشگاه:
    خو اینم نمیدونم
    پاسخ : آرشیو سوالات از گذشته تا کنون

    باور میکنی من هنوزم که هنوزه سوال رو نفهمیدم؟من ی چیز دیگه فهیده بودم کدی ام که نوشتم واسه اونی بود که اون موقه فهمیدم ولی الان فهمیدم که اونی که اونموقه فهمیدم اشتباه فهمیده بودم میفهمی که چی میگم؟
     
  19. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,913 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : آرشیو سوالات از گذشته تا کنون

    اینم حرفیه
    احتمالا منظور سوال این بوده که بدون دستور شرطی بین اعداد ورودی برنامه نویسیم
    آقا خب اگه قرار باشه مقایسه نکنیم باید چی کار کنیم؟ علم غیب که نداریم که (نا جدی)

    بدین وسیله از mhnp تقاضا میشود اصلاحاتی اعمال کند (اصلا به من چه؟)
     
  20. senator77

    senator77 کاربر نیمه حرفه ای

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

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

    +سوال خودم که اگه راهنمایی کنید ممنون میشم:سوال شیر دادن گاو ها سکشن 1.2 اولین سوالش

    اینم لینکش:http://cerberus.delos.com:790/usacoprob2?a=fDlUwxgrZiL&S=milk2