http://vjudge.net/problem/viewProblem.action?id=37481
East Central Regional Contest Problem D: I’ve Got Your Back(gammon)
A friend of yours is working on an AI program to play backgammon, and she has a small problem. At
the end of the game, each player’s pieces are moved onto a set of board positions called
points
,
numbered through . The pieces can be distributed in any manner across these points: all could
be on point ; could be on point , on point , on point and on point ; etc. Your friend
wants to store all these possible configurations (of which there are ) into a linear array, but she
needs a mapping from configuration to array location. It seems logical that the configuration with all
pieces on point should correspond to array location , and the configuration of all pieces on point
should correspond to the last array location. It’s the ones in between that are giving her problems.
That’s why she has come to you.
You decide to specify a configuration by listing the number of pieces on each point, starting with
point . For example, the two configurations described above could be represented by (
, , , , ,
)
and (
, , , , ,
). Then you can order the configurations in lexicographic ordering, starting with
(,,,,,), then (
, , , , ,
)
,
(
, , , , ,
)
, . . . ,
(
, , , , ,
)
,
(
, , , , ,
)
,
(
, , , , ,
),
(
, , , , ,
), etc., ending with (
, , , , ,
). Now all you need is a way to map these orderings to
array indices. Literally, that’s all you need, because that’s what this problem is all about.
Input
Each test case will consist of one line, starting with a single character, either
‘m’
or
‘u’
. If it is an
‘m’
it will be followed by a configuration and you must determine what array index it gets mapped to. If
it is a
‘u’
then it will be followed by an integer array index i,
≤
i <
, and you must determine
what configuration gets mapped to it. A line containing the single character
‘e’
will end input.
Output
For each test case, output the requested answer – either an array index or a configuration. Follow the
format in the examples below.
Sample Input
m
u
e
Sample Output
Case :
Case :
题目
把15分配到6个格子里，对应一个数。
例如0 0 0 0 0 15是1；
15 0 0 0 0 0是15503。
做法就是先把这些6人组不重复地全部弄出来存起来…然后排个序！然后就和数一一对应了，随便玩。
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll; struct six
{
int a[];
}; six d;
vector<six> v; void dfs(int x,int y)
{
int i;
if(x==)
{
d.a[]=-y;
v.push_back(d);
return;
}
for(i=; i<=-y; i++)
{
d.a[x]=i;
dfs(x+,y+i);
}
} bool cmp(six x,six y)
{
for(int i=; i<; i++)
{
if(x.a[i]<y.a[i]) return true;
if(x.a[i]>y.a[i]) return false;
}
return false;
} bool issame(six x,six y)
{
for(int i=; i<; i++)
{
if(x.a[i]!=y.a[i]) return false;
}
return true;
} int main()
{
int i,j;
v.clear();
dfs(,);
sort(v.begin(),v.end(),cmp);
// for(j=0; j<46; j++)
// {
// cout<<j<<". ";
// for(i=0; i<6; i++)
// cout<<v[j].a[i]<<' ';
// cout<<endl;
// }
char c;
six s;
int t=,x;
while(scanf(" %c",&c)!=EOF)
{
if(c=='m')
{
for(i=;i<;i++)
scanf("%d",&s.a[i]);
for(i=;i<;i++)
if(issame(s,v[i]))
{
printf("Case %d: %d\n",t++,i);
break;
}
}
else if(c=='u')
{
scanf("%d",&x);
printf("Case %d:",t++);
for(i=;i<;i++)
printf(" %d",v[x].a[i]);
puts("");
}
else if(c=='e')
{
break;
}
}
return ;
}