I solved the problem the way I understood it but then when staring at the discussion page I discovered that buying the same tap twice is allowed.

These two tests helped we find my bugs.

Test
2
1
3
0
2 1 2
The answer is 4.

Test
3
10
20
30
1
29 3 1 2 3
2 1 2
The answer is 29.

Hope it will help you too.

И не только мне,  как показывает форум.

Можно решить это с помощью алгоритма Дейкстры.

Моё время на Clang C++14 равно 2.7 сек.
На Visual C++2013 вообще  TLE#8.

"В первой строке записано число N — количество недостающих Петрову крышек (1 ≤ N ≤ 20)."

vs

"В последней строке перечислен минимальный набор крышек, который Петров намерен купить в любом случае."

Edited by author 26.12.2014 13:39

Taking hints from the forum I am using dynamic programming with bitmasking. But I cannot understand how to memoize the results as the number of subproblems are very large. ie.
2^n * m
that is 2^20 * 120.
I am getting Memory limit exceeded. Is there a better way to define the states of the dp?

  I regard it as a graph theory problem,and solve it in O(M*2^N).
  But it is very slow,so I would like to hear some others' algorithm.Maybe we can make progress together.
  Contact me: yym2008@hotmail.com

4
20
11
12
23
3
17 2 1 3
25 3 2 3 4
15 2 3 4
3 1 3 4

What is the answer? 32 or 35?
If 32, how is it possible to do that less that O(2^(N+M))?

use priority_queue, it eats less memory

The set of tests is not so good, because optimized backtracing can get AC in 0.015 sec and 129 Kb on Pascal. Try to add more good tests. I think there is no this test:

20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


This simplest test will be bad for some good optimazed brute forces...  Try spend little time to find some "good".

PS To Vladimir Yakovlev, give me please your e-mail, I can say more about this problem but not in the forum.

Thanks!

could anyone give me some tests?

Please, help to make it AC...
Thanks.

http://acm.timus.ru/rating.aspx?space=1&num=1326

time 2.671
memory 2349

I am happy!!!

Jooooooooouuuuuuuuuuuuuuuuuu! I did IT!!!
Whole day!!!!
I'm satisfied!

Hi to all from BSU!

   I code the offers as bitmaps and calculate the cost of every bitmap. This gives 2^N configurations. Then the algorithm is dynamic programming or minimum path in a directed acyclic graph.
   Please help me see where I am wrong.

   Here's part of my code

/* variables */

int prices[maxn];

struct offer {
    int tapcode;
    short int  price;
} offers[maxm];

int N, M, goal;

short int cost[1 << maxn];

void solve(void)
{
    int tapcodemax = 1 << N;
    int i, tapcode, k, j, sol;
    short int ccost;

    /* compute initial costs based on individual prices */

    for (i = 0; i < tapcodemax; i++) {
        tapcode = i, ccost = 0;
        for (j = 0; j < N; j++, tapcode /= 2)
            if (tapcode & 1)
               ccost += prices[j];
        cost[i] = ccost;
    }

    /* consider special offers */

    for (i = 0; i < tapcodemax; i++)
        for (k = 0; k < M; k++)
            if (cost[i | offers[k].tapcode] > cost[i] + offers[k].price)
               cost[i | offers[k].tapcode] = cost[i] + offers[k].price;

    for (sol = cost[goal], i = 0; i < tapcodemax; i++)
        if (((i & goal) == goal) && sol > cost[i])
           sol = cost[i];
    printf ("%d\n", sol);
}

Edited by author 30.08.2004 01:48

Edited by author 25.05.2004 09:09

What is that seperate in n lines and m lines ?
I don't understand it.

input
4
100
100
100
100
3
17 2 1 3
25 3 2 3 4
15 2 3 4
3 1 3 4

Is the answer to this data equal to 32(17+15)?
or there is no answer?