Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1321
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1321
Jollo
By Ricardo Anido 
Brazil
Timelimit: 1
Jollo is a simple card game which the children from Logonia love to play. It is played between two players with a normal deck of 52 cards. In the game, cards are ordered according to their rank and suit, forming a sequence of 52 distinct values.
The game is composed of three rounds, played in a best-of-three series (a player must win two rounds to win the game). At the beginning of the game the deck is shuffled and each player is given a hand of three cards. In each round the players show one card to each other and the player with the highest card wins the round. The cards shown in a round are discarded (i.e., they cannot be shown again).
The King's son loves to play the game. But he is not very smart, losing frequently to his little sister. And when he loses, he cries so loud no one can stand it. The servant who deals the cards to the Prince and his sister is afraid he will be sent to prison if the Prince continues to lose. The servant is allowed to see every card he deals, and after dealing five cards (three to the Princess and two to the Prince) he wants to know which is the lowest card he should deal to the Prince so that there is no chance he will lose the game, no matter how badly he plays.
Input
Each test case is given in a single line that contains five distinct integers A, B, C, X and Y, describing the cards dealt to the players. The first three cards are given to the Princess (1 ≤ A,B,C ≤ 52) and the last two cards are given to the Prince (1 ≤ X,Y ≤ 52).
The last test case is followed by a line containing five zeros.
Output
For each test case output a single line. If there exists a card that will make the Prince win the game no matter how badly he plays, you must print the lowest such a card. Otherwise, print -1.
| Sample Input | Sample Output |
|
28 51 29 50 52 |
30 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool cn[3];
int w[2][3];
bool solve(int, int);
int main(int argc, char **argv)
{
while (scanf("%d %d %d %d %d", &w[0][0], &w[0][1], &w[0][2], &w[1][0], &w[1][1]), w[0][0])
{
bool ps;
size_t i = 0;
for (i = 1; i < = 52; ++i)
{
ps = true;
for (size_t k = 0; k < 3; ++k)
if (w[0][k] == i)
ps = false;
for (size_t k = 0; k < 2; ++k)
if (w[1][k] == i)
ps = false;
if (!ps)
continue;
w[1][2] = i;
memset(cn, 0, sizeof(cn));
if (solve(0, 0))
break;
}
if (i == 53)
puts("-1");
else
printf("%ld\n", i);
}
return 0;
}
bool solve(int idx, int c)
{
if (idx == 3)
return c >= 2;
for (size_t i = 0; i < 3; ++i)
{
if (cn[i])
continue;
cn[i] = true;
if (!solve(idx + 1, c + (w[1][idx] > w[0][i] ? 1 : 0)))
return false;
cn[i] = false;
}
return true;
}
Input
50 26 19 10 27
10 20 30 24 26
46 48 49 47 50
0 0 0 0 0
Output
-1
21
51
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <string.h> // memset
#include <stdlib.h> // qsort
int compare(const void * x, const void * y)
{
return (*(int*)x - *(int*)y);
}
int main()
{
int A, B, C, X, Y;
while(1)
{
int cartas[52];
// inicializa as cartas com 0 (não utilizadas)
memset(cartas, 0, sizeof(cartas));
// obtém as entradas
scanf("%d %d %d %d %d", &A, &B, &C, &X, &Y);
if(A == 0)
break;
// marca as cartas utilizadas
cartas[A - 1] = 1;
cartas[B - 1] = 1;
cartas[C - 1] = 1;
cartas[X - 1] = 1;
cartas[Y - 1] = 1;
int cartas_princesa[] = {A, B, C};
// ordena as cartas da princesa em ordem crescente
qsort(cartas_princesa, 3, sizeof(int), compare);
int resp = -1;
// testa todas as cartas (menor carta possível)
for(int carta = 1; carta <= 52; carta++)
{
if(cartas[carta - 1] == 0)
{
int rounds_princesa = 0, rounds_principe = 0;
int cartas_principe[] = {X, Y, carta};
qsort(cartas_principe, 3, sizeof(int), compare>;
// primeiro round
// menor da princesa com maior do príncipe
// isso serve para eliminar a maior carta do príncipe
if(cartas_princesa[0] > cartas_principe[2])
rounds_princesa++;
else
rounds_principe++;
// segundo round
// a princesa joga com a maior e o principe com o segundo maior
if(cartas_princesa[2] > cartas_principe[1])
rounds_princesa++;
else
rounds_principe++;
// terceiro round
// princesa joga com a segunda maior e o principe com a menor
if(cartas_princesa[1] > cartas_principe[0])
rounds_princesa++;
else
rounds_principe++;
// testa se o príncipe ganhou
if(rounds_principe >= 2)
{
resp = carta;
break;
}
}
}
if(resp != -1)
printf("%d\n", resp);
else
printf("-1\n");
}
return 0;
}
Input
50 26 19 10 27
10 20 30 24 26
46 48 49 47 50
0 0 0 0 0
Output
-1
21
51