※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「会津大学オンラインジャッジ思考中問題一覧」の編集履歴(バックアップ)一覧はこちら

会津大学オンラインジャッジ思考中問題一覧」の最新版変更点

追加された行はこの色になります。

削除された行はこの色になります。

 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537
 0537 Bingo
 これ難しいなあ、本当に高校生2年生向けプログラムコンテストの予選問題?
 問題的にいえばs-(n*n*(n*n+1))/2=1*A1+2*A2+,,,,+n^2*An^2;
 Aiは0以上の整数。
 ベクトルB={A1,A2,,,An^2}
 この条件を満たすベクトルBが何本あるか答えよという問題なのだが。
 うーん?
 
 組み合わせ数からいって深さ優先探索は当然除外。
 幅優先探索は使えるのか使えないのか不明。
 メモ化探索した下記コードで一応正しい答えが出るものの速度が出ない。
 どうとけばいいのだろう?
 
 もしかして漸化式を立てて、升目サイズ、合計値、上限値の3次元空間で漸化式の計算をするのだろうか?
+上限値がなければ漸化式が楽に立てれそうなのだけど?
 恐ろしいのは高校生にしてこの問題を制限時間内に解いている人がいるというところだな。
 発送が柔軟なんだろうな、高校生以下の俺って一体、、、、
+
 
 
 // 0537bingo.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
 //
 
 #include "stdafx.h"
 
 #include<stdio.h>
 #include<map>
 
 void calc(int n,int m,int s){
 	int size=n*n;
 	int t,sum;
 	std::map<int,int> memo[2002];
 	std::map<int,int>::iterator it;
 
     s-=(size*(size+1))/2;
    
     if(s==0){
         printf("1\n");
         return ;
     }
     memo[0][0]=1;
 
     int ans=0;
 	for(int i=0;i<=size;i++){
 		t=size-i;
 		for(int j=0;j<m;j++){
             if(size+j>m) break;
 			if(memo[j].empty()==true) break;
             if(i==size){
                 it=memo[j].lower_bound(s-1);
             }else{
                 it=memo[j].begin();
             }
 
             while(it!=memo[j].end()){
                 sum=(*it).first+t;
                 if(i==size-1){
                     if((*it).first==s){
                         ans+=(*it).second;
                         ans%=100000;
                         break;
                     }
                 }
                 
 
                 if(sum>s) break;
 				if(memo[j+1].find(sum)==memo[j+1].end()){
 					memo[j+1][sum]=memo[j][(*it).first];
 				}else{
 					memo[j+1][sum]=(memo[j][(*it).first]+memo[j+1][sum])%100000;
 				}
 				it++;
 			}
 		}
         /*
         for(int k=0;k<m;k++){
             it=memo[k].begin();
             if(it==memo[k].end()) break;
             printf("\n%d\n",k);
             while(it!=memo[k].end()){
                 printf("<%d %d>",(*it).first,(*it).second );
                 it++;
             }
         }
         */
 	}
     printf("%d\n",ans);
 }
 
 
 int main(){
 	int n,m,s;
 	scanf("%d %d %d",&n,&m,&s);
 	while(n!=0 || m!=0 || s!=0){
 		calc(n,m,s);
 		scanf("%d %d %d",&n,&m,&s);
 	}
 }