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

[Fliqpy]

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

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

 

[Phanntom]

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

سوال خوب دارید معرفی کنید
+
این سوال 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; 

}

 

[kagali]

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

الف) درسته
ب)اشتباه
ج)هر دو جمله رو باهم
د)اشتباه

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

 

[miladaghajohari]

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

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

 

[rezaezio]

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

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

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

 

[miladaghajohari]

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

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

 

[rezaezio]

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

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

مثال نقض که نمی تونم بزنم ! ولی درست شنیدی، تو دوره درس نمیدن !

 

[senator77]

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

بچه ها یک سوال جالب
سخت ترین کار دنیا ترجمه کردن سوالات sgu هست خب منم که انگلیسی قوی دارم هزار ماشالا
میشه بگید جایی هست که ترجمه سوالات رو گذاشته باشه؟حداقل 20 تا سوال رو ترجمه کرده باشه ها ی چند جایی رفتم ولی همشون معمولا سه تا سوال اول رو ترجمه کرده بودن
اگه جایی هست بگید

 

[The Smith]

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

بچه ها یک سوال جالب
سخت ترین کار دنیا ترجمه کردن سوالات sgu هست خب منم که انگلیسی قوی دارم هزار ماشالا
میشه بگید جایی هست که ترجمه سوالات رو گذاشته باشه؟حداقل 20 تا سوال رو ترجمه کرده باشه ها ی چند جایی رفتم ولی همشون معمولا سه تا سوال اول رو ترجمه کرده بودن
اگه جایی هست بگید

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

 

[senator77]

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

آغا کلا از سر ترجمه گذشتم :-\ :-\ :-\ :-\
کسی ترجمه ی سوال های sgu رو داره جون من بگه منم بهره ببرم
بعدشم رفت سر یوساکو خیر سرم که ترجمه شدست فصل اول بخش اولشو 4 تا سوالشو حل کردم بعد رسیدم بخش دو سر سوال اول گیر کردم هر کی میتونه درباره ی اون سوال ی راهنمایی هم کنه
مر30