[UVA] 156 - Ananagrams

題意:
輸入很多字串，若該輸入的字串重組後不分大小寫
可以在之前輸入過字串中找到則不輸出。
例如:Apple banana orange appLE
則Apple和appLE都不輸出，
只輸出
banana
orange
要按照字典序!

方法:
map，若出現過的先用別的記號('#')取代，輸出時判斷是'#'則不輸出!


/* 20150731
 * hanting
 * UVa 156 - Ananagrams
 * C++
 */
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>//sort
using namespace std;
int main()
{
    map<string,string> Map;
    string str;
    while(cin>>str and str!="#")
    {
        string SortStr=str;
        transform(SortStr.begin(),SortStr.end(),SortStr.begin(),::tolower);
        sort(SortStr.begin(),SortStr.end());
        if(Map[SortStr].size()) Map[SortStr]="#";
        else Map[SortStr]=str;
    }
    vector<string> vec;
    for(map<string,string>::iterator it=Map.begin();it!=Map.end();++it)
    {
        if((it->second)!="#") vec.push_back(it->second);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++)
    {
        cout<<vec[i]<<endl;
    }
    return 0;
}

[UVA] 10815 - Andy's First Dictionary

題意:
輸入很多字串，
將字串以字典序且不重複的輸出，
輸出的字串都要小寫。
注意:what's  這樣是兩個字串  what  ,  s
要個別輸出!

方法:
讀字元方式一個字元一個字元讀進來，存進str裡面
遇到非字母字元(ex: " , @ # ...)就將str放進set裡，再將str清空!

/* 20150731
 * hanting
 * UVa 10815 - Andy's First Dictionary
 * C++
 */
#include <iostream>
#include <set>
using namespace std;
int main()
{
    set<string> Set;
    string str="";
    char ch;
    while(cin.get(ch))
    {
        if(isalpha(ch))//是字母
        {
            str+=tolower(ch);//變小寫
        }
        else if(str.size())
        {
            Set.insert(str);
            str="";
        }
    }
    for(set<string>::iterator itr=Set.begin();itr!=Set.end();++itr)
    {
        cout<<*itr<<endl;
    }
    return 0;
}

[UVA] 213 - Message Decoding

題意:
給一個字串，
依序以題目給的key做編碼，
範例輸入的TNM AEIOU
T:0
N:00
M:01
 :10
A:000
E:001
I:010
O:011
U:100
接下來開頭以二進位輸入解碼長度:
010表示接下來輸入以2個一組解碼，
100表示接下來輸入以4個一組解碼，依此類推，
解碼長度000表示結束，
輸入完解碼長度後，會有很多組，輸入都是1表示結束。
範例輸入:
001(長度1進行解碼)0 1(結束) =>T
011(長度3進行解碼)000 111(結束) =>A
010(長度2進行解碼)00 10 01 11(結束) =>N M
011(長度3進行解碼)001 111(結束) =>E
000(結束解碼)
輸出:TAN ME

方法:
先將key都列出來~最多到長度7
以map方式儲存每個字元對應到的編碼，
解碼的時候再照著對應到的字元輸出就可以了!

/* 20150730
 * hanting
 * UVa 213 - Message Decoding
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>//count
using namespace std;
string reset(int N)
{
    string str="";
    for(int i=0;i<N;i++)
    {
        str+='0';
    }
    return str;
}
string operator+(string str,int i)
{
    str[str.size()-1]+=1;
    for(int i=str.size()-2;i>=0;i--)
    {
        if(str[i+1]=='2')
        {
            str[i]++;
            str[i+1]='0';
        }
    }
    if(count(str.begin(),str.end(),'1')==str.size())
    {
        str="0"+reset(str.size());
    }
    return str;
}
void BuildKey(vector<string> &key)
{
    key.push_back("0");
    while(key.back().size()<9)
    {
        string last=key.back();
        key.push_back(last+1);
    }

}
int main()
{
    string header;
    vector<string> key;
    BuildKey(key);
    while(getline(cin,header))
    {
        map<string,char> EncodeTable;
        for(int i=0;i<header.size();i++)//編碼頭每個字元依序對應每個code
        {
            char ch=header[i];
            EncodeTable[key[i]]=ch;
        }
        char length[4]={0};
        while(cin>>length[0]>>length[1]>>length[2])
        {
            int codeL=strtol(length,NULL,2);//將010轉成10進位的2
            if(codeL==0) break;//輸入000結束
            while(true)//解碼
            {
                char ch;
                string code="";//將訊息中的01001存起來待等一下解碼
                for(int i=0;i<codeL;i++)
                {
                    cin>>ch;
                    code+=ch;
                }
                if(EncodeTable[code])cout<<EncodeTable[code];
                else break;//編碼111結束解碼
            }
        }
        cout<<endl;
        cin.get();
    }
    return 0;
}

[UVA] 133 - The Dole Queue

題意:
給你N個數，A和B兩個人在數數，A往右邊數k個，B往左邊數m個，
每一回合輸出被A和B數到的數並刪除。
例如:
有10 個數，A往右邊數4個，B往左邊數3個，
1 2 3 4 5 6 7 8 9 10
         ^         ^
         A        B
第一回合就輸出4 8
注意: B往左邊數小於0就從尾巴繼續數吧

解題:
開一維陣列，設定兩個指標posR和posL分別往右往左一個一個數吧，
數到的把它變成-1，下次數的時候就跳過。
小技巧:
讓posR和posL不超出陣列範圍，
把posL加上陣列大小之後再mod就可以了!
例如:
現在陣列大小10，
posL現在指到-1位置，
可是陣列沒有-1的這個位置，
就將(posL+10)%10變成9
讚讚

/* 20150729
 * hanting
 * UVa 133 - The Dole Queue
 * C++
 */
#include <iostream>
#include <vector>
#include <iomanip>//setw
using namespace std;
int main()
{
    int manN,right,left;//往右k//往左m
    while(cin>>manN>>right>>left and manN)
    {
        int posR=-1,posL=0;
        vector<int> vec(manN);
        for(int i=0;i<manN;i++)
        {
            vec[i]=i+1;
        }
        int cnt=0;
        while(cnt<vec.size())//數到陣列元素都變-1
        {
            for(int i=0;i<right;i++)//往右走
            {
                posR++;
                posR%=manN;
                if(vec[posR]==-1) i--;
            }
            for(int i=0;i<left;i++)//往左走
            {
                posL--;
                posL=(posL+manN)%manN;
                if(vec[posL]==-1) i--;
            }
            if(posR==posL)
            {
                cnt++;
                cout<<setw(3)<<vec[posR]<<(cnt<vec.size() ? ",":"");
            }
            else
            {
                cnt+=2;
                cout<<setw(3)<<vec[posR]<<setw(3)<<vec[posL]<<(cnt<vec.size() ? ",":"");
            }
            vec[posR]=vec[posL]=-1;
        }
        cout<<endl;
    }
    return 0;
}

[UVA] 489 - Hangman Judge

題意:
猜單字小遊戲，猜錯7次就輸了，猜錯7次以內猜對單字算贏，不然就算放棄。
同一個字母猜兩次不算錯。

解題:
用anscnt表示答案有幾種字母，
例如:AAB 這樣算A和B兩種
開一個字母表等於1表示是答案中的字母，
猜字母的時候去看字母表，
是1表示猜對，把字母表的1變成2，guesscnt++;
是0表示猜錯，wrong++
如果anscnt==guesscnt表示所有字母都猜對了，
就跳出迴圈不用繼續比囉

例如:
答案:abc
猜  :abcdfgertyuioptrewqwertylkj
輸出:You win.


/* 20150729
 * hanting
 * UVa 489 - Hangman Judge
 * C++
 */
#include <iostream>
using namespace std;
int main()
{
    int N;
    while(cin>>N and N!=-1)
    {
        string ans;
        string guess;
        cin>>ans>>guess;
        int AnsTable[123]={0};
        int AnsCnt=0,GuessCnt=0;
        for(int i=0;i<ans.size();i++)
        {
            int ch=ans[i];
            if(!AnsTable[ch])
            {
                AnsTable[ch]=1;
                AnsCnt++;
            }
        }
        int wrong=0;
        for(int i=0;i<guess.size() and AnsCnt!=GuessCnt;i++)
        {
            int ch=guess[i];
            if(AnsTable[ch]==0)
            {
                wrong++;
            }
            else if(AnsTable[ch]==1)
            {
                AnsTable[ch]++;
                GuessCnt++;
            }
        }
        bool Win=AnsCnt==GuessCnt;
        cout<<"Round "<<N<<endl;
        if(wrong<7)
        {
            if(Win) cout<<"You win."<<endl;
            else cout<<"You chickened out."<<endl;
        }
        else
            cout<<"You lose."<<endl;
    }

    return 0;
}

[UVA] 1584 - Circular Sequence

題意:
字串ACGTA 以各個位置為頭的字串分別為
ACGTA
CGTAA
GTAAC
TAACG
AACGT
取字典序最小的就是所求。

題解:
簡單的字串比大小，字串長度不長(<100)，
先設定初始字串為mini，表示字典序最小
假設字串長度L
將字串分割成前 i 個字元 與後 L-i 個字元，
產生新字串為後 L-i 個字元 + 前 i 個字元組成，
與mini做比較，更新mini ~
/* 20150728
 * hanting
 * UVa 1584 - Circular Sequence
 * C++
 */
#include <iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        string str;
        cin>>str;
        string mini=str;
        for(int i=0;i<str.size();i++)
        {
           string tmp=str.substr(i+1)+str.substr(0,i+1);
           if(tmp<mini) mini=tmp;
        }
        cout<<mini<<endl;
    }

    return 0;
}

[UVA] 1583 - Digit Generator

題意:
輸入Y，求出Y的最小生成元，
生成元定義為X+X的各個位數數字的和，
例如:Y=216，X=207,198
因為207+2+0+7=216，198+1+9+8=216，
題目要最小的，所以取198為答案。

題解:
如果直接一個一個找小於Y的所有生成元會超時，
這一題可以建表，再直接輸出所求即可。
table[y]=x; 意即 y的生成元為x
^0 ^ /
/* 20150728
 * hanting
 * UVa 1583 - Digit Generator
 * C++
 */
#include <iostream>
using namespace std;
const int MAXN=99999+9*5;
inline int Generate(int &n)
{
    return n+n%10+n/10%10+n/100%10+n/1000%10+n/10000%10;
}
int main()
{
    /*Build Table*/
    int table[MAXN]={0};
    for(int i=100000;i>=0;i--)//倒著回來可得min
    {
        table[Generate(i)]=i;
    }
    int N;
    cin>>N;
    while(N--)
    {
        int num;
        cin>>num;
        cout<<table[num]<<endl;
    }
    return 0;
}

[UVA] 340 - Master-Mind Hints

猜數字遊戲
方法:先算A再算B，每對到一個數字，就將個數字改掉避免後面的數字重複對
兩層for迴圈就可以了~
例如:
ANS    :1 2 2 3
GUESS:2 2 3 4
先算A之後變成
ANS    :1 A 2 3
GUESS:2 A 3 4
再算B
ANS    :1 A B B
GUESS:B A B 4
/* 20150728
 * hanting
 * UVa 340 - Master-Mind Hints
 * C++
 */
#include <iostream>
#include <iomanip>//setw
using namespace std;
int main()
{
    int gameN=1;
    int numN;
    while(cin>>numN and numN)
    {
        int ans[numN];
        for(int i=0;i<numN;i++)
        {
            cin>>ans[i];
        }
        int sum=0;
        cout<<"Game "<<gameN++<<":"<<endl;
        do
        {
            int A=0,B=0;
            int temp[numN];
            copy(ans,ans+numN,temp);
            sum=0;
            int guess[numN];
            for(int i=0;i<numN;i++)
            {
                cin>>guess[i];
                sum+=guess[i];
            }
            /*check*/
            //count A
            for(int i=0;i<numN;i++)
            {
                if(temp[i]==guess[i])
                {
                    A++;
                    temp[i]=-1;
                    guess[i]=-2;
                }
            }
            //count B
            for(int i=0;i<numN;i++)//ans
            {
                for(int j=0;j<numN;j++)//guess
                {
                    if(guess[j]==temp[i])
                    {
                        B++;
                        temp[i]=-1;
                        guess[j]=-2;
                    }
                }
            }
            if(sum)cout<<setw(5)<<"("<<A<<","<<B<<")"<<endl;
        }while(sum);
    }
    return 0;
}

[UVA] 401 - Palundromes

/* 20150728
 * hanting
 * UVa 401 - Palundromes
 * C++
 */
#include <iostream>
#include <algorithm>
using namespace std;
string Charactor="ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789";
string mirror   ="A   3  HIL JM O   2TUVWXYZ1SE Z  8 ";
string Mirror(string str)
{
    for(int i=0;i<str.size();i++)
    {
        int pos=Charactor.find(str[i]);
        str[i]=mirror[pos];
    }
    return str;
}
int main()
{
    string str;
    while(cin>>str)
    {
        string rstr=str;
        reverse(rstr.begin(),rstr.end());
        bool mirrored=false,palindrome=false;
        if(str==rstr) palindrome=true;
        if(Mirror(str)==rstr) mirrored=true;

        if(palindrome and mirrored)
        {
            cout<<str<<" -- is a mirrored palindrome."<<endl;
        }
        else if(palindrome)
        {
            cout<<str<<" -- is a regular palindrome."<<endl;
        }
        else if(mirrored)
        {
            cout<<str<<" -- is a mirrored string."<<endl;
        }
        else
        {
            cout<<str<<" -- is not a palindrome."<<endl;
        }
        cout<<endl;
    }

    return 0;
}

[UVA] 111 - History Grading

/* 20150704
 * hanting
 * [UVA] 111 -  History Grading
 *
 */
#include <iostream>
#include <sstream>
using namespace std;

int N;//event_num
istream& operator>>(istream& in,int *arr)
{
    string str;
    getline(in,str);
    stringstream sin(str);
    for(int i=1;i<=N;i++)//輸入1 3 4 2 表示順序為 event1,event4,event2,event3
    {
        int tmp;
        sin>>tmp;
        arr[tmp]=i;
    }
    return in;
}
int LCS(int *a,int *b)
{
    int table[N+1][N+1];
    fill(table[0],table[0]+(N+1)*(N+1),0);
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(a[i]==b[j])
            {
                table[i][j]=table[i-1][j-1]+1;
            }
            else
            {
                table[i][j]=max(table[i-1][j],table[i][j-1]);
            }
        }
    }
    return table[N][N];
}
int main()
{
    cin>>N;
    cin.get();
    int ans[N+1];
    cin>>ans;
    int student[N+1];
    while(cin>>student)
    {
        int lcs=LCS(ans,student);
        cout<<lcs<<endl;
    }
    return 0;
}

[UVA] 540 - Team Queue

/* 20150702
 * hanting
 * [UVA] 540 - Team Queue
 *
 */
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
    int N;
    int Sce=0;
    while(cin>>N and N)
    {
        cout<<"Scenario #"<<++Sce<<endl;
        map<int,int> team;
        vector<int> List[N];
        for(int i=0;i<N;i++)
        {
            int num;
            cin>>num;
            for(int j=0;j<num;j++)
            {
                int tmp;
                cin>>tmp;
                team[tmp]=i;//輸入的數字在哪一個team
            }
        }
        string str;
        vector<int> order;//team排隊的順序
        int x=0;
        int dex=0;
        while(cin>>str and str!="STOP")
        {
            if(str=="ENQUEUE")
            {
                int enqueueNum;
                cin>>enqueueNum;
                int TeamOfNum=team[enqueueNum];
                if(List[TeamOfNum].size()==0)
                {
                    order.push_back(TeamOfNum);
                }
                List[TeamOfNum].push_back(enqueueNum);//插入team中
            }
            else if(str=="DEQUEUE")
            {
                int tmp=order[dex];
                cout<<List[tmp][0]<<endl;
                List[tmp].erase(List[tmp].begin());
                if(List[tmp].size()==0) dex++;
            }
        }
        cout<<endl;
    }
    return 0;
}