[UVA] 254 - Towers of Hanoi

/*20150315 hanting*/
#include <iostream>
using namespace std;
class BigNum
{
private:
    long long num[15];
    int digit;

public:
    BigNum():num{0},digit(0){}
    BigNum(int a);
    void digitCount();
    BigNum operator*(BigNum a);
    friend BigNum operator+(BigNum Num,int a);
    friend BigNum operator-(BigNum Num,int a);
    BigNum operator-(BigNum a);
    friend bool operator>(BigNum a,BigNum b);
    friend bool operator==(BigNum a,BigNum b);
    friend BigNum pow(int a,int i);
    friend istream& operator>>(istream& in,BigNum &a);
    friend ostream& operator<<(ostream& out,BigNum a)
    {
        out<<a.num[a.digit-1];
        for(int i=a.digit-2;i>=0;i--)
        {
            out.width(4);
            out.fill('0');
            out<<a.num[i];
        }
        return out;
    }

};
int tower[3];
void hanoi(int n,int from,int temp,int to,BigNum &m)
{
    for(int i=n,j=0;i>=0;i--,j++)
    {
        BigNum t;
        t=pow(2,i)-1;
        if(m>t)
        {
            m=m-(t+1);
            tower[from]-=i+1;
            if(i&1)
            {
                tower[temp]+=i;
                tower[to]++;
                hanoi(i,temp,to,from,m);
            }
            else
            {
                tower[to]+=i;
                tower[temp]++;
                hanoi(i,to,from,temp,m);
            }
            break;
        }
        else if(m==t)
        {
            m=m-(t+1);
            tower[from]-=i;
            if(i&1)
            {
                tower[temp]+=i;
            }
            else
            {
                tower[to]+=i;
            }
            break;
        }
    }
}
int main()
{
    int n;
    BigNum m;
    while(cin>>n>>m && n)
    {
        tower[0]=n;
        for(int i=1;i<3;i++) tower[i]=0;

        hanoi(n,0,1,2,m);

        for(int i=0;i<2;i++)
        {
            cout<<tower[i]<<" ";
        }
        cout<<tower[2]<<endl;
    }
}
BigNum::BigNum(int a)
{
    digit=0;
    for(int i=0;i<15;i++) num[i]=0;
    while(a)
    {
        num[digit++]=a%10000;
        a/=10000;
    }
}
void BigNum::digitCount()
{
    for(int i=14;i>=0;i--)
    {
        if(num[i])
        {
            digit=i+1;
            break;
        }
    }
}
BigNum pow(int a,int i)
{
    BigNum temp;
    while(a)
    {
        temp.num[temp.digit++]+=a%10000;
        a/=10000;
    }
    BigNum ans;
    ans=temp;
    for(int j=0;j<i-1;j++)
    {
        ans=ans*temp;
    }
    return ans;
}
BigNum BigNum::operator*(BigNum a)
{
    BigNum ans;
    for(int i=0;i<digit;i++)
    {
        for(int j=0;j<a.digit;j++)
        {
            ans.num[i+j]+=num[i]*a.num[j];
        }
    }
    for(int i=1;i<15;i++)
    {
        ans.num[i]+=ans.num[i-1]/10000;
        ans.num[i-1]%=10000;
    }
    ans.digitCount();
    return ans;
}
BigNum operator+(BigNum Num,int a)
{
    Num.num[0]+=a;
    for(int i=1;i<15;i++)
    {
        Num.num[i]+=Num.num[i-1]/10000;
        Num.num[i-1]%=10000;
    }
    Num.digitCount();
    return Num;
}
BigNum operator-(BigNum Num,int a)
{
    BigNum ans;
    BigNum temp(a);
    ans=Num-temp;
    return ans;
}
BigNum BigNum::operator-(BigNum a)
{
    BigNum ans;
    for(int i=0;i<15;i++)
    {
        ans.num[i]=num[i]-a.num[i];
    }
    for(int i=0;i<14;i++)
    {
        if(ans.num[i]<0)
        {
            ans.num[i]+=10000;
            ans.num[i+1]--;
        }
    }
    ans.digitCount();
    return ans;
}
bool operator>(BigNum a,BigNum b)
{
    for(int i=14;i>=0;i--)
    {
        if(a.num[i]>b.num[i]) return 1;
        else if(a.num[i]<b.num[i]) return 0;
    }
}
bool operator==(BigNum a,BigNum b)
{
    for(int i=0;i<15;i++)
    {
        if(a.num[i]!=b.num[i]) return 0;
    }
    return 1;
}
istream& operator>>(istream& in,BigNum &a)
{
    BigNum temp;
    a=temp;
    string str;
    in>>str;
    if(str.size()%4!=0)
    for(int i=0;i<str.size()%4;i++)
    {
        str='0'+str;
    }
    for(int i=str.size()-1;i>=0;i-=4)
    {
        a.num[a.digit++]=(str[i]-48) + 10*(str[i-1]-48) + 100*(str[i-2]-48) + 1000*(str[i-3]-48);
    }
    return in;
}

[UVA] 10008 - What's Cryptanalysis?

/*20150310 hanting*/
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(pair<char,int> a,pair<char,int> b)
{
    if(a.second==b.second) return a.first<b.first;
    else return a.second>b.second;
}
int main()
{
    int N;
    cin>>N;
    cin.get();
    string str[N];
    string total="";
    for(int i=0;i<N;i++)
    {
        getline(cin,str[i]);
        for(int j=0;j<str[i].size();j++)
        {
            if(isalpha(str[i][j])) total+=toupper(str[i][j]);
        }
    }
    pair<char,int> letter[26];//< 字母 , 字母出現的次數 >
    for(int i=0;i<26;i++) letter[i].first=i+'A';
    for(int i=0;i<total.size();i++)
    {
        letter[total[i]-'A'].second++;
    }
    sort(letter,letter+26,compare);
    for(int i=0;letter[i].second;i++)//次數是0就停止輸出
    {
        cout<<letter[i].first<<" "<<letter[i].second<<endl;
    }
    return 0;
}
----------------------------------------

/* 20151012
 * hanting
 * UVa 10008 - What's Cryptanalysis?
 * C++
 */
#include <iostream>
#include <algorithm> //transform,sort
using namespace std;
struct Letter
{
    char ch;
    int cnt;
    Letter():cnt(0){}
    bool operator<(const Letter& another)const
    {
        return cnt>another.cnt or (cnt==another.cnt and ch<another.ch);
    }
};
int main()
{
    int N;
    while(cin>>N)
    {
        string str;
        cin.get();
        Letter letter[26];//A~Z
        for(int i=0;i<26;i++)
        {
            letter[i].ch='A'+i;
        }
        for(int i=0;i<N;i++)
        {
            getline(cin,str);
            transform(str.begin(),str.end(),str.begin(),::toupper);
            for(int i=0;i<str.size();++i)
            {
                if(isalpha(str[i])) letter[ str[i]-'A' ].cnt++;
            }
        }
        sort(letter,letter+26);
        for(int i=0;i<26;i++)
        {
            if(letter[i].cnt)
            {
                cout<<letter[i].ch<<" "<<letter[i].cnt<<endl;
            }
        }

    }
    return 0;

}

[UVA] 10420 - List of Conquests

/*20150302 hanting*/
#include <iostream>
#include <map>
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        map<string,int> store;
        string country,temp;
        for(int i=0;i<N;i++)
        {
            cin>>country;
            getline(cin,temp);
            store[country]++;
        }
        for(map<string,int>::iterator it=store.begin();it!=store.end();it++)
        {
            cout<<it->first<<" "<<it->second<<endl;
        }
    }
    return 0;
}

[UVA] 10101 - Bangla Numbers

/*20150302 hanting*/
#include <iostream>
#include <iomanip>//setw
using namespace std;
int main()
{
    long long N=0;
    int times=0;
    long long numbers[]={1e2,1e3,1e5,1e7,1e9,1e10,1e12,1e14};
    while(cin>>N)//23764//45897458973958
    {
        string Bangla[]={"shata","hajar","lakh","kuti","shata","hajar","lakh","kuti"};
        int x=0;//Bangla[]//numbers[]
        cout<<setw(4)<<++times<<". ";
        int ans[8]={0};
        for(int i=0;i<8;i++)
        {
            if(i<7)ans[i]=N/numbers[i]-N/numbers[i+1]*(numbers[i+1]/numbers[i]);
            else ans[i]=N/numbers[i];
        }
        int i=7;
        bool space=0;
        if(ans[3]==0)
        {
            for(int i=4;i<8;i++)
            {
                if(ans[i])
                {
                    Bangla[i]+=" kuti";
                    break;
                }
            }
        }
        for(;i>=0;i--)
        {
            if(ans[i])
            {
                cout<<ans[i]<<" "<<Bangla[i];
                i--;
                space=1;
                break;
            }
        }
        for(;i>=0;i--)
        {
            if(ans[i]) cout<<" "<<ans[i]<<" "<<Bangla[i];
        }

        if(N%100||N==0) cout<<(space ? " ":"")<<N%100;
        cout<<endl;
    }
    return 0;
}

[UVA] 10579 - Fibonacci Numbers

/*20150223 hanting*/
#include <iostream>
using namespace std;
int f[10001][401]={0};
void output(int *f)
{
    int i=400;
    while(f[i]==0 && i>0) i--;
    cout<<f[i];
    for(int j=i-1;j>=0;j--)
    {
        cout.width(3);
        cout.fill('0');
        cout<<f[j];
    }
    cout<<endl;
}
int main()
{
    f[0][0]=0;
    f[1][0]=1;
    for(int i=2;i<10001;i++)
    {
        //f[i]=f[i-1]+f[i-2]
        for(int j=0;j<400;j++)
        {
            f[i][j]=f[i-1][j]+f[i-2][j];
        }
        for(int j=1;j<400;j++)
        {
            f[i][j]+=f[i][j-1]/1000;
            f[i][j-1]%=1000;
        }
    }
    int N;
    while(cin>>N) output(f[N]);
    return 0;
}

[UVA] 495 - Fibonacci Freeze

/*20150223 hanting*/
#include <iostream>
using namespace std;
struct BigNum
{
    int num[1200];
    int digit;
    BigNum()
    {
        fill(num,num+1200,0);
        digit=0;
    }
    int digitCount()
    {
        for(int i=1200;i>=0;i--)
        {
            if(num[i]) return i+1;
        }
    }
    void operator=(int n)
    {
        if(n==0) digit++;
        while(n)
        {
            num[digit++]=n%10;
            n/=10;
        }
    }
    BigNum operator+(BigNum a)
    {
        BigNum sum;
        for(int i=0;i<1200;i++)
        {
            sum.num[i]=num[i]+a.num[i];
        }
        for(int i=1;i<1200;i++)
        {
            sum.num[i]+=sum.num[i-1]/10;
            sum.num[i-1]%=10;
        }
        sum.digit=sum.digitCount();
        return sum;
    }
    friend ostream& operator<<(ostream& bout,BigNum b)
    {
        bout<<b.num[b.digit-1];
        for(int i=b.digit-2;i>=0;i--)
        {
            bout<<b.num[i];
        }
        return bout;
    }
};
BigNum DP[5001];
BigNum f(int N)
{
    if(DP[N].digit) return DP[N];
    else
    {
        DP[N]=f(N-1)+f(N-2);
        return DP[N];
    }
}
int main()
{
    DP[0]=0;
    DP[1]=1;
    for(int i=200;i<=5000;i+=200)
    {
        DP[i]=f(i);
    }
    int N;
    while(cin>>N)
    {
        cout<<"The Fibonacci number for "<<N<<" is "<<f(N)<<endl;
    }
    return 0;
}

[UVA] 485 - Pascal's Triangle of Death


/*20150221 hanting*/
#include <iostream>
using namespace std;
struct BigNum
{
    int num[61];
    int digit;
    BigNum()
    {
        fill(num,num+61,0);
        digit=0;
    }
    int digitCount()
    {
        for(int i=60;i>=0;i--)
        {
            if(num[i]!=0) return i+1;
        }
    }
    BigNum operator+(BigNum a)
    {
        BigNum sum;
        for(int i=0;i<61;i++)
        {
            sum.num[i]=num[i]+a.num[i];
        }
        for(int i=1;i<61;i++)
        {
            sum.num[i]+=sum.num[i-1]/1000;
            sum.num[i-1]%=1000;
        }
        int sumDigit=max(digit,a.digit);
        sum.digit=(sum.num[sumDigit] ? sumDigit+1:sumDigit);

        return sum;
    }
    void operator=(int i)
    {
        digit=0;
        while(i)
        {
            num[digit++]=i%1000;
            i/=1000;
        }
    }
    friend ostream& operator<<(ostream& bout,BigNum bnum)
    {
        bout<<bnum.num[bnum.digit-1];
        for(int i=bnum.digit-2;i>=0;i--)
        {
            bout.width(3);
            bout.fill('0');
            bout<<bnum.num[i];
        }
        return bout;
    }
};
void output(BigNum *Last,int lastCount,BigNum *This)
{
    cout<<Last[0];
    for(int i=1;i<lastCount;i++)
    {
        cout<<" "<<Last[i];
    }
    cout<<endl;
    if(Last[lastCount/2].digit>=21) return ;
    int ThisCount=lastCount+1;
    This[0]=1;
    for(int i=1;i<=lastCount/2;i++)
    {
        BigNum temp;
        temp=Last[i]+Last[i-1];
        This[i]=This[lastCount-i]=temp;
    }
    This[lastCount]=1;
    BigNum *Next=Last;
    output(This,ThisCount,Next);
}
int main()
{
    BigNum Last[1000];
    BigNum This[1000];
    Last[0]=1;
    output(Last,1,This);
    return 0;
}


======================================================

# /* 題目: UVa 485 - Pascal’s Triangle of Death
#  * https://onlinejudge.org/external/4/485.pdf
#  * Language: Python
#  * Created on: 2019年12月19日
#  *   Author: hanting
#  */

times = 205
last = [1]
while(times > 0):
    times -= 1
    print(*last)
    cur = [last[x] + (last[x-1] if x>0 else 0) for x in range(len(last))] + [1]
    last = cur[:]