#include <stdio.h>
#include <stdlib.h>
int unp2pac(int m){
//transforma 1234 em 1*6^3+2*6^2+3*6 +4
return
m%10+m/10%10*6+m/100%10*36+m/1000%10*216;
}
int pac2unp(int m){
// transforma 1*6^3+2*6^2+3*6 +4 em
1234
return m%6 + m/6%6*10 +
m/36%6*100 + m/216%6*1000;
}
int respmm(int esc, int tent){
//retorna dezena=pinos pretos
unidade=brancos
int e[4]; //digitos da escolha
int t[4]; //digitos da tentativa
int
ed[4]={1,1,1,1}; //escolha-disponivel
int
td[4]={1,1,1,1}; //tentativa-disponivel
int uresp=0, dresp=0; //unidade/branco e dezena/preto
int i,j;
e[0]=esc%6; e[1]=esc/6%6;
e[2]=esc/36%6; e[3]=esc/216%6;
t[0]=tent%6; t[1]=tent/6%6;
t[2]=tent/36%6; t[3]=tent/216%6;
for(i=0; i<4; i++)
if(e[i]==t[i]) dresp++; //pinos pretos
//conta o
total de <pares distintos> os
pares cujos elementos
//nao estao na mesma
posição dao o numero de pinos brancos
for(i=0; i<4; i++)
for(j=0; j<4; j++)
if(e[i]==t[j]&&ed[i]&&td[j]){
uresp++;
//pinos brancos (u unidade)
ed[i]=0;
td[j]=0;
}
return dresp*10
+(uresp-dresp);
}
// 0 1
2 3 4
5 6 7
8 9
int dd2enum[41]={ 0, 1, 3, 6,10,-1,-1,-1,-1,-1,
2, 4,
7,11,-1,-1,-1,-1,-1,-1,
5,
8,12,-1,-1,-1,-1,-1,-1,-1,
9,-1,-1,-1,-1,-1,-1,-1,-1,-1,
13 };
// 0 1
2 3 4
5 6 7
8 9
int enum2dd[14]={ 0, 1,10, 2,11,20, 3,12,21,30,
4,13,22,40};
int str2mmint(char *p){
int n;
n=p[0]-'0';
n=n*6+p[1]-'0';
n=n*6+p[2]-'0';
n=n*6+p[3]-'0';
return n;
}
int main(int argc, char *argv[]){
int i;
int fRespAAAA[41];
int fRespAAAB[41];
int fRespAABB[41];
for(i=0; i<41; i++){
fRespAAAA[i]=0;
fRespAAAB[i]=0;
fRespAABB[i]=0;
}
for(i=0; i<1296; i++){
fRespAAAA[respmm(0,i)]++;
fRespAAAB[respmm(1,i)]++;
fRespAABB[respmm(1*6+1,i)]++;
}
for(i=0; i<14; i++){
printf("%2d
%2d %4d %4d %4d\n",i, enum2dd[i],
fRespAAAA[enum2dd[i]],
fRespAAAB[enum2dd[i]],
fRespAABB[enum2dd[i]]
);
}
system("PAUSE");
return 0;
}
------------------------------
(file name: game.c, game.p, game.C)
game.in, game.out
If you want to buy a new cellular phone, there are many various types
to choose from. To decide which one is the best for you, you have to consider
several important things: its size and weight, battery capacity, WAP support, colour, price. One of the most important things is also the
list of games the phone provides. Nokia is one of the most successful phone
makers because of its famous Snake and Snake II. ACM wants to make and
sell its own phone and they need to program several games for it. One of them is
Master-Mind, the famous board logical game.
The game is played between two players. One of them chooses a secret
code consisting of P ordered pins, each of them having one
of the predefined set of C colours.
The goal of the second player is to guess that secret sequence of colours. Some colours may not
appear in the code, some colours may appear more than
once.
The player makes guesses, which are formed in the same way as the secret
code. After each guess, he/she is provided with an information
on how successful the guess was. This feedback is called a hint.
Each hint consists of B black points and W white points.
The black point stands for every pin that was guessed right, i.e. the right colour was put on the right position. The white point means
right colour but on the wrong position. For example,
if the secret code is "white, yellow, red, blue, white" and the guess
was "white, red, white, white, blue", the hint would consist of one
black point (for the white on the first position) and three white points (for
the other white, red and blue colours). The goal is
to guess the sequence with the minimal number of hints.
The new ACM phone should have the possibility to play both roles. It can
make the secret code and give hints, but it can also make its own guesses. Your
goal is to write a program for the latter case, that
means a program that makes Master-Mind guesses.
There is a single positive integer T on the first line of
input. It stands for the number of test cases to follow. Each test case
describes one game situation and you are to make a guess. On the first
line of each test case, there are three integer numbers, P, C
and M. P ( 1 <= P
<= 10) is the number of pins, C (1 <= C <= 100)
is the number of colours, and M (1 <= M
<= 100) is the number of already played guesses.
Then there are 2 x M lines, two lines for every guess. At the
first line of each guess, there are P integer numbers representing colours of the guess. Each colour
is represented by a number Gi,
1 <= Gi <= C.
The second line contains two integer numbers, B and W,
stating for the number of black and white points given by the corresponding
hint.
Let's have a secret code S1, S2,
... SP and the guess G1, G2,
... GP. Then we can make a set H
containing pairs of numbers (I,J)
such that SI = GJ, and that any
number can appear at most once on the first position and at most once on the
second position. That means for every two different pairs from that set, (I1,J1) and (I2,J2),
we have I1 <> I2 and J1
<> J2. Then we denote B(H)
the number of pairs in the set, that meet the condition I = J,
and W(H) the number of pairs with I <> J.
We define an ordering of every two possible sets H1
and H2. Let's say H1 <= H2
if and only if one of the following holds:
Then we can find a maximal set Hmax
according to this ordering. The numbers B(Hmax) and W(Hmax) are the black and white points
for that hint.
For every test case, print the line containing P numbers representing
P colours of the next guess. Your guess
must be valid according to all previous guesses and hints. The guess is valid
if the sequence could be a secret code, i.e. the sequence was not
eliminated by previous guesses and hints.
If there is no valid guess possible, output the sentence You are cheating!.
If there are more valid guesses, output the one that is lexicographically
smallest. I.e. find such guess G that for every other valid guess V
there exists such a number I that:
3
4 3 2
1 2 3 2
1 1
2 1 3 2
1 1
4 6 2
3 3 3 3
3 0
4 4 4 4
2 0
8 9 3
1 2 3 4 5 6 7 8
0 0
2 3 4 5 6 7 8 9
1 0
3 4 5 6 7 8 9 9
2 0
1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9