[转帖]大字符窜（一道acm的题目）

gladrain

<FONT size=+0><!-- 固定文字颜色 -->题目：
                                  big String

Time limit: 1 second
input file : b.in

  we will construct an infinitely long string from two short strings:A = "^__^"(for characters), and B = "T.T"(three characters). Repeat the following steps:

1. Concatenate A after B to botain a new string C. for example, if A = "^__^" and B = "T.T",

then C = BA = "T.T^__^".
2. Let A= B, B=C -- as the example above A = "T.T", B= "T.T^__^".

  your task is to find out the n-th character of this infinite string.

Input :
  the input contains multiple test cases, each contains only one intger N (1 &lt;= N &lt;= 2^63-

1). Proceed to the end of file.

Output:
        for each test case ,print one character on each line ,which is the n-th(index begins

with 1) character of this infinite string.

sample input:
1
2
4
8

sample output:
T
.
^
T

<FONT size=+0><!-- 固定文字颜色 -->题目大体上是从文件b.in读入数据，然后根据数据来推测出大字符窜（big string）的该位置的字符是哪个（大字符窜的索引从1开始）。
大字符窜C的形成方法：
A = "^__^" and B = "T.T",
while(true)
{
    C = BA ;
   A= B;
  B=C;
}

</FONT></FONT>

gladrain

<FONT size=+0><!-- 固定文字颜色 -->#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;string&gt;
#include &lt;cmath&gt;
#include &lt;stdlib.h&gt;

using namespace std;

void Search(unsigned __int64 input, unsigned __int64&amp; result)
{
        unsigned __int64 A = 4;
        unsigned __int64 B = 3;
        unsigned __int64 C,CT=0;

        if(result)
                return ;
        if(input &lt;= 7)
        {
                if(input ==0)
                        input = 7;
                result = input;
        }
        else
        {
                while(true)
                {
                        C = A + B;
                        A = B;
                        B = C;
                        if(C &lt; input)
                                CT = C;
                        else
                                break;
                }
                Search(input - CT,result);
        }

}

string I64ToStr(unsigned __int64 input)
{
        string strTemp="";
        string strResult="";
        while(input/10)
        {
                strTemp += char('0' + input%10);
                input /= 10;
        }
        strTemp += char('0' + input%10);
        int len = strTemp.length();
        strResult.resize(len);
        for(int i=0; i &lt; len; i++)
                strResult[len-i-1] = strTemp;
        return strResult;
}

void main()
{
        string str = " T.T^__^";
        unsigned __int64 input;
        string strInput;

        fstream fs;
        fs.open("b.in");
        while(!fs.eof())
        {
                fs&gt;&gt;strInput;
                input = _atoi64(strInput.c_str());
                unsigned __int64 i=0;
//                strInput = I64ToStr(input);
                cout&lt;&lt;strInput&lt;&lt;endl;
//                strInput=I64ToStr(pow(2,63));
//                cout&lt;&lt;"2_63"&lt;&lt;" "&lt;&lt;strInput&lt;&lt;endl;
                Search(input,i);
                cout&lt;&lt;str&lt;&lt;endl;
        }
}
</FONT>

gladrain

<TABLE cellSpacing=0 cellPadding=0 border=0><TR><TD vAlign=top width=14 background=zba/center_l.gif></TD><TD 14pt" bgColor=#fffff1>
<FONT size=+0><!-- 固定文字颜色 -->题目的一个非常大的难点是：
2^63是19位数字，而long是10位数字（所以不符合要求），unsigned long 也不符合要求。只有unsigned __int64（可以到20位有效数字）符合要求！</FONT></TD><TD vAlign=top width=16 background=zba/center_r.gif><img src="http://www.beincity.net/stu/cdb/zba/top_r2.gif"></TD></TR><TR><TD vAlign=top width=14><img src="http://www.beincity.net/stu/cdb/zba/foot_l1.gif"></TD><TD background=zba/foot_c.gif><img src="http://www.beincity.net/stu/cdb/zba/foot_l3.gif"></TD></TR></TABLE>

gladrain

<FONT size=3>下面是我今天这道题的程序,(稍微改动了点)


#include &lt;iostream.h&gt;
#include &lt;string.h&gt;
#include &lt;stdio.h&gt; //FILE

unsigned __int64 fun( unsigned __int64 i )
{
        unsigned __int64 len;
        if(i==1)
                len=7;
        else if(i==2)
                len=10;
        else {
                unsigned __int64 c1Len=10,
                                                   c2Len=17,
                                                   c3Len=17;
                while( i!=3 ) {
                        i--;
                        c3Len=c1Len+c2Len;
                        c1Len=c2Len;
                        c2Len=c3Len;
                }
                len=c3Len;
        }
        return len;
}

int main()
{
        FILE * FP;
        fp=fopen("b.in","r");
        unsigned __int64 c1Len, c2Len,c3Len;
        unsigned __int64 n,i,distance;
        char c1[] = " T.T^__^";
        char c2[] = " T.T^__^T.T";

        while( fscanf(fp,"%I64u",&amp;n)!=EOF ) {
                if(n&lt;=7)
                        cout &lt;&lt; c1[n] &lt;&lt; endl;
                else if (n&lt;=10)
                        cout &lt;&lt; c2[n] &lt;&lt; endl;
                else {
                        c1Len=10;
                        c2Len=17;
                        c3Len=17;
                        i=3;
                        while( c3Len&lt;n ){
                                i++;
                                c3Len = c1Len+c2Len;
                                c1Len = c2Len;
                                c2Len = c3Len;
                        }
                        distance = c3Len-n;
                        while( ! (i==1 || i==2) ) {
                                if( distance &lt;= fun(i-2) )
                                        i-=2;
                                else {
                                        distance -= fun(i-2);
                                        i--;
                                }
                        }
                        if(i==1)
                                cout &lt;&lt; c1[7-distance] &lt;&lt; endl;
                        else
                                cout &lt;&lt; c2[10-distance] &lt;&lt; endl;
                }
        }
        fclose(fp);
        return 0;
}</FONT>