[UVA] 175 - Keywords

題意:
給幾個題材(profile)，每個題材都有2個以上的單字，
再給定幾個標題(title)，每個標題可能有用到某個題材的單字，
。單字每個字母皆視為小寫
。不是字母都略過
例如:
(Mis)-Conceptions == misconceptions
Metaphor in 1984, Concepts == metaphor in concepts
問:每個題材有被哪些標題取用兩個單字以上，且兩單字中間穿插的字串數在限制內

範例輸入
P: 0 rock art
P: 3 concepts conceptions
P: 1   art rock   metaphor concepts
T: Rock Art of the Maori|
T: Jazz and Rock - Art Brubeck and Elvis Presley|
T: Don't Rock --- the Boat as Metaphor in 1984, Concepts
   and (Mis)-Conceptions of an Art Historian.|
T: Carved in Rock, The Art and Craft of making promises
   believable when your `phone bills have gone
   through the roof|
#
P表示profile，數字表示被取用的兩個單字間有多少個其他單字穿插
T表示Title，最後以字元'|'表示結束這個title輸入
字元 # 為結束測資輸入

範例輸出
1: 1,2
2:
3: 1,2,3,4

1: 1,2表示
  profile1有被title1 和title2取用2個單字以上，
  且兩個單字間沒有其他單字穿插，
  title1: Rock Art of the Maori|
  title2: Jazz and Rock - Art Brubeck and Elvis Presley|
  Rock和Art間的'-'字元不是字母所以略過

2: 表示
  profile2的單字都沒有被任何title取用2個單字以上

3: 1,2,3,4表示
  profile3的單字有被title1 和 title2 和 title3 和 title4取用2個單字以上，
 且兩個單字間最多只有1個單字穿插
 title1: Rock Art of the Maori|
 title2: Jazz and Rock - Art Brubeck and Elvis Presley|
 title3: Don't Rock --- the Boat as Metaphor in 1984, Concepts
          and (Mis)-Conceptions of an Art Historian.|
 title4: Carved in Rock, The Art and Craft of making promises
          believable when your `phone bills have gone
          through the roof|


注意!
P1: 0 apple banana apple
P2: 0 apple banana

T1: apple apple只有P1符合，P2不符合(P2只有一顆apple不夠)
--------------------------------------------------

方法:
先做預處理，將每個字串做編號，
要判斷第j個title是否有用到第i個profile的兩個單字以上，
就是title[j]中的每個單字哪些是profile[i]有的，先做記號，
只要任兩個相鄰記號小於profile[i]的限制距離，
表示profile[i]有被title[j]取用到。

具體作法可以找到一個profile[i]的單字就先把profile[i]的那個單字erase，
避免重複取，最後找完再復原。


**************************************************


/* 20150927
 * hanting
 * UVa 175 - Keywords
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> //find
using namespace std;
vector<string> store;
map<string,int> Map;
int ID(string str)//為字串做編號
{
    if(Map.count(str)) return Map[str];
    else
    {
        store.push_back(str);
        return Map[str]=store.size()-1;
    }
}
void normalize(string &str)//將不是字母的字元去掉
{
    string tmp="";
    for(int i=0;i<str.size();i++)
    {
        if(isalpha(str[i])) tmp+=tolower(str[i]);
    }
    str=tmp;
}
vector<int> Distance(51);
vector<int> profile[51];
vector<int> title[51];
bool Find(int i,int id)//在第i個 profile 可以找到編號id
{
    vector<int>::iterator it=find(profile[i].begin(),profile[i].end(),id);
    if(it!=profile[i].end())
    {
        profile[i].erase(it);
        return true;
    }
    return false;
}
bool Selected(int i,int j)//第i個 profile 的字串有被第j個 Title選到，
{
    int last=-1,cur=-10000;
    for(int k=0;k<title[j].size();k++) //第j個 title的第k個字串
    {
        if(last>=0 and cur>=0 and title[j][k]==title[j][cur])
        {
            cur=k;
        }
        if(Find(i,title[j][k]))
        {
            last=cur;
            cur=k;
            if((cur-last)<=Distance[i]+1) return true;
            else if(last>=0) profile[i].push_back(title[j][last]);
        }
    }
    return false;
}
int main()
{
    string str;
    int Pidx=1;
    int Tidx=1;
    while(cin>>str and str[0]!='#')//讀P或T
    {
        if(str[0]=='P')
        {
            int dis;
            cin>>dis;
            Distance[Pidx]=dis;
            while(cin>>str)
            {
                profile[Pidx].push_back(ID(str));
                if(cin.get()=='\n') break;
            }
            Pidx++;
        }
        else//if(str[0]=='T')
        {
            while(cin>>str)
            {
                bool terminate=str[str.size()-1]=='|';
                normalize(str);
                if(str.size()==0) continue;
                title[Tidx].push_back(ID(str));
                if(terminate) break;
            }
            Tidx++;
        }
    }/*end of input*/


    vector<int> ans[51];
    for(int i=1;i<Pidx;i++)
    {
        for(int j=1;j<Tidx;j++)
        {
            vector<int> tmp(profile[i].begin(),profile[i].end());
            if(Selected(i,j)) ans[i].push_back(j);
            profile[i]=tmp;
        }
    }

    for(int i=1;i<Pidx;i++)
    {
        cout<<i<<": ";
        for(int j=0;j+1<ans[i].size();j++)
        {
            cout<<ans[i][j]<<",";
        }
        if(ans[i].size()) cout<<ans[i].back();
        cout<<endl;
    }
    return 0;
}

--------------------------------------------------
input.txt
output:
1: 1,2,3
2: 1,2,3

[UVA] 812 - Trade on Verweggistan

題意:
輸入數筆測資，
輸入N個數列，每個數列第一個數字表示該數列的元素數量，
每個數列的每個數字表示以多少錢進購產品，每個產品再以10元賣給荷蘭，
所以要求的是最大利潤，
以及要進購多少產品的前10個可能的值。
進購得產品是有依序的，也就是說要先進購第一個產品才能進購第二個產品。

測資間要空行，最後一筆測資後面不需要空行。

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

方法:
先將讀進來的每個數字改為進購第 i 個產品可得的利潤，
進而求出該數列最大可得利潤，
最後將每個數列的最大利潤相加總就是題目的第一個所求。
可以得知每個數列的最大利潤是在進購多少產品，
所以可以先記錄起來，
例如:
第一個數列有三個6,11,9，分別在進購第1個,第2個,第3個的利潤是
4,3,4
表示在連續進購 1 個或連續進購 3 個產品時可以得到最大利潤4，
那就將1 和 3記錄起來當記錄值，表示該數列可以進購1或3個都可以得到最大利潤，
最後用遞迴將每個數列的紀錄值去做組合，最後排序後輸出不重複的前10個數字。


注意!當最大利潤是0時，進購的產品數量也可以是0。

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

/* 20150923
 * hanting
 * UVa 812 - Trade on Verweggistan
 * C++
 */
#include <iostream>
#include <vector>
#include <cstring> //memset
#include <algorithm> //sort
#include <set>
using namespace std;
void DFS(vector<int> *vec,int N,set<int> &Set,int sum,int cur)
{
    if(cur==N)
    {
        Set.insert(sum);
    }
    else
    {
        for(int i=0;i<vec[cur].size();i++)
        {
            int tmp=vec[cur][i];
            DFS(vec,N,Set,sum+tmp,cur+1);
        }
    }
}
int main()
{
    int N;
    int caseN=0;
    while(cin>>N and N)
    {
        vector<int> profit[N];
        vector<int> NumToBuy[N];
        int Max[N];
        memset(Max,0,sizeof(Max));
        int MaximumProfit=0;
        for(int i=0;i<N;i++)
        {
            int numN;
            cin>>numN;
            for(int j=0;j<numN;j++)
            {
                int num;
                cin>>num;
                profit[i].push_back(10-num);
                if(j) profit[i][j]+=profit[i][j-1];
                Max[i]=max(Max[i],profit[i][j]);
            }
            if(Max[i]==0) NumToBuy[i].push_back(0);
            for(int j=0;j<numN;j++)
            {
                if(profit[i][j]==Max[i])
                    NumToBuy[i].push_back(j+1);
            }
            MaximumProfit+=Max[i];
        }
        set<int> Set;
        DFS(NumToBuy,N,Set,0,0);

        if(caseN) cout<<endl;
        cout<<"Workyards "<<++caseN<<endl;
        cout<<"Maximum profit is "<<MaximumProfit<<"."<<endl;
        cout<<"Number of pruls to buy:";
        int cnt=0;//輸出前10個即可
        for(set<int>::iterator it=Set.begin();it!=Set.end() and cnt<10;++it,cnt++)
        {
            cout<<" "<<*it;
        }
        cout<<endl;

    }
    return 0;
}

[UVA] 191 - Intersection

題意:
給一條線段和一個四方形，
判斷線段是否與四方形有香蕉。

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

方法:
注意喔!四方形他是給你對角兩點，但不一定是左上右下，要自己判斷!

線段有起始點和終點，
有兩點就可以求出線段斜率，斜率 = (y1-y0)/(x1-x0) = (終點y-起點y)/(終點x-起點x)
垂直線要另外判斷，斜率用很大的數字表示。

先判斷該線段是否可能相交四方形，
線段的兩點x要與四邊形的左右x交疊，
兩點y要與四邊形的上下交疊，

再來判斷線段有沒有交四邊形，
假設線段斜率是m，
斜率為m的線段有無限條，
但是通過起點終點的只有一條，而直線方程式有一常數(位移量)，y=mx+a的a就是常數
現在將四邊形的四個頂點帶進去斜率為m的線段都會各自得到1個常數，
若四個常數有>=a也有<=a則表示四個點分布在線段兩邊，也就是線段跟四邊形有相交。


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

/* 20150922
 * hanting
 * UVa 191 - Intersection
 * C++
 */
#include <iostream>
using namespace std;
struct point
{
    double x,y;
    point(double _x=0,double _y=0):x(_x),y(_y){}
    friend istream& operator>>(istream& in,point &p)
    {
        in>>p.x>>p.y;
        return in;
    }
};
struct rectangle
{
    point topLeft,bottomRight;
    point topRight,bottomLeft;
    point v1,v2;
    friend istream& operator>>(istream& in,rectangle &r)
    {
        in>>r.v1>>r.v2;
        r.Build();
        return in;
    }
    void Build()//建立四邊形四個頂點
    {
        if(v1.x>v2.x)
        {
            if(v1.y>v2.y)
            {
                topRight=v1;
                bottomLeft=v2;

                topLeft=point(bottomLeft.x,topRight.y);
                bottomRight=point(topRight.x,bottomLeft.y);
            }
            else
            {
                bottomRight=v1;
                topLeft=v2;

                bottomLeft=point(topLeft.x,bottomRight.y);
                topRight=point(bottomRight.x,topLeft.y);
            }
        }
        else
        {
            if(v1.y>v2.y)
            {
                topLeft=v1;
                bottomRight=v2;

                topRight=point(bottomRight.x,topLeft.y);
                bottomLeft=point(topLeft.x,bottomRight.y);
            }
            else
            {
                bottomLeft=v1;
                topRight=v2;

                bottomRight=point(topRight.x,bottomLeft.y);
                topLeft=point(bottomLeft.x,topRight.y);
            }
        }
    }
    inline bool xCover(point &start,point &End)
    {
        return !(start.x>topRight.x and End.x>topRight.x) and !(start.x<topLeft.x and End.x<topLeft.x);
    }
    inline bool yCover(point &start,point &End)
    {
        return !(start.y>topRight.y and End.y>topRight.y) and !(start.y<bottomLeft.y and End.y<bottomLeft.y);
    }
};
struct line
{
    point start,End;
    double m,a;//y=mx-a
    friend istream& operator>>(istream& in,line &l)
    {
        in>>l.start>>l.End;
        l.BuildEquation();
        return in;
    }
    void BuildEquation()
    {
        if(start.x==End.x)
            m=0x3fffffff;
        else
            m=(start.y-End.y)/(start.x-End.x);
        a=m*start.x-start.y;//a=mx-y
    }
    double equation(point &p)
    {
        return m*p.x-p.y;
    }
    bool intersect(rectangle &rec)
    {
        if(!rec.xCover(start,End) or !rec.yCover(start,End))
            return false;
        if(m==0x3fffffff) return true;
        double e1,e2,e3,e4;
        e1=equation(rec.topLeft);
        e2=equation(rec.topRight);
        e3=equation(rec.bottomLeft);
        e4=equation(rec.bottomRight);
        bool positive,negative;//判斷四個頂點是否在線段左右
        positive=e1>=a or e2>=a or e3>=a or e4>=a;
        negative=e1<=a or e2<=a or e3<=a or e4<=a;
        return positive and negative;
    }
};
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        line l;
        rectangle rec;
        cin>>l>>rec;
        cout<<(l.intersect(rec) ? 'T':'F')<<endl;
    }
    return 0;
}

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

input.txt
output.txt

[UVA] 10221 - Satellites

題意:
如圖，給你圓上兩點的夾角，和點與圓中心的距離，
求出兩點的弧長與弦長。

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

方法:
如果夾角超過180度則用360去減夾角，
例如兩點夾角200度，也就是說兩點其實是夾角160度。
60 degree =  1 min

弧長:圓周長*(給的角度/360)。

弦長:有邊有角度，餘弦定理。


注意! PI要用2*acos(0)


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

/* 20150922
 * hanting
 * UVa 10221 - Satellites
 * C++
 */
#include <iostream>
#include <cmath>//cos,sqrt
#include <iomanip>//setprecision
using namespace std;
#define PI 2*acos(0)
int main()
{
    double s,a;
    string str;
    while(cin>>s>>a>>str)
    {
        if(a>180) a=360-a;
        double r=6440+s;
        double arc,chord;
        if(str=="min")
        {
            a/=60; //degree=min/60
        }
        arc=2*PI*r*a/360.;
        chord=sqrt(r*r+r*r-2*r*r*cos(PI*a/180.));
        cout<<fixed<<setprecision(6)<<arc<<" "<<chord<<endl;
    }
    return 0;
}

[UVA] 478 - Points in Figures: Rectangles, Circles, and Triangles

題意:
輸入三種圖形，
再輸入點，判斷該點在哪幾個圖形裡面(不包括邊上)。
r是rectangle 四方形(輸入左上和右下的點)
c是circle 圓形(輸入中心點和半徑)
t是triangle 三角形(輸入三個頂點)

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

方法:
四方形:
    只要判斷x是否在四方形的左右兩邊裡面，y是否在四方形的上下兩邊。
圓形:
    判斷點到圓中心的距離是否小於半徑。
三角形:
    該點連接到三角形三個頂點可以切成三個三角形，
    任三點可以形成兩個向量，兩個向量可以形成一個三角形，
    所以!如果三個小三角形面積總和等於原始大三角形面積，則點在三角形內
    另外需要注意的是，其中一個小三角形不能為零(若為零表示點在邊上)。
--------------------------------------------------

/* 20150922
 * hanting
 * UVa 478 - Points in Figures: Rectangles, Circles, and Triangles
 * C++
 */
#include <iostream>
#include <vector>
#include <cstdlib>//fabs
#include <cmath>//sqrt
#include <algorithm>//sort
using namespace std;
#define DISTANCE(a,b) sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
#define VEC(a,b) point(b.x-a.x,b.y-a.y)
#define AREA(a,b) fabs((a.x*b.y-a.y*b.x)/2)
struct point
{
    double x,y;
    point(double _x=0,double _y=0):x(_x),y(_y){}
    friend istream& operator>>(istream& in,point &p)
    {
        in>>p.x>>p.y;
        return in;
    }
    bool operator!=(double d)
    {
        return x!=9999.9 and y!=9999.9;
    }
};
struct rectangle
{
    int id;
    point upLeft,lowRight;
    friend istream& operator>>(istream& in,rectangle &rec)
    {
        in>>rec.upLeft>>rec.lowRight;
        return in;
    }
    bool contain(const point &p)
    {
        return p.x>upLeft.x and p.x<lowRight.x and p.y>lowRight.y and p.y<upLeft.y;
    }
};
struct circle
{
    int id;
    point center;
    double radius;
    friend istream& operator>>(istream& in,circle &cir)
    {
        in>>cir.center>>cir.radius;
        return in;
    }
    bool contain(const point &p)
    {
        return DISTANCE(p,center)<radius;
    }
};
struct triangle
{
    int id;
    point v1,v2,v3;
    friend istream& operator>>(istream& in,triangle &tri)
    {
        in>>tri.v1>>tri.v2>>tri.v3;
        return in;
    }
    bool contain(const point &p)
    {
        double a1,a2,a3;
        a1=AREA(VEC(p,v1),VEC(p,v2));
        a2=AREA(VEC(p,v2),VEC(p,v3));
        a3=AREA(VEC(p,v1),VEC(p,v3));
        return a1 and a2 and a3 and (a1+a2+a3)- AREA(VEC(v1,v2),VEC(v1,v3))<1e-8;
    }
};
int main()
{
    char ch;
    vector<rectangle> rec;
    vector<circle> cir;
    vector<triangle> tri;
    int idN=1;
    while(cin>>ch and ch!='*')
    {
        if(ch=='r')
        {
            rectangle tmp;
            cin>>tmp;
            tmp.id=idN;
            rec.push_back(tmp);
        }
        else if(ch=='c')
        {
            circle tmp;
            cin>>tmp;
            tmp.id=idN;
            cir.push_back(tmp);
        }
        else//if(ch=='t)
        {
            triangle tmp;
            cin>>tmp;
            tmp.id=idN;
            tri.push_back(tmp);
        }
        idN++;
    }

    point p;
    int pointN=1;
    while(cin>>p and p!=9999.9)
    {
        vector<int> ans;
        sort(ans.begin(),ans.end());
        for(int i=0;i<rec.size();i++)
        {
            if(rec[i].contain(p))
            {
                ans.push_back(rec[i].id);
            }
        }
        for(int i=0;i<cir.size();i++)
        {
            if(cir[i].contain(p))
            {
                ans.push_back(cir[i].id);
            }
        }
        for(int i=0;i<tri.size();i++)
        {
            if(tri[i].contain(p))
            {
                ans.push_back(tri[i].id);
            }
        }
        if(ans.size())
        {
            for(int i=0;i<ans.size();i++)
            {
                cout<<"Point "<<pointN<<" is contained in figure "<<ans[i]<<endl;
            }
        }
        else
        {
            cout<<"Point "<<pointN<<" is not contained in any figure"<<endl;
        }
        pointN++;
    }
    return 0;
}

[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;
}