COCI '22 Contest 3 #1 Estimathon

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Paula and Domagoj are organizing an exciting team competition called Estimathon. They have already prepared the questions, and now they are arranging the room for the quiz.

Before you could blink, Domagoj had already placed n tables in the room. Now they need to add chairs. They have very colourful chairs. They come in m colours, and there are a_i chairs of the i-th colour. Every team consists of four people. Therefore, for each table, Paula and Domagoj need to add four chairs. They want to make the room look as nice as possible. To make that happen, they agreed on these conditions:

  • Each table has all chairs of the same colour
  • Every chair colour is used; that is, for every colour, there exists at least one table that has chairs of that colour

Caring too much about how nice the room will look, they suddenly realized that the quiz would start very soon! Help them find out if a chair arrangement with these conditions is even possible.

Input Specification

The first line contains integers n and m (1 \le n, m \le 100), the number of tables and the number of chair colours.

The second line contains m integers a_i (1 \le a_i \le 100), where the i-th number is the number of chairs of the i-th colour.

Output Specification

In the first and only line, output DA if it is possible to arrange the chairs so that both conditions hold; otherwise, output NE.


Subtask Points Constraints
1 11 a_1 = \dots = a_m = 4
2 39 No additional constraints.

Sample Input 1

7 3
5 21 9

Sample Output 1


Sample Input 2

5 4
8 5 10 3

Sample Output 2


Explanation for Sample 2

We can have 5 tables with chairs of the same colour, but we cannot have a table with colour 4, so the second condition can't be satisfied.

Sample Input 3

6 5
5 5 5 5 5

Sample Output 3



There are no comments at the moment.