2015年9月5日 星期六

[UVA] 11059 - Maximum Product

題意:
求最大連乘積。
如果最大連乘積小於0要輸出0。
--------------------------------------------------

方法:
因為資料量不多,
可以枚舉起點和終點,
計算起點到終點的連乘積。

注意!要用long long!

--------------------------------------------------


/* 20150906
 * hanting
 * UVa 11059 - Maximum Product
 * C++
 */
#include <iostream>
using namespace std;
int main()
{
    int N;
    int caseN=1;
    while(cin>>N)
    {
        int num[N];
        for(int i=0;i<N;i++)
        {
            cin>>num[i];
        }
        long long Max=0;//Max最小是0
        for(int i=0;i<N;i++)//start
        {
            for(int j=i+1;j<=N;j++)//end
            {
                long long sum=num[i];
                for(int k=i+1;k<j;k++)
                {
                    sum*=num[k];
                }
                if(Max<sum) Max=sum;
            }
        }
        cout<<"Case #"<<caseN++<<": The maximum product is "<<Max<<"."<<endl<<endl;
    }
    return 0;
}

[UVA] 725 - Division

題意:
輸入N,找到所有解可以滿足
abcde / fghij = N,
其中abcde fghij 是0~9的數字,每個數字都要用到,
不能重複!
測資間要有空行,最後一筆後面不用空行。
--------------------------------------------------

方法:
N去乘以除數得到被除數,
分別去判斷除數和被除數是否有用到重複的數字,
除數可以用for迴圈從1234開始到100000/N,
(1234是最小不重複數字的數,注意! int 的 1234 不等於 int 的 01234 喔!)

--------------------------------------------------


/* 20150906
 * hanting
 * UVa 725 - Division
 * C++
 */
#include <iostream>
using namespace std;
bool check(int n,int p)
{
    if(p<10000 and n<10000) return false;//除數和被除數不都是0開頭
    int vis[10]={n<10000};
    while(n)
    {
        int m=n%10;
        if(vis[m]) return false;
        else
        {
            vis[m]=true;
            n/=10;
        }
    }
    while(p)
    {
        int m=p%10;
        if(vis[m]) return false;
        else
        {
            vis[m]=true;
            p/=10;
        }
    }
    return true;
}
int main()
{
    int N;
    bool blank=false;
    while(cin>>N and N)
    {
        if(blank++) cout<<endl;
        bool solution=false;
        for(int i=1234;i<100000/N;i++)
        {
            if(check(i,i*N))
            {
                solution=true;
                cout<<i*N<<" / "<<(i<10000 ? "0":"")<<i<<" = "<<N<<endl;
            }
        }
        if(!solution)
        {
            cout<<"There are no solutions for "<<N<<"."<<endl;
        }
    }
    return 0;
}

2015年8月27日 星期四

[UVA] 10305 - Ordering Tasks

題意:
輸入節點數和有向邊的數量,
接下來輸入節點 A 指向節點 B ,
最後要輸出的是一拓樸排序,
當 A 指向 B ,就要先輸出 A 再輸出 B ,
範例輸入
5 4
1 2
2 3
1 3
1 5
只要滿足節點 1 在 2 3 5 之前輸出以及 2 在 3 之前輸出即可,
所以也可以輸出
4 1 5 2 3
--------------------------------------------------

方法:
拓樸排序,
先利用 DFS 到最深層的節點,
表示該節點一定可以先輸出,
那麼有指向其他節點的一定會比較後面輸出,
根節點也會最後輸出~
--------------------------------------------------

/* 20150827
 * hanting
 * UVa 10305 - Ordering Tasks
 * C++
 */
#include <iostream>
#include <vector>
#include <cstring>//memset
using namespace std;
vector<int> ans;
void Topology(vector<int> *vec,int *visit,int cur)
{
    static int flag=1;
    visit[cur]=flag++;
    for(int i=0;i<vec[cur].size();i++)
    {
        int t=vec[cur][i];
        if(!visit[t])
        {
            Topology(vec,visit,t);
        }
    }
    ans.push_back(cur);
}
int main()
{
    int N,messageN;
    while(cin>>N>>messageN and N+messageN)
    {
        ans.clear();
        vector<int> vec[N+1];
        for(int i=0;i<messageN;i++)
        {
            int a,b;
            cin>>a>>b;
            vec[a].push_back(b);
        }
        int visit[N+1];
        memset(visit,0,sizeof(visit));
        for(int i=1;i<N+1;i++)
        {
            if(!visit[i])
            {
                Topology(vec,visit,i);
            }
        }
        for(int i=ans.size()-1;i>0;i--)
        {
            cout<<ans[i]<<" ";
        }
        cout<<ans[0]<<endl;
    }
    return 0;
}

2015年8月26日 星期三

[UVA] 699 - The Falling Leaves

題意:
遞迴輸入一棵二元樹,
若子節點是葉子則輸入-1,
最後輸出由左到右的垂直節點的權值和,













輸入: 9 5 3 -1 7 -1 -1 4 -1 -1 8 1 -1 6 -1 -1 -1
就會建出像這樣一棵二元樹,
最後由左邊開始輸出每一垂直線的加總,
3 (5+7) (9+4+1) (8+6)
所以是3 12 14 14

每一個測資後面要一個空行(最後一筆也要)。


--------------------------------------------------

方法:
若子節點不是葉子表示還有子樹要輸入,
所以再進去遞迴,
我以位置10000為根節點,
輸入左節點就在位置9999加上左節點的數字,
輸入右節點就在位置10001加上右節點的數字,
最後再從0開始去找第一個非零的數字開始去輸出~

--------------------------------------------------


/* 20150826
 * hanting
 * UVa 699 - The Falling Leaves
 * C++
 */
#include <iostream>
#include <cstring>//memset
using namespace std;
int sum[20000];
void input(int cur)
{
    int L,R;
    cin>>L;
    if(L!=-1)
    {
        sum[cur-1]+=L;
        input(cur-1);
    }
    cin>>R;
    if(R!=-1)
    {
        sum[cur+1]+=R;
        input(cur+1);
    }
}
int main()
{
    int caseN=1;
    int root;
    while(cin>>root and root != -1)
    {
        memset(sum,0,sizeof(sum));
        sum[10000]=root;
        input(10000);
        cout<<"Case "<<caseN++<<":"<<endl;

        int i=0;
        for(;i<20000;i++)
        {
            if(sum[i]!=0)
            {
                cout<<sum[i];
                i++;
                break;
            }
        }
        for(;i<20000;i++)
        {
            if(sum[i]==0) break;
            cout<<" "<<sum[i];
        }
        cout<<endl<<endl;
    }
    return 0;
}

2015年8月25日 星期二

[UVA] 839 - Not so Mobile

題意:
要問這個天平是否是平衡的,

注意!題目是遞迴輸入喔!
--------------------------------------------------

方法:
建立一個遞回函式進行輸入,
在輸入的時候就順便做判斷,
並回傳總重量(該天平的左+右)。

--------------------------------------------------


/* 20150826
 * hanting
 * UVa 839 - Not so Mobile
 * C++
 */
#include <iostream>
using namespace std;
bool balance;
int input()
{
    int w1,d1,w2,d2;
    cin>>w1>>d1>>w2>>d2;
    if(w1==0) w1=input();
    if(w2==0) w2=input();
    if(w1*d1!=w2*d2) balance=false;
    return w1+w2;
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        balance=true;
        input();
        if(balance)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

        if(caseN)
            cout<<endl;
    }
    return 0;
}

2015年8月24日 星期一

[UVA] 531 - Compromise

題意:
輸入兩個字串,輸出最長共同子序列(Longest Common Subsequence)。

最長共同子序列就是指兩序列在相同順序下的相同元素,不一定要連續!
舉個例子,
1 2 3 5 7 6
1 3 6 5 7
最長共同子序列就是:
1 3 5 7

1 3 5 7是兩個序列的相同元素,而且都以相同順序出現 1->3->5->7,
像是 1 3 5 6 就不是,因為第二個序列找不到依序出現1 3 5 6的

這一題就是把數字換成字串去找LCS而已。

---------------------------------------------

方法:
動態規劃,以先前已經計算好的結果來做下一次的計算,
我先做預處理,將字串先以數字代替,以加快之後在字串上的比較。
我這裡將到目前為止最長的子序列以vector存取,
所以最後直接輸出最後一個vector,
但是其實每計算一次就複製一個vector效率並不高。

在計算過程做標記,最後再循著標記走回來輸出也是一個方法。

Longest Common Subsequence: Dynamic Programming
這個網站寫的蠻好懂得可以參考看看!

---------------------------------------------


/* 20150825
 * hanting
 * UVa 531 - Compromise
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <cstring>//memset
using namespace std;
map<string,int> id;
vector<string> store;
int ID(string str)
{
    if(id.count(str)) return id[str];
    else
    {
        store.push_back(str);
        return id[str]=store.size()-1;
    }
}
bool input(vector<int> &a,vector<int> &b)
{
    a.resize(1);
    b.resize(1);

    string str;
    bool chk=false;
    while(cin>>str and str!="#")
    {
        chk=true;
        a.push_back(ID(str));
    }

    while(cin>>str and str!="#")
    {
        b.push_back(ID(str));
    }
    return chk;
}
vector<int> operator+(vector<int>& vec,int c)
{
    vec.push_back(c);
    return vec;
}
vector<int> Max(vector<int> &a,vector<int> &b)
{
    return a.size()>b.size() ? a : b;
}
int main()
{
    vector<int> a,b;
    while(input(a,b))
    {
        vector<int> LCS[a.size()+1][b.size()+1];
        for(int i=1;i<a.size();i++)
        {
            for(int j=1;j<b.size();j++)
            {
                if(a[i]==b[j])
                {
                    LCS[i][j]=LCS[i-1][j-1]+a[i];
                }
                else
                {
                    LCS[i][j]=Max(LCS[i-1][j],LCS[i][j-1]);
                }
            }
        }
        vector<int> ans=LCS[a.size()-1][b.size()-1];
        for(int i=0;i<ans.size()-1;i++)
        {
            int t=ans[i];
            cout<<store[t]<<" ";
        }
        cout<<store[ans.back()]<<endl;
    }
    return 0;
}

[UVA] 679 - Dropping Balls

題意:
有一棵full binary tree,
從根節點開始,
從左到右,由上到下,
編號1到n,
且每一個節點都為開關都為false。

現在從根節點每放一顆球,
如果求經過該節點開關為false則往左子節點去,若為true則往右子節點去,
而該節點的開關就會相反,
球跑到葉子節點停止。

輸入樹的深度 d 與 i 顆球,
輸出第 i 顆球落在編號多少。

--------------------------------------------------

方法:
模擬操作會超時,
我是推出規律,
直接在輸入前建表,
再依照輸入去查表,

應該有更直覺的方法!

另外一個小發現! 若 i 為奇數則必會落在左子樹,若為偶數必會落在右子樹。
--------------------------------------------------



/* 20150824
 * hanting
 * UVa 679 - Dropping Balls
 * C++
 */
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector<int> table[21];
vector<int> ans[21];
vector<int> ID[21];
void initial()
{
    int id=1;
    for(int i=0;i<20;i++)
    {
        table[i].resize(1<<i);
        ans[i].resize(1<<i);
        ID[i].resize(1<<i);
        for(int j=0;j<ID[i].size();j++)
        {
            ID[i][j]=id++;
        }
    }
    ans[0][0]=ID[0][0];
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<table[i].size();j++)
        {
            if(j&1)
            {
                table[i][j]=table[i][j-1]+(1<<i-1);
            }
            else
            {
                table[i][j]=table[i-1][j/2];
            }
            ans[i][table[i][j]]=ID[i][j];
        }
    }
}
int main()
{
    initial();
   // freopen("1.txt","r",stdin);
    int N;
    while(cin>>N and N!=-1)
    {
        int depth,ballN;
        for(int i=0;i<N;i++)
        {
            cin>>depth>>ballN;
            cout<<ans[depth-1][ballN-1]<<endl;
        }
    }
    return 0;
}