Форум Всеукраїнської інтернет-олімпіади NetOI

Самое прикольное решение ДСП::-)

Ответ (a*b)div(x*y)

jack_spektor написав:

Кстати у тебя в решениях решения только первого тура...

Второго тоже

Решение это хорошо,а лучше б смысл объяснил.
Вот например твоего решения Билдинга

Вот мой алгоритм Билдинга:
Есть три функции:
1.Проверяет есть ли данная часть территории полностью пригодной
Параметры:
координаты начала,длина
2.Проверяет сколько в данном ряде есть максимально подряд таких территорий
3.Находит максимальное значение для всех рядов(2)
4.Находит максимальное для всех длин
max=(3)*длину

Всё

jack_spektor написав:

Вот мой алгоритм Билдинга:
Есть три функции:
1.Проверяет есть ли данная часть территории полностью пригодной
Параметры:
координаты начала,длина
2.Проверяет сколько в данном ряде есть максимально подряд таких территорий
3.Находит максимальное значение для всех рядов(2)
4.Находит максимальное для всех длин
max=(3)*длину

Всё

Лично я не понял есть и легше алгоритмы!!!

Как смог так и сделал.
Чем легче алгоритм-тем сложнее до него додуматься :-)

ROBOT написав:

Проверьте тест 16 для COUNTRY у меня один ответ а у моего друга - другой...
Обе проги верные, а тест большой и руками не посчитать....

Подозреваю тест 16. Моя прога выдала ответ 11190.

Ура! Пашет
wood 40/40

Круто у меня в WOOD 40/40, в DSP 40/40, а что значит 161/161  в Primenum? Почему не 40?

Да, Онлайн взятка!!!

reiten написав:

Вот мои решения:
Wood:O(n* log(maxh))

Код:

#include <iostream>
#include <cmath>

using namespace std;

const int maxN=500;
const int afterComa=3;
const double mult=pow(10.0,(double)afterComa+1.0);

struct section
{
     double length;
    double miny,maxy;
};

int n;

section sects[maxN];

double under(double y)
{
     int i;
    double perim;
    for(i=0,perim=0.0;i<n;i++)
       if(sects[i].maxy<=y)perim+=sects[i].length;
       else if(sects[i].miny<y)
       {
            perim+=sects[i].length*(y-sects[i].miny)/
                (sects[i].maxy-sects[i].miny);
       }
    return perim;
}

int main()
{
     double min,max,mid,ro,perim;
     int i;
     double x1,y1,x,y,xprv,yprv;

     cin>>n>>x1>>y1;
     max=y1;
     for(xprv=x1,yprv=y1,i=1,perim=0.0;i<n;i++,xprv=x,yprv=y)
     {
          cin>>x>>y;
        if(y>yprv)
        {
             sects[i].maxy=y;
            sects[i].miny=yprv;
        }
        else
        {
             sects[i].maxy=yprv;
            sects[i].miny=y;
        }
         sects[i].length=sqrt((x-xprv)*(x-xprv)+(y-yprv)*(y-yprv));
        if(max<y)max=y;
         perim+=sects[i].length;
     }
     if(y1>yprv)
     {
           sects[0].maxy=y1;
        sects[0].miny=yprv;
     }
     else
     {
           sects[0].maxy=yprv;
        sects[0].miny=y1;
     }
     sects[0].length=sqrt((x1-xprv)*(x1-xprv)+(y1-yprv)*(y1-yprv));
     perim+=sects[0].length;
     cin>>ro;
     min=0.0;
     perim*=ro;
     while(floor(min*mult+0.5)!=floor(max*mult+0.5))
     {
          mid=(min+max)/2.0;
        if(under(mid)>=perim)max=mid;
        else min=mid;
     }

     cout.setf(ios::fixed);
     cout.precision(afterComa);
     cout<<min<<endl;

     return 0;
}

Dsp:O(m*n*(m+n))

Код:

#include <iostream>

using namespace std;

const int maxMN=201;

int main()
{
     int a,b,m,n;
     unsigned short counts[maxMN][maxMN]={0};
     int i,j,k,tmp;

     cin>>m>>n>>a>>b;
     counts[a][b]=counts[b][a]=1;
     for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
        {
            for(k=1;k<=i-k;k++)
                if(counts[i][j]<(tmp=counts[k][j]+counts[i-k][j]))
                    counts[i][j]=tmp;
            for(k=1;k<=j-k;k++)
                if(counts[i][j]<(tmp=counts[i][k]+counts[i][j-k]))
                    counts[i][j]=tmp;
        }

     cout<<counts[m][n]<<endl;

     return 0;
}

Building:O(m*n)

Код:

#include <iostream>

using namespace std;

const int maxMN=200;

int main()
{
    int high[maxMN+2]={0};
    int stk[maxMN+2][2];
    int m,n,i,j,stkptr,curr,maxs,s,st;
    
    cin>>m>>n;
    for(i=0,maxs=0;i<m;i++)
    {
        stkptr=0;
        stk[0][0]=0;
        stk[0][1]=-1;
        for(j=0;j<n;j++)
        {
            cin>>curr;
            if(!curr)high[j]=0;
            else high[j]++;
            for(st=j;high[j]<stk[stkptr][0];stkptr--)
            {
                s=(j-stk[stkptr][1])*stk[stkptr][0];
                if(s>maxs)maxs=s;
                st=stk[stkptr][1];
            }    
            if(high[j]>stk[stkptr][0])
            {
                stk[++stkptr][0]=high[j];
                stk[stkptr][1]=st;
            }    
        }    
        for(;stkptr>0;stkptr--)
        {
            s=(n-stk[stkptr][1])*stk[stkptr][0];
            if(s>maxs)maxs=s;
        }            
    }    
    
    cout<<maxs<<endl;
    
    return 0;
}

Primenum:O(l)

Код:

#include <iostream>
#include <climits>

using namespace std;

const int primesCnt=3;
const int maxL=5000;

unsigned long long nums[maxL];

int main()
{
    int i,j,l;
    unsigned long long primes[primesCnt],lasts[primesCnt];
    unsigned long long minNum;
    for(i=0;i<primesCnt;i++)
    {
       cin>>primes[i];
       lasts[i]=0;
    }
    cin>>l;
    for(nums[0]=1,i=1;i<l;i++)
    {
        for(minNum=ULONG_LONG_MAX,j=0;j<primesCnt;j++)
        {
             while(nums[lasts[j]]*primes[j]<=nums[i-1])lasts[j]++;
            if(nums[lasts[j]]*primes[j]<minNum)minNum=nums[lasts[j]]*primes[j];
        }
        nums[i]=minNum;
    }

    cout<<nums[l-1]<<endl;

     return 0;
}

Country:O(n)

Код:

#include <iostream>

using namespace std;

const int maxN=50000;

inline int min(int a,int b)
{
     if(a<b)return a;
    else return b;
}

int main()
{
     char families[maxN];
    int n,i,j,ans,curr;
    int famcnts[3]={0};
    int cnts[3][3]={0};

    cin>>n;
    for(i=0;i<n;i++)
    {
         cin>>families[i];
        families[i]-='1';
        famcnts[families[i]]++;
    }

    for(i=0;i<famcnts[0];i++)
        cnts[0][families[i]]++;
    for(j=0;j<famcnts[2];i++,j++)
        cnts[2][families[i]]++;
    for(j=0;j<famcnts[1];i++,j++)
        cnts[1][families[i]]++;

    ans=0;
//1-2-3
    curr=min(min(cnts[0][1],cnts[1][2]),cnts[2][0]);
    cnts[0][1]-=curr;
    cnts[1][2]-=curr;
    cnts[2][0]-=curr;
    ans+=curr;
//1-3-2
    curr=min(min(cnts[0][2],cnts[2][1]),cnts[1][0]);
    cnts[0][2]-=curr;
    cnts[2][1]-=curr;
    cnts[1][0]-=curr;
    ans+=curr;
//1-2
    curr=min(cnts[0][1],cnts[1][0]);
    cnts[0][1]-=curr;
    cnts[1][0]-=curr;
    ans+=curr;
//1-3
    curr=min(cnts[0][2],cnts[2][0]);
    cnts[0][2]-=curr;
    cnts[2][0]-=curr;
    ans+=curr;
//2-3
    curr=min(cnts[1][2],cnts[2][1]);
    cnts[1][2]-=curr;
    cnts[2][1]-=curr;
    ans+=curr;

    cout<<ans<<endl;

    return 0;
}

Данилка,нормальные люди на С не пишут!!!

Bot17 написав:

Данилка,нормальные люди на С не пишут!!!

Как раз наоборот. На С пишут нормальные люди. Доказательство тому - турнирная таблица. Ты там где, умник? Сиди себе со своим паскалем.