結果

問題 No.1463 Hungry Kanten
ユーザー tsuishitsuishi
提出日時 2021-04-13 19:00:37
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 262 ms / 2,000 ms
コード長 8,632 bytes
コンパイル時間 948 ms
コンパイル使用メモリ 34,360 KB
実行使用メモリ 36,124 KB
最終ジャッジ日時 2023-09-12 11:17:57
合計ジャッジ時間 3,037 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,636 KB
testcase_01 AC 2 ms
5,684 KB
testcase_02 AC 11 ms
6,144 KB
testcase_03 AC 252 ms
36,124 KB
testcase_04 AC 3 ms
5,844 KB
testcase_05 AC 262 ms
34,156 KB
testcase_06 AC 2 ms
5,700 KB
testcase_07 AC 3 ms
5,696 KB
testcase_08 AC 3 ms
5,868 KB
testcase_09 AC 2 ms
5,688 KB
testcase_10 AC 3 ms
5,704 KB
testcase_11 AC 3 ms
5,716 KB
testcase_12 AC 3 ms
5,684 KB
testcase_13 AC 3 ms
5,836 KB
testcase_14 AC 5 ms
5,748 KB
testcase_15 AC 3 ms
5,860 KB
testcase_16 AC 11 ms
6,276 KB
testcase_17 AC 32 ms
7,560 KB
testcase_18 AC 9 ms
6,028 KB
testcase_19 AC 131 ms
17,460 KB
testcase_20 AC 168 ms
21,392 KB
testcase_21 AC 3 ms
5,788 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
extern int getchar_unlocked(void);
extern int putchar_unlocked(int);
#define DEBUGs

#define NOP do{}while(0)
#define gc(d)	(d)=getchar_unlocked()
#define	pc(d) putchar_unlocked(d)
#define PRINCR pc('\n')
#ifdef DEBUG
#include <time.h>
#define TRACE(...) do{fprintf(stderr,__VA_ARGS__);}while(0)
#define TRACECR do{putchar_unlocked('\n');fflush(stdout);}while(0)
static clock_t	startclock;
void DEBUGSTART(void){TRACE("--DEBUG MODE --\n");startclock=clock();}
void DEBUGEND(void){startclock=clock()-startclock;TRACE("--finish --\ntime is %.3fms\n",startclock/1000.);}
#else
#define TRACE(...) NOP
#define TRACECR NOP
void DEBUGSTART(void){return;}
void DEBUGEND(void){return;}
#endif

#define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)
#define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0)
#define MAX(a,b)	((a)>(b)?(a):(b))
#define MIN(a,b)	((a)<(b)?(a):(b))
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define REP1(a,b) for(int a=1;a<=(int)(b);++a)
static char *GETWORD(char* str) {char c;char *cp;cp=&str[0];gc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;gc(c);}*cp='\0';return &str[0];}
#define GETLINE(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define mygc(c) (c)=getchar()
static void read1(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
static void read2(int *x, int *y){read1(x);read1(y);}
#define INPUT(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define lolong long long
static int GETLINEINT(void) {char s[34];GETLINE(s);return atoi(s);}
static int GETWORDINT(void) {char s[34];GETWORD(s);return atoi(s);}
static int cmpint123(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
static int cmpint321(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
#define	ull	unsigned long long
#define	ui	unsigned int
// *********************
#define	CAMA  (3710886LL)
int	seisuu[19];
int	K;
typedef struct cval {
	ull	n1;
	ull	n2;
	ull	n3;
	ull	n4;
} CVALDEF;
CVALDEF	 ncash[CAMA];
ull cidx;
// *********************
ull inl()   // 整数の入力（負数に対応）
{
	ull n = 0ULL;
	int c;
	gc(c);
	do {
		n = 10 * n + (c & 0xf);
		gc(c);
	} while (c >= '0');
	return n;
}
void outl(ull n) {
	int i;
	char b[70];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}
ull matoll( char *b) {
	ull ans = 0;
	int i;
	i = 0; while (b[i]) ans *= 10ULL , ans += b[i++] -'0';
	return ans;
}
// *********************
// for MultiInt 多倍長整数
#define MAXDIGIT (250/7)
#define ONEWORDMAX (1000000)
// ***********************
// 外部変数
static int Biga[MAXDIGIT];
static int Bigb[MAXDIGIT];
static int Bigc[MAXDIGIT];
// ***********************
extern  int cmpintint(const void * n1, const void * n2) {
    ull  a, b;
    CVALDEF *dp1,*dp2;
    dp1 = (CVALDEF*)n1;    a = dp1->n4;
    dp2 = (CVALDEF*)n2;    b = dp2->n4;
    if( a == b ) {
		a = dp1->n3;
		b = dp2->n3;
	}
    if( a == b ) {
		a = dp1->n2;
		b = dp2->n2;
	}
    if( a == b ) {
		a = dp1->n1;
		b = dp2->n1;
	}
#if 1
    // 1 is 降順 5 4 3 2 1
    if( a > b ) return -1;
    else if( a < b ) return 1;
    else return 0;
#else
    // 0 is 昇順 1 2 3 4 5
    if( a < b ) return -1;
    else if( a > b ) return 1;
    else return 0;
#endif
}
void MultiIntMul(int *ret, int *a, int *b) // 掛算
{
    int  i, j;
    int  la, lb;
    int  *aa;
    int  ca;
    long x;


    la = *a;
    lb = *b;


    if(la == 0 || lb == 0) { // どちらかがゼロ
        *ret = 0;
        return;
    }


    for (i = la + lb; i > 0; i--) *(ret + i) = 0; // 解答領域クリア


    // 筆算（一桁づつ掛け算）をする
    for (j = 1; j <= lb; j++) {
        ca = 0;
        b++; // 注目するbの桁を上へ
        for (i = 1, aa = a; i <= la; i++) {
            x = *++aa; // 一桁上へ
            x = x * *b + *(ret + i + j - 1) + ca; // 掛算分を足す（繰上付）
            *(ret + i + j - 1) = x % ONEWORDMAX; // 一桁分
            ca = x / ONEWORDMAX; // 繰り上げ分
        }
        *(ret + i + j - 1) = ca;
    }
    *ret = (ca != 0) ? la + lb : la + lb - 1;
}

void MultiInt2Str(char *str, int *num) // 数値を文字化
{
    int  i, j;
    char *ss;
    int  x;


    if (*num == 0) { // ゼロの場合
        *str++ = '0';
        *str = '\0';
        return;
    }


    ss = str - 1; // 加算前提で一つ前が初期値
    for (i = *num; i > 0; i--) { // 最大桁数から１まで
        x = *++num; // １単位取得
        for (j = 1; j < ONEWORDMAX; j *= 10) { // １から単位割当分の桁まで
            *++ss = x % 10 + '0'; // j の桁
            x /= 10; // 1桁目を切り捨てて1/10
        }
    }
    while (*ss == '0') ss--; // ゼロサプレス


    *(ss + 1) = '\0'; // 終端文字追加
    // 前後逆転
    while (str < ss) { // 交差するまで
        x = *str; // 退避
        *str++ = *ss; // 最後の文字を文字列追加
        *ss-- = x; // 退避文字を低い桁側に代入
    }
}
void MultiIntFromUlong(int *num, unsigned long ul)	// 値を代入する
{
    int  *nn = num;


    while (ul != 0) {
        *++nn = ul % ONEWORDMAX;
        ul /= ONEWORDMAX;
    }
    *num = nn - num; // アドレスの差が桁数
}
void MultiIntCopy(int *to, int *from)	// 値をコピーする
{
	memcpy( (void*)to , (void*)from , sizeof( int )*MAXDIGIT );
}
inline ui bits_count( unsigned int v ) {
  v = (v & 0x55555555) + (v >>  1 & 0x55555555);
  v = (v & 0x33333333) + (v >>  2 & 0x33333333);
  v = (v & 0x0f0f0f0f) + (v >>  4 & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) + (v >>  8 & 0x00ff00ff);
  v = (v & 0x0000ffff) + (v >> 16 & 0x0000ffff);
  return v;
}
#define	KUGIRI	(17)
void cook(ui x, ull *fry, ull *crush , ull *crush2, ull *crush3, ull *crush4  ) {
	ull f = 0L;
	ull c = 1L;
	ull c2 = 0L;
	ull m;
	int		len;
	int	*ip = &seisuu[0];
	char	ost[256];
	MultiIntFromUlong( Biga , 1UL );
	while( x ) {
		if( x & 1 ) {
			f += (ull)*ip;
			MultiIntFromUlong( Bigb , (unsigned long)*ip );
			MultiIntMul( Bigc , Biga , Bigb );
			MultiIntCopy( Biga , Bigc );
		}
		x >>= 1;
		ip++;
	}
	*fry = f;
	MultiInt2Str( ost , Biga );
	len = strlen(ost);
	if( len > KUGIRI*3 ) {
		int	i = len -KUGIRI;
		TRACE("%d,",len);
		//TRACE("%s>",ost);
		*crush = matoll( &ost[i] );
		ost[i] = '\0';
		i = len -KUGIRI*2;
		*crush2 = matoll( &ost[i] );
		ost[i] = '\0';
		i = len -KUGIRI*3;
		*crush3 = matoll( &ost[i] );
		ost[i] = '\0';
		*crush4 = matoll( ost );
		//TRACE("[%llu:%llu:%llu],",*crush3,*crush2,*crush);
	} else if( len > KUGIRI*2 ) {
		int	i = len -KUGIRI;
		TRACE("%d,",len);
		//TRACE("%s>",ost);
		*crush = matoll( &ost[i] );
		ost[i] = '\0';
		i = len -KUGIRI*2;
		*crush2 = matoll( &ost[i] );
		ost[i] = '\0';
		*crush3 = matoll( ost );
		*crush4 = 0;
		//TRACE("[%llu:%llu:%llu],",*crush3,*crush2,*crush);
	} else if( len > KUGIRI ) {
		//TRACE("%s>",ost);
		int	i = len -KUGIRI;
		*crush = matoll( &ost[i] );
		ost[i] = '\0';
		*crush2 = matoll( ost );
		*crush3 = 0;
		*crush4 = 0;
		//TRACE("[%llu:%llu],",*crush2,*crush);
	} else {
		*crush = matoll( ost );
		*crush2 = 0;
		*crush3 = 0;
		*crush4 = 0;
		//TRACE("%llu,",*crush);
	}
	return;
}
void push( ull x1, ull x2, ull x3, ull x4) {
	ncash[ cidx ].n1 = x1;
	ncash[ cidx ].n2 = x2;
	ncash[ cidx ].n3 = x3;
	ncash[ cidx ].n4 = x4;
	cidx++;
	return;
}

// ***********************
int main( void ) {
	int N;
	ui	mbc;
	ui	ans = 0;
	ull f,c,c2,c3,c4;
	ull	mv,mv2,mv3,mv4;
	CVALDEF *cp;

	cidx = 0;
	memset( ncash , 0 , CAMA * sizeof(char) );
	N = GETWORDINT();
	K = GETWORDINT();
	REP(i,N) {
		seisuu[i] = GETWORDINT();
	}
	mbc = (1 << N) +1;

	DEBUGSTART();
	for(ui i = 1; i < mbc; i++ ) {
		if( bits_count(i) >= K ) {
			cook(i, &f, &c ,&c2, &c3, &c4);
			push(f,0,0,0);
			push(c,c2,c3,c4);
		}
	}
	qsort( ncash, cidx, sizeof(CVALDEF),cmpintint);
	TRACE("cidx %llu\n",cidx);
	cp = &ncash[0];
	ans = 1;
	mv = cp->n1;
	mv2 = cp->n2;
	mv3 = cp->n3;
	mv4 = cp->n4;
	cp++;
	for(ull i=1; i < cidx ; i++ ) {
		if( mv != cp->n1 || mv2 != cp->n2 || mv3 != cp->n3 || mv4 != cp->n4) {
			ans++;
			mv = cp->n1;
			mv2 = cp->n2;
			mv3 = cp->n3;
			mv4 = cp->n4;
		}
		//TRACE("%u,",*cp);
		cp++;
	}
	DEBUGEND();
	outl( ans );
}
0