Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1495
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1495
Football
ArgentinaTimelimit: 2
Your favorite football team is playing a charity tournament, which is part of a worldwide fundraising effort to help children with disabilities. As in a normal tournament, three points are awarded to the team winning a match, with no points to the losing team. If the game is drawn, each team receives one point.
Your team played N matches during the first phase of the tournament, which has just finished. Only some teams, the ones with more accumulated points, will advance to the second phase of the tournament. However, as the main objective of the tournament is to raise money, before the set of teams that will pass to the second phase is determined, each team is allowed to buy additional goals. These new goals count as normally scored goals, and may be used to alter the result of any of the matches the team played.
Your team’s budget is enough to buy up to G goals. Can you tell the maximum total number of points your team can get after buying the goals, supposing the other teams will not buy any goals?
Input
The input consists of many test cases and ends with EOF. The first line of each test case contains two integers N (1 ≤ N ≤ 105) and G (0 ≤ G ≤ 106) representing respectively the number of matches your team played and the number of goals your team can buy. Each of the next N lines describes a match result with two integers S and R (0 ≤ S, R, ≤ 100), indicating respectively the goals your team scored and received on that match before buying goals.
Output
For each test case, print a line with an integer representing the maximum total number of points your team can get after buying the goals.
| Sample Input | Sample Output |
|
2 1 |
4 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
#define MAXSIZE 100100
int diffn[MAXSIZE];
void print_d(int n);
char scanff(int *);
int compare(int *, int *);
int main(int argc, char **argv)
{
int n, g, i;
int s, r, x, k;
while (~scanf("%d %d%*c", &n, &g))
{
int ans = 0;
for (i = k = 0; i < n; ++i)
{
scanff(&s);
scanff(&r);
x = s - r;
if (x == 0)
{
if (g > 0)
ans += 3, --g;
else
++ans;
}
else if (x < 0)
diffn[k++] = x;
else
ans += 3;
}
qsort(diffn, k, sizeof(int), compare);
i = 0;
while (g > 0 && i < k)
{
if (g - (-(diffn[i] - 1)) >= 0)
g -= (-(diffn[i] - 1)), ans += 3;
else if (g - (-(diffn[i] - 1)) < 0)
if (diffn[i] + g == 0)
++ans, g = -1;
++i;
}
print_d(ans);
putchar_unlocked('\n');
}
return 0;
}
int compare(int *a, int *b)
{
return *b - *a;
}
inline char scanff(int *a)
{
register char c = 0;
*a = 0;
c = getchar_unlocked();
while (c >= 48)
*a = *a * 10 + (c - '0'), c = getchar_unlocked();
return c;
}
inline void print_d(int n)
{
int i = 10;
char output_buffer[10];
do{
output_buffer[--i] = (n % 10) + '0';
n /= 10;
}while(n);
do
{
putchar_unlocked(output_buffer[i]);
}while(++i < 10);
}
Input
1 1
1 1
3 2
1 3
3 1
2 2
4 10
1 1
2 2
1 3
0 4
Output
6
12
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
int main() {
int n, g;
while (scanf("%d %d", &n, &g) != EOF) {
priority_queue < int, vector<int>, greater < int> > gols;
int empates = 0, vitorias = 0;
while (n--) {
int a, b;
scanf("%d %d", &a, &b);
if (a == b)
empates++;
else if (a > b)
vitorias++;
else
gols.push(b - a);
}
int compra_empates = min(empates, g);
empates -= compra_empates;
vitorias += compra_empates;
g -= compra_empates;
while (g > 0 && !gols.empty()) {
int davez = gols.top();
gols.pop();
if (g >= davez + 1) {
g -= davez + 1;
vitorias++;
} else if (g == davez) {
empates++;
g -= davez;
}
}
printf("%d\n", empates + (3 * vitorias));
}
return 0;
}
Input
1 1
1 1
3 2
1 3
3 1
2 2
4 10
1 1
2 2
1 3
0 4
Output
6
12
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws IOException {
String l;
String[] P;
int[] goals;
int N, G, w;
long points;
boolean f;
while ((l = read()) != null) {
points = 0;
P = l.split("\\s");
N = toInt(P[0]);
G = toInt(P[1]);
Integer[] matches = new Integer[N];
for (int i = 0; i < N; i++) {
goals = readArray();
matches[i] = goals[0] - goals[1];
}
Arrays.sort(matches, new Comparator < Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
f = true;
for (Integer match : matches) {
w = match.compareTo(0);
switch (w) {
case 1:
points += 3;
break;
case 0:
if (G > 0) {
G--;
points += 3;
} else {
points++;
}
break;
case -1:
if (G + match - 1 >= 0) {
G += match - 1;
points += 3;
} else {
if(G + match == 0){
points++;
}
f = false;
break;
}
break;
}
if(!f){
break;
}
}
out.println(points);
}
out.close();
}
private static String read() throws IOException {
return in.readLine();
}
private static int toInt(String s) {
return Integer.parseInt(s);
}
private static int[] readArray() throws IOException {
String[] line = in.readLine().split("\\s");
int l = line.length;
int[] a = new int[l];
for (int i = 0; i < l; i++) {
a[i] = Integer.parseInt(line[i]>;
}
return a;
}
}
Input
1 1
1 1
3 2
1 3
3 1
2 2
4 10
1 1
2 2
1 3
0 4
Output
6
12