2015年11月1日 星期日

[UVA] 10602 - Edit Nottobad

題目連結

題意:

以第一個輸入為例,
this
thin
thing
第一個輸入 this 這個字串,
可以刪除最後幾個字母後再加上幾個字母可以變成另一個字串,
像是刪除 s 後再加上 n 可以變成 thin,
然後不刪除直接加上 g 就可以變成 thing。

另一個例子,
popcorn
apple
apricote
plum
第一個輸入不能改,就是 popcorn 這個字串,
接著刪除掉 opcorn 再加上 lum 就可以變成 plum,
接著刪除 plum 再加上 apple 就可以變成 apple,
接著刪除 ple 再加上 ricote 就可以變成 apricote,

他要求的是你要加上的所有字串的總長度要最小,
最後再加上第一個輸入的字串的長度就是要輸出的數字。

例如以上兩個例子,
第一個例子 n + g 長度2
this + 2 = 6
第二個例子 lum + apple + ricote 長度14
popcorn + 14 = 21

接著要輸出每個字串的順序。


我的作法:

我是用suffix tree的方式,
將每個字串存在一棵多元樹裡面,










像這樣將每個字串存進去,
從根節點開始,
如果該節點的字元跟要存的字串的字元相同就繼續往下走,
如果不同就分支,
例如圖中的 n 就是一個分支,
'*' 表示依個字串結束,
存完後,就DFS就好囉~
輸出整個樹的全部節點的數量(不包括'*'),

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

/* 20151101
 * hanting
 * UVa 10602 - Edit Nottobad
 * C++
 * suffix tree
 */
#include <iostream>
#include <vector>
using namespace std;
struct Tree
{
    char ch;
    vector<Tree*> node;
};
vector<string> ans;
void BuildTree(Tree *root,string str);
int DFS(Tree *root,string str);
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        ans.clear();
        Tree *head = new Tree;
        int strN;
        cin >> strN;
        for(int i = 0; i < strN; i++)
        {
            string str;
            cin >> str;
            BuildTree(head, str);
        }
        cout << DFS(head, "")-1 << endl;
        for(int i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << endl;
        }
    }
    return 0;
}
void BuildTree(Tree *root,string str)
{
    int i;
    bool New = true;
    for(i = 0; i < root->node.size(); i++)
    {
        if(root->node[i]->ch == str[0])
        {
            New = false;
            BuildTree(root->node[i], str.substr(1));
            break;
        }
    }
    if(New)//分支
    {
        Tree *NewRoot;
        root->node.push_back(NewRoot);
        root->node[root->node.size()-1] = new Tree;
        if(str.size())
        {
            root->node[root->node.size()-1]->ch = str[0];
            BuildTree(root->node[root->node.size()-1], str.substr(1));
        }
        else
        {
            root->node[root->node.size()-1]->ch = '*';
        }
    }
}
int DFS(Tree *root,string str)
{
    int cnt = 0;
    if(root->node.size())
    {
        cnt++;
        for(int i = 0; i < root->node.size(); i++)
        {
            cnt += DFS(root->node[i], str + root->node[i]->ch);
        }
    }
    else //一個字串結束
    {
        ans.push_back(str.substr(0,str.size()-1));
    }
    delete(root);
    return cnt;
}

2015年10月22日 星期四

[UVA] 10023 - Square root

題目連結

題意:

給你一個整數 n,求出 n 的 正平方根。
n 介於 1 到 10的1000次方。
--------------------------------------------------

我的作法:

利用二分法找根,雖然效率不好但可以過!
可以先寫 int 版本進行測試,
測試OK再將 int 改成大樹class,
重載有用到的運算子~

注意喔!題目中有一句話:
It is guaranteed, that for given Y , X will be always an integer.
的中文翻譯是
保證Y不會是一個整數的平方哦 !
所以像是 99 開方根要輸出 9

--------------------------------------------------
/* 20151023
 * hanting
 * UVa 10023 - Square root
 * C++
 */
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
using namespace std;
#define Capacity 8//每一格存8位數
const int maxValue=1e8;//每一格最大儲存值
const int Size = 255;// 1000位數*2/每一格存8位數

class BigInteger
{
private:
    long long value[Size];
    int digit;
    void digitCheck();
    void Carry();
    void init();
public:
    BigInteger():digit(0)
    {
        memset(value, 0 ,sizeof(value));
    }
    friend istream& operator>>(istream& in,BigInteger &B);
    friend ostream& operator<<(ostream& out,BigInteger &B);
    void operator = (int n);
    bool operator < (BigInteger &B);
    bool operator > (BigInteger &B);
    BigInteger operator + (int n);
    BigInteger operator + (BigInteger &B);
    BigInteger operator * (BigInteger &B);
    BigInteger operator / (int n);
    void operator--(int t);
};
BigInteger SquareRoot(BigInteger &num)
{
    BigInteger low, up, mid;
    low = 1;
    up = num;
    mid = (low + up) / 2;
    while(low < up)
    {
        if(mid * mid > num)
        {
            up = mid;
            mid = (low + up) / 2;
        }
        else if(mid * mid < num)
        {
            low = mid + 1;
            mid = (low + up) / 2;
        }
        else
        {
            return mid;
        }
    }
}
int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        BigInteger num;
        cin >> num;
        BigInteger ans = SquareRoot(num);
        if(ans*ans > num)//99開根號是9
        {
            ans--;
        }
        cout << ans << endl;
        if(testCase) cout<<endl;
    }
    return 0;
}
void BigInteger::init()
{
    memset(value , 0 ,sizeof(value));
    digit=0;
}
istream& operator>>(istream& in,BigInteger &B)
{
    B.init();
    string str;
    in >> str;
    while( str.size() >= Capacity )
    {
        B.value[B.digit++] = atoi((char*)(str.substr(str.size()-Capacity)).c_str());
        str.erase(str.size()-Capacity,Capacity);
    }
    if(str.size())
    {
        B.value[B.digit++] = atoi((char*)str.c_str());
    }
    return in;
}

ostream& operator<<(ostream& out,BigInteger &B)
{
    out << B.value[B.digit-1] ;
    for(int i = B.digit-2; i >= 0;i--)
    {
        out << setw(Capacity) << setfill('0') << B.value[i] ;
    }
    return out;
}
void BigInteger::digitCheck()
{
    while(!value[digit-1]) digit--;
}
void BigInteger::Carry()
{
    for(int i = 0; i < digit ; i++)
    {
        value[i+1] += value[i]/maxValue;
        value[i] %= maxValue;
    }
}
void BigInteger::operator = (int n)
{
    value[0] = n;
    digit = 1;
    /*Carry();
    digitCheck();*/
}
bool BigInteger::operator < (BigInteger &B)
{
    if(digit > B.digit) return false;
    else if (digit < B.digit) return true;
    else//digit == B.digit
    {
        for(int i = digit-1; i >= 0; i--)
        {
            if(value[i] > B.value[i]) return false;
            else if(value[i] < B.value[i]) return true;
        }
    }
    return false;
}
bool BigInteger::operator > (BigInteger &B)
{
    if(digit > B.digit) return true;
    else if (digit < B.digit) return false;
    else//digit == B.digit
    {
        for(int i = digit-1; i >= 0; i--)
        {
            if(value[i] > B.value[i]) return true;
            else if(value[i] < B.value[i]) return false;
        }
    }
    return false;
}
BigInteger BigInteger::operator + (int n)
{
    BigInteger result = *this;
    result.value[0] += n;
    result.Carry();
    result.digitCheck();

    return result;
}
BigInteger BigInteger::operator + (BigInteger &B)
{
   BigInteger result;
   for(int i = 0; i < digit or i < B.digit ;i++)
   {
       result.value[i] = value[i] + B.value[i];
   }
   result.digit = max(digit, B.digit) + 1;
   result.Carry();
   result.digitCheck();
   return result;
}
BigInteger BigInteger::operator * (BigInteger &B)
{
    BigInteger result;
    for(int i = 0; i < digit ;i++)
    {
        for(int j = 0; j < B.digit ;j++)
        {
            result.value[i+j] += value[i] * B.value[j];
        }
    }
    result.digit = digit + B.digit + 1;
    result.Carry();
    result.digitCheck();

    return result;
}
BigInteger BigInteger::operator / (int n)
{
    BigInteger result = *this;
    for(int i = digit-2; i >= 0 ; i--)
    {
        result.value[i] += maxValue*(result.value[i+1]&1);
        result.value[i+1] /= 2;
    }
    result.value[0] /= 2;
    result.digitCheck();
    return result;
}
void BigInteger::operator--(int t)
{
    value[digit-1]--;
    for(int i=digit-2;i>=0;i--)
    {
        value[i]+=maxValue-1;
    }
    Carry();
    digitCheck();
}

2015年10月20日 星期二

[UVA] 10125 - Sumsets

題目連結

題意:

給你一堆數字,
問能不能找到 a + b + c =  d,
如果可以,求出 最大的 d。
--------------------------------------------------

我的作法:

把柿子變成 a + b = d - c,
然後窮舉 a b 算出 A= a+b 再 窮舉 d c 算出 B= d-c,
如果有A等於B再去判斷 a b 是否有任一個數是c d,
例如:
1 , 5 , 11 , 13
可以找到
A = 1 + 5 = 6,
B = 11 - 5 = 6 ,
雖然A=B,
但其實 5 是同一個,所以是找不到 a + b + c = d 的可能!
--------------------------------------------------
/* 20151010
 * hanting
 * UVa 10125 - Sumsets
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> //find
using namespace std;
int main()
{
    int N;
    while(cin>>N and N)
    {
        int num[N];
        for(int i=0;i<N;i++)
        {
            cin>>num[i];
        }
        bool No=true;
        int maxi=-0x7fffffff;
        /*a+b*/
        map<int,vector<pair<int,int> > > ADD;
        for(int i=0;i<N;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                int add=num[i]+num[j];
                ADD[add].push_back(pair<int,int>(i,j));
            }
        }
        /*d-c*/
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(i!=j)
                {
                    int sub=num[i]-num[j];
                    for(int k=0;k<ADD[sub].size();k++)
                    {
                        int tmpi=ADD[sub][k].first , tmpj=ADD[sub][k].second;
                        if(i!=tmpi and i!=tmpj and j!=tmpi and j!=tmpj)
                        {
                            No=false;
                            maxi=max(maxi,num[i]);
                            break;
                        }
                    }
                }
            }
        }
        if(No)
            cout<<"no solution"<<endl;
        else
            cout<<maxi<<endl;
    }
    return 0;
}

[UVA] UVa 756 - Biorhythms

題目連結

題意

給你四個數字 r1 , r2 , r3 ,d;
x ≡ r1 ( mod 23 )
x ≡ r2 ( mod 28 )
x ≡ r3 ( mod 33 )
求出x後,
如果 x > d ,輸出 x - d
如果 x < d ,輸出 x + 21252 - d
--------------------------------------------------

我的作法

這裡有一個小知識喔!
13 ≡ 2 (mod 11)
不是說 13 % 11 等於2喔!
是說 13 % 11 == 2 %11的意思,稱作 13 和 2 同餘,
所以也可以寫成像這樣
13 ≡ 35 (mod 11)
因為 13 % 11 == 35 % 11 == 2,
所以,
當題目給你的 r1 >23 時, 例如 r1 = 25 ,
你可以先把他變成 r1 % 23 = 25 % 23 = 2
因為 x ≡ 25 (mod 23) 就是 x ≡ 2 (mod 23)。

*****
這種類型的題目就是將柿子展開!
一層一層求解,
這是我們老師提供給我們看的解法,可以參考












下面有我把這題的柿子展開的方程式!

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

/* 20151020
 * hanting
 * UVa 756 - Biorhythms
 * C++
 */
#include <iostream>
using namespace std;
/* 已知 r1 ,r2 ,r3
 *  x = 23 * p1 + r1 ,r1 < 23
 *  x = 23 * (28 * p2 + R2) + r1 ,R2 < 28
 *     = 23 * 28 * p2 + [ (23 * R2) + r1 ]
 *     => r2 = [ (23 * R2) + r1 ] % 28
 *  x = 23 * 28 * p2 + [ (23 * R2) + r1 ]
 *     = 23 * 28 * (33 * p3 + R3) + [ (23 * R2) + r1 ] ,R3 < 33
 *     = 23 * 28 * 33 * p3 + { (23 * 28 * R3) +  [ (23 * R2) + r1 ] }
 *     => r3 = { (23 * 28 * R3) +  [ (23 * R2) + r1 ] } % 33
 */
inline int solve(int r1 , int r2 , int r3)
{
    int x;
    int R2 = 0 , R3 = 0;
    for(; R2 < 28 ; R2++)
    {
        if(r2 == (23 * R2 + r1) % 28) break;
    }
    for(; R3 < 33 ; R3++)
    {
        if(r3 == ((23 * 28 * R3) + ((23 * R2) + r1)) % 33) break;
    }
    int k = ( (23 * 28 * R3 ) +  ( (23 * R2) + r1 ) );
    for(int p3 = 1 ; ; p3--)
    {
        int tmp = 23 * 28 * 33 * p3 + k;
        if(tmp <= 0 ) break;
        x = tmp;
    }
    return x;
}
int main()
{
    int phy , emo , intel, today;
    int case_num = 1;
    while(cin >> phy >> emo >> intel >> today and phy != -1)
    {
        int x = solve( phy%23 , emo%28 , intel%33 );
        int ans = ((x + 21252) - today) % 21252;
        cout << "Case " << case_num++ << ": the next triple peak occurs in " << (!ans ? 21252 : ans )   << " days." << endl;
    }
    return 0;
}

2015年10月9日 星期五

[UVA] 1016 - Silly Sort

題目連結

題意:

給一個數列,
一次只能做一個交換,
每做一次a b交換,就要將sum加入a跟b,
最後sum要最小,且要把這個數列排序好。
範例輸入:
3 2 1
1跟3交換   1 2 3  ,sum=4

8 1 2 4
1跟2交換  8 2 1 4,sum=3
1跟4交換  8 2 4 1,sum=3+5
1跟8交換  1 2 4 8,sum=3+5+9=17

1 8 9 7 6
1跟6交換 6 8 9 7 1,sum=7
1跟9交換 6 8 1 7 9,sum=7+10
1跟7交換 6 8 7 1 9,sum=7+10+8
1跟8交換 6 1 7 8 9,sum=7+10+8+9
1跟6交換 1 6 7 8 9,sum=7+10+8+9+7=41




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

我的作法:

 將數列分成n個cycle,
每個Cycle表示該值要到下一個值的位置,
例如藍色cycle:
6要到8的位置,
8要到7的位置,
7要到9的位置,
9要到6的位置。

取一個值可以讓cycle中的每一個值到正確位置
例如:
取6當交換的元素,
6跟9做交換,9就到正確位置了,
6再繼續跟7做交換,7就到正確位置了,
6再跟8做交換,8就到正確位置,
最後6也會到正確位置。

所以如果用cycle中的最小值去做交換,
那麼sum一定最小。


但是!
如果先把6跟數列中最小值1交換,
再用1去做cycle交換的元素,
最後再把6跟1交換回來,
可能讓sum更小喔!
所以要兩個做判斷去擇優!












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

/* 20151009
 * hanting
 * UVa 1016 - Silly Sort
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm> //sort,min_element
#include <cstring> //memset
using namespace std;
struct node
{
    int num;
    int origPos;
    bool operator<(const node &a)const
    {
        return num<a.num;
    }
};
int main()
{
    int N;
    int caseN=1;
    while(cin>>N and N)
    {
        vector<node> vec(N);
        for(int i=0;i<N;i++)
        {
            cin>>vec[i].num;
            vec[i].origPos=i;
        }
        sort(vec.begin(),vec.end());
        int AllMin=vec[0].num;
        bool visit[N];
        memset(visit,0,sizeof(visit));
        int sum=0;
        for(int i=0;i<N;i++)
        {
            vector<int> Cycle;
            if(visit[i]==false)//i位置這個數字還不是任一cycle的元素
            {
                visit[i]=true;
                Cycle.push_back(vec[i].num);//cycle的第一個元素
                int next=vec[i].origPos;
                while(visit[next]==false)//建立cycle
                {
                    visit[next]=true;
                    Cycle.push_back(vec[next].num);
                    next=vec[next].origPos;
                }
                int CycleMin=*std::min_element(Cycle.begin(),Cycle.end());
                if(2*(CycleMin+AllMin)+(AllMin)*(Cycle.size()-1) >= CycleMin*(Cycle.size()-1) )
                {
                    for(int i=0;i<Cycle.size();i++)
                    {
                        sum+=Cycle[i]+CycleMin;
                    }
                    sum-=CycleMin*2;
                }
                else
                {//若將AllMin跟CycleMin交換再去做Cycle中的轉換總和比較少
                    for(int i=0;i<Cycle.size();i++)
                    {
                        sum+=Cycle[i]+AllMin;
                    }
                    sum+=(CycleMin+AllMin);
                }
            }
        }
        cout<<"Case "<<caseN++<<": "<<sum<<endl<<endl;
    }

    return 0;
}

2015年10月6日 星期二

[UVA] 1026 - The Solar System

題意:
克普勒定律,
1.每一個行星都沿各自的橢圓軌道環繞太陽,而太陽則處在橢圓的一個焦點中。
2.在相等時間內,太陽和運動著的行星的連線所掃過的面積都是相等的。
3.(t1/t2)平方=(a1/a2)三方。
參考維基百科

現在有兩顆星球,
給你第一顆星球的半長軸(a1),半短軸(b1),還有週期(t1),
再給你另一顆星球的半長軸(a2)和半短軸(b2),
在給一個時間 t,
問第二顆星球從起始點(a2,0),
經過 t 時間後,移動後的座標。


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

我的作法:
幾個數學知識可以先背起來,
。π = 2*acos(0)
。橢圓面積 = π *半短軸*半長軸
。中心到焦點的距離 c =開根號(半長軸平方 - 半短軸平方)
。橢圓扇形面積 = π *半短軸*半長軸/2要先算出第二顆星球的週期 t2,
可以利用克普勒第三定律求出,
有週期後,可以算出行星經過 t 時間後走的面積(繞著焦點),
如下圖,










藍色區塊 = 經過 t 時間後行星走的面積
               = 橢圓面積(πab) * t/t2
               = 橢圓扇形面積(θab/2) - 紅色三角形面積(cbsinθ)


利用二分法,找出角度θ,
所求座標(x,y)=( 半長軸*cosθ , 半短軸*sinθ)。

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

/* 20151007
 * hanting
 * UVa 1026 - The Solar System
 * C++
 */
#include <iostream>
#include <iomanip> //setprecision
#include <cmath> //acos,sqrt,sin,cos
using namespace std;
#define pi 2*acos(0)
double a1,b1,t1,a2,b2,t2,t;
int main()
{
    int caseN=1;
    while(cin>>a1>>b1>>t1>>a2>>b2>>t and a1+b1+t1)
    {
        t2=sqrt(t1*t1*a2*a2*a2/a1/a1/a1);//  t1平方/t2平方 = a1三方/a2三方
        t=fmod(t,t2);
        double ellipseArea = pi*a2*b2;//橢圓面積
        double runArea=ellipseArea*(t/t2);//t時間行星行走的面積
        double low=0,up=2*pi;
        double mid=(low+up)/2;//theta

        double c2=sqrt(a2*a2-b2*b2);//中心到焦點的距離
        while(up-low>1e-7)
        {
            double area=(mid*a2*b2)/2. - (c2*b2*sin(mid))/2.;
            //令theta為角度,介於0到2pi
            //扇形面積 = theta*a*b/2  , 三角形面積 = 底(c2)*高(b2*sin(theta))/2
            if(area<runArea)
            {
                low=mid;
                mid=(low+up)/2;
            }
            else
            {
                up=mid;
                mid=(low+up)/2;
            }
        }
        cout<<"Solar System "<<caseN++<<": "<<fixed<<setprecision(3)<<a2*cos(low)<<" "<<b2*sin(low)<<endl;
    }
    return 0;
}

2015年10月4日 星期日

[UVA] 714 - Copying Books

題意:
給你很多書的頁數,
要你分成n份後,頁數最多的那一份他的頁數要盡量小,
範例輸入:
9 3 //9本書,分3份
100 200 300 400 500 600 700 800 900 //9本書的頁數
可以這樣分
100 200 300  (總頁數=100+200+300=600)
400 500 600  (總頁數=400+500+600=1500)
700 800 900  (總頁數=700+800+900=2400)
頁數最多的那一份總頁數是2400

也可以這樣分
100 200 300 400 500   (總頁數=100+200+300+400+500=1500)
600 700   (總頁數=600+700=1300)
800 900   (總頁數=800+900=1700)
頁數最多的那一份總頁數是1700,
就比上一個分法少。

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

我的作法:
令P(x)為分成n堆後每一堆的總頁數都<=x,
回傳true表示可能,回傳false表示不可能(例如上面的範例,P(10)就是false),
利用二分法,
lower=所有書當中頁數最多的(因為不管怎麼分堆,其中一堆一定有這本書的頁數),
upper=所有書的頁數總和(全部分成一堆),
用middle去帶入P(x),
若P(middle)為true,表示x可以更小,
若為false,表示x應該要更大。

P(x):
在分堆的時候第一堆從最右邊的頁數先塞,
不能塞了就換下一堆,
在過程中可以先儲存'/'的位置!
另外需要注意的是:
剩餘書的數量要>=剩餘堆的數量,
因為每一堆都至少要有一本書

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

/* 20151004
 * hanting
 * UVa 714 - Copying Books
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm> //max_element
using namespace std;
#define MID(x,y) (x+y)/2
vector<int> page;
vector<int> group;
long long sumOfPage()//所有頁數的總和
{
    long long sum=0;
    for(int i=0;i<page.size();i++)
    {
        sum+=page[i];
    }
    return sum;
}
bool P(long long x)//各個堆的總數都小於等於x
{
    group.assign(group.size(),0);
    long long sum=0;
    int j=0;
    int i=page.size()-1;
    for(;i>=0;i--)
    {
        if(j>=group.size()) break;
        if(sum+page[i] <= x and i+1>=group.size()-j)//書的數量要大於等於scriber的數量
        {
            sum+=page[i];
            group[j]=i;//將'/'的位置紀錄
        }
        else
        {
            j++;
            i++;
            sum=0;
        }
    }
    return i==-1;
}
void solution()
{
    long long low=*std::max_element(page.begin(),page.end());//最小是所有書當中頁數最多的
    long long up=sumOfPage();//最大是所有書的頁數總和
    long long mid=MID(low,up);
    while(low<up)
    {
        if(P(mid))
        {
            up=mid;
            mid=MID(low,up);
        }
        else
        {
            low=mid+1;
            mid=MID(low,up);
        }
    }
    P(low);
    reverse(group.begin(),group.end());
    int j=1;
    for(int i=0;i<page.size();i++)
    {
        if(j<group.size() and i==group[j])
        {
            cout<<"/ ";
            j++;
        }
        cout<<page[i];
        if(i!=page.size()-1) cout<<" ";
        else cout<<endl;
    }
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        int bookN,groupN;
        cin>>bookN>>groupN;
        page.assign(bookN,0);
        group.assign(groupN,0);
        for(int i=0;i<bookN;i++)
        {
            cin>>page[i];
        }
        solution();
    }
    return 0;
}