2015年8月16日 星期日

[UVA] 11988 - Broken Keyboard

題意:
一個字元一個字元輸入,
若輸入'[',就跑回起點,
若輸入']',就跑到終點,

例如
輸入123[4
就會輸出4123

輸入1[23]4
就會輸出2314

方法:
如果使用陣列儲存,
若很多'['或']'就會超時,
使用linked list一個串一個,
紀錄起點和終點~


/* 20150817
 * hanting
 * UVa 11988 - Broken Keyboard
 * C++
 */
#include <iostream>
using namespace std;
#define head 100001
#define last 100002
int Left[100003];
int Right[100003];

void Link(int L,int R)
{
    Left[R]=L;
    Right[L]=R;
}
int main()
{
    string str;
    while(getline(cin,str))
    {
        int cur=head;
        Link(head,last);
        Right[last]=-1;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]=='[')
            {
                cur=head;
            }
            else if(str[i]==']')
            {
                cur=Left[last];
            }
            else
            {
                Link(i,Right[cur]);
                Link(cur,i);
                cur=Right[cur];
            }
        }
        int now=Right[head];
        while(now!=last)
        {
            cout<<str[now];
            now=Right[now];
        }

        cout<<endl;
    }
    return 0;
}

2015年8月14日 星期五

[UVA] 514 - Rails

題意:
火車有n節車廂,
每個車廂都有依序的編號1...n,
現在這些車廂要從A到B,這個火車可以重組,
重組的方法如下:
車廂是一個一個到車站,
來到車站後可以往B方向去,也可以先暫放在車站。
輸入往另一個方向的車廂編號,
問是否可以藉由重組,
往另一個方向去。
範例輸入:
5           //5節車廂
1 2 3 4 5
5 4 1 2 3
0           //結束
問是否可以以1 2 3 4 5的順序往B方向,
一開始從A方向也是1 2 3 4 5
所以1先進車站,直接往B去,
接著2進車站,直接往B去,
接著3進車站,直接往B去,
接著4進車站,直接往B去,
接著5進車站,直接往B去,
就可以以1 2 3 4 5的順序往B方向去,
所以輸出Yes
而5 4 1 2 3,
1先進車站,先暫放,
2進車站,先暫放,
3進車站,先暫放,
4進車站,先暫放,
5進車站,往B方向去,
接著4往B方向去,
再來車站只能把3往B送,不能送1 2(因為3還沒出),
不可能以5 4 1 2 3的順序重組輸出,
所以輸出No

方法:
車站是一個stack
直接模擬操作,使用一個queue儲存輸入,
依序將1 2 ...n送入stack,
若stack.top==queue.front,那就pop
若stack最後不為空就是No,反之就是Yes



/* 20150814
 * hanting
 * UVa 514 - Rails
 * C++
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
bool CanRestructure(queue<int> &que)
{
    vector<int> from(que.size());
    for(int i=0;i<from.size();i++)
    {//給予from初始值1 2 ...n
        from[i]=i+1;
    }
    stack<int> stk;
    for(int i=0;i<from.size();i++)
    {
        stk.push(from[i]);//車廂一個個進車站
        while(stk.size() and que.front()==stk.top())
        {//若與B的頭一樣就輸出,也就是pop車站的車廂
            stk.pop();
            que.pop();
        }
    }
    if(stk.size()) return false;
    else return true;
}
int main()
{
    int N;
    while(cin>>N and N)
    {
        while(true)
        {
            queue<int> que;
            int num;
            cin>>num;
            if(!num) break;//0跳出
            que.push(num);
            for(int i=1;i<N;i++)
            {
                cin>>num;
                que.push(num);
            }
            if(CanRestructure(que))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        cout<<endl;
    }
    return 0;
}

2015年8月11日 星期二

[UVA] 221 - Urban Elevations

題意:
給你一個城市的俯視圖,
輸入每一棟建築物的
。x 座標
。y 座標
。寬
。長
。高
每一個資訊都是實數,(不是整數)
建築物編號為輸入順序,
例如第一個輸入的編號為1
問正視圖中可見的建築物有哪些,
輸出建築物編號,
以建築物的 x 座標由小到大輸出,
注意!若 x 座標相同以建築物 y 座標由小到大輸出!
例如:
輸入
3//三個建築物
0 0 10 1 50
0 1 11 1 20
0 2 10 1 100








建築物1 2 3都可看到,
但要依照 x 座標案 y 座標輸出,
所以輸出1 2 3。


方法:
離散化
可以列舉每一個x座標,然後看該 x 座標有哪些建築物可見,
但是問題在於,x 座標有無限個,不可能全部列舉,
所以用離散化的方式,將無限變有限。
作法是將每一個建築物的頭和尾的 x 座標紀錄起來排序後做unique,
然後去列舉這些 x 座標就好,
判斷在 x 座標為 i 時該建築物可不可見,
先判斷該建築物是否有覆蓋到 i (頭<=i<=尾),
然後再判斷該建築物前面是否有比他高的,
也就是 y 座標比該建築物小的也覆蓋到 i ,是否有比他高!

注意!每一筆測資之間需空一行,最後一筆測資後面不需要空行。



/* 20150812
 * hanting
 * UVa 221 - Urban Elevations
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>//sort,unique
using namespace std;
struct Building
{
    int id;
    double x,y,width,depth,height;
    friend istream& operator>>(istream& in,Building &b)
    {
        in>>b.x>>b.y>>b.width>>b.depth>>b.height;
        return in;
    }
    bool operator<(const Building &B)const
    {
        return (x<B.x) or (x==B.x and y<B.y);
    }
    bool cover(double t)
    {
        return t>=x and t<=x+width;
    }
    bool visible(double x,Building *b,int n)
    {
        for(int i=0;i<n;i++)
        {
            if(b[i].cover(x) and b[i].y<y and b[i].height>=height) return false;
        }
        return true;
    }
};
int main()
{
    int buildingN;
    int Case=1;
    int blank=0;
    while(cin>>buildingN and buildingN)
    {
        if(blank++) cout<<endl;
        Building building[buildingN];
        double xCoor[buildingN*2];
        for(int i=0;i<buildingN;i++)
        {
            cin>>building[i];
            building[i].id=i+1;//編號從1開始
            xCoor[i*2]=building[i].x;
            xCoor[i*2+1]=building[i].x+building[i].width;
        }
        sort(building,building+buildingN);
        sort(xCoor,xCoor+buildingN*2);
        int m=unique(xCoor,xCoor+buildingN*2)-xCoor;
        vector<int> ans;
        ans.push_back(0);

        for(int i=1;i<buildingN;i++)
        {
            for(int j=0;j<m-1;j++)
            {
                double x=(xCoor[j]+xCoor[j+1])/2;
                if(building[i].cover(x) and building[i].visible(x,building,buildingN))
                {
                    ans.push_back(i);
                    break;
                }
            }
        }

        cout<<"For map #"<<Case++<<", the visible buildings are numbered as follows:"<<endl;

        for(int i=0;i<ans.size()-1;i++)
        {
            cout<<building[ans[i]].id<<" ";
        }
        cout<<building[ans.back()].id<<endl;
    }
    return 0;
}

2015年8月5日 星期三

[UVA] 1592 - Database

題意:
輸入列數和行數,
表示有一個列*行個欄位的字串表,
每個欄位一個字串,
問說能不能找到r1,r2,c1,c2
使得字串(r1,c1)==字串(r2,c1) and 字串(r1,c2)==字串(r2,c2),
如果有就輸出NO,並輸出哪兩列的哪兩行
如果沒有就輸出YES
範例輸入:










所以輸出
2 3
2 3

方法:
這題要先做預處理喔,
將字串都以編號代替,
不然除了會TLE外,
還會TLE。
再來不需要一個一個列舉,
只需要枚舉行就好,(因為題目有說行數<=10)
 再把每一列的兩個字串編號和列數以二元組存取,
例如該列有兩個字串編號:15和23,
那就將10和23合體當first,該列數當second,
(1500023,2),表示第二列有字串10和字串23,
如果該二元組已經存在,
表示找到題目所求,即可輸出!
注意只要找到一組就好哦!

/* 20150803
 * hanting
 * UVa 1592 - Database
 * C++
 */
#include <iostream>
#include <map>
#include <cstring>//strtok
using namespace std;
map<string,int> ID;
int sum=0;
int idx=1;
int StrID(string str)
{
    if(ID[str]) return ID[str];
    return ID[str]=idx++;
}
int main()
{
    int row,col;
    while(cin>>row>>col)
    {
        cin.get();
        string table[row+2][col+2];
        string tmp;
        for(int i=1;i<=row;i++)
        {
            getline(cin,tmp);//注意要讀一整行再做切割
            char *pch=strtok((char*)tmp.c_str(),",");

            int j=1;
            while(pch)
            {
                table[i][j++]=pch;
                pch=strtok(NULL,",");
            }
        }
        int IDtable[row+2][col+2];//預處理,將字串予編號
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                IDtable[i][j]=StrID(table[i][j]);
            }
        }
        bool Yes=true;//找到一項即可
        for(int i=1;i<=col and Yes;i++)
        {
            for(int j=i+1;j<=col and Yes;j++)
            {
                map<int,int> Map;//Map[idx]=列
                for(int k=1;k<=row and Yes;k++)
                {
                    int idx=IDtable[k][i]*100000+IDtable[k][j];
                    if(Map.count(idx))
                    {
                        cout<<"NO"<<endl;
                        cout<<Map[idx]<<" "<<k<<endl;
                        cout<<i<<" "<<j<<endl;
                        Yes=false;
                    }
                    else
                    {
                        Map[idx]=k;
                    }
                }
            }
        }
        if(Yes) cout<<"YES"<<endl;

    }
    return 0;
}

2015年8月4日 星期二

[UVA] 400 - Unix ls

題意:
輸入多個字串,
以最長字串的格子數+2為每一個字串可輸出的格子數,
以字典序先由上而下再從左到右輸出,
也就是以行為主!
每一列最長60字元。

方法:
先找出最長字串,
因為每個字串的格子數固定,
所以可以算出每一列最多可以放幾個字串,
再把它一個一個放進一個二維陣列,
注意是以行為主喔!
再以列為主輸出二維陣列的字串就好。

/* 20150803
 * hanting
 * UVa 400 - Unix ls
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>//sort
#include <iomanip>//setw
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        cout<<"------------------------------------------------------------"<<endl;
        vector<string> vec(N);
        int maxi=0;
        for(int i=0;i<N;i++)
        {
            cin>>vec[i];
            if(maxi<vec[i].size()) maxi=vec[i].size();
        }
        sort(vec.begin(),vec.end());
        int w;//欄位
        int h;//列
        w=(60-maxi)/(maxi+2)+1;
        h=N/w+(N%w ? 1 : 0);
        string output[h][w];
        int x=0;
        for(int i=0;i<w and x<vec.size();i++)
        {
            for(int j=0;j<h and x<vec.size();j++)
            {
                output[j][i]=vec[x++];
            }
        }

        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                cout<<setw(j!=w-1 ? maxi+2 : maxi)<<left<<output[i][j];
            }cout<<endl;
        }
    }
    return 0;
}

2015年8月3日 星期一

[UVA] 12096 - The SetStack Computer

題意:
有一個裝set的stack,
五種操作:
PUSH:裝一個空集合進去stack
DUP:複製stack 最頂端的set再push進去stack
UNION:拿stack最頂端兩個set做聯集再push進去stack
INTERSERT:拿stack最頂端兩個set做交集再push進去stack
ADD:將stack最頂端的set拿出來後insert進去stack最頂端的set
每一次操作都要輸出stack最頂端的set的size
範例輸入的示意圖:(藍色數字就是輸出目前stack最頂端的set的size)




















方法:
如果直接操作會超時,
先將set做編號,
例如{}編號為0,
那麼PUSH時就可以PUSH 0進去stack,
這樣stack可以用stack<int>做儲存,
set也可以用set<int>做儲存,
接下來就可以做五種操作了,
在取top跟pop時要注意有沒有少pop!

/* 20150803
 * hanting
 * UVa 12096 - The SetStack Computer
 * C++
 */
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>//set_union,set_intersection
using namespace std;
stack<int> stk;
map<set<int>,int> Map;
vector<set<int> > vec;
int SetID(set<int> &s)
{
    if(Map.count(s)) return Map[s];
    vec.push_back(s);
    return Map[s]=vec.size()-1;
}
set<int> Empty;
void PUSH()
{
    stk.push(SetID(Empty));
}
void DUP(int t)
{
    stk.push(t);
    stk.push(t);
}
void UNION(int t)
{
    int t2=stk.top();
    stk.pop();
    set<int> un;
    set_union(vec[t].begin(),vec[t].end(),vec[t2].begin(),vec[t2].end(),inserter(un,un.begin()));
    stk.push(SetID(un));
}
void INTERSECT(int t)
{
    int t2=stk.top();
    stk.pop();
    set<int> in;
    set_intersection(vec[t].begin(),vec[t].end(),vec[t2].begin(),vec[t2].end(),inserter(in,in.begin()));
    stk.push(SetID(in));
}
void ADD(int t)
{
    set<int> s(vec[stk.top()].begin(),vec[stk.top()].end());
    stk.pop();
    s.insert(t);
    stk.push(SetID(s));
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        while(stk.size()) stk.pop();//initial
        int cmdN;
        cin>>cmdN;
        for(int i=0;i<cmdN;i++)
        {
            string cmd;
            cin>>cmd;
            if(cmd=="PUSH")
            {
                PUSH();
            }
            else
            {
                int top=stk.top();
                stk.pop();
                if(cmd=="DUP")
                {
                    DUP(top);
                }
                else if(cmd=="UNION")
                {
                    UNION(top);
                }
                else if(cmd=="INTERSECT")
                {
                    INTERSECT(top);
                }
                else//ADD
                {
                    ADD(top);
                }
            }
            cout<<vec[stk.top()].size()<<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}

2015年8月1日 星期六

[UVA] 136 - Ugly Numbers

題意:
醜數:質因數只有2 3 5,
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40...這些都是醜數
求第1500個醜數。

方法:
醜數一定是2a*3b*5c,其中 a,b,c >= 0,
所以先把2 3 5放進優先佇列,一個一個pop,
取出後分別將*2和*3和*5的數再push進去佇列,
pop第1500次就是答案囉
(答案:859963392)


/* 20150801
 * hanting
 * UVa 136 - Ugly Numbers
 * C++
 */
#include <iostream>
#include <map>
#include <queue>
using namespace std;

int main()
{
    long long init[]={5,3,2,1};
    priority_queue<long long,vector<long long>,greater<long long> > prq(init,init+4);
    map<long long,long long> Map;
    Map[1]=Map[2]=Map[3]=Map[5]=1;
    for(long long i=0;i<1500-1;i++)
    {
        long long x2,x3,x5;
        long long top=prq.top();
        prq.pop();
        x2=top*2;
        x3=top*3;
        x5=top*5;
        if(Map[x2]==0)
        {
            prq.push(x2);
            Map[x2]=1;
        }
        if(Map[x3]==0)
        {
            prq.push(x3);
            Map[x3]=1;
        }
        if(Map[x5]==0)
        {
            prq.push(x5);
            Map[x5]=1;
        }
    }
    cout<<"The 1500'th ugly number is "<<prq.top()<<"."<<endl;
    return 0;
}