2013年中南大学大学院二次試験機（1000～1004）

ディレクトリ:
A：回文串問題B：水仙数C：安全パスワードD：最低貨幣数E：恵民工程
A：回文串問題
http://39.106.164.46/problem.php?id=1000
考え方：回文文字列かどうかを判断します。ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 1005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

string s;

int main(){
     
    int cnt=1;
    while(cin>>s){
     
        int len=s.length();
        int i=0,j=len-1;
        bool flag=true;
        while(i<=j){
     
            if(s[i]!=s[j]){
     
                flag=false;
                break;
            }
            i++;
            j--;
        }
        if(flag) cout<<"case"<<cnt<<": yes"<<endl;
        else cout<<"case"<<cnt<<": no"<<endl;
        cnt++;
    }
    return 0;
}

B：水仙の数
http://39.106.164.46/problem.php?id=1001
構想：m~nの間のすべての水仙の数を探し出して、小さい時から大出力まで、ない時はno ACコードを出力します。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 1005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int m,n;

bool judge(int x){
     
    int a=x%10;
    int b=(x/10)%10;
    int c=(x/100)%10;
    int tmp=a*a*a+b*b*b+c*c*c;
    if(x==tmp) return true;
    return false;
}

int main(){
     
    while(cin>>m>>n){
     
        int cnt=0;
        vector<int> res;
        for(int i=m;i<=n;i++){
     
            if(judge(i)){
     
                res.push_back(i);
                cnt++;
            }
        }
        if(cnt==0) cout<<"no"<<endl;
        else{
     
            for(int i=0;i<res.size();i++){
     
                printf("%s%d",i==0?"":" ",res[i]);
            }
            cout<<endl;
        }
    }
    return 0;
}

C：セキュリティパスワード
http://39.106.164.46/problem.php?id=1003
構想：文字列の問題。ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

string s;

int main(){
     
    while(cin>>s){
     
        int len=s.length();
        if(len<8){
     
            cout<<"NO"<<endl;
            continue;
        }
        bool f1=false,f2=false,f3=false,f4=false;
        int cnt=0;
        for(int i=0;i<len;i++){
     
            if(s[i]>='A'&&s[i]<='Z'){
     
                if(!f1){
     f1=true;cnt++;}
            }else if(s[i]>='a'&&s[i]<='z'){
     
                if(!f2){
     f2=true;cnt++;}
            }else if(s[i]>='0'&&s[i]<='9'){
     
                if(!f3){
     f3=true;cnt++;}
            }else{
     
                if(!f4){
     f4=true;cnt++;}
            }
        }
        if(cnt>=3) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D：最低貨幣数
http://39.106.164.46/problem.php?id=1003
考え：毎回、一番大きなお金を持って集めればいいと考えています。ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,a[MAX];
int b[6]={
     100,50,10,5,2,1};

int main(){
     
    while(cin>>n){
     
        for(int i=0;i<n;i++){
     
            cin>>a[i];
        }
        int ans=0;
        for(int i=0;i<n;i++){
     
            int tot=a[i],now=0;
            while(now<tot){
     
                for(int j=0;j<6;j++){
     
                    int num=(tot-now)/b[j];
                    if(num!=0){
     
                        ans+=num;
                        now+=num*b[j];
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

E：恵民プロジェクト
http://39.106.164.46/problem.php?id=1004
考え方：最小生成ツリーの合計値。ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,m;
int mp[MAX][MAX],dis[MAX],vis[MAX];

int prim(){
     
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
     
        dis[i]=mp[1][i];
    }
    vis[1]=1;
    int ans=0;
    for(int i=0;i<n-1;i++){
     
        int u=-1,minl=INF;
        for(int j=1;j<=n;j++){
     
            if(vis[j]==0&&dis[j]<minl){
     
                minl=dis[j];
                u=j;
            }
        }
        if(u==-1) return -1;//    ，   
        vis[u]=1;
        ans+=dis[u];
        for(int v=1;v<=n;v++){
     
            if(vis[v]==0&&mp[u][v]<dis[v]){
     
                dis[v]=mp[u][v];
            }
        }
    }
    return ans;
}

int main(){
     
    while(cin>>n>>m){
     
        for(int i=1;i<=n;i++){
     
            for(int j=1;j<=n;j++){
     
                if(i==j){
     
                    mp[i][j]=0;
                }else{
     
                    mp[i][j]=INF;
                }
            }
        }
        int a,b,len;
        for(int i=0;i<m;i++){
     
            cin>>a>>b>>len;
            mp[a][b]=mp[b][a]=len;
        }
        int res=prim();
        if(res==-1) {
     cout<<"?"<<endl;continue;}
        else cout<<res<<endl;

        //  ？？？
        /*int sum=0;
        for(int i=1;i<=n;i++){
            sum+=dis[i];
        }
        cout<
    }
    return 0;
}