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


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

Ви не зайшли.

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

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: DVD

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

Поза форумом

 

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

qen
Новий користувач
Зареєстрований: 2010-01-25
Повідомлень: 2

Re: DVD

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

Поза форумом

 

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

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: DVD

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

Какой была авторская идея?
Я практически уверен, что такое решение правильное(см. ниже), но оно не проходит один тест. Можно ли увидеть 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 и максимальной доступной секундой.

Поза форумом

 

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

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: DVD

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

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

Насчёт идеи — в основу положены вышеупомянутые семь пунктов, первый пункт делал так: для начала 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.

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

Поза форумом

 

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

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: DVD

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

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

Поза форумом

 

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

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: DVD

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

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

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

Поза форумом

 

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

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: DVD

Код:

#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)

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

Тест
93 2 8 1 48 64

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

Поза форумом

 

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

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: DVD

kadr написав:

Тест
93 2 8 1 48 64

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

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

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

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

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

pilya написав:

kadr написав:

Тест
93 2 8 1 48 64

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

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

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

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

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

Поза форумом

 

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

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: DVD

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

Поза форумом

 

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

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

Re: DVD

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

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

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

Поза форумом

 

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

Vinnie
Новий користувач
Зареєстрований: 2010-01-07
Повідомлень: 9

Re: DVD

kadr написав:

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

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

Поза форумом

 

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

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: DVD

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

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

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

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

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

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

Поза форумом

 

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

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: DVD

kadr написав:

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

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

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

Поза форумом

 

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

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

Re: DVD

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

Поза форумом

 

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

RaMoN
Новий користувач
Звідки: Дніпропетровськ
Зареєстрований: 2008-09-22
Повідомлень: 28

Re: DVD

kadr написав:

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

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

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

Поза форумом

 

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

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: DVD

RaMoN написав:

kadr написав:

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

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

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt