Waterloo 2023 Fall A - Black Frame

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 256M

Problem type

When it's freezing outside, there isn't much to do in Waterloo. Luckily for you, you stumbled onto the "Black Square" painting by Kazimir Malevich. While that painting is literally just a black square, you were marveled by its simplicity and use of color. And that's how your weekend art project was born. You took some old jigsaw puzzle and painted every single puzzle piece black. As a result, you ended up with pieces of seven kinds, as shown in the picture below. You have varying quantities of each kind. By interlocking puzzle pieces, you connect them together. The "Black Square" was already painted and you're interested in making frames for it, which also must be completely black. Since you're also interested in combinatorics, the following question entered your mind.

You're interested in how many integers n \ge 3 exist such that you can make an n by n frame from the jigsaw puzzle pieces that you have (each puzzle piece is 1 by 1). You don't have to use every single puzzle piece that you have. You can rotate puzzle pieces but you are not allowed to flip them over (as the back texture is not the same as the front texture). An n by n square frame is a structure of size n by n whose n-2 by n-2 interior is completely empty. That means that you cannot have any puzzle parts sticking in or out, nor can you have any emptiness left in a puzzle piece. Lastly, each puzzle piece has to be connected to exactly two other puzzle pieces. This means that putting two flat sides together does not count as a valid connection.

Input Specification

The only line of input contains seven integers ranging from 0 to 10^9 (inclusive) - the quantities of each puzzle piece kind. The order of input corresponds to the order shown in the image (so the first integer is the count of the leftmost puzzle piece kind, and so on).

Output Specification

Output one number - how many valid values of n exist.

Sample Input 1

0 0 4 0 4 0 2

Sample Output 1


Sample Input 2

1 1 1 1 1 1 1

Sample Output 2


Sample Input 3

0 4 0 4 4 4 12

Sample Output 3



There are no comments at the moment.