Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1366
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1366
Sticks Game
By Ricardo Anido 
Brazil
Timelimit: 1
There are a lot of fun games that use small colored sticks. The variable used in this problem involves building rectangles. The game consists in, given a set of sticks of variables sizes, draw rectangles on the floor, utilizing the sticks as the sides of the rectangle, with the condition that each stick can be used in only one rectangle, and each side of the rectangle has only one stick. In this game, two kids receive two equal sets of sticks. Wins the game the one who draw the greatest number of rectangles with the sticks.
Given a set of sticks of integer sizes, you must write a software to determinate the greatest number of rectangles that it's possible to draw.
Input
The input contains several test cases. The first line of a test case contains an integer N that indicates the number of different stick sizes (1 ≤ N ≤ 1.000) in the set. Each one of the N following lines contains two integers Ci and Vi, representing respectively a size (1 ≤ Ci ≤ 1.000) and the number of sticks with that size (1 ≤ Vi ≤ 1.000). Each stick size appears at most once in a test case (which means, the values of C1 are different). The end of the input is indicated by N = 0.
Output
For each test case your software must print only one output line, with an integer indicating the maximum number of rectangles that can be formed with the given set of sticks.
| Sample Input | Sample Output |
|
1 |
1 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int main() {
int i, N, T, Q;
while(1)
{
scanf("%d", &N);
if(N == 0) break;
else
{
int ACUM = 0;
for(i = 1; i <= N; i++)
{
scanf("%d %d", &T, &Q);
if(Q % 2 == 0) ACUM += Q;
else ACUM += Q - 1;
}
printf("%d\n", ACUM / 4>;
}
}
return 0;
}
Input
10 7
4
50 2
40 2
30 4
60 4
5
15 3
6 3
12 3
70 5
71 1
0
Output
3
2
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
for (cin >> n; n != 0; cin >> n) {
int tam, v, qtd = 0;
for (int i = 0; i < n; ++i) {
cin >> tam >> v;
if (v % 2 == 0)
qtd += v;
else
qtd += v - 1;
}
cout << qtd / 4 << "\n";
}
return 0;
}
Input
10 7
4
50 2
40 2
30 4
60 4
5
15 3
6 3
12 3
70 5
71 1
0
Output
3
2
#3 Code Example with Python Programming
Code -
Python Programming
while True:
n = int(input())
if not n: break
s = 0
for i in range(n):
s += [int(x) for x in input().split()][1] // 2
print(s//2)
Input
10 7
4
50 2
40 2
30 4
60 4
5
15 3
6 3
12 3
70 5
71 1
0
Output
3
2