674 - Coin Change (Uva Solution)

674 - Coin Change

import java.util.Scanner;

class Main {
public static long [] ways=new long [10000];

public static void main(String[] args) {


Scanner sc =new Scanner(System.in);
int n;
int [] coin=new int[5];
coin[0]=1;
coin[1]=5;
coin[2]=10;
coin[3]=25;
coin[4]=50;
int i,j;
ways[0]=1;
for(i=0;i<5;i++){
for(j=coin[i];j<10000;j++){
ways[j]+=ways[j-coin[i]];

}

}
while(sc.hasNext())
{

n=sc.nextInt();




System.out.println(ways[n]);

}

}


}

Read More»

423 - MPI Maelstrom uva soliution

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int dp[151][151];
int main()
{
    int n;
    char ch[200];
    int i,j,ans,k,l;
    while(cin>>n)
    {
        ans=0;
        memset(dp,0,sizeof(dp));
        for(i=2;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {

                cin>>ch;
                if(ch[0]=='x')
                    dp[i][j]=INF;
                else
                    dp[i][j]=atoi(ch);
                if(ch[0]=='x')
                    dp[j][i]=INF;
                else
                    dp[j][i]=atoi(ch);


            }
        }


        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(dp[i][j]>dp[i][k]+dp[k][j])
                        dp[i][j]=dp[i][k]+dp[k][j];
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(dp[1][i]>ans)
                ans=dp[1][i];



        }
        cout<<ans<<endl;

    }
    return 0;
}

Read More»