Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1318
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1318
Fake Tickets
ACM/ICPC South America Contest, Warm-Up 
Brasil
Timelimit: 1
Your school organized a big party to celebrate your team brilliant win in the prestigious, world-famous ICPC (International Collegiate Poetry Contest). Everyone in your school was invited for an evening which included cocktail, dinner and a session where your team work was read to the audience. The evening was a success – many more people than you expected shoed interested in your poetry – although some critics of yours said it was food rather than words that attracket such an audience.
Whatever the reason, the next day you found out why the school hall had seemed so full: the school director confided he had discovered that several of the tickets used by the guests were fake. The real tickets were numbered sequentially from 1 to N (N ≤ 10000). The director suspects some people had used the school scanner and printer from the Computer Room to produce copies of the real tickets. The director gave you a pack with all tickets collected from the guests at the party’s entrance, and asked you to determine how many tickets in the pack had “clones”, that is, another ticket with the same sequence number.
Input
The input contains data for several test cases. Each test case has two lines. The first line contains two integers N and M which indicate respectively the number of original tickets and the number of persons attending the party (1 ≤ N ≤ 10000 and 1 ≤ M ≤ 20000). The second line of a test case contains M integers Ti, representing the ticket numbers in the pack the director gave you (1 ≤ Ti ≤ N). the end of input is indicated by (N = M = 0).
Output
For each test case your program should print one line, containing the number of tickets in the pack that had another ticket with the same sequence number.
| Sample Input | Sample Output |
|
5 5 |
1 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
int main (void)
{
unsigned short contador = 0, i, j, k;
unsigned short numBilhtes, numPessoas;
while (1)
{
scanf("%hu %hu", &numBilhtes, &numPessoas);
if (numBilhtes == 0 && numPessoas == 0)
break;
short codBilhete[numPessoas], codBilheteCpy[numPessoas];
for (i = 0; i < numPessoas; i++)
scanf("%hd", &codBilhete[i]);
//Cria uma cópia do vetor codBilhete para fazer modificações futuras;
for (i = 0; i < numPessoas; i++)
codBilheteCpy[i] = codBilhete[i];
//Percorre o vetor codBilhete;
for (i = 0; i < numPessoas; i++)
{
for (j = 0; j < numPessoas; j++)
{
//É preciso que a posição do codBilhete seja diferente do codBilheteCpy
//Para não contar repetições;
if (i != j)
if (codBilhete[i] == codBilheteCpy[j])
{
contador++;
codBilheteCpy[j] = 0;
//Se pelo menos um valor igual for constatado
//É preciso escrever 0 em todas as posições que têm o mesmo valor
//Para não contar na próxima iteração;
for (k = j; k < numPessoas; k++)
if (codBilhete[i] == codBilheteCpy[k])
codBilheteCpy[k] = 0;
//Para o laço for 'j' logo em seguida;
break;
}
//Por fim, escreve 0 na posição que estava sendo avaliada com i;
codBilheteCpy[i] = 0;
}
}
printf("%hu\n", contador);
contador = 0;
}
}
Input
3 3 1 2 4
6 10
6 1 3 6 6 4 2 3 1 2
0 0
Output
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ,k;
while(cin >> n >> k && n !=0 && k != 0){
int ticket[100000] = {0};
for(int i = 0; i < k ; ++i){
int a; cin >> a;
ticket[a]++;
}
int count = 0;
for(int i = 1 ;i < = n;++i)
{
if(ticket[i] > 1) count++;
}
cout << count << endl;
}
return 0;
}
Input
3 3 1 2 4
6 10
6 1 3 6 6 4 2 3 1 2
0 0
Output
4
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", { encoding: "utf8" })
.split("\n")
.map((line) => line.split(" ").map(Number))
/**
* @param {any[]} list
* @returns {{ [n: string]: number }}
*/
function getFrequenciesOnQueue(list) {
return list.reduce((frequencies, key) => ((frequencies[`${key}`] = ++frequencies[`${key}`] || 1), frequencies), {})
}
function main() {
const responses = []
for (let index = 0; index < input.length; index += 2) {
const [N, M] = input[index]
if (N == 0 && M == 0) break
const tickets = input[index + 1].slice(0, M)
const fakeTicketsQuant = Object
.entries(getFrequenciesOnQueue(tickets))
.reduce((sum, [key, frequency]) => (frequency > 1 || Number.parseInt(key, 10) > N) ? sum + 1 : sum, 0)
responses.push(fakeTicketsQuant)
}
console.log(responses.join("\n"))
}
main()
Input
3 3 1 2 4
6 10
6 1 3 6 6 4 2 3 1 2
0 0
Output
4
#4 Code Example with Python Programming
Code -
Python Programming
while True:
e = [int(x) for x in str(input()).split()]
n = e[0]
m = e[1]
if n == m == 0: break
e = str(input()).split()
r = 0
for i in range(1, n + 1):
q = e.count(str(i))
if q > 1: r += 1
print(r)
Input
3 3 1 2 4
6 10
6 1 3 6 6 4 2 3 1 2
0 0
Output
4