[UVA] 11936 - The Lazy Lumberjacks

/*20150131 hanting*/
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int edge[3];
        cin>>edge[0]>>edge[1]>>edge[2];
        sort(edge,edge+3);
        cout<<(edge[0]+edge[1]>edge[2] ? "OK":"Wrong!!")<<endl;
    }
    return 0;
}

[UVA] 610 - Street Directions

/*20150131 hanting*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool Find(vector<int> &vec,int i)
{
    vector<int>::iterator it=find(vec.begin(),vec.end(),i);
    return (it!=vec.end());
}
int DFS(int *visit,vector<int> *node,int vertex,int parent,vector<int> *store)
{
    static int time=0;
    int mini=time;
    visit[vertex]=time++;
    for(int i=0;i<node[vertex].size();i++)
    {
        int temp=mini;
        if(visit[ node[vertex][i] ]==-1)
        {
            store[vertex].push_back(node[vertex][i]);//路徑儲存
            temp=DFS(visit,node,node[vertex][i],vertex,store);
            if(temp>visit[vertex])//找橋
            {
                store[ node[vertex][i] ].push_back(vertex);
            }
        }
        else if(node[vertex][i]!=parent)//其他路徑//backedge
        {//若已存1 3 不必存3 1
            if(!Find(store[ node[vertex][i] ],vertex))store[vertex].push_back(node[vertex][i]);
            temp=visit[  node[vertex][i] ];
        }
        if(temp<mini) mini=temp;

    }
    return mini;//由backedge能回溯的最小visit
}
int main()
{
    int nodeNum,connectNum;
    int Times=0;
    while(cin>>nodeNum>>connectNum && nodeNum+connectNum)
    {
        cout<<++Times<<endl<<endl;
        vector<int> node[nodeNum+1];
        for(int i=0;i<connectNum;i++)
        {
            int a,b;
            cin>>a>>b;
            node[a].push_back(b);
            node[b].push_back(a);
        }

        int visit[nodeNum+1];
        vector<int> store[nodeNum+1];
        fill(visit,visit+nodeNum+1,-1);
        for(int i=1;i<=nodeNum;i++)
        {
            if(visit[i]==-1)
            {
                DFS(visit,node,i,-1,store);
            }
        }
        for(int i=1;i<=nodeNum;i++)
        {
            sort(store[i].begin(),store[i].end());
            for(int j=0;j<store[i].size();j++)
            {
                cout<<i<<" "<<store[i][j]<<endl;
            }
        }
        cout<<"#"<<endl;
    }
    return 0;
}

[UVA] 796 - Critical Links

/*20150131 hanting*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int DFS(vector<int> *vertex,int node,int parent,int *visit,vector<int> *store)
{
    static int Count=0;
    int mini=Count;
    visit[node]=Count++;
    for(int i=0;i<vertex[node].size();i++)
    {
        int temp=mini;
        if(visit[ vertex[node][i] ]==-1)/*子節點 沒拜訪過的*/
        {
            temp=DFS(vertex,vertex[node][i],node,visit,store);
            if(temp>visit[node])/*橋*/
            {
                int x=node;
                int y=vertex[node][i];
                if(x>y) swap(x,y);
                store[x].push_back(y);
            }
        }
        else if(vertex[node][i]!=parent)/*拜訪過 判斷回溯*/
        {
            temp=visit[ vertex[node][i] ];
        }
        if(mini>temp) mini=temp;
    }
    return mini;
}

int main()
{
    int N;
    while(cin>>N)
    {
        vector<int> vertex[N];
        vector<int> store[N];
        int visit[N];
        fill(visit,visit+N,-1);
        for(int i=0;i<N;i++)
        {
            int server,connectNum,connect;
            char c;
            cin>>server>>c>>connectNum>>c;
            for(int j=0;j<connectNum;j++)
            {
                cin>>connect;
                vertex[server].push_back(connect);
            }
        }
        for(int i=0;i<N;i++)
        {
            if(visit[i]==-1)
            {
                DFS(vertex,i,-1,visit,store);
            }
        }
        int count=0;
        for(int i=0;i<N;i++)
        {
            count+=store[i].size();
        }
        cout<<count<<" critical links"<<endl;
        for(int i=0;i<N;i++)
        {
            sort(store[i].begin(),store[i].end());
            for(int j=0;j<store[i].size();j++)
            {
                cout<<i<<" - "<<store[i][j]<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}

[UVA] 516 - Prime Land

/*20141122 hanting*/
#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s) && s!="0")
    {
        stringstream sin(s);
        int sum=1;
        int _pow;
        int num;
        while(sin>>num>>_pow) sum*=pow(num,_pow);
        sum--;
        bool Num[50000]={0};
        int prime[10000];
        int x=0;
        for(int i=2;i<50000;i++)
        {
            if(Num[i]==0)
            {
                prime[x++]=i;
                for(int j=i*2;j<50000;j+=i)
                {
                    Num[j]=1;
                }
            }
        }
        int ans[1000];
        int q=0;
        for(int i=0;sum!=1;i++)
        {
            while(sum%prime[i]==0)
            {
                ans[q++]=prime[i];
                sum/=prime[i];
            }
        }
        for(int i=q-1;i>=0;i--)
        {
            int pow=1;
            if(i!=q-1) cout<<" ";
            cout<<ans[i];
            while(i-1>=0 && ans[i-1]==ans[i])
            {
                pow++;
                i--;
            }
            cout<<" "<<pow;
        }
        cout<<endl;
    }
}

[UVA] 11879 - Multiple of 17

/*20141111 hanting*/
#include <iostream>
using namespace std;
int seventeen[105]={0};
inline bool compare(int *seventeen,int *num)
{
    for(int i=104;i>=0;i--)
    {
        if(num[i]>seventeen[i]) return 0;
        else if(num[i]<seventeen[i]) return 1;
    }
    return 1;
}
bool IsSeventeen(int* num,int p)
{
    if(compare(seventeen,num))
    {
        if((num[0]==7 && num[1]==1)||p==0) return 1;
        else return 0;
    }
    else
    {
        int d=num[0];
        d*=5;
        for(int i=0;i<p-1;i++)//shift ( remove the last number )
        {
            num[i]=num[i+1];
        }

        num[p-1]=0;
        p--;
        int sub_5d[105]={d};
        for(int i=1;i<2;i++)//carry
        {
            sub_5d[i]+=sub_5d[i-1]/10;
            sub_5d[i-1]%=10;
        }
        /*num-5d*/
        int siz=max(p,2);
        for(int i=0;i<siz;i++)
        {
            num[i]-=sub_5d[i];
        }
        for(int i=0;i<siz;i++)
        {
            if(num[i]<0)
            {
                num[i]+=10;
                num[i+1]--;
            }
        }
        if(num[siz]<0)//if( num < 5d )
        {
            num[siz]=0;
            for(int i=0;i<siz;i++)//complement
            {
                num[i]=9-num[i];
            }
            num[0]++;
            for(int i=1;i<siz;i++)//carry
            {
                num[i]+=num[i-1]/10;
                num[i-1]%=10;
            }
        }
        for(int i=104;i>=0;i--)
        {
            if(num[i]!=0)
            {
                p=i+1;
                break;
            }
            else if(i==0) p=0;
        }
        return IsSeventeen(num,p);
    }
}
int main()
{
    seventeen[0]=7;
    seventeen[1]=1;
    string s;
    while(cin>>s && s!="0")
    {
        int num[105]={0};
        int p=0;
        for(int i=s.size()-1;i>=0;i--)
        {
            num[p++]=s[i]-48;
        }
        cout<<IsSeventeen(num,p)<<endl;
    }
    return 0;
}

[UVA] 10140 - Prime Distance

/*20141108 hanting*/
#include <iostream>
#include <cmath>
#include <sstream>
using namespace std;
bool Num[100000];
int prime[10000];
int x=0;
bool isprime(unsigned int num)
{
    if(num<100000) return Num[num]==0 ? 1:0;
    int s=sqrt(num);//另存s//在for迴圈會慢
    for(int i=0;prime[i]<=s;i++)
    {
        if(num%prime[i]==0) return 0;
    }
    return 1;
}
int main()
{
    for(unsigned int i=2;i<100000;i++) Num[i]=0;
    Num[1]=1;
    for(unsigned int i=2;i<100000;i++)
    {
        if(!Num[i])
        {
            prime[x++]=i;
            for(unsigned int j=i*2;j<100000;j+=i)
            {
                Num[j]=1;
            }
        }
    }
    unsigned int L,U;
    string s;
    while(getline(cin,s))
    {
        stringstream sin(s);
        sin>>L>>U;
        unsigned int l,u;
        for(l=L;!isprime(l);l++);
        L=l;
        for(u=U;!isprime(u);u--);
        U=u;
        if(L>=U) cout<<"There are no adjacent primes."<<endl;
        else
        {
            int clos1=L,clos2=L,dis1=L,dis2=L;
            int temp1=L,temp2=L;
            int mini=U-L+1,maxi=0;
            unsigned int i;
            if(L==2) i=L+1;
            else i=L+2;
            for( i;i<=U;i+=2)
            {//質數一定是6n+1或6n-1，所以+2+4+2+4判斷增加效率
                if(isprime(i))
                {
                    temp1=temp2;
                    temp2=i;
                    if(temp2-temp1<mini)
                    {
                        clos1=temp1;
                        clos2=temp2;
                        mini=clos2-clos1;
                    }
                    if(temp2-temp1>maxi)
                    {
                        dis1=temp1;
                        dis2=temp2;
                        maxi=dis2-dis1;
                    }
                }
                if((i-1)%6==0) i+=2;//+4
            }
            cout<<clos1<<","<<clos2<<" are closest, "<<dis1<<","<<dis2<<" are most distant."<<endl;
        }
    }
    return 0;
}

[UVA] 369 - Combinations

/*20141107 hanting*/
#include <iostream>
using namespace std;
int prime[30];
int factor[100]={0};
int x=0;
void part1(int num)
{
    for(int i=0;num!=1;i++)
    {
        while(num%prime[i]==0)
        {
            factor[prime[i]]++;
            num/=prime[i];
        }
    }
}
void part2(int num)
{
    for(int i=0;num!=1;i++)
    {
        while(num%prime[i]==0)
        {
            factor[prime[i]]--;
            num/=prime[i];
        }
    }
}
void mul(int* ans,int n)
{
    for(int i=0;i<100;i++)
    {
        ans[i]*=n;
    }
    for(int i=1;i<100;i++)
    {
        ans[i]+=ans[i-1]/10;
        ans[i-1]%=10;
    }
}
void output(int *ans)
{
    int i;
    for(i=99;i>=0;i--)
    {
        if(ans[i]!=0) break;
    }
    for(int j=i;j>=0;j--)
    {
        cout<<ans[j];
    }
}
int main()
{
    int Num[100]={0};
    for(int i=2;i<100;i++)
    {
        if(Num[i]==0)
        {
            prime[x++]=i;
            for(int j=i;j<100;j+=i) Num[j]=1;
        }
    }
    int n,m;
    while(cin>>n>>m && n+m)
    {
        for(int i=0;i<100;i++) factor[i]=0;
        cout<<n<<" things taken "<<m<<" at a time is ";
        int ans[100]={1};
        if(m>n/2) m=n-m;;
        for(int i=2;i<=m;i++)
        {
            part2(i);
        }
        for(int i=n;m--;i--)
        {
            part1(i);
        }
        for(int i=2;i<98;i++)
        {
            while(factor[i]--)
            {
                mul(ans,i);
            }
        }
        output(ans);
        cout<<" exactly."<<endl;
    }
    return 0;
}


================================================

# /* 題目: UVa 369 - Combinations
#  * onlinejudge.org/external/3/369.pdf
#  * Language: Python
#  * Created on: 2019年12月19日
#  *   Author: hanting
#  */
def C(a, b):
    if a-b < b :
        b = a-b
    result = 1
    w = 1
    for i in range(a-b+1, a+1):
        result *= i
        result //= w
        w += 1
    return result
while(True):
    x, y = map(int, input().split())
    if [x, y] == [0, 0]:
        break
    print('{} things taken {} at a time is {} exactly.'.format(x, y, C(x, y)))