Apparently, this is a very complicated problem,
but 1115 allows solutions with naive implementations.
I almost used brute force here, with some little optimizations (like looking for solutions for the next few sums while working on the 'current' one).

6 2
2 10 11 16 16 21
32
33

I wrote program on Python 3, but second test is wrong for me. Why? I need a hint. Maybe, you can wrote test for my program?

Idea:
1. sort length descending
2. take first that smaller SUM in row
3. reduce SUM and colored ship
4. take next
5. finally for SUM if they == 0 -> go to next row


My solution:

[n, m] = [ int(x) for x in input().split() ]
a = []
for i in range(n):
    a.append(int(input()))
b = []
for i in range(m):
    b.append(int(input()))
a.sort(reverse=True)
color = [-1 for x in range(n)]

i = 0
while i < m:
    s = b[i]
    z = 0
    while z < n:
        aa = []
        j = z
        while s > 0:
            while j < n and a[j] > s :
                j += 1
            if j >= n:
                for ee in aa:
                    s += a[ee]
                    color[ee] = -1
                aa = []
                break
            elif color[j] != -1:
                j += 1
            else:
                s = s - a[j]
                aa.append(j)
                color[j] = i
        z += 1
        if s == 0:
            break
    i += 1
for i in range(m):
    aa = []
    cnt = 0
    for j in range(n):
        if color[j] == i:
            aa.append(a[j])
            cnt += 1
    print(cnt)
    aa.sort(reverse=True)
    ab = [str(x) for x in aa]
    ss = " ".join(ab)
    print(ss)

any good test case, thanks

help.
send please the test 1 for mail antonluzhbin@yandex.ru

Is there only one solution for test??

but i still can't pass test 10
what's in it?

Is it really appropriate to translate 'целые числа' as 'whole numbers'?

I write it here because there exist data sets which will TL it out.

1. Sort rows ascendingly
2. Sort ships descendingly
3. Recurse row-by-row, ship-by-ship
4. Keep ships in the linked list, so you don't have to skip them over and over once they are taken.
5. For each row try only next ships (1+2+3 is same as 1+3+2).
6. Once you reach the last row, don't recurse over it, just pick remaining ships.

This yields AC in 0.015 sec

More optimizations can be done:
1. For each row store index of the first ship which fits in it
(don't forget to skip this ship(s) if it's already taken by the time you reach the row)
2. Store amounts of same-size ships, so that 2+2 is processed only once with 6 ships of size 2, but not C(2,6) times.

Edited by author 30.07.2008 14:41

I used knapsack to find all the ways in order to fill a row and solved the problem for other rows with remained ships.

I have some questions about the problem's statement:
1. Is the sum of lengths of the ships equal to the sum of the lengths of the rows?
2. What is the maximum length of a single row?
3. Should I output the lengths in each row in ascending order or in any order I like?

I've got WA1 :rolleyes:
My program gives this output on the sample test:
3
5 2 4
2
3 10

My algorithm is follow.
1.I'm starting to put ships to the most short row ( ships are sorted from shortest to longest and I'm considering them in this order ).
2.I'm trying to put ships with maximum total length as it is possible. So, recoursive searching ( from longest free ships to shortest ) take place.
3.If all ships are already used and there are still free row(s), I put at this row(s) some ship(s) from other row(s) which have already more then one ship.

Please, give me some test data or tell me why does such algorithm return WA.

Edited by author 01.06.2006 19:20

Hope to be Rejudged soon!!!!!!!!!!!

  var
    n, m : longint;
    f : boolean;
    done : array[1..100] of boolean;
    put : array[1..100, 0..100] of longint;
    board : array[1..100] of longint;
        row, order : array[0..10] of longint;

  procedure sort;
    var
    i, j, x, y : longint;
    begin
      for i := 1 to n - 1 do
        for j := i + 1 to n do
          if board[i] < board[j]
            then begin
          x := board[i];
          board[i] := board[j];
          board[j] := x;
        end;
      for i := 1 to m - 1 do
        for j := i + 1 to m do
          if row[i] < row[j]
            then begin
          x := row[i];
          row[i] := row[j];
          row[j] := x;
          x := order[i];
          order[i] := order[j];
          order[j] := x;
        end;
    end;

  procedure init;
    var
    i, j, x : longint;
    begin
      readln(n, m);
      f := false;
          fillchar(put, sizeof(put), 0);
      fillchar(done, sizeof(done), false);
      for i := 1 to n do
        begin
              readln(board[i]);
            end;
      row[0] := 0;
      for i := 1 to m do
            begin
          readln(row[i]);
              order[i] := i;
        end;
    end;

  procedure print;
    var
    i, j, l : longint;
    begin
      for i := 1 to m do
        begin
          writeln(put[i, 0]);
          for j := 1 to put[i, 0] do
            write(put[i, j], ' ');
          writeln;
        end;
      halt;
    end;

  procedure make(k : longint);
    var
    i : longint;
    begin
      if f then exit;
      if (k = m + 1)
        then begin
          print;
          f := true;
          exit;
        end;
      for i := 1 to n do
        if (not done[i]) and (board[i] <= row[k])
          then begin
        done[i] := true;
                dec(row[k], board[i]);
                inc(put[order[k], 0]);
        put[order[k], put[order[k], 0]] := board[i];
        make(k + ord(row[k] = 0));
        if f then exit;
        dec(put[order[k], 0]);
                inc(row[k], board[i]);
        done[i] := false;
          end;
    end;

  begin
           init;
    sort;
    make(1);
  end.

I know you all submit heuristics and get AC. In fact, tests are very easy to pass. I can change it.

I have new tests. These tests are really good. I think nobody's current solution get AC with these tests. But I have a solution and can't create a test that break it.

Do you want me to add this tests?

Edited by author 10.07.2005 23:49

Edited by author 10.07.2005 23:50

850784 15:24:03
20 May 2005 Fu Dong 1115 Pascal Accepted
 0.001 141 KB

I think the most important thing to this problem is to sort ships' length.

First I sorted them from short to long, but I got TLE on test #8, then I sorted from long to short, to my surprise, I got AC with 0.001s!

this algo got TL
choose the row for each ships
ship 1  try [1,...,m]
ship 2  try [1,...,m]
...
ship n  try [1,...,m]

you could get TLE even you've bounded it (sorting)


another algo ,which is AC
fill the row until full
row 1  try 2^n
row 2  try 2^(n-1)
...
row m  try 2^(n-(m-1))

2^n looks bad but it works!

[code cut out]

Edited by moderator 08.08.2004 03:46