Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1407
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1407
Weekend Lottery
BrazilTimelimit: 1
Some people are against lotteries on moral grounds, some governments forbid lotteries, but with the advent of Internet this popular form of gambling, which started in China and helped finance the Great Wall, is thriving.
But the odds of winning a national lottery are tiny, and therefore your college classmates decided to organize a private lottery, with draws every Friday. The lottery is based on a popular style: a student who wants to bet chooses C distinct numbers from 1 to K and pays US$ 1.00 (notice that traditional lotteries such as US$ National Lotto use C = 6 and K = 49). On Friday during lunch C numbers (also from 1 to K) are drawn. The student whose bet has the largest number of correct guesses receives the amount collected in the bets. This amount is shared in case of ties and accumulates to next week if no one guessed any of the numbers drawn.
Some of your colleagues do not believe in the laws of probability and asked you to write a program that determines the numbers that have been drawn the fewest times considering all previous draws, so that they can bet on those numbers.
Input
The input contains several test cases. The first line of a test case contains three integers N, C and K which indicate respectively the number of draws that have already happened (1 ≤ N ≤ 10000), how many numbers comprises a bet (1 ≤ C ≤ 10) and the maximum value of the numbers to be chosen in a bet (C < K ≤ 100). Each of the next N lines contains C distinct integers Xi indicating the numbers drawn in each previous contest (1 ≤ Xi ≤ K, for 1 ≤ i ≤ C). The end of input is indicated by N = C = K = 0.
Output
For each test case in the input your program must write one line of output, containing the set of numbers that have been drawn the fewest times. This set must be printed as a list, in increasing order of numbers. Leave one blank space between two consecutive numbers in the list.
| Sample Input | Sample Output |
|
5 4 6 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <iostream>
#include <queue>
#define mp make_pair
using namespace std;
int loteria[110];
int n, c, k, p, MAX;
typedef pair < int, int> ii;
int main()
{
ios::sync_with_stdio(false);
bool flag = false;
while (cin >> n >> c >> k && n + c + k) {
if (flag)
for (int i = 0; i < k; ++i)
loteria[i] = 0;
priority_queue < ii> pq;
for (int i = 0; i < n; ++i)
for (int j = 0; j < c; ++j) {
cin >> p;
loteria[p - 1]++;
}
for (int i = 0; i < k; ++i)
pq.push(mp(-(loteria[i]), -(i + 1)));
MAX = -pq.top().first;
int cont = 0;
while (-pq.top().first == MAX && !pq.empty()) {
if (cont == 0)
cout << -pq.top().second;
else
cout << " " << -pq.top().second;
pq.pop();
cont++;
}
cout << "\n";
flag = true;
}
return 0;
}
Input
6 2 3 4
3 4 6 5
2 3 6 5
4 5 2 6
2 3 6 4
4 3 4
3 2 1
2 1 4
4 3 2
1 4 3
0 0 0
Output
1 2 3 4