ms-onlinetest-question02

浏览数：36 / 时间：2015年06月09日

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: [email protected]
*/

#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;
}