Difference between revisions of "KGS math club/solution 11 2"
(added solution) |
|||
| (6 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | Given n, k, and | + | Given n, k, and a k-member subset K of the n-member set N, we form the (n-k)-member subset it is paired with as follows. |
| − | Assign integers modulo n to the members of N | + | Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K. |
| + | |||
| + | Solution by iceweasel. | ||
| + | |||
| + | He supplied this C code to compute it: | ||
| + | |||
| + | main(int a, char **v) { | ||
| + | int n=atoi(v[1]), | ||
| + | ss=atoi(v[2]), | ||
| + | x0=0, | ||
| + | x1=0, | ||
| + | m; | ||
| + | |||
| + | for ( m=1<<n ; m>>=1 ; (m&ss?(x1|=m):x1?(x1&=(x1-1)):(x0|=m)) ); | ||
| + | for ( m=1<<n ; m>>=1 ; m&x0&&x1&&(x1&=(x0^=m,x1-1)) ); | ||
| + | printf("%d\n",ss^x0^x1); | ||
| + | } | ||
| + | The arguments to the program are two integers: n, and one whose set bits correspond to the elements of K. | ||
| + | |||
| + | He also supplied this Perl code: | ||
| + | |||
| + | <nowiki>$_=shift;print $_;while(s/[A-Z][a-z]//){}while(s/^[a-z](.*)[A-Z]$/\1/){}print "^$_\n";</nowiki> | ||
| + | |||
| + | which requires presenting the subset as a word in mixed upper (members) and lower (non-member) case. | ||
Latest revision as of 17:08, 21 February 2011
Given n, k, and a k-member subset K of the n-member set N, we form the (n-k)-member subset it is paired with as follows.
Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K.
Solution by iceweasel.
He supplied this C code to compute it:
main(int a, char **v) {
int n=atoi(v[1]),
ss=atoi(v[2]),
x0=0,
x1=0,
m;
for ( m=1<<n ; m>>=1 ; (m&ss?(x1|=m):x1?(x1&=(x1-1)):(x0|=m)) );
for ( m=1<<n ; m>>=1 ; m&x0&&x1&&(x1&=(x0^=m,x1-1)) );
printf("%d\n",ss^x0^x1);
}
The arguments to the program are two integers: n, and one whose set bits correspond to the elements of K.
He also supplied this Perl code:
$_=shift;print $_;while(s/[A-Z][a-z]//){}while(s/^[a-z](.*)[A-Z]$/\1/){}print "^$_\n";
which requires presenting the subset as a word in mixed upper (members) and lower (non-member) case.
