Programming contests

ECN selejtező programozó csapatverseny, 2017. április 12.

April 12, 2017 10:00 AM – April 12, 2017 3:00 PM

Sonya Wants More Equal Numbers

Pussycat Sonya has an array A consisting of N integers. She can replace some adjacent elements Ai and Ai + 1 with their sum. Sonya can perform this operation any number of times she wants. What is the maximum number of equal elements Sonya can get, and what can be the possible values of these equal elements?

Input Specification

The first line of the input contains one integer N, the number of elements in array A (1 ≤ N ≤ 100). The second line contains N space-separated positive integers, the elements of array A (1 ≤ Ai ≤ 1000).

Output Specification

In the first line, print the maximum number of equal elements Sonya can get. In the second line, print all the possible values of these equal elements in ascending order, separated by a space.

Sample Input

  1. 6
  2. 11 5 6 2 8 10
download as text file

Output for Sample Input

  1. 2
  2. 8 10 11 16
download as text file

Sample Explanation

In this case, the maximum number of equal elements Sonya can get is 2. Now let's see the possible values of these equal elements:

  • This is how we can get an array with two 8s: {11, 5, 6, 2, 8, 10} → {11, 5, 8, 8, 10}.
  • This is how we can get an array with two 10s: {11, 5, 6, 2, 8, 10} → {11, 5, 6, 10, 10}.
  • This is how we can get an array with two 11s: {11, 5, 6, 2, 8, 10} → {11, 11, 2, 8, 10}.
  • This is how we can get an array with two 16s:
    {11, 5, 6, 2, 8, 10} → {11, 5, 8, 8, 10} → {11, 5, 16, 10} → {16, 16, 10}.
University of Debrecen; Faculty of Informatics; v. 05/24/2018