ZeroJudge D577: Equivalent Head and Tail and Variations

The master specializes in instantly solving problems for a living.

One day, after instantly solving a problem related to the sum of the first and last elements, he had an idea.

If I randomly take N numbers from the front and add them together.

How many of those numbers would be the same?

And which number appears the most frequently?

He said this is beyond his IQ.

So he looked for someone who knew how to code to help him.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input: The first line contains two numbers, a and b (where a represents how many numbers there are, and b represents how many numbers to select) with the constraints 0 <= b <= a <= 20. The next line contains a numbers, each not exceeding 2147483647 (the numbers may not be sorted). The input ends when a = 0 and b = 0.Output two numbers c and d where c represents the number that appears the most frequently and d represents the number of ways to select it. If there are multiple values for c, output the smallest one.
10 2
1 2 3 4 5 6 7 8 9 10
5 3
1 2 3 4 5
0 0		11 5
8 2

Thought Process

You can use Depth-First Search (DFS) to accumulate b numbers. In the DFS function, you need to ensure that the current number being processed is after the last selected number. To achieve this, you can include a start variable as a parameter, initialized to 0, and start the loop from start. When calling the DFS function again, set the start parameter to i + 1.

Use a map to record the frequency of each sum, and use for (auto it : Map) to determine which sum appears the most. Finally, output the answer.

Sample Code－ZeroJudge D577: Equivalent Head and Tail and Variations

#include <iostream>
#include <map>
using namespace std;

int a, b;
int num[30] = {};
bool visited[30] = {};
map<int, int>MAP;

void DFS(const int count, const int add, const int start) {
    if (count == b) {
        MAP[add]++;
    }
    for (int i = start; i<a; i++) {
        if (!visited[i]) {
            visited[i] = true;
            DFS(count+1, add+num[i], i+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> a >> b && a != 0 && b != 0) {
        MAP.clear();
        for (int i = 0; i < a; i++) {
            cin >> num[i];
            visited[i] = false;
        }
        DFS(0, 0, 0);
        int max = -999, maxNum = 0;
        for (auto it:MAP) {
            if (it.second > max) {
                max = it.second;
                maxNum = it.first;
            }
        }
        cout << maxNum << " " << max << "\n";
    }
}

//ZeroJudge D577
//Dr. SeanXD
Tags

Related Posts

Comments