ZeroJudge B112: Sport Day

Every year, Dream City organizes a sports event for all high school students in the city. To promote interaction among students from different schools, a special team formation method is adopted: Students from each school must be evenly distributed among teams so that the number of students from each school in each team is the same. To increase the competitiveness of the competition, it is desirable to form as many teams as possible. Your task is to determine the maximum number of teams that can be formed based on the number of students from each school.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input is used, where the first line of input is a positive integer N between 1 and 500, representing the number of schools. This is followed by N lines, each containing a positive integer between 1 and 10000, representing the number of students in each of the N schools.The maximum number of teams that can be formed.
3
12
16
20
4
400
200
150
625		4
25

Thought Process

When receiving the data, first store the factors of the received numbers in a Map. Then, create a Vector data structure to store the factor Maps of each school.

Later, use auto to iterate through the for loop of the first school's Map, and compare it with the Maps of other schools to see if the same factors appear. If all schools have the same factors, set the answer to this factor, taking the maximum value.

Sample Code－ZeroJudge B112: Sport Day

#include <iostream>
#include <vector>
#include <math.h>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N)
    {
        vector<int>num;
        vector<map<int, int>>vMAP;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
            map<int, int>MAP;
            for (int j = 2; j<int(sqrt(tmp))+1; j++)
            {
                if (tmp % j == 0)
                {
                    MAP[j]++;
                    MAP[tmp/j]++;
                }
            }
            vMAP.push_back(MAP);
        }
        int ans = 1;
        for (auto it:vMAP[0])
        {
            int factor = it.first;
            bool ok = true;
            for (int i = 1; i<N; i++)
            {
                if (vMAP[i][factor] == 0)
                {
                    ok = false;
                    break;
                }
            }
            if (ok) ans = factor;
        }
        cout << ans << "\n";
    }
}

//ZeroJudge B112
//Dr. SeanXD
Tags

Related Posts

Comments