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

Dark_Dimius · 2006-11-30 22:56:50

Здесь предлагаю обсуждать решения

Dark_Dimius · 2006-11-30 23:01:04

Код:

//ferry.cpp
#include <iostream>;
#include <algorithm>;
using namespace std;
int main()
{
    int a[10001];
    int n,i,j;
    long ans;
    cin>>n;
    i=0;
    ans=0;
    cin>>a[0];
    while (++i<n)  cin>>a[i];
    sort(a,a+n);
    i=n-1;
    while (i>2)
    {
          if (2*a[1]>a[0]+a[i-1]) ans+=2*a[0]+a[i]+a[i-1];
          else ans+=a[0]+2*a[1]+a[i];
          i-=2;
    }
    if (i==2) ans+=a[2]+a[1]+a[0];
    if (i==1) ans+=a[1];
    cout<<ans<<endl;
}
.

идея такова - либо возит людей первый либо он с вторым, корректность решения доказана математически строго.

Dark_Dimius · 2006-11-30 23:05:13

Код:

//mayor.cpp
#include <iostream>;
#include <cmath>;
using namespace std;


#define BASE 10000    // Основание
#define MAX_DIG 9999    // Максимальная цифра
#define BASE_DIG 4    // Количество десятичных цифр в разряде(для печати)


class BigInt {
public:
    long long Size, SizeMax;
    short *Coef;

    BigInt();
    BigInt(long long);
    BigInt(const BigInt&);
    virtual ~BigInt();

    void zero();

    BigInt& operator=(const BigInt&);
    operator long();
};

void Add(const BigInt&, const BigInt&, BigInt&);
int  Sub(const BigInt&, const BigInt&, BigInt&);
void Div(const BigInt&, BigInt&, BigInt&, BigInt&);
void SMul(const BigInt&, const short B, BigInt&);
void Mul(const BigInt&, const BigInt&, BigInt&);
void SDiv(const BigInt &A, const short B, BigInt &Q, short &R);
void Div(const BigInt &A, const BigInt &V, BigInt &Q, BigInt &R);
ostream& operator<<(ostream& os, const BigInt& A);

clock_t    time_global;

void error(char *error_text) {
    std::cout << "Run-time error...\n" << error_text << "\n";
    exit(0);
}

template<class T>
inline void swap(T& a, T& b) {
    T temp = a;
    b = a;
    a = temp;
}

void start() {
    time_global = clock();
}

clock_t finish() {
    return (clock() - time_global);
}


BigInt::BigInt() {
    SizeMax = Size = 0;
    Coef = NULL;
}


BigInt::BigInt(long long MaxLen) {
    Coef = new short[MaxLen];
    SizeMax = MaxLen;
}


BigInt::BigInt(const BigInt &A) {
    SizeMax = A.SizeMax;
    Size = A.Size;
    Coef = new short[SizeMax];
    for(long long i=0; i<SizeMax; i++) Coef[i] = A.Coef[i];
}

BigInt::~BigInt() {
    delete Coef;
}

void BigInt::zero() {
     Coef= new short[1000];
     SizeMax=1000;
    for(long long i=0; i<SizeMax; i++) Coef[i]=0;
    Size=1;
}    


BigInt::operator long() {
    long tmp=0;
    // warning: overflow possible !
    for(short i=0; i<Size; i++) tmp += Coef[i]*(long)pow( BASE, (double)i);
    return tmp;
}

    

inline BigInt& BigInt::operator=(const BigInt &A) {
    const short *a = A.Coef;
    if (this == &A) return *this;
    if ( SizeMax < A.Size ) {
        delete Coef;
        Coef = new short[A.Size];
        SizeMax = Size = A.Size;
    } else Size = A.Size;
    for(long long l=0; l<Size; l++)
        Coef[l] = a[l];
    return *this;
}


void Add(const BigInt &A, const BigInt &B, BigInt &C) {
    long long i;
    long temp;
    const short *a=A.Coef, *b=B.Coef;
    short *c=C.Coef, carry = 0;

    if ( A.Size < B.Size ) {
        Add(B,A,C);
        return;
    }

    for (i=0; i<B.Size; i++) {
        temp = a[i] + b[i] + carry;
        if (temp >= BASE) {
            c[i] = temp - BASE;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }

    for (; i < A.Size; i++) {
        temp = a[i] + carry;
        if (temp >= BASE) {
            c[i] = temp - BASE;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }
    if (carry) {
        c[i] = carry;
        C.Size = A.Size+1;
    } 
    else C.Size = A.Size;
}






void SMul(const BigInt &A, const short B, BigInt &C) {
    long i, temp;
    const short *a=A.Coef;
    short *c=C.Coef, carry=0; 

    for (i=0; i<A.Size;i++) {
        temp = a[i]*B + carry;
        carry = temp / BASE;
        c[i] = temp - carry*BASE;
    }

    if (carry) {
        c[i] = carry;
        C.Size = A.Size+1;
    } 
    else C.Size = A.Size;

}




        

ostream& operator<<(ostream& os, const BigInt& A) {
    long j, Digit=0;
    short Pow, Dec, Coef;

    os << A.Coef[A.Size-1];

    for (long i=A.Size-2; i>=0; i--) {
        Pow = BASE/10;
        Coef = A.Coef[i];
        for (j=0; j<BASE_DIG; j++) {
            Dec = Coef/Pow;
            Coef -= Dec*Pow;
            Pow /= 10;
            os << Dec;
            Digit++;
            /*if (Digit%1000==0) os << "\n\n";
            else if (Digit%50==0) os << "\t: " << Digit << "\n";*/
        }
    }
    return os;
}

//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
int main()
{
    BigInt a[2][9];
    int i,j,k,n;
    cin >> n;
    i=0;
   a[0][2].zero();
   a[0][1].zero();
   a[0][1].Coef[0]=1;
   a[0][3].zero();
   a[0][4].zero();
   a[0][5].zero();
   a[0][6].zero();
   a[0][7].zero();
   a[0][8].zero();
   a[1][2].zero();
   a[1][1].zero();
   a[1][3].zero();
   a[1][4].zero();
   a[1][5].zero();
   a[1][6].zero();
   a[1][7].zero();
   a[1][8].zero();
  while (++i<=n)
    {
          j=i%2;
          k=(j+1)%2;
          SMul(a[k][1],3,a[j][1]);
          Add(a[j][1],a[k][2],a[j][1]);
          Add(a[j][1],a[k][2],a[j][1]);
          Add(a[j][1],a[k][3],a[j][1]);
          Add(a[j][1],a[k][4],a[j][1]);//a[j][1]=a[k][1]*3+a[k][2]*2+a[k][3]+a[k][4]*2+a[k][5]+a[k][7]+a[k][6]+a[k][8];
          Add(a[j][1],a[k][4],a[j][1]);
          Add(a[j][1],a[k][5],a[j][1]);
          Add(a[j][1],a[k][6],a[j][1]);
          Add(a[j][1],a[k][7],a[j][1]);
          Add(a[j][1],a[k][8],a[j][1]);
          
          SMul(a[k][1],2,a[j][2]);
          Add(a[j][2],a[k][3],a[j][2]);
          Add(a[j][2],a[k][4],a[j][2]);//a[j][2]=a[k][1]*2+a[k][3]+a[k][4]+a[k][7];
          Add(a[j][2],a[k][7],a[j][2]);
          
          a[j][3]=a[k][1];
          Add(a[j][3],a[k][2],a[j][3]);
          Add(a[j][3],a[k][4],a[j][3]);//a[j][3]=a[k][1]+a[k][2]+a[k][4]+a[k][6];
          Add(a[j][3],a[k][6],a[j][3]);
          
          SMul(a[k][1],2,a[j][4]);
          Add(a[j][4],a[k][2],a[j][4]);
          Add(a[j][4],a[k][3],a[j][4]);//a[j][4]=a[k][1]*2+a[k][2]+a[k][3]+a[k][5];
          Add(a[j][4],a[k][5],a[j][4]);
          
          
          a[j][5]=a[k][1];
          Add(a[j][5],a[k][4],a[j][5]);//a[j][5]=a[k][1]+a[k][4];
          
          a[j][6]=a[k][1];//a[j][6]=a[k][1]+a[k][3];
          Add(a[j][6],a[k][3],a[j][6]);
          
          a[j][7]=a[k][1];
          Add(a[j][7],a[k][2],a[j][7]);//a[j][7]=a[k][1]+a[k][2];
          
          a[j][8]=a[k][1];
          /*
          a[j][8]=a[k][1];*/
          }
          cout<<a[j][1]<<endl;
          }

Мой метод майора - динамика по краю+длинная арифметика.

Vladimir · 2006-11-30 23:06:57

Привет Дима

Off top
Если на e-mail получил 5 "Принято" а в результатах токо 4
сколько задач будут оценивать

Dark_Dimius · 2006-11-30 23:10:35

Код:

//mayor2.cpp
#include <iostream>;
#define PPP 2;
#defiine QQQ 1;
using namespace std;
int main()
{
    int n,p,i,j,k,prd,py;
    char a[1001][1001];
    cin>>n>>p;
    for (i=0;i<=1000;i++)
    for (j=0;j<=1000;j++)
        a[i,j]=0;
    for(i=1;i<=p;i++)
    {
        cin>>j>>k;
        a[j][k]=QQQ;
    }
    prd=0;
    k=0;
    j=2;
    while (p) 
    {
        prd++;
        i=prd;
        j=1;
        k++;
        while (i<=n)
        {
            py=j;
            while ((j<=n)&&(a[j][i]!=PPP))
        {
            
            if (a[j][i]==QQQ)
            {
                py=j;
                p--;
            }
            a[j][i]=PPP;
            j++;
        }
        i++;
        j=py;        
    }
    }
    cout<<k<<endl;
}

идия майора2 - строим огибающюю далее для осавшыхся точек тоже - количество огибающих - ответ

Dark_Dimius · 2006-11-30 23:11:55

Vladimir написав:
Привет Дима

Off top
Если на e-mail получил 5 "Принято" а в результатах токо 4
сколько задач будут оценивать

4 к сожелению... читай другие посты, у когото в прошлом туре так было - поледнее письмо дошло позже 24

Dark_Dimius · 2006-11-30 23:17:52

идей зигзага в транзитивности бинарных отношений небольше и неменьше отсюда решение.

Код:

#include <iostream>;
using namespace std;
short sr(long double a, long double b)
{
    if (a>b) return 3;
    if (a<b) return 1;
    return 2;}

int main()
{
     long double a[4];
    int i,n,ans;
    short g,k;
                bool q;
    cin>>n;
    i=1;
    ans=0;
    k=0;
    cin>>a[0]>>a[1];
    g=sr(a[0],a[1]);
                q=(a[0]==a[1]);
    while (++i<n)
    {
        cin>>a[(i)%3];
        k=g;
        g=sr(a[(i+2)%3],a[(i)%3]);
                                q=q&&(a[(i+2)%3]==a[(i)%3]);
        if (((k>1)&&(g>1))||((k<3)&&(g<3))) ans++;
    }
                if (q) ans++;
    cout<<ans<<endl;
}

Dark_Dimius · 2006-11-30 23:29:01

а ньюареа идея такова - строим масив смежности(кто с кам пересикается) и ищем количество связных облостей и выписываем размер наибольшей

Yevgeniy · 2006-12-01 06:18:10

FERRY
Ідея проста: найшвидший перевозить всіх остальних.
//#define MY_DEBUG 10
//-------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>

#ifdef MY_DEBUG
#include <conio>
#include <fstream>
#pragma hdrstop
#include <system.hpp>
#pragma argsused
#endif
using namespace std;
#pragma comment(linker, "/STACK:16777216")

//global variable;
#define PI 3.1415926535897932384626433832795
#ifdef MY_DEBUG
ifstream in("in.txt",ios::in | ios::binary);
ofstream out("out.txt",ios::out | ios::binary);
#endif
//function
//class
class Task
{
//global variable
int N;
int people[20000];
int res;
public:
Task()
{
}
~Task()
{
}
//this is my code
void ReadData()
{
#ifdef MY_DEBUG
//here reading in file
in >> N;
for(int i = 0;i < N;++i)
in >> people[i];
#endif
#ifndef MY_DEBUG
//here standart reading
cin >> N;
for(int i = 0;i < N;++i)
cin >> people[i];
#endif
}
void OutData()
{
#ifdef MY_DEBUG
//here writing in file
cout << res;
#endif
#ifndef MY_DEBUG
//here writing in consol
cout << res;
#endif
}
void Solve()
{
//here solving problem
int min;
res = 0;
sort(people,people + N);
min = people[0];
for(int i = 1;i < N - 1;++i)
{
res += min + people[i];
}
res += people[N - 1];
}
};
int main(int argc, char* argv[])
{
Task a;
#ifdef MY_DEBUG
TDateTime time,time2;
time = time.CurrentDateTime();
#endif
a.ReadData();
a.Solve();
a.OutData();
#ifdef MY_DEBUG
time2 = time2.CurrentDateTime() - time;
unsigned short msec,sec,h,m;
time2.DecodeTime(&h,&m,&sec,&msec);
cout<<endl<<"Solve Time: "<<sec<<":"<<msec<<endl;
in.close();
out.close();
getch();
#endif
return 0;
}
//---------------------------------------------------------------------------

Відредаговано Yevgeniy (2006-12-01 06:20:40)

Женя · 2006-12-01 08:31:24

Yevgeniy написав:
FERRY
Ідея проста: найшвидший перевозить всіх остальних.
//#define MY_DEBUG 10
//-------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>

#ifdef MY_DEBUG
#include <conio>
#include <fstream>
#pragma hdrstop
#include <system.hpp>
#pragma argsused
#endif
using namespace std;
#pragma comment(linker, "/STACK:16777216")

//global variable;
#define PI 3.1415926535897932384626433832795
#ifdef MY_DEBUG
ifstream in("in.txt",ios::in | ios::binary);
ofstream out("out.txt",ios::out | ios::binary);
#endif
//function
//class
class Task
{
//global variable
int N;
int people[20000];
int res;
public:
Task()
{
}
~Task()
{
}
//this is my code
void ReadData()
{
#ifdef MY_DEBUG
//here reading in file
in >> N;
for(int i = 0;i < N;++i)
in >> people[i];
#endif
#ifndef MY_DEBUG
//here standart reading
cin >> N;
for(int i = 0;i < N;++i)
cin >> people[i];
#endif
}
void OutData()
{
#ifdef MY_DEBUG
//here writing in file
cout << res;
#endif
#ifndef MY_DEBUG
//here writing in consol
cout << res;
#endif
}
void Solve()
{
//here solving problem
int min;
res = 0;
sort(people,people + N);
min = people[0];
for(int i = 1;i < N - 1;++i)
{
res += min + people[i];
}
res += people[N - 1];
}
};
int main(int argc, char* argv[])
{
Task a;
#ifdef MY_DEBUG
TDateTime time,time2;
time = time.CurrentDateTime();
#endif
a.ReadData();
a.Solve();
a.OutData();
#ifdef MY_DEBUG
time2 = time2.CurrentDateTime() - time;
unsigned short msec,sec,h,m;
time2.DecodeTime(&h,&m,&sec,&msec);
cout<<endl<<"Solve Time: "<<sec<<":"<<msec<<endl;
in.close();
out.close();
getch();
#endif
return 0;
}
//---------------------------------------------------------------------------

Твоё решение "пролетает" на тесте 4 1 1 8 8 твое решение выдаст 19 а надо 12(4 - количество человек)(если правильно понял идею)

Pavel · 2006-12-01 08:57:22

Ferry
Есть 2 тривиальных метода:
1. самый быстрый перевозит всех (идея Yevgeniy)
2. тормоза переправляются парами и двое самых быстрых гоняют лодку.
эти методы и надо скомбинировать. Точка перехода -- условие от Dark_Dimius (2*a[1]>a[0]+a[i-1])
доказывается строго

У реализовавших один из методов пройдет, имхо, 1 тест
если реализовать оба и выбирать лучший -- 2.

Код:

#include <stdio.h>

#define maxN 10000

int N, i, tt[maxN];
long T, t_crit, t_const;

int qsort(int l, int r)
{
    int i, j, m, t;
    i=l, j=r, m=tt[(l+r)/2];
    do{
        for (; tt[i]<m; i++);
        for (; tt[j]>m; j--);
        if (i<=j)
        {
            t=tt[i];
            tt[i]=tt[j];
            tt[j]=t;
            i++;
            j--;
        };
    }while (i<=j);
    if (i<r) qsort(i,r);
    if (l<j) qsort(l,j);
    return 0;
};

int main()
{
    scanf("%d",&N);
    for (i=0; i<N; i++) scanf(" %d",&(tt[i]));
    qsort(0,N-1);
    T=0;
    t_crit=2*tt[1]-tt[0];
    t_const=2*tt[1]+tt[0];
    for (i=N-1; tt[i-1]>t_crit; i-=2) T+=t_const+tt[i];
    for (; i>1; i--) T+=tt[0]+tt[i];
    T+=tt[1];
    printf("%ld",T);
    return 0;
};

Відредаговано Pavel (2006-12-01 08:58:51)

Pavel · 2006-12-01 09:40:01

mayor
динамика + длинная арифметика. У меня 12 состояний и ручками прорисованы зависимости.
сложность задачи в невозможности проверить-прорисовать варианты даже для 3 (у меня 131)
тут либо zero либо full.

Код:

#include <stdio.h>
#define maxN 1000
#define maxCond 12
#define maxLayer 2
#define maxRef 11
#define maxL 1000
//000
//100, 010, 110, 101
//200, 020
//210, 201, 120 
//220, 202

int CondCRef[maxCond][2]={
    {11,11},{2,0},{2,0},{4,3},{4,4},{2,0},
    {2,0},{2,0},{2,0},{2,0},{4,3},{4,4}};
int CondRef_p[maxCond][maxRef][2]={
    {{3,0},{3,0},{4,0},{0,1},{1,1},{1,1},{2,1},{4,1},{10,1},{10,1},{11,1}},
    {{0,0},{3,1}},
    {{0,0},{4,1}},
    {{1,0},{2,0},{8,1},{9,1}},
    {{1,0},{1,0},{7,1},{7,1}},
    {{0,0},{1,0}},
    {{0,0},{2,0}},
    {{2,0},{3,0}},
    {{1,0},{4,0}},
    {{1,0},{3,0}},
    {{5,0},{6,0},{7,0},{9,0}},
    {{5,0},{5,0},{8,0},{8,0}}};
int CondRef_m[maxCond][maxRef][2]={
    {{0,0},{2,0},{5,1},{5,1},{6,1},{7,1},{7,1},{8,1},{8,1},{9,1},{9,1}},
    {},
    {},
    {{1,1},{3,1},{4,1}},
    {{0,0},{2,1},{3,1},{3,1}},
    {},
    {},
    {},
    {},
    {},
    {{0,0},{1,0},{2,0}},
    {{0,0},{1,0},{1,0},{4,0}}};
    
int CondL[maxCond][maxLayer];
int Cond[maxCond][maxLayer][maxL];

int out(int c, int l)
{
    for (int i=CondL[c][l]-1; i>=0; i--)
        printf("%d",Cond[c][l][i]);
    return 0;
};

int clearCV(int *c)
{
    for (int i=0; i<maxL; i++)
        c[i]=0;
    return 0;
};

int plusCV(int *c, int &cl, int *a, int al)
{
    int over=0, i;
    for (i=0; i<al; i++)
    {
        over=c[i]+a[i]+over;
        c[i]=over%10;
        over/=10;
    };
    while (over>0)
    {
        over=c[i]+over;
        c[i]=over%10;
        over/=10;
        i++;
    };
    cl=(i<cl)?cl:i;
    return 0;
};
    
int minusCV(int *c, int &cl, int *a, int al)
{
    int over=0, i;
    for (i=0; i<al; i++)
    {
        over=c[i]-a[i]+over;
        c[i]=(10+over)%10;
        over=(10+over)/10-1;
    };
    while (over<0)
    {
        over=c[i]+over;
        c[i]=(10+over)%10;
        over=(10+over)/10-1;
        i++;
    };
    for (cl=(i<cl)?cl:i; c[cl-1]==0; cl--);
    return 0;
};

int copyCV(int *s, int sl, int *d)
{
    for (int i=0; i<sl; i++)
        d[i]=s[i];
    return 0;
};
    
int main()
{
    int i,j,N;
    int plus, minus, Ci, Cl;
    int curC[maxL], curCl;
    for (int i=0; i<maxCond; i++)
        for (j=0; j<maxLayer; j++)
        {
            CondL[i][j]=1;
            Cond[i][j][0]=0;
        };
    Cond[0][0][0]=1;
    scanf("%d",&N);
    for (;N>0; N--)
    {
        for (j=1; j<maxCond; j++)
        {
            curCl=0;
            clearCV(curC);
            plus=CondCRef[j][0];
            for (i=0; i<plus; i++)
            {
                Ci=CondRef_p[j][i][0];
                Cl=CondRef_p[j][i][1];
                plusCV(curC, curCl, Cond[Ci][Cl], CondL[Ci][Cl]);
            };
            minus=CondCRef[j][1];
            for (i=0; i<minus; i++)
            {
                Ci=CondRef_m[j][i][0];
                Cl=CondRef_m[j][i][1];
                minusCV(curC, curCl, Cond[Ci][Cl], CondL[Ci][Cl]);
            };
            copyCV(curC, curCl, Cond[j][0]);
            CondL[j][0]=curCl;
        };
        curCl=0;
        clearCV(curC);
        plus=CondCRef[0][0];
        for (i=0; i<plus; i++)
        {
            Ci=CondRef_p[0][i][0];
            Cl=CondRef_p[0][i][1];
            plusCV(curC, curCl, Cond[Ci][Cl], CondL[Ci][Cl]);
        };
        minus=CondCRef[0][1];
        for (i=0; i<minus; i++)
        {
            Ci=CondRef_m[0][i][0];
            Cl=CondRef_m[0][i][1];
            minusCV(curC, curCl, Cond[Ci][Cl], CondL[Ci][Cl]);
        };
        for (i=0; i<maxCond; i++)
            for (j=maxLayer-1; j>0; j--)
            {
                copyCV(Cond[i][j-1], CondL[i][j-1], Cond[i][j]);
                CondL[i][j]=CondL[i][j-1];
            };
        copyCV(curC, curCl, Cond[0][0]);
        CondL[0][0]=curCl;
    };
    out(0,0);
    return 0;
};

Pavel · 2006-12-01 09:54:14

mayor2
ступенчатые огибающие. изысков 0.

Код:

#include <stdio.h>

#define maxN 1000
#define maxP 1000000

int N, x, y, ct, res;
long i, j, P, ST;
char CR[maxN+1][maxN];
int Top[maxN];

int main()
{
    scanf("%d %ld",&N,&P);
    for (i=0; i<N; i++) 
    {
        Top[i]=0; //topest
        CR[0][i]=1;
        for (j=1; j<=N; j++)
            CR[j][i]=0;
    };
    for (i=0; i<P; i++)
    {
        scanf("%d %d",&x,&y);
        y--;
        CR[x][y]=1;
        if (x>Top[y]) Top[y]=x;
    };
    res=0;
    ST=0;
    for (i=0; i<N; ST+=Top[i++]);
    while (ST)
    {
        ct=0;
        for (i=0; i<N; i++)
        {
            if (ct<Top[i]) 
            {
                for (j=ct-1; (j>0) && (CR[i][j]==0); j--);
                ct=Top[i];
                Top[i]=(j>0)?j:0;
            };
        };
        res++;
        ST=0;
        for (i=0; i<N; ST+=Top[i++]);
    };
    printf("%d",res);
    return 0;
};

zigzag
главное аккуратность

Код:

#include <stdio.h>

#define MaxN 10000
#define MaxX 1000

int N, mode, s, k, x, y, i;

int sign(int x, int y)
{
    if (x<y) return 1;
    if (x>y) return -1;
    return 0;
};

int main()
{
    scanf("%d %d %d",&N,&x,&y);
    mode=sign(x,y);
    k=N-2;
    for (i=2; i<N; i++)
    {
        scanf("%d",&x);
        s=sign(y,x);
        y=x;
        if (s*mode==-1) k--;
        if (s!=0) mode=s;
    };
    if (mode==0) k++;
    printf("%d",k);
    return 0;
};

Yevgeniy · 2006-12-01 14:11:22

Коли у нас є два берега, то якби ми не переправляли туристів злівого берега на правий бурег, то за раз ми можемо максимально переправити 1 туриста, бо з правого берега потрібно повернути лодку до лівого (місць тільки 2), при цьому витративши менше часу, і тільки коли на лівому березі знаходиться один турист, то можемо переправити двох одночасно. Звідки слідує єдине рішеня -- найшвидший перевозить всіх остальних.

Junker · 2006-12-01 16:58:20

var n,i,j,t,res:integer;
a,b:array[1..10000]of integer;
tep:boolean;
begin
read(n);
read(a[1]);
b[1]:=0;
for i:=2 to n do
begin
read(a[i]);
if a[i] > a[i-1] then b[i]:=b[i-1]+1;
if a[i] < a[i-1] then b[i]:=b[i-1]-1;
if a[i] = a[i-1] then b[i]:=b[i-1];
end;
tep:=true;
if a[1] > a[2] then t:=-1;
if a[1] < a[2] then t:=1;
if a[1] = a[2] then
begin
i:=1;
while (a[i] = a[i+1])and(i < n) do inc(i);
if (i < n) then
begin
if a[1] > a[i+1] then t:=-1;
if a[1] < a[i+1] then t:=1;
end else
begin
res:=n-1;
tep:=false;
end;
end;
if tep = true then
begin
for i:=1 to n-1 do a[i]:=b[i+1]-b[i];
res:=0;
for i:=1 to n-1 do
begin
if a[i] <> t then
begin
j:=i;
while (a[j] <> t) and (j <= n-1) do
begin
inc(j);
inc(res);
end;
i:=j;
end;
if t = 1 then t:= -1 else t:=1;
if i > n-1 then break;
end;
end;
writeln(res);
end.

Зигзаг - идея в том:
Пример: 5 1 100 -100 220 40
представим числа в виде : 1 2 1 2 1 (1 100 -100 220 40 : от 1 до 100 возрастает от 100 до -100 убывает от -100 до 220 возрастает и от 220 до 40 убывает)
Вычтем из второго первое получим: -1 -1 -1 тоесть послед является зигзагом

Max94 · 2006-12-01 19:01:54

Хто найде тест при якому програма збоїть (памагите!). Дам рубль.

program ZigZag;
var ch:array [1..10000] of integer;
i,n,ch_pop,ch_isn,spos,k:integer;

procedure zbig (var x,y:integer);
begin
x:=x+1;
if y=1 then y:=2 else y:=1;
end;

begin
k:=0;
read (n,ch[1]);
for i:=2 to n do
begin
read (ch[i]);
if i=2 then if ch[1]>ch[2] then spos:=1 else spos:=2;
case spos of
1:begin
if (((i mod 2)=0) and (ch[i-1]<=ch[i])) then zbig (k,spos);
if (((i mod 2)=1) and (ch[i-1]>=ch[i])) then zbig (k,spos);
end;
2:begin
if (((i mod 2)=0) and (ch[i-1]>=ch[i])) then zbig (k,spos);
if (((i mod 2)=1) and (ch[i-1]<=ch[i])) then zbig (k,spos);
end;
end;
end;

writeln (k);
end.

Ivan · 2006-12-01 20:40:00

А если первый равен второму?

Ostap · 2006-12-01 21:06:37

В мене невідомо чому пролетіла перша задача:-) я там занадно нахімічив з оптимізацією...
а так все решта пройшло по максимумах...

2. Ferry
Розглядається два варіанти, або найлегший тягає всіх, або комбінація 2 найлегші - 2 найважчі.

Код:

program Ferry;

Type TArray = Array[1..10000] of integer;

var A : TArray;
N, I, K, S, M1, M2, M3 : longint;
F : boolean;

Procedure QuickSort(M,T : Integer);
var I, J, X, W : Integer;
begin
                         I := M;
                         J := T;
                         X := A[(M+T) div 2];

                        repeat
                          while A[i] < X do
                           Inc(I);
                          while A[J] > X do
                           Dec(J);
                          if I <= J then
                           begin
                            W := A[i];
                            A[i] := A[J];
                            A[J] := W;
                            Inc(I);
                            Dec(J);
                           end;
                        until I > J;

                       if M < J then QuickSort(M,J);
                       if I < T then QuickSort(I,T);
end;


begin
                         read(N);

                        for I := 1 to N do begin
                          read(A[i]);
                        end;

                        QuickSort(1,N);

                        K := N;
                        S := 0;
                        M1 := 2 * A[2] - A[1];
                        M2 := 2 * A[2] + A[1];
                        M3 := 2 * A[1];
                        F := False;

                        repeat
                          if K = 3 then
                           begin
                             S := S + A[1] + A[2] + A[3];
                             break;
                           end
                          else
                           if K = 2 then
                            begin
                              S := S + A[2];
                              break;
                            end;

                           if F = True then
                            begin
                              S := S + M3 + A[K] + A[K-1];
                              K := K - 2;
                              continue;
                            end;

                           if M1 - A[K-1] > 0 then
                            begin
                              S := S + M3 + A[K] + A[K-1];
                              F := True;
                            end
                           else
                             S := S + M2 + A[K];

                             K := K -2;
                        until   False;

                          write(S);
end.

3. Mayor
Тут треба використовувати динамічне програмування... і довго арифметику, але так, що в одному елементі масиву знаходиться кілька цифр(в мене 6)

Код:

program Mayor;

const Osn = 1000000;

Type TLong = Array[0..135] of longint;

var An, Bn, Zn, An1, Bn1, Zn1, An2, Bn2, Zn2, T1, T2, T3, T4, tBn, tBn1 : Tlong;
N, I : integer;

procedure Sum(var A, B, C : TLong);
var I, K : Integer;
begin
                      FillChar(C, SizeOf(C), 0);
                     if A[0] > B[0] then
                       K := A[0]
                     else
                       K := B[0];

                    for I := 1 to K do begin
                       C[I+1] := (C[i]+A[i]+B[i]) div Osn;
                       C[i] := (C[i]+A[i]+B[i]) mod Osn;
                    end;

                    if C[K+1] = 0 then
                      C[0] := K
                    else
                      C[0] := K + 1;
end;

procedure WriteLong(Const A : Tlong);
var Ls, S : string;
I : integer;
begin
                    str(Osn div 10, Ls);
                    write(A[A[0]]);
                   for I := A[0] - 1 downto 1 do begin
                     str(A[i],S);
                    while Length(S) < Length(Ls) do
                      S := '0' + S;
                    write(S);
                   end;
end;



begin
                   read(N);

                  if N = 2 then
                   begin
                     write(22);
                     halt(0);
                   end;

                   An2[0] := 1;
                   An2[1] := 1;
                   Bn2[0] := 1;
                   Bn2[1] := 1;
                   Zn2[0] := 1;
                   Zn2[1] := 3;
                   An1[0] := 1;
                   An1[1] := 8;
                   Bn1[0] := 1;
                   Bn1[1] := 5;
                   Zn1[0] := 1;
                   Zn1[1] := 22;

              for I := 3 to N do begin
                   Sum(An2,Zn2,T1);
                   Sum(Bn1,Bn2,T2);
                   Sum(T1,T2,T3);
                   Sum(Zn1,T3,Bn);
                   Sum(T3,T1,T4);
                   Sum(T4,Bn,An);
                   Sum(Bn, Bn, tBn);
                   Sum(Bn1, Bn1, tBn1);
                   Sum(An1, Zn2, T1);
                   Sum(An, tBn, T2);
                   Sum(T1, tBn1, T3);
                   Sum(T2, T3, Zn);

                   An2 := An1;
                   Bn2 := Bn1;
                   Zn2 := Zn1;
                   An1 := An;
                   Bn1 := Bn;
                   Zn1 := Zn;
              end;

                 WriteLong(Zn);
end.

4. Mayor2
Я цю задачу зробив двома способами, перший - динамічні списки, другий - просто прохід по матриці...
Я відіслав другий спосіб, хоча на тестах зараз перший варіант працює навіть швидше...
Одразу кажу, що я память не очищав:-) зайвий час... тому і впринципі трохи забоявся відсилати цей варіант...
Mayor2(спосіб1)

Код:

program Mayor2;

Type Pt = ^elem;
   Elem = Record
      data : integer;
      next : Pt;
      previous : Pt;
   end;
   PMas = Array[1..1000] of Pt;
    Mas1 = Array[0..1000] of integer;

var PFirstX, PLastX : PMas;
Len : Mas1;
Z, Q, PFirstY, PLastY, PX, PY : Pt;
X, Y, N, Kp, I, KY, MaxX, K, J : integer;
F : boolean;

procedure InsBegin(var PFirst : pt; var  El : integer);
var NewFirst : pt;
begin
               New(NewFirst);
               NewFirst^.next := PFirst;
              if PFirst <> nil then
                PFirst^.previous := NewFirst;
               NewFirst^.data := El;
               PFirst := NewFirst;
               PFirst^.previous := nil;
end;

procedure InsEnd(var PLast : pt; var El : integer);
var Q : pt;
begin
               New(PLast^.next);
               Q := PLast;
               PLast := PLast^.next;
               PLast^.data := El;
               PLast^.next := nil;
               PLast^.previous := Q;
end;

procedure InsMed(var PFirst : pt;var  El : integer);
var Q, NewM : pt;
begin
               New(NewM);
               Q := PFirst;

             while El > Q^.next^.data do
                Q := Q^.next;

               NewM^.next := Q^.next;
               Q^.next^.previous := NewM;
               NewM^.data := El;
               Q^.next := NewM;
               NewM^.previous := Q;
end;

procedure InsEl(var PFirst, PLast : pt; var El : integer);
begin
             if El < PFirst^.data then
               InsBegin(PFirst,El)
             else
              if El > PLast^.data then
                InsEnd(PLast,El)
              else
                InsMed(PFirst,El);
end;

procedure ReadData;
begin
                  read(N);
                  read(Kp);

                  FillChar(Len,SizeOf(Len),0);

                  KY := 0;

               for I := 1 to Kp do begin
                    read(X,Y);

                  if Len[Y] = 0 then
                   begin
                     PFirstX[Y] := nil;
                     InsBegin(PFirstX[Y],X);
                     PLastX[Y] := PFirstX[Y];
                     Inc(Len[Y]);
                    if Ky = 0 then
                     begin
                       PFirstY := nil;
                       InsBegin(PFirstY,Y);
                       PLastY := PFirstY;
                     end
                    else
                     begin
                       InsEl(PFirstY, PLastY, Y);
                     end;
                      inc(Ky);
                     continue;
                   end
                  else
                   begin
                     InsEl(PFirstX[Y], PLastx[Y], X);
                     Inc(Len[Y]);
                   end;
               end;
end;

procedure DelEl(var Pel : pt);
begin
          if Pel = PFirstY then
           begin
            if Pel^.next = nil then
             begin
               PFirstY := nil;
               exit;
             end;
             PFirstY := Pel^.next;
             PFirstY^.previous := nil;
           end
          else
           if Pel = PLastY then
            begin
              PLastY := Pel^.previous;
              PLastY^.next := nil;
            end
           else
             begin
               Pel^.previous^.next := Pel^.next;
               Pel^.next^.previous := Pel^.previous;
             end;
end;

begin

              ReadData;

              K := 0;

            repeat
               Py := PFirstY;
               MaxX := PLastX[PFirstY^.data]^.data;
               PFirstX[Py^.data] := PLastX[Py^.data];
               PLastX[Py^.data]^.previous := nil;

              while Py <> nil do begin
                 Px := PLastX[Py^.data];
                 F := False;

                if Px^.data < MaxX then
                 begin
                   Py := Py^.next;
                   continue;
                 end;

                while Px <> nil do begin
                  if Px^.data < MaxX then
                   begin
                     F := True;
                     MaxX := PLastX[Py^.data]^.data;
                     PLastX[Py^.data] := Px;
                     PLastX[Py^.data]^.next := nil;
                     break;
                   end;

                   Px := Px^.previous;
                end;

                 if F = False then
                  begin
                    MaxX := PLastX[Py^.data]^.data;
                    DelEl(Py);
                    dec(Ky);
                  end;

                  Py := Py^.next;
              end;
                inc(K);
            until (Ky = 0);


                write(K);
end.

Mayor2(2 спосіб) я його відіслав...

Код:

program Mayor2;

Type Mas1 = Array[1..1000,1..1000] of byte;
     Mas2 = Array[1..1000] of boolean;
     Mas3 = Array[1..1000] of integer;

var A : Mas1;
    B : Mas2;

MaxX, MinX : Mas3;

N, P, MaxP, MinY, MaxY, Ky, K, X, Y, H, I, J : integer;

begin
                         read(N);
                         read(P);

                         MaxY := 0;
                         MinY := 1000;
                         Ky := 0;
                         K := 0;

                         FillChar(A,SizeOf(A),0);
                         FillChar(B,SizeOf(B),False);
                         FillChar(MaxX,SizeOf(MaxX),0);

                        for I := 1 to N do
                          MinX[i] := 1000;

                      for I := 1 to P do begin

                        read(X,Y);
                        A[X,Y] := 1;

                       if X > MaxX[Y] then
                         MaxX[Y] := X;

                       if X < MinX[Y] then
                         MinX[Y] := X;

                       if Y > MaxY then
                         MaxY := Y;

                       if Y < MinY then
                         MinY := Y;

                       if B[Y] = False then
                        begin
                          B[Y] := True;
                          inc(Ky);
                        end;

                      end;


                      for I := MinY to MaxY do begin

                        if B[i] = False then
                          continue;
                         MaxP := MaxX[i];
                         B[i] := False;
                         dec(Ky);

                       for Y := I + 1 to MaxY do begin

                          if B[Y] = False then
                            continue;

                          if MaxX[Y] < MaxP then
                            continue;

                          if MinX[Y] >= MaxP then
                           begin
                             B[Y] := False;
                             dec(Ky);
                             MaxP := MaxX[Y];
                             continue;
                           end;

                            H := MaxP;
                          for X := H-1 downto MinX[Y] do
                           if (A[X,Y] = 1) then
                            begin
                              MaxP := MaxX[Y];
                              MaxX[Y] := X;
                              break;
                            end;

                       end;

                          inc(K);
                         if Ky = 0 then
                           break;
                      end;

                         write(K);
end.

5. ZigZag
задача проста... треба просто розглянути по два варіанти на кожен випадок...
тобто варіанти зміни + -. ну в коді повинно бути зрозуміло...

Код:

program Zigzag;

Type TNumberArray = Array[1..10000] of integer;

var A : TNumberArray;
N, Res, MinRes, I : longint;
Next : boolean; 

function Insertions(Next : boolean) : integer;
var  K : integer;
begin
                   K := 0;

                 for I := 3 to N do begin
                   if Next = True then
                    begin
                     if A[i] > A[I-1] then
                      begin
                        Next := not Next;
                        continue
                      end
                    end
                   else
                    if Next = False then
                      if A[i] < A[I-1] then
                       begin
                         Next := not Next;
                         continue
                       end;

                     inc(K);  
                 end;

                  Insertions := K;

end;

begin
                  read(N);

                 for I := 1 to N do
                   read(A[i]);

                 if A[1] > A[2] then
                  begin
                    MinRes := Insertions(True);
                    Res := 1 + Insertions(False);
                  end
                 else
                  if A[1] < A[2] then
                   begin
                     MinRes := Insertions(False);
                     Res := 1 + Insertions(True);
                   end
                  else
                    begin
                       MinRes := 1 + Insertions(False);
                       Res := 1 + Insertions(True);
                    end;

                 if Res < MinRes then
                   MinRes := Res;


                  write(MinRes);
end.

ех, якби не NewArea... в мене за неї 22 бали... :-(((

xXx · 2006-12-02 08:43:55

У меня чего-то сейчас недоступна страница NetOI... и поэтому я не могу протестить своё решение ( может кто-нибудь скажет почему такое решение Mayor2 набирает 38б ?

Код:

#include<cstdio>

#define max(x,y)    (x>y?x:y)

short f[1000][1000];
int i,j,n,p;

main(){
    for(scanf("%d%d",&n,&p);p;--p){
        scanf("%d%d",&i,&j);
        if(i>=1 && i<=n && j>=1 && j<=n)
            f[n-i][j-1]=1;
    }
    for(i=1;i<n;++i)
        for(j=1;j<n;++j)
            if(f[i][j])f[i][j]+=f[i-1][j-1];
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
    printf("%hd\n",f[n-1][n-1]);
    return 0;
}

Відредаговано xXx (2006-12-02 08:44:52)

alex_kasycky · 2006-12-02 13:30:16

xXx написав:
У меня чего-то сейчас недоступна страница NetOI... и поэтому я не могу протестить своё решение ( может кто-нибудь скажет почему такое решение Mayor2 набирает 38б ?

ТЛ

Dark_Dimius · 2006-12-02 13:53:07

alex_kasycky написав:
xXx написав:
У меня чего-то сейчас недоступна страница NetOI... и поэтому я не могу протестить своё решение ( может кто-нибудь скажет почему такое решение Mayor2 набирает 38б ?
ТЛ

а мне дало WA

alex_kasycky · 2006-12-02 14:23:52

Dark_Dimius написав:
а мне дало WA

Попробуй еще раз. Именно 38 баллов? Я еще раз проверил все тесты проходит.
(некоторые на грани => ТЛ)

xXx · 2006-12-02 16:48:19

Дайте плиз ссылку на онлайн-проверку...

Відредаговано xXx (2006-12-02 16:49:24)

Anna · 2006-12-02 18:23:24

xXx написав:
Дайте плиз ссылку на онлайн-проверку...

http://www2.olymp.vinnica.ua/cgi-bin/v_ … mand=check
А вобще, у меня получилось 40 из 40.
ЗЫ Тебе повезло, а то...

xXx · 2006-12-02 20:26:42

16 из 20 тестирований на 40 б. на остальных Тайм аут на 17ом тесте.

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

#1 2006-11-30 22:56:50

Обсуждаем идеи решений

#2 2006-11-30 23:01:04

Re: Обсуждаем идеи решений

Код:

#3 2006-11-30 23:05:13

Re: Обсуждаем идеи решений

Код:

#4 2006-11-30 23:06:57

Re: Обсуждаем идеи решений

#5 2006-11-30 23:10:35

Re: Обсуждаем идеи решений

Код:

#6 2006-11-30 23:11:55

Re: Обсуждаем идеи решений

Vladimir написав:

#7 2006-11-30 23:17:52

Re: Обсуждаем идеи решений

Код:

#8 2006-11-30 23:29:01

Re: Обсуждаем идеи решений

#9 2006-12-01 06:18:10

Re: Обсуждаем идеи решений

#10 2006-12-01 08:31:24

Re: Обсуждаем идеи решений

Yevgeniy написав:

#11 2006-12-01 08:57:22

Re: Обсуждаем идеи решений

Код:

#12 2006-12-01 09:40:01

Re: Обсуждаем идеи решений

Код:

#13 2006-12-01 09:54:14

Re: Обсуждаем идеи решений

Код:

Код:

#14 2006-12-01 14:11:22

Re: Обсуждаем идеи решений

#15 2006-12-01 16:58:20

Re: Обсуждаем идеи решений

#16 2006-12-01 19:01:54

Re: Обсуждаем идеи решений

#17 2006-12-01 20:40:00

Re: Обсуждаем идеи решений

#18 2006-12-01 21:06:37

Re: Обсуждаем идеи решений

Код:

Код:

Код:

Код:

Код:

#19 2006-12-02 08:43:55

Re: Обсуждаем идеи решений

Код:

#20 2006-12-02 13:30:16

Re: Обсуждаем идеи решений

xXx написав:

#21 2006-12-02 13:53:07

Re: Обсуждаем идеи решений

alex_kasycky написав:

xXx написав:

#22 2006-12-02 14:23:52

Re: Обсуждаем идеи решений

Dark_Dimius написав:

#23 2006-12-02 16:48:19

Re: Обсуждаем идеи решений

#24 2006-12-02 18:23:24

Re: Обсуждаем идеи решений

xXx написав:

#25 2006-12-02 20:26:42

Re: Обсуждаем идеи решений

Нижній колонтитул