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

guest1 · 2010-01-25 16:47:58

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

qen · 2010-01-25 18:56:43

Все таки мы не достигли взаимопонимания , я вот про это:
"Нужно узнать, сколько времени потратит Петя на запись дисков при условии, что суммарное качество дисков будет максимальным из возможных, а если таких вариантов несколько, то найти такой, при котором затраченное время минимально."
Затраченное время минимально, значит должен быть минимален номер последней секунды, затраченной на запись?Согласитесь это не одно и то же

guest1 · 2010-01-25 23:13:48

Что нужно «узнать» и «найти» — это, можно сказать, даже небольшая подсказка по решению.
А то, что нужно «вывести» — это техническое условие и ему нужно следовать.

kadr · 2010-01-30 15:35:02

Какой была авторская идея?
Я практически уверен, что такое решение правильное(см. ниже), но оно не проходит один тест. Можно ли увидеть 8 тест или контрпример к решению?
Идея такая:
Для начала, решим задачу, где нужно найти только максимальное суммарное качество (без минимизации времени):
1. Найдем все "свободные" отрезки времени (т.е. такие, в которые мы можем непрерывно записывать диски).
2. Забьем все отрезки дисками качества 3 по максимуму. Если дисков больше не осталось, то наилучшее расположение найдено.
3. Если после выполнения предыдущего пункта остались диски, забьем все оставшееся пространство, которое можем, дисками качества 2. Если дисков нету, то это и есть оптимальное расположение.
4. Если после предыдущего пункта диски остались, забьем все оставшееся пространство по максимуму дисками качества 1. Если дисков не осталось, ответ найден.
5. Если все еще есть диски, тогда будем заменять по очереди диски качества 3 на 2 диска качества 2, пока не закончатся диски качества 3. После каждой такой замены мы будем записывать на 1 диск больше, а так же будем увеличивать суммарное качество на 1.
6. Если диски остались, тогда будем так же заменять по очереди диски качества 2 на диски качества 1, пока диски качества 2 не закончатся. После каждой такой замены мы будем записывать на 1 диск больше, а качество меняться не будет.
7. Если все еще остались диски, значит все их записать невозможно, т.к. у нас и так все отрезки забиты дисками качества 1.

Теперь, что касается наименьшего времени. Будем делать бинарный поиск по последней доступной секунде и проверять, какое макс. качество можем получить, если считать что после последней (в бинпоиске) секунды X, свет отрубается навсегда. Если суммарное качество такое же, как и при максимальном доступном времени, тогда, очевидно, мы можем получить такое же качество и для всех X' между X и максимальной доступной секундой.

guest1 · 2010-01-30 15:56:45

kadr, пункты 4 и 5 надо поменять местами. В пункте 4 при добавлении диска мы получаем [–1 диск, +1 качество, +время Q]. В пункте 5 при замене одного диска 4х на два по 8х мы получаем [–1 диск, +1 качество, время не меняется (!!!)]. А так как стоит задача минимизации времени, то пункт 5 должен выполняться до пункта 4.

Что касается тестов — я проверил их ещё раз, они корректные, но всё же не самые лучшие — в начале января я поленился сделать нормальные тесты, а потом как-то об этом и забыл, так их и осталось, 10 штук. Хотя результаты говорят о том, что всё же тесты не самые лёгкие

Насчёт идеи — в основу положены вышеупомянутые семь пунктов, первый пункт делал так: для начала QSort'ил координаты, потом в отдельный массив записывал длины промежутков.

Вот исходник:

Код:

program DVD;
const kmax = 10000;
var i, j, M, N, K, newK, Q, chmode: longint;
    raw, nex: array[0..kmax + 1, 1..2] of longint;
    cur, max: array[0..kmax + 1] of longint;
    quality: int64;
procedure SortX(lo, hi: longint);
var l, r: longint;
    x, y: longint;
begin
    l:=lo; r:=hi; x:=raw[(l + r) div 2, 1];
    repeat
        while raw[l, 1] < x do inc(l);
        while raw[r, 1] > x do dec(r);
        if l <= r then begin
            y:=raw[l, 1]; raw[l, 1]:=raw[r, 1]; raw[r, 1]:=y;
            y:=raw[l, 2]; raw[l, 2]:=raw[r, 2]; raw[r, 2]:=y;
            inc(l); dec(r);
        end;
    until l > r;
    if l < hi then SortX(l, hi);
    if lo < r then SortX(lo, r);
end;
procedure NextOperation;
var xI: longint;
begin
    inc(i);
    if i > newK + 1 then begin
        inc(chmode);
        i:=1;
    end;
    if max[i] > 0 then begin
        case chmode of
            1: begin
                xI:=max[i] div (Q * 4);
                if xI > N then xI:=N;
                inc(cur[i], xI * Q * 4);
                inc(quality, xI * 3);
                dec(N, xI);
            end;
            2: if max[i] - cur[i] >= Q * 2 then begin
                inc(quality, 2); dec(N);
                inc(cur[i], Q * 2);
            end;
            3: begin
                xI:=max[i] div (Q * 4);
                if xI > N then xI:=N;
                inc(quality, xI);
                dec(N, xI);
            end;
            4: if max[i] - cur[i] >= Q then begin
                inc(quality); dec(N);
                inc(cur[i], Q);
            end;
            5: begin
                xI:=max[i] div (Q * 2);
                if xI > N then xI:=N;
                dec(N, xI);
            end;
        end;
    end;
end;
begin
    read(M, N, Q, K);
    for i:=1 to K do read(raw[i, 1], raw[i, 2]);
    SortX(1, K); i:=1; newK:=0;
    while i <= K do begin
        inc(newK);
        nex[newK, 1]:=raw[i, 1];
        nex[newK, 2]:=raw[i, 2];
        j:=i + 1;
        while (raw[i, 2] >= raw[j, 1]) and (j <= K) do inc(j);
        i:=j;
    end;
    fillchar(cur, sizeof(cur), 0);
    max[1]:=nex[1, 1]; max[newK + 1]:=M - nex[newK, 2];
    for i:=2 to newK do max[i]:=nex[i, 1] - nex[i - 1, 2] - 1;
    i:=0; chmode:=1; quality:=0;
    if N = 0 then begin write('0 0'); halt; end;
    while (N > 0) and (chmode < 6) do NextOperation;
    if N > 0 then write(-1) else begin
        if chmode > 1 then begin
            for i:=newK + 1 downto 1 do if cur[i] > 0 then begin
                write(nex[i - 1, 2] + cur[i]);
                break;
            end;
        end else write(nex[i - 1, 2] + cur[i]);
        write(' ', quality);
    end;
end.

kadr · 2010-01-30 16:02:46

А разве бинпоиск не гарантирует минимальности времени?

guest1 · 2010-01-30 16:06:49

Можно немного подробнее и для чайников? Я так давно ничего не кодил...

kadr · 2010-01-30 16:12:09

Тест
28 28 1 0
Ваша программа выдает
28 28
Моя программа выдает
28 29

В условии сказано, что первое число - номер последней имеющейся в распоряжении секунды.
Значит, у нас есть секунды 0-28. Запишем диски качества 1 на секундах 0-26 и диск качества 2 на 27-28. Суммарное качество 29.

guest1 · 2010-01-30 16:13:57

Сейчас посмотрю.

UPD, ну да, вполне возможно, что там ошибка. Я пересмотрю исходник ещё раз и напишу жюри.

Відредаговано guest1 (2010-01-30 16:20:32)

kadr · 2010-01-30 17:09:59

Даже если это баг в решении, то я не вижу, как гарантировать минимальность без бинарного поиска. Можно ли увидеть исправленный код?

pilya · 2010-01-30 17:21:08

Код:

#include <iostream>
using namespace std;
struct myStruct
{
    long b;
    long e;
};
void mySwap(myStruct *m1,myStruct *m2)
{
    long t;
    t=m1->b;
    m1->b=m2->b;
    m2->b=t;
    t=m1->e;
    m1->e=m2->e;
    m2->e=t;

}
int main(void)
{
    myStruct *mp;
    long i,j,m,n,q,k,et,bt,Mint,iMint,t,n1,n2,n4,nt,nn1,nn2,nn4,nq;
    cin>>m>>n>>q>>k;
    mp=new myStruct[k+1];
    iMint=0;
    Mint=2000000001;
    n1=0;
    n2=0;
    n4=0;
    for(i=0;i<k;i++)
    {
        cin>>bt>>et;
        mp[i].b=bt;
        if(et>m)mp[i].e=m; else mp[i].e=et;
        if(bt<Mint)
        {
            iMint=i;
            Mint=bt;
        }
    }
    m++;
    mp[k].b=m;
    mp[k].e=m;
    k++;
    mySwap(&mp[0],&mp[iMint]);
    if(mp[0].b<q) mp[0].b=0;
    t=mp[0].b/q;
    n1=t;
    n2=t>>1;
    n4=t>>2;
    for(i=1;i<k;i++)
    {
        j=i;
        iMint=i;
        Mint=2000000001;
        while(j<k)
        {
            if(mp[j].b<=mp[i-1].e || mp[j].b>m)
            {
                mySwap(&mp[j],&mp[k-1]);
                k--;
            }
            else
            {
                if(mp[j].b<Mint)
                {
                    iMint=j;
                    Mint=mp[j].b;
                }
                j++;
            }
        }
        if(iMint<k)
        {
            mySwap(&mp[i],&mp[iMint]);
            if(mp[i].b<=mp[i-1].e+q)
            {
                mp[i-1].e=mp[i].e;
                mySwap(&mp[i],&mp[k-1]);
                k--;
                i--;
            }
            else
            {
                t=(mp[i].b-mp[i-1].e-1)/q;
                n1+=t;
                n2+=t>>1;
                n4+=t>>2;
            }
        }
    }
    t=(m-mp[k-1].e)/q;
    n1+=t;
    n2+=t>>1;
    n4+=t>>2;
    //for(i=0;i<k;i++)
    //{
    //    cout<<'['<<mp[i].b<<','<<mp[i].e<<"] ";
    //}
    //cout<<endl;
    if(n1>=n)
    {
        nn1=n;
        nn2=0;
        nn4=0;
        nt=n1-n;
        t=(n2<nt)?n2:nt;
        t=(t<n)?t:n;
        nn2=t;
        nn1-=t;
        if(nt>n)
        {
            nt=n2-t;
                                    //t=(n4<nt)?n2:nt;
            t=(n4<nt)?n4:nt;
            t=(t<n)?t:n;
            nn4=t;
            nn2-=t;
        }
        nq=nn1+nn2*2+nn4*3;
        et=-1;
        nt=0;
        //cout<<nn1<<' '<<nn2<<' '<<nn4<<' '<<endl;
        i=0;
        while(nn1!=0 || nn2!=0 || nn4!=0)
        {
            t=(mp[i].b-et-1)/q;
            n4=t>>2;
            nt=et;
            if(nn4 && n4)
            {
                n4=(n4>nn4)?nn4:n4;
                t-=n4<<2;
                nt+=(n4<<2)*q;
                nn4-=n4;
            }
            n2=t>>1;
            if(nn2 && n2)
            {
                n2=(n2>nn2)?nn2:n2;
                t-=n2<<1;
                nt+=(n2<<1)*q;
                nn2-=n2;
            }
            n1=t;
            if(nn1 && n1)
            {
                n1=(n1>nn1)?nn1:n1;
                t-=n1;
                nt+=n1*q;
                nn1-=n1;
            }
            et=mp[i].e;
            i++;
        }
        cout<<nt<<" "<<nq<<endl;
    }
    else
    {
        cout<<"-1"<<endl;
    }
    delete[] mp;
    return 0;
}

Вот код который проходит 60 из 60 и на ввод 28 28 1 0 выдает 28 29

минимальность гарантируется математически без всякого поиска

Відредаговано pilya (2010-01-30 19:00:05)

kadr · 2010-01-30 17:29:25

Тест
93 2 8 1 48 64

Ваша программа вылетает с ошибкой. Да и вообще, почему вы так уверенно говорите, что минимальность гарантируется? 60 из 60 еще ничего не значит

pilya · 2010-01-30 19:04:09

kadr написав:
Тест
93 2 8 1 48 64

Ваша программа вылетает с ошибкой. Да и вообще, почему вы так уверенно говорите, что минимальность гарантируется? 60 из 60 еще ничего не значит

Извините действительно была ошибка вкралась когда оптимизировал код(изначально он был чуть больше но работал правильно )
Хотя даже такой набрал 60 из 60 (Жури можете снять пару балов)

Исправленный код находится в сообщении выще. И еще раз говорю что минимизировать можно без поиска.

P.S. D В коде строка t=(n4<nt)?n2:nt; заменена на t=(n4<nt)?n4:nt;

Відредаговано pilya (2010-01-30 19:15:39)

kadr · 2010-01-30 20:11:15

pilya написав:
kadr написав:
Тест
93 2 8 1 48 64

Ваша программа вылетает с ошибкой. Да и вообще, почему вы так уверенно говорите, что минимальность гарантируется? 60 из 60 еще ничего не значит
Извините действительно была ошибка вкралась когда оптимизировал код(изначально он был чуть больше но работал правильно )
Хотя даже такой набрал 60 из 60 (Жури можете снять пару балов)

Исправленный код находится в сообщении выще. И еще раз говорю что минимизировать можно без поиска.

P.S. D В коде строка t=(n4<nt)?n2:nt; заменена на t=(n4<nt)?n4:nt;

Пожалуй, вы правы - исправленный код, вроде, работает верно. Но как по мне, тесты стоило бы немного поменять, т.к. я знаю нескольких людей с 60 баллами, у которых решение не проходило довольно простых тестов. И плюс ко всему, непонятно что с 8 тестом из текущего набора.

pilya · 2010-01-30 21:08:03

Один из этих людей я

Жюри_Пасихов · 2010-01-30 23:36:37

Да, тут есть авторская недоработка. да и моя тоже :-( Но утешает 2 соображения:

1. Как я понимаю, это первая авторская задача, и в принципе, сыграла. Недостаточно продуман набор тестов, неточности в авторском решении....НО ОДНИМ АВТОРОМ ЗАДАЧ СТАЛО БОЛЬШЕ!!!
1. Изменить что-либо "уточнение неточностей" не сможет (в смысле результата). Но я обязателно проведу перепроверку на более полном и уточненном наборе тестов (жду от автора)

Да,"нелегкая это работа - из болота тащить бегемота" - это я про подготовку задач для олимпиады

Vinnie · 2010-01-31 08:13:21

kadr написав:
Но как по мне, тесты стоило бы немного поменять, т.к. я знаю нескольких людей с 60 баллами, у которых решение не проходило довольно простых тестов.

Не могли бы Вы поподробнее указать эти простые тесты?
Интересно проверить свое решение.

kadr · 2010-01-31 10:46:12

Vinnie написав:
kadr написав:
Но как по мне, тесты стоило бы немного поменять, т.к. я знаю нескольких людей с 60 баллами, у которых решение не проходило довольно простых тестов.
Не могли бы Вы поподробнее указать эти простые тесты?
Интересно проверить свое решение.

Несколько тестов есть выше в этой теме. Могу выложить еще штуки 2, если Ваша программа пройдет их все, можете выложить исходник, я попробую подобрать. Не выкладываю больше из тех соображений, что тесты составлены конкретно под программы нескольких участников.
Тест 1:
92 9 3 0
Ответ:
89 24
Тест 2:
71 3 5 3 0 26 1 33 17 29
Ответ:
66 7
Тест 3:
93 2 8 1 48 64
Ответ:
47 5
Тест 4:
28 28 1 0
Ответ:
28 29

Присяжнюк А.В. · 2010-01-31 10:47:35

Жюри_Пасихов написав:
... Как я понимаю, это первая авторская задача, и в принципе, сыграла. Недостаточно продуман набор тестов, неточности в авторском решении....НО ОДНИМ АВТОРОМ ЗАДАЧ СТАЛО БОЛЬШЕ!!! ...

Мои поздравления по этому поводу всему жюри и прошлогоднему призеру межнара - автору: Твердохлебу Ярославу.
Так держать !!!

kadr · 2010-01-31 10:50:13

Присяжнюк А.В. написав:
Жюри_Пасихов написав:
... Как я понимаю, это первая авторская задача, и в принципе, сыграла. Недостаточно продуман набор тестов, неточности в авторском решении....НО ОДНИМ АВТОРОМ ЗАДАЧ СТАЛО БОЛЬШЕ!!! ...
Мои поздравления по этому поводу всему жюри и прошлогоднему призеру межнара - автору: Твердохлебу Ярославу.
Так держать !!!

Я, конечно извиняюсь, но я не автор этой задачи

Присяжнюк А.В. · 2010-01-31 12:34:48

kadr написав:
Я, конечно извиняюсь, но я не автор этой задачи

А почему на ник авторские права не "застолбили"?

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

kadr · 2010-02-06 11:04:43

Что-то известно насчет ретеста? Ведь если в тестах есть ошибка, то результаты могут поменяться, а значит, те у кого сейчас есть 200 могут их потерять и наоборот, поэтому список участников 4 тура может поменяться, разве не так?

Жюри_Пасихов · 2010-02-06 14:54:17

Могут. Но на состав участников 4-го тура это не повлияет. "Выводить" уже раз внесенных в список не корректно (ошибка автора - они не виноваты, раз уж огласили, то участвуют) , а новые появится не могут - у них нечего тестировать.
В связи с делением баллов 1-3 тура на 10 изменения - в пределах округления.

RaMoN · 2010-02-06 14:54:56

kadr написав:
Что-то известно насчет ретеста? Ведь если в тестах есть ошибка, то результаты могут поменяться, а значит, те у кого сейчас есть 200 могут их потерять и наоборот, поэтому список участников 4 тура может поменяться, разве не так?

Я в списке нашел всего одного человека, у которого от задачи ДВД зависит его проход в следующий тур.

Відредаговано RaMoN (2010-02-06 14:56:02)

kadr · 2010-02-06 15:07:52

RaMoN написав:
kadr написав:
Что-то известно насчет ретеста? Ведь если в тестах есть ошибка, то результаты могут поменяться, а значит, те у кого сейчас есть 200 могут их потерять и наоборот, поэтому список участников 4 тура может поменяться, разве не так?
Я в списке нашел всего одного человека, у которого от задачи ДВД зависит его проход в следующий тур.

Ну тут дело даже не в проходе в 4 тур, а в самом принципе. Думаю, будет не правильно оставлять тесты с ошибкой и баллы полученные за них учитывать в борьбе за проход на всеукраинскую олимпиаду.

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

#26 2010-01-25 16:47:58

Re: DVD

#27 2010-01-25 18:56:43

Re: DVD

#28 2010-01-25 23:13:48

Re: DVD

#29 2010-01-30 15:35:02

Re: DVD

#30 2010-01-30 15:56:45

Re: DVD

Код:

#31 2010-01-30 16:02:46

Re: DVD

#32 2010-01-30 16:06:49

Re: DVD

#33 2010-01-30 16:12:09

Re: DVD

#34 2010-01-30 16:13:57

Re: DVD

#35 2010-01-30 17:09:59

Re: DVD

#36 2010-01-30 17:21:08

Re: DVD

Код:

#37 2010-01-30 17:29:25

Re: DVD

#38 2010-01-30 19:04:09

Re: DVD

kadr написав:

#39 2010-01-30 20:11:15

Re: DVD

pilya написав:

kadr написав:

#40 2010-01-30 21:08:03

Re: DVD

#41 2010-01-30 23:36:37

Re: DVD

#42 2010-01-31 08:13:21

Re: DVD

kadr написав:

#43 2010-01-31 10:46:12

Re: DVD

Vinnie написав:

kadr написав:

#44 2010-01-31 10:47:35

Re: DVD

Жюри_Пасихов написав:

#45 2010-01-31 10:50:13

Re: DVD

Присяжнюк А.В. написав:

Жюри_Пасихов написав:

#46 2010-01-31 12:34:48

Re: DVD

kadr написав:

#47 2010-02-06 11:04:43

Re: DVD

#48 2010-02-06 14:54:17

Re: DVD

#49 2010-02-06 14:54:56

Re: DVD

kadr написав:

#50 2010-02-06 15:07:52

Re: DVD

RaMoN написав:

kadr написав:

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