#907. ESCAPE - Chạy trốn

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Những con bò vừa có một quyết định táo bạo để thoát khỏi nanh vuốt của nông dân John (FJ). Chúng thu xếp để có được một cái bè nhỏ không phẳng và với sự che chở của bóng đêm, một số con bò sẽ lên bè chèo dọc theo con sông tiếp giáp với đồng cỏ. Kế hoạch trông rất hoàn hảo cho tới khi những con bò nhận ra rằng chiếc bè không phẳng không thể chở được quá nhiều cân.

Cả đàn có N con bò có trọng lượng là w_1, w_2, \ldots, w_N . Để tìm ra một nhóm những con bò đủ nhẹ để tránh vụ chìm bè những con bò lấy tổng các trọng lượng của chúng. Thật không may, bò vốn nổi tiếng về kém số học, cho nên nếu một lần thêm trọng lượng của một con bò gây ra một phép cộng có nhớ (trong cơ số 10 ) đàn bò sẽ bỏ cuộc và kết luận là nhóm của chúng quá nặng để có thể đi trên bè (:D).

Hãy giúp các con bò tính toán nhóm nhiều bò nhất mà đàn bò tin tưởng có thể chở được trên cái bè (tức là nhóm nhiều bò nhất mà khi trọng lượng của nó được thêm vào tổng thì không có sự cố xảy ra - không phát sinh nhớ).

Dữ liệu:

  • Dòng đầu tiên ghi số lượng các con bò N\ (1≤N≤20) ;
  • N dòng tiếp theo, mỗi dòng ghi trọng lượng của một con bò là một số nguyên dương không vượt quá 10^8 .

Kết quả:

  • Ghi ra số lượng lớn nhất các con bò mà trọng lượng của chúng khi thêm vào không phát sinh phép cộng có nhớ.

Ví dụ:

Dữ liệu:

5
522
6
84
7311
19

Kết quả:

3

Giải thích:

  • Chọn 3 con có trọng lượng là 522, 6, 7311 ).