ranhaの日記

2007-07-08

アルゴリズム研究3(問1、および問2ソースコード) 12:37

問1

#include<stdio.h>

typedef unsigned int uint32_t;//no necessity
typedef unsigned int uint16_t;
typedef unsigned char uint8_t;

int main(int argc,const char **argv){
    register const char *tmp;
    register uint16_t c100,c50,c10,c5,c1;
    register uint32_t coin;
    register uint16_t total;
    
    uint32_t k;

    //for(k = 0; k < 100000000; ++k){
	tmp=argv[1];
	coin=0;
	while(*tmp){
	    coin=(coin*10+(*tmp++)-48);
	}
	total=c1=coin-5*(coin/5);
	coin/=5;

	c5=coin&1;
		
	c10=(coin>>=1)-5*(coin/5);
	coin/=5;

	c50=coin&1;
		
	c100=(coin>>=1)-5*(coin/5);
	coin/=5;
	
	total+=coin+c100+c50+c10+c5;
	//}
    printf("500 %u\n100 %u\n50 %u\n10 %u\n5 %u\n1 %u\n%u\n",
	   coin,c100,c50,c10,c5,c1,total);
}

問2

#include<stdio.h>
#include<stdlib.h>

typedef unsigned long uint32_t;
typedef unsigned short uint16_t;

uint32_t score[10000001];
uint16_t p_coin[10000001];

uint32_t cnum[10];
uint32_t coins[10];
uint32_t total;

int i;
uint32_t j;
uint32_t money,upper;
uint32_t tmp;
uint16_t kinds;
uint16_t last;

inline uint32_t my_atoi(const char *str){
    uint32_t coin=0;
    while(*str)
	coin=(*str++)-48+coin*10;
    return coin;
}

int main(int argc,const char **argv){
    upper=money=my_atoi(argv[1]);
    
    last=-1+(kinds=my_atoi(argv[2]));
    
    for(i=0;i<kinds;++i)
	coins[i]=my_atoi(argv[3+i]);
    
    if(kinds>1)
	upper=money-coins[1]+1;

    for(i = 0;i <= money;)
	score[i]=i++;
    
    for(i = 0; i < upper; ++i){
	while(i+coins[last]>money)
	    --last;
	for(j = 1; j <= last; ++j){
	    tmp = i+coins[j];
	    if(score[tmp] > score[i]+1){
		score[tmp] = score[i]+1;
		p_coin[tmp] = j;
	    }
	}
    }
    
    
    for(i = money; i; i-=coins[tmp]){
	++cnum[tmp=p_coin[i]];
	++total;
    }
    for(i = kinds-1; i>=0 ; --i){
	printf("%u %u\n",coins[i],cnum[i]);
    }
    printf("%u\n",total);
}

汚いですが、どういう事をやっているかは分かると思います。


問3は無理矢理ダイクストラを使って提出したのですが・・・、それでは小サイズの問題しか解けません。

まぁ問2もNPと言えばNPなんでしょうが。