[UVA] 627 - The Net

/*20140729 hanting*/
#include <iostream>
#include <sstream>
using namespace std;
void run(int a[][1000],int,int);
int router_num;
int main()
{
    while(cin>>router_num)
    {
        cout<<"-----"<<endl;
        int Net[router_num+2][1000];
        for(int i=0;i<router_num+2;i++)
            for(int j=0;j<router_num+2;j++)
                Net[i][j]=0;
        int ID,temp;
        char c;
        for(int i=0;i<router_num;i++)
        {
            cin>>ID;
            string s;
            getline(cin,s);
            if(s.size()==1) continue;
            istringstream sin(s);
            char c;
            while(sin>>c)
            {
                sin>>temp;
                Net[ID][temp]=1;
            }
        }
        int connect_num;
        cin>>connect_num;
        int starting,ending;
        for(int i=0;i<connect_num;i++)
        {
            cin>>starting>>ending;
            run(Net,starting,ending);
        }
    }
    return 0;
}
void run(int a[][1000],int starting,int ending)
{
    int tempa[router_num+2][router_num+2];
    for(int i=0;i<router_num+2;i++)
        for(int j=0;j<router_num+2;j++)
            tempa[i][j]=a[i][j];
    int b[100][1000]={starting};
    int m,n=1;
    int i;
    for(i=1;i>=0;i++)
    {
        m=n;
        n=0;
        for(int j=0;j<m;j++)
        {
            int ID=b[i-1][j];
            for(int k=1;k<=router_num;k++)
            {
                if(tempa[ID][k])
                {
                    b[i][n++]=k;
                    if(k==ending)
                    {
                        m=0;
                        break;
                    }
                    tempa[ID][k]=0;
                }
            }
        }
        if(!n)
        {
            cout<<"connection impossible"<<endl;
            return;
        }
        if(!m) break;
    }
    int temp=ending;
    int route[1000]={temp};
    int con=0;
    for(int j=i-1;j>=0;j--)
    {
        for(int k=0;k>=0;k++)
        {
            int ID=b[j][k];
            if(a[ID][temp])
            {
                temp=ID;
                route[con++]=temp;
                break;
            }
        }
    }
    for(int i=con-1;i>=0;i--)
    {
        cout<<route[i]<<" ";
    }
    cout<<ending<<endl;
}

[UVA] 1225 - Digit Counting

/*20140728 hanting*/
#include <iostream>
using namespace std;
void count(int *a,int i)
{
    while(i)
    {
        a[i%10]++;
        i/=10;
    }
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int n;
        cin>>n;
        int a[10]={0};
        for(int i=1;i<=n;i++)
        {
            count(a,i);
        }
        for(int i=0;i<10;i++)
        {
            cout<<a[i]<<(i!=9 ? ' ':'\n');
        }
    }
    return 0;
}

[UVA] 11687 - Digits

/*20140728 hanting*/
#include <iostream>
#include <sstream>
using namespace std;
int dcount(long long int a)
{
    int temp=0;
    if(!a) return 1;
    while(a)
    {
        a/=10;
        temp++;
    }
    return temp;
}
int main()
{
    string s;
    long long int a;
    while(cin>>s && s!="END")
    {
        stringstream ss;
        ss<<s;
        ss>>a;
        int x1=a,x2=dcount(a);
        int con=0;
        while(x1!=x2)
        {
            x1=x2;
            x2=dcount(x2);
            con++;
        }
        cout<<++con<<endl;
    }
    return 0;
}

[UVA] 825 - Walking on the Safe Side

/*20140727 hanting*/
#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    int blankline=0;
    while(N--)
    {
        if(blankline) cout<<endl;
        int w,e;
        cin>>w>>e;
        int a[500][500]={1};
        int temp,temp2;
        for(int i=0;i<w;i++)
        {
            cin>>temp;
            string s;
            getline(cin,s);
            istringstream sin(s);
            while(sin>>temp2)
            {
                a[temp-1][temp2-1]=-1;
            }
        }

        for(int i=0;i<w;i++)
        {
            for(int j=0;j<e;j++)
            {
                if(a[i][j]==-1) continue;
                if(a[i-1][j]!=-1 && i)
                {
                    a[i][j]+=a[i-1][j];
                }
                if(a[i+1][j]!=-1)
                {
                    a[i][j]+=a[i+1][j];
                }
                if(a[i][j-1]!=-1 && j)
                {
                    a[i][j]+=a[i][j-1];
                }
                if(a[i][j+1]!=-1)
                {
                    a[i][j]+=a[i][j+1];
                }
            }
        }
        cout<<a[w-1][e-1]<<endl;
        blankline=1;
    }
    return 0;
}

[UVA] 294 - Divisors

/*20140725 hanting*/
#include <iostream>
using namespace std;
int prime[10000];
int div(int N)
{
    int DivSum=1;
    for(int i=0;N!=1;i++)
    {
        int x=0;
        if(prime[i]==0)
        {
            return DivSum*2;
        }
        while(N%prime[i]==0)
        {
            x++;
            N/=prime[i];
        }
        DivSum*=x+1;
    }
    return DivSum;
}
int main()
{
    int Num[50000]={0};
    int x=0;
    for(int i=2;i<50000;i++)
    {
        if(Num[i]==0)
        {
            prime[x++]=i;
            for(int j=i;j<50000;j+=i)
            {
                Num[j]=1;
            }
        }
    }
    int N;
    cin>>N;
    while(N--)
    {
        int m,n;
        int num;
        int MaxDiv=0;
        cin>>m>>n;
        for(int i=m;i<=n;i++)
        {
            int Div=div(i);
            if(Div>MaxDiv)
            {
                MaxDiv=Div;
                num=i;
            }
        }
        cout<<"Between "<<m<<" and "<<n<<", "<<num<<" has a maximum of "<<MaxDiv<<" divisors."<<endl;
    }
    return 0;
}

[UVA] 10465 - Homer Simpson

/*20140723 hanting*/
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int m,n,t;
    while(cin>>m>>n>>t)
    {
        if(m>n) swap(m,n);
        if(t<m)/*it's possible that Homer can't eat anything*/
        {
            cout<<0<<" "<<t<<endl;
            continue;
        }
        vector<int> a(11000);
        for(int j=0;j<11000;j+=n)
        {
            for(int i=j;i<11000;i+=m)
            {
                if(a[i]==0)a[i]=(i-j)/m+j/n;
            }
        }
        if(a[t])cout<<a[t]<<endl;
        else
        {
            for(int i=0;i<t;i++)
            {
                if(a[t-i])
                {
                    cout<<a[t-i]<<" "<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

[UVA] 10189 - Minesweeper

/*20140722 hanting*/
#include <iostream>
using namespace std;
int main()
{
    int n,m;
    int times=0;
    while(cin>>n>>m ,n+m)
    {
        char c[200][200]={0};
        int a[200][200]={0};
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>c[i][j];
                if(c[i][j]=='*')
                {
                    for(int x=0;x<3;x++)
                    {
                        for(int y=0;y<3;y++)
                        {
                            a[i-1+x][j-1+y]++;
                        }
                    }
                }
            }
        }
        if(times!=0) cout<<endl;
        cout<<"Field #"<<++times<<":"<<endl;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(c[i][j]=='*') cout<<'*';
                else cout<<a[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}

[UVA] 11185 - Ternary

/*20140721 hanting*/
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
void Itoa(int N,char *s,int ary);
int main()
{
    int N;
    char s[25];
    while(cin>>s && s[0]!='-')
    {
        char ans[25];
        for(int i=0;i<25;i++) ans[i]='-';
        N=atoi(s);
        Itoa(N,ans,3);
        cout<<ans<<endl;
    }
    return 0;
}
void Itoa(int N,char *ans,int ary)
{
    int i=0;
    for(i=0;i<25;i++)
    {
        ans[i]=(N%ary)+48;
        N/=ary;
        if(N==0) break;
    }
    reverse(ans,ans+i+1);
    ans[i+1]=0;
}

[UVA] 10473 - Simple Base Conversion

/*20140720 hanting*/
#include <iostream>
#include <iomanip>
#include <sstream>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s) && s[0]!='-')
    {
        stringstream ss;
        long long int a;
        if(s[1]=='x')
        {
            ss<<s;
            ss>>hex>>a;
            cout<<dec<<a<<endl;
        }
        else
        {
            ss<<s;
            ss>>a;
            cout<<"0x"<<hex<<uppercase<<a<<endl;
        }
    }
    return 0;
}