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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2014-02-07 10:34:32

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Разбор задач

И всё же в этом году я возьму на себя смелость разобрать некоторые задачи и с третьего тура smile

Прошлый год в этом плане был для меня не очень удачным, т.к. тогда я полностью не решил ни одной задачи. В этом же году ситуация немного другая. Мною были полностью решены все задачи, кроме Rook.

1. Bracket.
Для начала заметим, что нам лучше рассматривать эту задачу не с той стороны, что мы будем удалять, а что нам надо оставить. Это позволит изменить задачу на такую: "Сколько подпоследовательной данной последовательности сами являются правильными скобочными последовательностями?". При этом надо заметить, что подпоследовательности, отличающиеся только начальными номерами входящих в них символов считаются различными. Применяем идею динамического программирования. Будем вести двумерный массив DP[i][j], где i - номер символа, к которому мы подошли, а j - количество незакрытых скобок, которые мы можем к этому моменту иметь. DP[i][j] - количество различных подпоследовательностей, последний символ которых имеет индекс <=i и при этом в них имеется ровно j открытых скобок. Понятно, что по окончанию работы нашей программы ответ будет лежать в ячейке DP[n][0]. Теперь пройдёмся в цикле по нашей строке. Рассмотрим, как мы можем повлиять на значения в DP если мы возьмём символ i. Пусть a[i]=='('. Тогда мы сможем увеличить кол-во открытых скобок в любой последовательности на 1. Если же a[i]==')', то мы напротив сможем уменьшить кол-во открытых скобок на 1 (если их не 0). Если же a[i]==']', то мы можем свести кол-во открытых скобок в 0  (если их не 0). Объединяем это всё и получаем решение.
Наилучшая ассимптотика: O(n^2).
Код:

Код:

int DP[800][800];

main()
 {
    char s[800];
    cin>>s;
    int n=strlen(s);
    DP[0][0]=1;
    
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
    {DP[i][j]=(DP[i][j]+DP[i-1][j])%1000007;
    if(s[i-1]==']' && j)
    DP[i][0]=(DP[i][0]+DP[i-1][j])%1000007;
    if(s[i-1]==')' && j)
    DP[i][j-1]=(DP[i][j-1]+DP[i-1][j])%1000007;
    if(s[i-1]=='(')
    DP[i][j+1]=(DP[i][j+1]+DP[i-1][j])%1000007;}
    
    cout<<DP[n][0]<<endl;
 }

2. TETRIS365.
Я не знаю, как это доказать, но такая идея оказалась правильной:
Если n нечётное - то ответ 0 (это доказывается раскраской фигур в шахматном порядке). Иначе пройдёмся по всем делителям n*4*5 (площадь полученной фигуры) за O(sqrtn). Утверждается, что любой прямоугольник, одна из сторон которого больше, чем 2 можно замостить.
Наилучшая ассимптотика: O(sqrtn)
Код:

Код:

main()
 {
    int n;
    cin>>n;
    if(n%2)
    {cout<<0<<endl;return 0;}
    int S=n*4*5;
    int s=0;
    for(int i=3;i*i<=S;i++)
    if(!(S%i))
    s++;
    cout<<s<<endl;
 }

3. Traceroute.
Мне так и не удалось найти ассимптотически оптимальное решение этой задачи. Однако, я порасчитывал на то, что смогу очень-очень хорошо модифицировать неоптимальное, чтобы оно набрало как можно больше баллов. К моему превеликому удивлению оно действительно набрало много баллов. 60/60 smile. Моя идея заключалась в том, чтобы сначала дважды пройтись по графу алгоритмом Дейкстры - из начальной и из конечной точек, а затем использовать полученные данные в качестве эвристики для алгоритма А*. Кроме того, в моём решении использовалась структура данных "система непересекающихся множеств", которая позволяла за O(n) узнавать, будет ли для данного запроса ответ равен -1. Подробнее можно посмотреть в коде - я снабдил его множеством комментариев.
Наилучшая ассимптотика: O(mnlogn)
Код:

Код:

#define INF 1000000000

struct DSU
{
int *parent;
int *size;

void make_set(int x)
{parent[x]=x;
size[x]=1;}

DSU(int n)
{parent=new int[n];
size=new int[n];
for(int i=0;i<n;i++)
make_set(i);}

DSU(DSU t,int n)
{parent=new int[n];
size=new int[n];
for(int i=0;i<n;i++)
parent[i]=t.parent[i],
size[i]=t.size[i];}

int find_set(int x)
{
    if(parent[x]==x)
    return x;
    else
    return parent[x]=find_set(parent[x]);
}

void union_set(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(size[a]<size[b])
        swap(a,b);
        parent[b]=a;
        size[a]+=size[b];
        
    }
}

};
int n=1000;

int mat[2000][2000];
int G[2000][2000];
int path[2][2000][2000];
bool good[2000*2000];

main()
 {
ios::sync_with_stdio(0);

/*--------- Считывание графа ----------*/
    int a,b;
    cin>>n>>a>>b;
    int sz[n];
    fill(sz,sz+n,0);
    fill(good,good+n*n,1);
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        cin>>mat[i][j];
        if(!mat[i][j])
        mat[i][j]=INF,good[min(i,j)*n+max(i,j)]=0;
        else
        G[i][sz[i]++]=j;
    }
    
    int m;
    cin>>m;
    int bad[m-1];
    int divn[m-1];
    int modn[m-1];
    int x,y;
    cin>>x;
    x--;
    for(int i=1;i<m;i++)
    {
        cin>>y;
        y--;
        bad[i-1]=min(x,y)*n+max(x,y);
        divn[i-1]=min(x,y);
        modn[i-1]=max(x,y);
        good[min(x,y)*n+max(x,y)]=0;
        swap(x,y);
    }
/*-------------------------------------*/
    
    
/*------- Препроцессинг алгоритмом ----*/
/*-------------- Дейкстры -------------*/
    //int path[2][n][n]; // Рёбра, входящие в путь к начальной и конечной вершине от заданной
    int len[2][n]; // Длины кратчайших путей
    int prev[2][n]; // Предыдущие вершины в кратчайших путях
    int ans[2][n]; // Длина кратчайших путей
    bool used[2][n]; // ...
    
    for(int i=0;i<2;i++)
    {
        fill(ans[i],ans[i]+n,INF);
        fill(len[i],len[i]+n,0);
        fill(used[i],used[i]+n,0);
        fill(prev[i],prev[i]+n,-1);
        if(i) ans[i][b-1]=0;
        else ans[i][a-1]=0;
        
        for(int j=0;j<n;j++)
        { // Магия
            int cur=-1;
            for(int k=0;k<n;k++)
                if(!used[i][k] && (cur==-1 || ans[i][k]<ans[i][cur]))
                cur=k;
            
            if(ans[i][cur]==INF)
            break;
            
            used[i][cur]=1;
            
            for(int k=0;k<sz[cur];k++)
            {
                int cc=G[cur][k];
                if(ans[i][cur]+mat[cur][cc]<ans[i][cc])
                {
                    ans[i][cc]=ans[i][cur]+mat[cur][cc];
                    prev[i][cc]=cur;
                }
            }
        }
        
        for(int j=0;j<n;j++)
        { // Восстанавливаем пути и превращаем их, как списки вершин в списки рёбер
            int k=j;
            while(prev[i][k]+1)
            path[i][j][len[i][j]++]=min(prev[i][k],k)*n+max(prev[i][k],k),
            k=prev[i][k];
            sort(path[i][j],path[i][j]+len[i][j]);
        }
    }
/*-------------------------------------*/


/*---------- Подготовка DSU -----------*/
    DSU t(n); 
    for(int j=0;j<n;j++)
    for(int i=0;i<j;i++)
    if(good[i*n+j])
    t.union_set(i,j); // Добавляем все рёбра, кроме "плохих"
/*-------------------------------------*/

/*----------- Поиск ответа ------------*/
    int c_bad;
    
    int c_ans[n]; // Эвристика расстояния до конечной вершины от заданной
    int cost[n]; // Расстояние до начальной вершины от заданной
    
    int i,j;
    
    int c_a,c_b; // Количество вершин, путь в которых из первой 
                 //и из второй вершины соответственно не проходит через запретное ребро
                 
    int c_len; // Длина запрещённого ребра для быстрой замены
    
    int c_num,c_cost,c_h; // Внутри цикла номер текущей вершины, 
                          //длина пути в неё из начала и эвристика длины до конца соответственно
    int c_ok[2][n];
    int mod;
    set<pair<pair<int,int>,int> > que; // Ку!
    for(i=0;i<m-1;i++)
    {
        DSU c(t,n);
        for(j=0;j<m-1;j++) // Быстро (за O(m)) проверяем, будет ли вообще ответ
        if(i!=j)
        c.union_set(divn[j],modn[j]);
        if(c.find_set(a-1)!=c.find_set(b-1))
        {cout<<-1<<' ';continue;}
        
        c_bad=bad[i];
        fill(c_ans,c_ans+n,INF);
        fill(cost,cost,INF);
        
        c_a=0,c_b=0;
        
        for(j=0;j<n;j++) // Считаем, в какую сторону нам предположительно выгоднее искать - к концу или к началу
        c_a+=c_ok[1][j]=!binary_search(path[0][j],path[0][j]+len[0][j],c_bad), // Из данной вершины есть путь в начальную без плохого ребра
        c_b+=c_ok[0][j]=!binary_search(path[1][j],path[1][j]+len[1][j],c_bad); // Из данной вершины есть путь в конечную  без плохого ребра    
        
        c_len=mat[divn[i]][modn[i]]; // Удаляем плохое ребро
        mat[divn[i]][modn[i]]=INF;
        mat[modn[i]][divn[i]]=INF;
        
        if(c_ok[1][b-1])
        {cout<<ans[1][a-1]<<' ';goto PERFECT;}
        if(c_ok[0][a-1])
        {cout<<ans[0][b-1]<<' ';goto PERFECT;}
        
        
        que.clear();
        if(c_a<c_b) 
        mod=0,que.insert(make_pair(make_pair(ans[1][a-1],a-1),0));
        else
        mod=1,que.insert(make_pair(make_pair(ans[0][b-1],b-1),0));
        
        while(!que.empty())
        { 
            c_num=que.begin()->first.second;
            c_h=que.begin()->first.first;
            c_cost=que.begin()->second;
            que.erase(que.begin());
            c_ans[c_num]=c_h;
            cost[c_num]=c_cost;
            
            if(c_ok[mod][c_num])
            {c_ans[mod?a-1:b-1]=c_h;break;}
            for(j=0;j<sz[c_num];j++) 
            {
                int cc=G[c_num][j];
                if(c_ans[cc]>c_cost+mat[c_num][cc]+ans[!mod][cc])
                {
                    que.erase(make_pair(make_pair(c_ans[cc],cc),cost[cc]));
                    c_ans[cc]=c_cost+mat[c_num][cc]+ans[!mod][cc];
                    cost[cc]=c_cost+mat[c_num][cc];
                    que.insert(make_pair(make_pair(c_ans[cc],cc),cost[cc]));
                }
            }
        }
        if(c_a<c_b)
        cout<<c_ans[b-1]<<' ';
        else
        cout<<c_ans[a-1]<<' ';
        
        PERFECT:
        mat[divn[i]][modn[i]]=c_len;
        mat[modn[i]][divn[i]]=c_len;
    }
/*-------------------------------------*/
 }

4. Garden365.
Скажу прямо - банальнейшея задача на умение пользоваться гуглом. Легко заметить, что это задача решается с помощью формулы Брахмагупты, описывающей площадь вписанного четырёхугольника. Зная расширенную формулу Брахмагупты, легко доказать, что именно у вписанного четырёхугольника площадь максимальна.
Формула:
http://upload.wikimedia.org/math/2/e/7/2e7ed2bdda9ec26095c511d1b0e68247.png
Ассимптотика: О(1).

5. Rook.
Можно заметить, что с таким небольшим N, мы можем, применив технику сжатия координат свести нашу плоскость 1e9*1e9 к вполне себе безобидному 2000*2000. После этого можно найти ответ с помощью грамотного bfs. Моё решение даёт TLE на одном тесте (по всей видимости, в связи с большой константой) и WA на одном, набирая 54/60 баллов. Немного позднее я постараюсь разобраться с причинами неправильного ответа и сообщу о результатах. Пока что предоставлю код.
Наилучшая ассимптотика: O(n^2)
Код:

Код:

#define INF 1000000000

struct point
{int x,y;
point(){}
point(int a,int b){x=a,y=b;}
};


main()
{
    ios::sync_with_stdio(0);
// Считывание данных
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int n;
    cin>>n;
    point coords[n+4];
    for(int i=0;i<n;i++)
    cin>>coords[i].x>>coords[i].y;
    coords[n].x=x1;
    coords[n].y=y1;
    coords[n+1].x=x2;
    coords[n+1].y=y2;
    coords[n+2].x=-2000000007;
    coords[n+2].y=-2000000007;
    coords[n+3].x=2000000007;
    coords[n+3].y=2000000007;
    int X[n+4],Y[n+4];
    for(int i=0;i<n+4;i++)
    X[i]=coords[i].x,Y[i]=coords[i].y;
    sort(X,X+n+4);
    sort(Y,Y+n+4);
// Сжатие координат
    map<int,int> new_coord_x,new_coord_y;
    int curx=0,cury=0;
    new_coord_x[X[0]]=0,new_coord_y[Y[0]]=0;
    for(int i=1;i<n+4;i++)
    {
        if(X[i]-X[i-1]==1)
        curx++;
        else if(X[i]-X[i-1]>1)
        curx+=2;
        if(Y[i]-Y[i-1]==1)
        cury++;
        else if(Y[i]-Y[i-1]>1)
        cury+=2;
        
        new_coord_x[X[i]]=curx,
        new_coord_y[Y[i]]=cury;
    }
// Создание карты местности
    int MAP[curx+1][cury+1][4];
    int ans[curx+1][cury+1][4];
    for(int i=0;i<=curx;i++)
    for(int j=0;j<=cury;j++)
    for(int k=0;k<4;k++)
    MAP[i][j][k]=1,
    ans[i][j][k]=INF;
    
    for(int i=0;i<n;i++)
    for(int j=0;j<4;j++)
    MAP[new_coord_x[coords[i].x]][new_coord_y[coords[i].y]][j]=0;
    
    x1=new_coord_x[x1];
    y1=new_coord_y[y1];
    x2=new_coord_x[x2];
    y2=new_coord_y[y2];
    for(int i=0;i<4;i++)
    ans[x1][y1][i]=0,
    MAP[x1][y1][i]=1;
// Поиск в ширину по сжатым координатам
    deque<pair<point,int> > que;
    que.push_back(make_pair(point(x1,y1),4));
    
    int dx[]={1,0,-1,0};
    int dy[]={0,1,0,-1};
    while(!que.empty())
    {
        point cur=que[0].first;
        int x=cur.x;
        int y=cur.y;
        int to=que[0].second;
        que.pop_front();
        if(to!=4)
        {if(!MAP[x][y][to])
        continue;
        MAP[x][y][to]=0;}
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]>=0 && x+dx[i]<=curx && y+dy[i]>=0 && y+dy[i]<=cury && MAP[x+dx[i]][y+dy[i]][i])
            {
                if(i==to)
                {
                    que.push_front(make_pair(point(x+dx[i],y+dy[i]),i));
                    ans[x+dx[i]][y+dy[i]][i]=ans[x][y][i];
                }
                else if(MAP[x+dx[i]][y+dy[i]][i]==1)
                {
                    que.push_back(make_pair(point(x+dx[i],y+dy[i]),i));
                    MAP[x+dx[i]][y+dy[i]][i]=2;
                    if(to==4)
                    ans[x+dx[i]][y+dy[i]][i]=1;
                    else
                    ans[x+dx[i]][y+dy[i]][i]=ans[x][y][to]+1;
                }
            }
        }
    }
    int ANS=*min_element(ans[x2][y2],ans[x2][y2]+4);
    if(ANS==INF)
    cout<<-1<<endl;
    else
    cout<<ANS<<endl;
    
    
}

На этом всё. Всем, кто пройдёт, удачи на четвёртом туре! Пусть победит сильнейший и всё такое smile

P.S. У меня сегодня День Рождения, мне исполнилось 18 лет smile

Відредаговано adamant (2014-02-07 10:44:11)

Поза форумом

 

#2 2014-02-07 11:01:07

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Очень хотелось бы услышать комментарий жюри по поводу теста к задаче Garden365, который никто не смог сдать smile

Поза форумом

 

#3 2014-02-07 11:28:53

traveller6
Новий користувач
Зареєстрований: 2011-10-19
Повідомлень: 22

Re: Разбор задач

Вот такой тест у меня не проходит:
1.00000000000000000000000001 1 1 3
Возможно нужна была длинная арифметика

Відредаговано traveller6 (2014-02-07 11:31:13)

Поза форумом

 

#4 2014-02-07 11:30:10

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

В задаче Traceroute только в трёх тестах n>=100 и ни в одном n>=200.

Это при ограничениях в N<=2000 Oo

Поза форумом

 

#5 2014-02-07 11:34:17

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

traveller6 написав:

Вот такой тест у меня не проходит:
1.00000000000000000000000001 1 1 3

Так чтобы такой вход хранить, точности long double не хватает. От нас что, длинную арифметику тут ждали?

Поза форумом

 

#6 2014-02-07 11:35:54

traveller6
Новий користувач
Зареєстрований: 2011-10-19
Повідомлень: 22

Re: Разбор задач

Кроме длинной арифметики тут больше по-моему ничего не придумаешь.

Відредаговано traveller6 (2014-02-07 11:36:03)

Поза форумом

 

#7 2014-02-07 11:38:26

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

В условии вообще ничего не намекало на неё, особенно учитывая то, что точность вывода в примере стоит 8 знаков.

Відредаговано adamant (2014-02-07 11:38:37)

Поза форумом

 

#8 2014-02-07 11:40:56

traveller6
Новий користувач
Зареєстрований: 2011-10-19
Повідомлень: 22

Re: Разбор задач

Возможно ничего не намекало на длинную арифметику потому, что автроры хотели проверить нашу внимательность/находчивость/или просто ради смеху. Тем более, что за это давали всего 3 балла. Да и задача получилась подорзрительно легкая. По-моему то, что все получили на 3 балла меньше вполне справедливо.

Відредаговано traveller6 (2014-02-07 11:43:47)

Поза форумом

 

#9 2014-02-07 11:44:19

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Кстати, в Traceroute, как оказалось, проходил и обычный вызов Дейкстры после каждого удаления. Вот умора-то.

И да, странная проверка находчивости - дать человеку лопату, сказать копать яму и ожидать, пока он для этих целей сделает из лопаты экскаватор...

Поза форумом

 

#10 2014-02-07 11:45:36

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Хм, перетестирование пошло Оо

Поза форумом

 

#11 2014-02-07 11:48:38

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Ну вот, версия про длинную арифметику и отпала

Поза форумом

 

#12 2014-02-07 12:05:40

samus1c
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 18

Re: Разбор задач

adamant написав:

В задаче Traceroute только в трёх тестах n>=100 и ни в одном n>=200.

Это при ограничениях в N<=2000 Oo

Откуда это вам известно?

Поза форумом

 

#13 2014-02-07 12:06:45

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

В дорешивании немного поразвлекался с дописыванием while(n>=x); в код.

Поза форумом

 

#14 2014-02-07 12:43:03

OArtem3
Новий користувач
Звідки: Харьков
Зареєстрований: 2011-10-27
Повідомлень: 6

Re: Разбор задач

Никто не подскажет, что за проблема с 10 тестом в последней задаче? Ни у кого такого не было? У меня в ней сжатие координат + 0-1bfs.

Поза форумом

 

#15 2014-02-07 12:52:01

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

У меня WA3, TLE 9, ничем не могу помочь

Поза форумом

 

#16 2014-02-07 19:19:57

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Тем временем Traceroute перепроверили.

Ну ладно, а у кого больше, чем 48 баллов по нему - как решали-то?

Відредаговано adamant (2014-02-07 19:27:16)

Поза форумом

 

#17 2014-02-07 19:37:44

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Разбор задач

Подведены окончательные итоги 3-го тура и всех 3-х туров сумарно. Не будем отступать от традиций - в финал проходят все, кто набрал 200+ баллов, принося с собой 1/10 от набранной суммы в первых 3-х турах. Таких около 180. Ждите информацию по почте!

Поза форумом

 

#18 2014-02-07 21:13:09

Жюри_Непомнящий
Журі
Зареєстрований: 2005-11-03
Повідомлень: 151

Re: Разбор задач

adamant написав:

Тем временем Traceroute перепроверили.

Ну ладно, а у кого больше, чем 48 баллов по нему - как решали-то?

Эффективным алгоритмом Дейкстры с очередью по приоритетом или Левитом e-maxx.ru

Поза форумом

 

#19 2014-02-07 21:33:09

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Жюри_Непомнящий написав:

adamant написав:

Тем временем Traceroute перепроверили.

Ну ладно, а у кого больше, чем 48 баллов по нему - как решали-то?

Эффективным алгоритмом Дейкстры с очередью по приоритетом или Левитом e-maxx.ru

Если вызывать его каждый раз - это даст ассимптотику O(mnlogn), что для полного графа с 2000 вершин выльется в n^3*logn, что даже хуже, чем если запускать "обычный" алгоритм Дейкстры. Кроме того, в моём решении используется алгоритм А* на контейнере set, что даёт в худшем случае такую же ассимптотику, как и Дейкстра (т.к. A* по сути является его модификацией), но в то же время ещё и значительно улучшает время работы в среднем за счёт множества отсечений. Алгоритм Левита с e-maxx, как было выяснено на codeforces работает в худшем случае за экспоненциальное время, что превращает его использование на соревнованиях в азартную игру - угадай, поставят ли авторы тест, который заставляет его работать по-настоящему медленно.

И да, я правильно понял - в авторском решении алгоритм Дейкстры запускается КАЖДЫЙ РАЗ при удалении ребра? Или всё же он запускается вначале, а затем пересчёт ответа на запрос делается за время меньшее, чем O(mlogn)?

Відредаговано adamant (2014-02-07 21:33:33)

Поза форумом

 

#20 2014-02-07 22:22:32

Liko
Новий користувач
Зареєстрований: 2014-01-05
Повідомлень: 4

Re: Разбор задач

Код:

#include <iostream>
using namespace std;


int main()
{
    long long k; // Количество комплектов (вводимые данные)
    int v;         // Количество полученных прямоугольников (выводимые данные)
    long long m; // Временная переменная, которая хранит минимальное значение целочисленного деления
    cin >> k;
    v = 0;
    if ((k % 2) == 0)
    {
        k *= 20;
        m = k;
        for (long long i = 3; (i <= 10^12) && (m > i); i++)
        {
            if ((k % i) == 0) 
            {
                m = k / i;
                v++;
                //cout << "i = " << i << "   m = " << m << "   k = " << k << "   v = " << v << endl;
            }
        }
    }
    cout << v << endl;
    return 0;
}

Извините, но у меня стоит 57, хотя проходит на 60, в чем проблема???

Поза форумом

 

#21 2014-02-07 23:04:28

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Разбор задач

adamant написав:

Жюри_Непомнящий написав:

adamant написав:

Тем временем Traceroute перепроверили.

Ну ладно, а у кого больше, чем 48 баллов по нему - как решали-то?

Эффективным алгоритмом Дейкстры с очередью по приоритетом или Левитом e-maxx.ru

Если вызывать его каждый раз - это даст ассимптотику O(mnlogn), что для полного графа с 2000 вершин выльется в n^3*logn, что даже хуже, чем если запускать "обычный" алгоритм Дейкстры.  O(mlogn)?

Дейскстра пропорциональна квадрату, а не как вы сказали -  "обычный" алгоритм Дейкстры.  O(mlogn)

Відредаговано LeonID (2014-02-07 23:05:47)

Поза форумом

 

#22 2014-02-07 23:15:09

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

LeonID написав:

Дейскстра пропорциональна квадрату, а не как вы сказали -  "обычный" алгоритм Дейкстры.  O(mlogn)

Э... Я не понял, о чём это сообщение. Я написал о том, что в случае полного графа Дейкстра с приоритетной очередью даст при кратчайшем пути из n вершин итоговую ассимптотику порядка n^3logn, а квадратичный алгоритм - n^3.

Поза форумом

 

#23 2014-02-08 00:29:39

IGOS
Новий користувач
Зареєстрований: 2013-11-07
Повідомлень: 1

Re: Разбор задач

adamant написав:

4. Garden365.
Скажу прямо - банальнейшея задача на умение пользоваться гуглом. Легко заметить, что это задача решается с помощью формулы Брахмагупты, описывающей площадь вписанного четырёхугольника. Зная расширенную формулу Брахмагупты, легко доказать, что именно у вписанного четырёхугольника площадь максимальна.
Формула:
http://upload.wikimedia.org/math/2/e/7/ … e68247.png
Ассимптотика: О(1).

какой угол ты добавлял в формулу ?

Поза форумом

 

#24 2014-02-08 00:37:53

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Разбор задач

То есть в тестах к задаче Traceroute, оказывается, ребер меньше, чем n^2? Но это нигде не указано, на это даже нету намеков..

Поза форумом

 

#25 2014-02-08 07:33:52

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

IGOS написав:

adamant написав:

4. Garden365.
Скажу прямо - банальнейшея задача на умение пользоваться гуглом. Легко заметить, что это задача решается с помощью формулы Брахмагупты, описывающей площадь вписанного четырёхугольника. Зная расширенную формулу Брахмагупты, легко доказать, что именно у вписанного четырёхугольника площадь максимальна.
Формула:
http://upload.wikimedia.org/math/2/e/7/ … e68247.png
Ассимптотика: О(1).

какой угол ты добавлял в формулу ?

Вписанному четырёхугольнику соответствует угол в 90 градусов. В таких условиях вычитаемое вырождается в ноль.

Да, тета - полусумма противолежащих углов.

Відредаговано adamant (2014-02-08 07:36:02)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt