Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1245
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1245
Lost Boots
Maratona de Programação da SBC 
Brazil
Timelimit: 1
The Boots and Shoes supplies division of the Army purchased a large number of pairs of boots of various sizes for his soldiers. However, a failure of the packaging factory contracted, not all supplied boxes containing a pair of boots correct, with two boots of the same size, one for each foot. The sergeant told the recruits withdraw all boots all the boxes to repack them, this time correctly.
When the sergeant discovered that you knew programming, he asked with the usual kindness you write a program that, given a list containing the description of each boot delivered, determines how many pairs of boots could be formed in total.
Input
The input consists of several test cases. The first line of a test case contains an integer N (2 ≤ N ≤ 104), N is even, indicating the number of individual boots delivered. Each of the N rows following describes a boot, containing an integer number M (30 ≤ M ≤ 60) and a letter L, separated by a blank space. M indicates the number of the boot and L indicates the size of the boot: L = 'D' indicates that the boot is to the right foot, L = 'E' indicates that the boot is for the left foot.
Output
For each test case print one line containing a single integer indicating the total number of pairs that can be formed correct.
| Sample Input | Sample Output |
|
4 |
2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
typedef struct{
unsigned short ladoDireito;
unsigned short ladoEsquerdo;
}bota;
unsigned short min(unsigned short, unsigned short);
int main (void)
{
unsigned short casos, i;
unsigned short numBota, qtsPares;
bota botas[70];
char ladoBota;
while (scanf("%hu", &casos) != EOF)
{
i = 0;
memset(botas, 0, sizeof(botas));
while (casos--)
{
scanf("%hu", &numBota);
scanf(" %c", &ladoBota);
if (ladoBota == 'D')
botas[numBota].ladoDireito++;
else
botas[numBota].ladoEsquerdo++;
}
qtsPares = 0;
for (i = 30; i < 70; i++)
qtsPares += min(botas[i].ladoDireito, botas[i].ladoEsquerdo);
printf("%hu\n", qtsPares);
}
}
unsigned short min(unsigned short ladoDireito, unsigned short ladoEsquerdo)
{
if (ladoEsquerdo < ladoDireito)
return ladoEsquerdo;
else
return ladoDireito;
}
Input
40 D
41 E
41 D
40 E
6
38 E
38 E
40 D
38 D
40 D
37 E
Output
1
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<iostream>
#include<cstring>
using namespace std;
int T[100][2];
int main() {
int N;
while(cin >> N) {
memset(T, 0, sizeof T);
for(int i = 0; i < N; i++) {
int size; char c;
cin >> size >> c;
T[size][c=='D']++;
}
int total = 0;
for(int i = 0; i < 100; i++) {
total += min(T[i][0], T[i][1]);
}
cout << total << endl;
}
}
Input
40 D
41 E
41 D
40 E
6
38 E
38 E
40 D
38 D
40 D
37 E
Output
1
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.Locale;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sc.useLocale(Locale.ENGLISH);
Locale.setDefault(new Locale("en", "US"));
while(sc.hasNext()){
int max=61;
int D[] = new int[max];
int E[] = new int[max];
int N = sc.nextInt();
int cont = 0;
if(N>=2 && N<=10000 && N%2==0){
for (int i=0 ; i < N ; i++){
int M = sc.nextInt();
char L = sc.next().charAt(0);
if (L == 'D'>{
D[M]++;
if (E[M]>0){
E[M]--;
D[M]--;
cont++;
}
}
else{
E[M]++;
if (D[M]>0){
D[M]--;
E[M]--;
cont++;
}
}
}
System.out.println(cont);
}
}
sc.close();
}
}
Input
40 D
41 E
41 D
40 E
6
38 E
38 E
40 D
38 D
40 D
37 E
Output
1
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { createReadStream } = require("node:fs")
const { createInterface } = require("node:readline")
//// READING FILE | STREAMS ////
class LineReader {
/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
* @return {import("node:readline").ReadLine}
*/
static createReadLineInterface(path, encoding = "utf8") {
const readStreamOptions = {
encoding: encoding,
flags: "r",
emitClose: true,
autoClose: true
}
return createInterface({
input: createReadStream(path, readStreamOptions),
crlfDelay: Infinity,
terminal: false
})
}
/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
*/
static create(path, encoding) {
const RLI = LineReader.createReadLineInterface(path, encoding)
let EOF = false
const nextLineGenerator = (async function* () {
for await (const line of RLI)
yield line
})()
RLI.once("close", () => { EOF = true })
return {
hasNextLine: () => !EOF,
nextLine: async (/** @type {unknown} */ fn) => {
const { value } = (await nextLineGenerator.next())
return (typeof fn === "function") ? fn(value) : value
},
close: () => RLI.close()
}
}
}
//// MAIN ////
async function main() {
const PATH = "/dev/stdin"
const ENCODING = "utf8"
const output = []
const lineReader = LineReader.create(PATH, ENCODING)
while (lineReader.hasNextLine()) {
const store = new Map()
const N = Number.parseInt(await lineReader.nextLine(), 10)
if (Number.isNaN(N)) break // EOF Condition
for (let i = 0; i < N; i++) {
const [M, L] = (await lineReader.nextLine()).split(" ", 2)
if (!store.has(M)) store.set(M, { D: 0, E: 0 })
switch (L) {
case "D": store.get(M)["D"]++; break
case "E": store.get(M)["E"]++; break
}
}
let correctPairsShoesQuantity = 0
store.forEach(({ D, E }) => correctPairsShoesQuantity += Math.min(D, E))
output.push(correctPairsShoesQuantity)
}
if (lineReader.hasNextLine())
lineReader.close()
console.log(output.join("\n"))
}
main()
Input
40 D
41 E
41 D
40 E
6
38 E
38 E
40 D
38 D
40 D
37 E
Output
1
#5 Code Example with Python Programming
Code -
Python Programming
while True:
try:
n = int(input())
v = []
q = 0
for i in range(n):
t = []
p = []
e = str(input()).split()
t.append(int(e[0]))
p.append(int(e[0]))
t.append(e[1])
if e[1] == 'E': p.append('D')
else: p.append('E')
if p in v:
v.remove(p)
q += 1
else: v.append(t)
print(q)
except EOFError: break
Input
40 D
41 E
41 D
40 E
6
38 E
38 E
40 D
38 D
40 D
37 E
Output
1