BCC32には64bit整数型ないのでしょうか？

[ｈ]

普段私はコマンドプロンプトでBCC32でソースコードをコンパイルしてC++の勉強をしているのですが、
63Bitで表せる整数までを扱う問題にぶち当たりました。

BigIntを作って計算しても良いのですが、もっと手軽な方法を探しています。

何か良い方法ないでしょうか？

[bitter_fox]

普段私はコマンドプロンプトでBCC32でソースコードをコンパイルしてC++の勉強をしているのですが、
63Bitで表せる整数までを扱う問題にぶち当たりました。

ボーランドでも__int64という変数型が定義されていると思います。
これを使えばおそらく64bitまで扱えると思います。

http://www.wdic.org/w/TECH/__int64

[h]

http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 57&lang=jp

リンク先問題なのですがどうもうまく解けません。

アドバイスに従いint64を使ってメモカで解くコードを書いてみたのですが、
ある一定の値を超えると超えた分が切り捨てられてるようなのです。
その値が数１０億あたりにあるようです、もっと大きな値を使いたいのですが。

コード:

#include <stdio.h>
int main()
{
	unsigned __int64 a[21];
	unsigned __int64 next[21];
	for(int i=0;i<21;i++){
		a[i]=0;
	}
	int n,t;
	scanf("%d",&n);
	scanf("%d",&t);
	a[t]=1;
	for(int i=2;i<n;i++){
		scanf("%d",&t);
		for(int j=0;j<21;j++){
			next[j]=0;
		}
		for(int j=0;j<21;j++){
			if(j+t<21) next[j+t]+=a[j];
			if(j-t>=0) next[j-t]+=a[j];
		}
		for(int j=0;j<21;j++){
			a[j]=next[j];
			printf("%llu ",a[j]);
		}
		printf("\n\n");
	}
	scanf("%d",&t);
	printf("%llu\n",a[t]);
}

[non]

ｈさんのプログラムをVCで実行した結果です。
カウント回数の出力だけ付け加えました。

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[ 2]1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 3]0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 4]2 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 5]0 5 0 4 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 6]5 0 9 0 5 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 7]0 14 0 14 0 6 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

[ 8]14 0 28 0 20 0 7 0 1 0 0 0 0 0 0 0 0 0 0 0 0

[ 9]0 42 0 48 0 27 0 8 0 1 0 0 0 0 0 0 0 0 0 0 0

[10]42 0 90 0 75 0 35 0 9 0 1 0 0 0 0 0 0 0 0 0 0

[11]0 132 0 165 0 110 0 44 0 10 0 1 0 0 0 0 0 0 0 0 0

[12]132 0 297 0 275 0 154 0 54 0 11 0 1 0 0 0 0 0 0 0 0

[13]0 429 0 572 0 429 0 208 0 65 0 12 0 1 0 0 0 0 0 0 0

[14]429 0 1001 0 1001 0 637 0 273 0 77 0 13 0 1 0 0 0 0 0 0

[15]0 1430 0 2002 0 1638 0 910 0 350 0 90 0 14 0 1 0 0 0 0 0

[16]1430 0 3432 0 3640 0 2548 0 1260 0 440 0 104 0 15 0 1 0 0 0 0

[17]0 4862 0 7072 0 6188 0 3808 0 1700 0 544 0 119 0 16 0 1 0 0 0

[18]4862 0 11934 0 13260 0 9996 0 5508 0 2244 0 663 0 135 0 17 0 1 0 0

[19]0 16796 0 25194 0 23256 0 15504 0 7752 0 2907 0 798 0 152 0 18 0 1 0

[20]16796 0 41990 0 48450 0 38760 0 23256 0 10659 0 3705 0 950 0 170 0 19 0 1

[21]0 58786 0 90440 0 87210 0 62016 0 33915 0 14364 0 4655 0 1120 0 189 0 20 0

[22]58786 0 149226 0 177650 0 149226 0 95931 0 48279 0 19019 0 5775 0 1309 0 209
0 20

[23]0 208012 0 326876 0 326876 0 245157 0 144210 0 67298 0 24794 0 7084 0 1518 0
229 0

[24]208012 0 534888 0 653752 0 572033 0 389367 0 211508 0 92092 0 31878 0 8602 0
1747 0 229

[25]0 742900 0 1188640 0 1225785 0 961400 0 600875 0 303600 0 123970 0 40480 0 1
0349 0 1976 0

[26]742900 0 1931540 0 2414425 0 2187185 0 1562275 0 904475 0 427570 0 164450 0
50829 0 12325 0 1976

[27]0 2674440 0 4345965 0 4601610 0 3749460 0 2466750 0 1332045 0 592020 0 21527
9 0 63154 0 14301 0

[28]2674440 0 7020405 0 8947575 0 8351070 0 6216210 0 3798795 0 1924065 0 807299
0 278433 0 77455 0 14301

[29]0 9694845 0 15967980 0 17298645 0 14567280 0 10015005 0 5722860 0 2731364 0
1085732 0 355888 0 91756 0

[30]9694845 0 25662825 0 33266625 0 31865925 0 24582285 0 15737865 0 8454224 0 3
817096 0 1441620 0 447644 0 91756

[31]0 35357670 0 58929450 0 65132550 0 56448210 0 40320150 0 24192089 0 12271320
0 5258716 0 1889264 0 539400 0

[32]35357670 0 94287120 0 124062000 0 121580760 0 96768360 0 64512239 0 36463409
0 17530036 0 7147980 0 2428664 0 539400

[33]0 129644790 0 218349120 0 245642760 0 218349120 0 161280599 0 100975648 0 53
993445 0 24678016 0 9576644 0 2968064 0

[34]129644790 0 347993910 0 463991880 0 463991880 0 379629719 0 262256247 0 1549
69093 0 78671461 0 34254660 0 12544708 0 2968064

[35]0 477638700 0 811985790 0 927983760 0 843621599 0 641885966 0 417225340 0 23
3640554 0 112926121 0 46799368 0 15512772 0

[36]477638700 0 1289624490 0 1739969550 0 1771605359 0 1485507565 0 1059111306 0
650865894 0 346566675 0 159725489 0 62312140 0 15512772

[37]0 1767263190 0 3029594040 0 3511574909 0 3257112924 0 2544618871 0 170997720
0 0 997432569 0 506292164 0 222037629 0 77824912 0

[38]1767263190 0 4796857230 0 6541168949 0 6768687833 0 5801731795 0 4254596071
0 2707409769 0 1503724733 0 728329793 0 299862541 0 77824912

[39]0 6564120420 0 11338026179 0 13309856782 0 12570419628 0 10056327866 0 69620
05840 0 4211134502 0 2232054526 0 1028192334 0 377687453 0

6564120420

ただ、解答とは値が違いますね。
誤りを発見できませんでした。間違っていないように思えました。
別の方法で試して検証しないとわかりませんね。

[mats]

hさんのプログラムで正しい解が得られます
AOJに投げるときは少々修正が必要ですが…

nonさんの入力はインプットを間違えています
サンプルでは、最後から3番目と4番目が0です

[non]

nonさんの入力はインプットを間違えています
サンプルでは、最後から3番目と4番目が0です

おお、ほんとだ。全部１だと思いました。
プログラムに、間違いはないし、出題者の解答ミスかと思いました。

[h]

問題は解けて合格したのですが、私の環境でコードを実行するとおかしな結果になります。
最初の方はいいのですが、最後の３行で値の切り捨てのようなものが発生してしまいます。
コンパイラのバグかもしれません。


D:\borlandC\mysorce>0557AFirstGrader.exe
40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 5 0 4 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

5 0 9 0 5 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 14 0 14 0 6 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

14 0 28 0 20 0 7 0 1 0 0 0 0 0 0 0 0 0 0 0 0

0 42 0 48 0 27 0 8 0 1 0 0 0 0 0 0 0 0 0 0 0

42 0 90 0 75 0 35 0 9 0 1 0 0 0 0 0 0 0 0 0 0

0 132 0 165 0 110 0 44 0 10 0 1 0 0 0 0 0 0 0 0 0

132 0 297 0 275 0 154 0 54 0 11 0 1 0 0 0 0 0 0 0 0

0 429 0 572 0 429 0 208 0 65 0 12 0 1 0 0 0 0 0 0 0

429 0 1001 0 1001 0 637 0 273 0 77 0 13 0 1 0 0 0 0 0 0

0 1430 0 2002 0 1638 0 910 0 350 0 90 0 14 0 1 0 0 0 0 0

1430 0 3432 0 3640 0 2548 0 1260 0 440 0 104 0 15 0 1 0 0 0 0

0 4862 0 7072 0 6188 0 3808 0 1700 0 544 0 119 0 16 0 1 0 0 0

4862 0 11934 0 13260 0 9996 0 5508 0 2244 0 663 0 135 0 17 0 1 0 0

0 16796 0 25194 0 23256 0 15504 0 7752 0 2907 0 798 0 152 0 18 0 1 0

16796 0 41990 0 48450 0 38760 0 23256 0 10659 0 3705 0 950 0 170 0 19 0 1

0 58786 0 90440 0 87210 0 62016 0 33915 0 14364 0 4655 0 1120 0 189 0 20 0

58786 0 149226 0 177650 0 149226 0 95931 0 48279 0 19019 0 5775 0 1309 0 209 0 2
0

0 208012 0 326876 0 326876 0 245157 0 144210 0 67298 0 24794 0 7084 0 1518 0 229
0

208012 0 534888 0 653752 0 572033 0 389367 0 211508 0 92092 0 31878 0 8602 0 174
7 0 229

0 742900 0 1188640 0 1225785 0 961400 0 600875 0 303600 0 123970 0 40480 0 10349
0 1976 0

742900 0 1931540 0 2414425 0 2187185 0 1562275 0 904475 0 427570 0 164450 0 5082
9 0 12325 0 1976

0 2674440 0 4345965 0 4601610 0 3749460 0 2466750 0 1332045 0 592020 0 215279 0
63154 0 14301 0

2674440 0 7020405 0 8947575 0 8351070 0 6216210 0 3798795 0 1924065 0 807299 0 2
78433 0 77455 0 14301

0 9694845 0 15967980 0 17298645 0 14567280 0 10015005 0 5722860 0 2731364 0 1085
732 0 355888 0 91756 0

9694845 0 25662825 0 33266625 0 31865925 0 24582285 0 15737865 0 8454224 0 38170
96 0 1441620 0 447644 0 91756

0 35357670 0 58929450 0 65132550 0 56448210 0 40320150 0 24192089 0 12271320 0 5
258716 0 1889264 0 539400 0

35357670 0 94287120 0 124062000 0 121580760 0 96768360 0 64512239 0 36463409 0 1
7530036 0 7147980 0 2428664 0 539400

0 129644790 0 218349120 0 245642760 0 218349120 0 161280599 0 100975648 0 539934
45 0 24678016 0 9576644 0 2968064 0

129644790 0 347993910 0 463991880 0 463991880 0 379629719 0 262256247 0 15496909
3 0 78671461 0 34254660 0 12544708 0 2968064

0 477638700 0 811985790 0 927983760 0 843621599 0 641885966 0 417225340 0 233640
554 0 112926121 0 46799368 0 15512772 0

477638700 0 1289624490 0 1739969550 0 1771605359 0 1485507565 0 1059111306 0 650
865894 0 346566675 0 159725489 0 62312140 0 15512772

955277400 0 2579248980 0 3479939100 0 3543210718 0 2971015130 0 2118222612 0 130
1731788 0 693133350 0 319450978 0 124624280 0 31025544

1910554800 0 863530664 0 2664910904 0 2791454140 0 1647062964 0 4236445224 0 260
3463576 0 1386266700 0 638901956 0 249248560 0 62051088

0 2774085464 0 3528441568 0 1161397748 0 143549808 0 1588540892 0 2544941504 0 3
989730276 0 2025168656 0 888150516 0 311299648 0

[non]

BCCではlong long型の書式指定子が、違うようです。
printf("%I64llu ",a[j]);
で、試してください。

[ｈ]

ありがとうございます。
問題解けました。

[ｈ]

解決マーク忘れてました。