Problem 1

Problem Statement

You have some items. The weight of the i-th (0-based) item is item[i]. You want to put all items into backpacks.

The capacity of each backpack is 300. You can put an arbitrary number of items into a single backpack, but the total weight of items in a backpack must be less than or equal to 300.

You are given the int[] item. It is known that the weight of each item is between 101 and 300, inclusive. Return the minimal number of backpacks required to store all items.

Definition

Class: BackPacks Method: getMin

Parameters: Java: int[]; C++: vector<int> &; Python: list[int] Returns: int

Method signature: Java: int getMin(int[] item)

C++: int getMin(vector<int> & item) Python: def getMin(self, item)

′′′′′′

:type item: list[int]

:rtype: int

′′′′′′

(Your code will be tested by a testing program, so please ensure that you follow the above definition, i.e., the Class name and Method name are exactly the same as defined, and your method is public and returns proper value and type.)

Constraints

itme will contain between 1 and 15 elements, inclusive.
Each element of itme will be between 101 and 300, inclusive.

Examples

0. Input: 150, 150, 150, 150, 150

Output: 3

You have five items and each backpack can hold at most two of them. You need at least three backpacks.

1. Input: 130, 140, 150, 160

Output: 2

For example, you can distribute the items in the following way: Backpack 1: 130, 150

Backpack 2: 140, 160

2. Input: 101, 101, 101, 101, 101, 101, 101, 101, 101

Output: 5

3. Input: 101, 200, 101, 101, 101, 101, 200, 101, 200

Output: 6

4. Input: 123, 145, 167, 213, 245, 267, 289, 132, 154, 176, 198

Output: 8

Problem 2

Problem Statement

You have a 50 times 50 chessboard. Both rows and columns of the chessboard are numbered from 0 to 49, inclusive.

A super attacker is a chess piece that attacks all cells that are in the same row, in the same column, or on the same diagonal. In this problem we will be using at most sixteen super attackers. Some super attackers are already placed on the board. You are given their coordinates in the int[]s row and col. More precisely, for each valid i there is a super attacker on the cell (row[i],

col[i]). These super attackers are placed in such a way that no two of them attack each other.

You want to place add additional super attackers onto the chessboard in such a way that in the final configuration no two super attackers will attack each other. Find any one valid solution.

Return a int[] with the coordinates of the added super attackers. More precisely, if you want to place super attackers onto the cells (r0, c0), (r1, c1), and so on, return the int[] { r0, c0, r1, c1, … }.

Definition

Class: SuperAttackers Method: addAttackers

Parameters: Java: int[], int[], int;

C++: vector<int> &, vector<int> &, int; Python: list[int], list[int], int

Returns: Java: int[]; C++: vector<int>; Python: list[int]

Method signature: Java: int[] addAttackers(int[] row, int[] col, int add)

C++: vector<int> addAttackers(vector<int> & row, vector<int> & col,

int add)

Python: def addAttackers(self, row, col, add)

′′′′′′

:type row: list[int]

:type col: list[int]

:type add: int

:rtype: list[int]

′′′′′′

Notes

For the given constraints a solution always exists. Any valid solution will be accepted.

Constraints

row will have between 0 and 16 elements, inclusive.
Each element of row will be between 0 and 49, inclusive.
col will have the same number of elements as row.

Each element of col will be between 0 and 49, inclusive.
The super attackers described by row and col stand on distinct cells and they do not attack each other.
add will be between 0 and 16, inclusive.
The number of elements in row plus the value of add will be at most 16.

Examples

Input:

{3}

{5}

Example output: 0, 0

There is a super attacker at (3,5). We are asked to add one more super attacker. In the example output shown above we place it at (0,0).

Input:

{0}

{1}

Example output: 4, 7

There is a super attacker at (0,1). This time we cannot place the second super attacker at (0,0) because the two super attackers would attack each other.

Input:

{0}

{1}

Example output: 4, 7, 15, 0, 49, 49 Adding three super attackers.

Input:

{14, 19}

{3, 47}

Example output:

The easiest inputs are those where you don’t have to add any new super attackers.

Input:

{ }

Example output: 0, 0, 1, 2

There can be zero super attackers on the board before you start adding the new ones.

Input:

{1, 2, 3}

{7, 2, 19}

Example output: 0, 1

There are three super attackers already on the board: at (1,7), (2,2), and (3,19). Our solution proposes to put the fourth super attacker onto the cell (0,1). There are many other valid solutions, and any of those will be accepted as well.