Question 2
Time Limit: 10000ms
Case Time Limit: 1000ms
Memory
Limit: 256MB
Description
Consider a string set that each
of them consists of {0, 1} only. All strings in the set have the same number of
0s and 1s. Write a program to find and output the K-th string according to the
dictionary order. If s?uch a string doesn’t exist, or the input is not valid,
please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s, we
will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100},
and the 4th string is 1001.
Input
The first line of the input
file contains a single integer t (1 ≤ t ≤ 10000), the number of test cases,
followed by the input data for each test case.
Each test case is 3 integers
separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0), K(1
<= K <= 1000000000). N stands for the number of ‘0’s, M stands for the
number of ‘1’s, and K stands for the K-th of string in the set that needs to be
printed as output.
Output
For each case, print exactly one
line. If the string exists, please print it, otherwise print “Impossible”.
Sample In
3
2 2 2
2 2 7
4 7 47
Sample
Out
0101
Impossible
01010111011
代码：（不确定是否AC）
#pragma once /* @note: 这个题目模拟生成升序二进制序列，有点意思 :) @algm: 如果采用构造这样的二进制序列的话，可看做递归式的"1"与"0"的移动 @date: 04/14/2014 @author: worksdata@163.com */ #include <iostream> using namespace std; #define SAFE_DEL_POINTER(p) if(p) {delete[] p; p = NULL;} void FindBinarySequence(int nZero, int nOne, int kth); void NextSequence(char*& szBiSeq, int nPosFirstOne, int nLen, int& nID, int kth); void SwapChar(char& a, char& b); void RunQuest02() { int nCount = 0; cin>>nCount; if(nCount > 0) { int* a = new int[nCount]; memset(a, 0, nCount); int* b = new int[nCount]; memset(b, 0, nCount); int* c = new int[nCount]; memset(c, 0, nCount); cout<<endl;//"input the cases:" for(int i = 0; i < nCount; ++i) cin>>a[i]>>b[i]>>c[i]; cout<<endl;//<<"finding.." for(int i = 0; i < nCount; ++i) { FindBinarySequence(a[i], b[i], c[i]); } SAFE_DEL_POINTER(a); SAFE_DEL_POINTER(b); SAFE_DEL_POINTER(c); } } void FindBinarySequence(int nZero, int nOne, int kth) { if(nZero<0 || nOne < 0 || nZero+nOne<2 || nZero+nOne > 33 || kth < 1 || kth > 1000000000) { cout<<"impossible"<<endl; return; } char* szBiSeq = new char[nZero+nOne+1]; for(int i = 0; i < nZero+nOne; ++i) { if(i < nZero) szBiSeq[i] = ‘0‘; else szBiSeq[i] = ‘1‘; } szBiSeq[nZero+nOne] = ‘\0‘; //output the first binary sequence int nID = 1; //cout<<szBiSeq<<"\t"<<nID<<endl; NextSequence(szBiSeq, nZero, nZero+nOne, nID, kth); if(nID < kth) cout<<"impossible"<<endl; if(szBiSeq) { delete szBiSeq; szBiSeq = NULL; } } void NextSequence(char*& szBiSeq, int nPosFirstOne, int nLen, int& nID, int kth) { //"1" 与最左边的"0"交换位置，同时所有的"1"靠向最右边 if(nPosFirstOne == 0 || nID == kth) { cout<<szBiSeq<<endl; return; } SwapChar(szBiSeq[nPosFirstOne-1], szBiSeq[nPosFirstOne]); int nOneCount = 0; for(int i = nPosFirstOne+1; i < nLen; ++i) { if(szBiSeq[i] == ‘1‘) { ++nOneCount; szBiSeq[i] = ‘0‘; } } int i = nLen-1; int n = nOneCount; for(; i > nPosFirstOne && n > 0; --i, --n) szBiSeq[i] = ‘1‘; //new binary sequence //cout<<szBiSeq<<"\t"<<++nID<<endl; ++nID; if(nOneCount > 0) NextSequence(szBiSeq, i+1, nLen, nID, kth); else { //从右边开始找到"1"出现后的第一个"0" bool bOneOccur = false; bool bFound = false; int nFirstOne = 0; for(int i = nLen -1; i >= 0; --i) { if(szBiSeq[i] == ‘1‘) bOneOccur = true; else if(szBiSeq[i] == ‘0‘ && bOneOccur) { bFound = true; nFirstOne = i + 1; break; } } if(bFound) NextSequence(szBiSeq, nFirstOne, nLen, nID, kth); } } void SwapChar(char& a, char& b) { a = a + b; b = a - b; a = a - b; }