سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

[Admin2]

تعدادی از معلمین و مسئولین سمپاد یک سایت راه انداختن برای پیشرفت برنامه نویسی در بین دانش آموزان سمپاد. به این شکل که عضوش میشید. تعدادی مسابقه در حال برگزاریه. مسابقه رو انتخاب میکنید و هر مسابقه هم تعدادی سوال داره که شما باید کدش رو بنویسید. یک تایمر معکوس هم داره که مهلت برگزاری مسابقست. بعد براساس کدتون و مدت زمانی که کد رو نوشتید بهتون امتیاز میدن و رده بندی میشید. سایت جالبیه بین بقیه برنامه نویس های سمپادی. ببینید:

http://ctalk.ir​

 

[@LiReZ@]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

ممنون از سایتی که معرفی کردید

خوب بود

 

[rezaezio]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

سوالات تکراری به همراه جاج غیر استاندارد ! :)

 

[daneshvar.amrollahi]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

سلام. من کد سوال ۶ چالش چهارمش رو نوشتم. سوال سی دی. باید تعداد عناصر مشترک یک آرایه رو بگه. به ترتیب طول آرایه اول و دوم رو میگه بعدش عناصر آرایه اول و دوم (هر دو سورت شده اند - یعنی به ترتیب صعودی میده). من این کد رو نوشتم ۷ تا تست کیس بهش میده ۳ تاش تایم لیمیت میخوره. کسی الگوریتم بهینه تری سراغ داره؟
کد تقریبا واضحه. سوالی داشتید در موردش بپرسید:

#include<iostream>
#include<vector>
using namespace std;
vector <int> a,b;

bool repeat(vector <int> v,int x)
{
    for (int i=0;i<v.size();i++)
        if (x==v[i])
            return true;
    return false;
}

int main()
{
    long int n,m;
    cin>>n>>m;
    int x;
    for (int i=0;i<n;i++)
    {
        cin>>x;
        if (repeat(a,x)==false)
            a.push_back(x);
    }
    for (int i=0;i<m;i++)
    {
        cin>>x;
        if (repeat(b,x)==false)
            b.push_back(x);
    }

    int res = 0;
    int sa=a.size(),sb=b.size();
    for (int i=0;i<sa;i++)
    {
        for (int j=0;j<sb;j++)
        {
            if ( (a[i]==b[j]) )
            {
                res++;
                break;
            }

            if ( b[j]>a[i])
                break;
        }
    }
    cout<<res<<endl;
    return 0;
}

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

 

[most wanted]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

این کاری که واسه حذف عنصرا تکراری کردی از اردر n به توان ۲‌ ِ اگه طول آرایه هات بزرگ تر از ده هزار باشه تایم میشه .
اون کار پایینِتم از همون اردر ِ پس باتوجه به سایز ورودی ممکن ِ تایم بشه !
واسه حذف عنصر تکراری ها سورت ِ شون کن بعد میتونی با اردر n حذف کنی تکراری هارو .
بعد رو یکی از آرایه هات حرکت کن با باینری سرچ ببین تو اون یکی هست یا نه ! این میشه O(nlogn)

پ.ن. :‌ الگوریتم از اردر ماکسیمم عدد آرایه هام میشه نوشت !

 

[daneshvar.amrollahi]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

این کاری که واسه حذف عنصرا تکراری کردی از اردر n به توان ۲‌ ِ اگه طول آرایه هات بزرگ تر از ده هزار باشه تایم میشه .
اون کار پایینِتم از همون اردر ِ پس باتوجه به سایز ورودی ممکن ِ تایم بشه !
واسه حذف عنصر تکراری ها سورت ِ شون کن بعد میتونی با اردر n حذف کنی تکراری هارو .
بعد رو یکی از آرایه هات حرکت کن با باینری سرچ ببین تو اون یکی هست یا نه ! این میشه O(nlogn)

پ.ن. :‌ الگوریتم از اردر ماکسیمم عدد آرایه هام میشه نوشت !

درست شد ممنونو این کدش:
#include<iostream>
#include<vector>
using namespace std;
vector <int> a,b;
int main()
{
int v1[1000000],v2[1000000];
int n,m;
cin>>n>>m;
for (int i=0;i<n;i++)
cin>>v1;

for (int i=0;i<m;i++)
cin>>v2;

for (int i = 0; i < n; i++) {
if ( (v1 == v1[i - 1]) && (i>0) )
continue;
a.push_back(v1);
}
for (int i = 0; i < m; i++) {
if ( (i>0) && (v2 == v2[i - 1]) )
continue;
b.push_back(v2);
}

long int res = 0;
long int l,h;
int sa=a.size();
for (int i=0;i<sa;i++)
{
l = 0; h = b.size()-1;
while (l<=h) //binary search
{
long int m = l+(h-l)/2;
if (b[m]==a)
{
res++;
break;
} else
if (b[m]<a)
l = m+1;
else
h = m-1;
}

}
cout<<res<<endl;
return 0;
}

 

[most wanted]

پاسخ : سایت مسابقات برنامه نویسی مخصوص سمپادی‌ها

اگه صعودی میده این شکلی میشه !‌

  vector<int> v;
  int n;
  cin>>n;
  int x;
  cin>>x;
  v.push_back(x);
  for(int i=1;i<n;i++){
    cin>>x;
    if(x!=v.back())
      v.push_back(x);
  }