you can only use dfs , but don't forget to sort the team . When I
use sorting as from short to long , I got TL , but when from long to
short , only 0.02s !

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

//Please, don't post your codes here.
#include <stdio.h>
#include <string.h>
#define infile "1115.in"
#define outfile "1115.out"

int main()
{
  init();
  work();
  print();
  return 0;
}

Edited by moderator 16.04.2004 18:16

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!

Edited by author 10.07.2005 23:49

Edited by author 10.07.2005 23:50

  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.

Yes, I passed it just by searching. But firstly I sorted the ships
from short to long, then it was easy to cut the useless branch and
retrace when necessary.

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

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?

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