• Зарегистрирован: 2010-02-24
  • Сообщений: 19

Тема: Максимальное время разговора

Время телефонного разговора состоит из N частей. Первые N-1 частей имеют длительности Ki минут, и каждая минута из i-й части стоит Ei. Последняя часть имеет бесконечную длительность, и каждая минута этой части стоит En. Все части идут последовательно, т.е. сразу после завершения i-й части начинается часть i+1. Тарификация поминутная, т.е. деньги снимаются в начале каждой минуты за всю минуту целиком. Если у абонента не хватает денег на разговор в следующей минуте, разговор обрывается.

Нужно найти максимальную общую длину разговора (в минутах) при наличии M денег. Возможно делать несколько звонков.

Входные данные:
В первой строке два целых числа N, M.
В следуюзей строке задано N-1 чисел, которые соответствуют длительностям Ki.
Далее идут N чисел, которые соответствуют стоимостям Ei.

Выходные данные:
Одно число - макс. количество минут.

Ограничения:
1 <= N <= 77,
1 <= M, Ki, Ei <= 1000000 (10^6)
вермя 5 с, память 64 мб

Пример ввода:
2 10
5
1 2

Пример вывода:
10

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

Вы хотели поделиться с нами задачей?

3 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Максимальное время разговора

Я полагаю все задачи, которые находятся в этом разделе, и так подразумевают просьбу что-нибудь посоветовать в плане их решения. Есть еще какие-то причины "делиться" задачами?

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

А можно ссылку на задачу?

5 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Максимальное время разговора

Задача 1098 с acm.lviv.ua. К сожалению, этот сервер сейчас лежит.

6 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

Не уверен что это верно, но возможно пройдет:
Пусть f(x) это минимальное количество денег, требуемое чтобы поговорить x минут, а g(x) это количество денег, требуемое чтобы поговорить x минут за один разговор.
Тогда получаем формулу:

f(x)=min(f(x-k)+g(k)) по всем k<=x.

g(x) легко предпосчитать в самом начале программы для всех x.

Пускай мы вычислили f(x) для какого-то x и для всех i<x мы знаем h(i)=f(x-k)+g(k), где x-k=i. Нам нужно придумать структуру данных, которая будет быстро находить этот минимум. Теперь, когда мы приступим к вычислению f(x+1) нам нужно как-то обновить нашу структуру. Заметим, что x-k не поменяется для фиксированного i, потому что x увеличился на 1, а требуемое k уменьшилось на 1. Значит, нам нужно поменять всего лишь g(k) для всех i<x т.к. k увеличится на 1, а так же добавить значение g(x-1)+g(1) для i=x.

Для всех i<x k увеличится ровно на 1. Разобьем все i на N групп, в каждой из которых стоимость одной минуты будет фиксированной. В таком случае, для всех i таких что соответствующие k и k+1 лежат в одной группе, нам надо всего-лишь увеличить h(i) на соответствующую цену минуты. Будет еще O(N) таких i для которых k и k+1 лежат в разных группах и надо "перевести" этот i из одной группы в другую и увеличить h(i) на стоимость одной минуты уже в новой группе.

Эту задачу уже можно решать либо деревом отрезков с поддержанием указателей на начало каждой группы и переходом от f(x) к f(x+1) за O(NlogM), либо заметить что если элемент A вошел в какую-то группу раньше элемента B, то и выйдет он из нее раньше. Значит, можно создать N очередей и поддерживать для каждой минимум, переходя от f(x) к f(x+1) за O(N).

Суммарная сложность выйдет либо O(NMlogM), если делать деревом отрезков, либо O(NM), если делать очередями.

7 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Максимальное время разговора

Заметим, что x-k не поменяется для фиксированного i, потому что x увеличился на 1, а требуемое k уменьшилось на 1. Значит, нам нужно поменять всего лишь g(k) для всех i<x т.к. k увеличится на 1, а так же добавить значение g(x-1)+g(1) для i=x.

Не уверен, что я правильно Вас понял, вроде, при увеличении x и неизменном i k должно увеличиваться, а не уменьшаться:
i = 0 = x-k = 1-1 = 2-2 = 3-3 = 4-4
i = 1 = x-k = 2-1 = 3-2 = 4-3

Согласно первой формуле, значения f для х=3 и х=4 вычисляются так:
f[3] = min(f[3-1]+g[1], f[3-2]+g[2], f[3-3]+g[3]) = min(f[2]+g[1],f[1]+g[2],f[0]+g[3])
f[4] = min(f[4-1]+g[1], f[4-2]+g[2], f[4-3]+g[3], f[4-4]+g[4]) = min(f[3]+g[1], f[2]+g[2], f[1]+g[3], f[0]+g[4])
Для вычисления х=3 и для х=4 используются одни и те же fi, но разные g. Здесь, как я понял, Вы предлагаете что-то сохранить в дереве отрезков и изменять его элементы на разницу g[2]-g[1], g[3]-g[2], g[4]-g[3] и добавлять, кроме того, f[3]+g[1]. Что именно мы сохраняем и как именно следует обновлять дерево? Если мы сохраняем значения f[2]+g[1], f[1]+g[2], f[0]+g[3], т.е. f[x-k]+g[k], то количество элементов в дереве может быть порядка M, и потребуется обновлять их все. Вы написали о разбиении множества i на группы, но я не очень понимаю: там фигурируют k и k+1, от которых мы вообще, вроде, пытаемся избавиться. Можно ли вместо дерева отрезков использовать дерево Фенвика?

8 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

Ой, я имел ввиду что k увеличивается - дальше именно это и подразумевалось.
Для всех i<x у нас известно h(i)=f(i)+g(k).

f(i) не меняется, значит нужно обновлять g(k). Для этого заметим, что при сдвиге x на один вправо у нас ко всем h(i) прибавится стоимость k-й минуты разговора.

Отнесем каждое i к одной из N групп в зависимости от номера части к которой относится k-я минута. Очевидно, что группы будут состоять из последовательных i. При сдвиге x вправо из некоторых групп по одному элементу перейдут в следующую группу, а все остальные не изменят номера своих групп.

Если решать при помощи дерева, то нужно хранить указатели на начало и конец каждой из групп. Передвинуть указатели можно за O(N) операций. Теперь к каждому из отрезков (которому соответствует какая-то группа) прибавим стоимость минуты разговора, таким образом обновив h(i). В конце нам останется только найти минимум. Дерево Фенвика использовать нельзя, потому что чтобы в нем можно было искать минимум значения нужно только уменьшать, а мы их увеличиваем.

Сложность выйдет O(NMlogM) и я не уверен что оно уложится в 5 секунд с такими ограничениями.

Поэтому я предлагаю делать немного иначе: хранить каждую группу в своей очереди. Тогда передвижения элемента из группы в группу эквивалентно доставанию его из начала одной очереди и добавлению в конец следующей очереди. Как теперь искать минимум? Очень просто - можно для каждой очереди хранить глобальный счетчик - количество дополнительных минут, которые были прибавлены ко всей группе. В таком случае мы можем из каждой очереди за O(1) извлекать минимум и прибавлять к нему количество минут умноженное на стоимость одной такой минуты. А чтобы передвинуть элемент из группы в группу достаточно прибавить к нему накопившееся количество минут умноженное на стоимость предыдущей группы и отнять эту же величину для следующей группы.

9 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Максимальное время разговора

Вы не могли бы продемонстрировать этот подход на каком-нибудь примере?

10 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

Пусть, например у нас N=3, M=12
Стоимость 1-3 минут равна 2, стоимость 4 минуты равна 3, стоимость 5-INF минут равна 10.
Изначально f(0)=0, g(0)=0.

Считаем f(1):
f(1)=f(0)+g(1)=2
Для первой очереди делаем счетчик количества минут равным 1 и добавляем туда число 2-2*0=0.
Состояние очередей:
1) {2}, счетчик 1
2)-...   {}, счетчики 0
Состояние первой очереди {2} означает что когда мы будем считать f(2) у нас f(1)+g(1) будет равно 2+счетчик*цену=2+1*2=4.

Считаем f(2):
f(2)=min(f(0)+g(2),f(1)+g(1))=4
Минимальный из предыдущих элементов это 4.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 4-2*1=2.
Состояние очередей:
1) {2,2}, счетчик 2
2)-... {}, счетчики 0
Состояние первой очереди {2,2} и счетчик 2 означает что когда мы будем считать f(3) у нас f(1)+g(2) будет равно 2+счетчик*цену=2+2*2=6. Аналогично f(2)+g(1)=6.

Считаем f(3):
f(3)=min(f(0)+g(3),f(1)+g(2),f(2)+g(1))=6.
Минимальный из предыдущих элементов это 6.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 6-2*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 3
2)-... {}, счетчики 0
Состояние первой очереди {2,2,2} и счетчик 3 означает что когда мы будем считать f(4) у нас f(1)+g(3) будет равно 2+счетчик*цену=2+3*2=8. Аналогично f(2)+g(2)=f(3)+g(1)=8.

Считаем f(4):
f(4)=min(f(0)+g(4),f(1)+g(3),f(2)+g(2),f(3)+g(1))=8.
Минимальный из предыдущих элементов это 8.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+3*2=8, переносим его во вторую очередь, прибавляем там счетчик 1 и добавляем туда число 8-3*0=8.
У первой очереди увеличиваем счетчик на 1 и добавляем туда 8-3*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 4
2) {8}, счетчик 1
3)-... {}, счетчики 0

Считаем f(5):
f(5)=min(f(0)+g(5),...)=10.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+4*2=10, переносим его во вторую очередь и добавляем туда число 10-3*1=7.
Одновременно с этим достаем элемент 8 из второй очереди, находим его реальное значение, т.е. 8+3*1=11, переносим его в третью очередь и добавляем туда число 11-10*0=11.
Увеличиваем счетчики очередей 1,2,3.
Состояние очередей:
1) {2,2,2}, счетчик 5
2) {7}, счетчик 2
3) {11}, счетчик 1


Считаем f(6):
f(6)=min(f(0)+g(6),...)=12.
...
Теперь состояние очередей:
1) {2,2,2}, счетчик 6
2) {6}, счетчик 3
3) {11,3}, счетчик 2

Это значит, что при подсчете f(7) у нас будет:
h(1)=f(1)+g(6)=11+2*10=31
h(2)=f(2)+g(5)=3+2*10=23
h(3)=f(3)+g(4)=6+3*3=15
h(4)=f(4)+g(3)=2+6*2=14
h(5)=f(5)+g(2)=2+6*2=14
h(6)=f(6)+g(1)=2+6*2=14

Дальше, очевидно, f(x) будет >12, поэтому ответ для данного теста будет равен 6.

11 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Максимальное время разговора

Вот моя реализация этого алгоритма (как я понял). Не прошла по времени 34 тест.

#pragma comment(linker,"/STACK:16777216")

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

#define rep(i,n) for (int i = 0, _##i = (n); i<_##i; ++i)
#define memclr(m) memset(m, 0, sizeof(m))

enum:int {MAX_N = 77, MAX_M = 1000000, INF = 0xfffffff};

queue<int> q[MAX_N];

void main()
{
    int n, m, k[MAX_N], e[MAX_N];

    scanf("%d %d",&n,&m);

    rep(i,n-1) {
        scanf("%d",&k[i]);
    }

    k[n-1] = MAX_M+1;

    rep(i,n) {
        scanf("%d",&e[i]);
    }
    

    int g[MAX_M+1], f[MAX_M+1];
    memclr(g);
    memclr(f);

    for (int t = 1, trel = 1, i = 0, cur_cost = 0; t<=m ; ++t) {
        g[t] = g[t-1] + e[i];
        
        if (trel == k[i]) {
            trel = 1;
            ++i;
        } else ++trel;
    }

    int qcounter[MAX_N];
    memclr(qcounter);
    
    int max_time = 0;

    for (int t = 1, trel = 1, i = 0; t<=m; ++t) {

        f[t] = g[t];
        for (int j = 0; j<=i; ++j) {
            if (!q[j].empty())
                f[t] = min(f[t], q[j].front()+qcounter[j]*e[j]);            
        }

        for (int j = i-1; j>=0; --j) {
            if (t>k[0]) {
                int elem = q[j].front()+qcounter[j]*e[j];
                q[j].pop();
                q[j+1].push(elem - qcounter[j+1]*e[j+1]);
                qcounter[j+1]++;
            }             
        }

        q[0].push(f[t] - qcounter[0]*e[0]);
        qcounter[0]++;


        if (t>=max_time && f[t]<=m)
            max_time = t;
        else if (f[t]>m)
            break;

        if (trel == k[i]) {
            trel = 1;
            ++i;
        } else ++trel;
    }    //    for t

    printf("%d",max_time);
}

12 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальное время разговора

Можно хранить очереди неявно.
У нас в одной очереди лежат последовательные элементы массива, значит можно просто в каком-то одном массиве хранить все элементы, а вместо очередей поддерживать указатели на начало и конец каждой "виртуальной очереди". Тогда константа будет намного меньше.