任意の金額をお札の枚数で表現するプログラムを再帰関数で書きたい

Question

こちらの問題を解いていました
お札n枚でY円を作ることが可能か、可能な場合は一つだけその組を出力せよ、という問題です
これは単純な全探索で解くことができ、自力で解くことができました
しかし初めは再帰関数を使おうと思って解こうと思ったのですが、それではうまくいきませんでした
色々試してごちゃごちゃですが、コードは以下の通りでした
なおコメントアウトの部分はメモ化を行おうとしたけどメモリが足りなくなったのでやめた跡です（多分vectorを使えばいけると思いますが、今回はそこまで制約の厳しい問題ではないので）

#include<bits/stdc++.h>
using namespace std;

//long long dp[2000][2000][2000];

bool solve(long long x,long long y,long long z,long long n,long long Y){
/*	if(dp[x][y][z]!=-1){
		return dp[x][y][z];
	}*/
	int flag=0;
	long long sum=0;
	long long res;
	long long *ans_x=0,*ans_y=0,*ans_z=0;
	sum = x*1000+y*5000+z*10000;
	//cout<<sum<<endl;
	if((x+y+z)==n){
		if(sum==Y){
			//cout<<z<<" "<<y<<" "<<x<<endl;//複数出力されてしまう
			flag=1;
			*ans_x=x;
			*ans_y=y;
			*ans_z=z;
			return true;
		}
	}else if((x+y+z)<n){
//		return dp[x][y][z]=solve(x+1,y,z,n);
//		return dp[x][y][z]=solve(x,y+1,z,n);
//		return dp[x][y][z]=solve(x,y,z+1,n);
		solve(x+1,y,z,n,Y);
		solve(x,y+1,z,n,Y);
		solve(x,y,z+1,n,Y);
	}else{
		//return false;
	}
}

int main(){
//	memset(dp,-1,sizeof(dp));
	long long n,Y;
	cin>>n>>Y;
	long long x=0,y=0,z=0;
	long long *ans_x=0,*ans_y=0,*ans_z=0;
	long long check=n*10000;
	if(check<Y){
		cout<<"-1 -1 -1"<<endl;
	}else{
		if(solve(x,y,z,n,Y)){
			//cout<<"aaa"<<endl;
			cout<<*ans_z<<" "<<*ans_y<<" "<<*ans_x<<endl;
			return 0;
		}else{
			cout<<"-1 -1 -1"<<endl;
		}
	}
	return 0;
}

再帰関数では見ての通り、1000円、5000円、10000円札のどれかを1つ増やしていって、合計枚数がnと一致すれば出力といった風にしたいです
しかし、再帰関数では並列処理が行われてしまうため、プログラムが試した全ての組みが出力されてしまいます。単純にフラグを建てる方法などでは無意味でした
そのためポインタを使って、最初に見つけたお札の組みをmain関数に送ろうと考えたのですが、現状ではx+y+z>nのとき(solve関数内のelseの部分です)も試されてしまっており、ここを何とかしなければならないのですが、どうすれば良いのか分かりませんでした
それにより挙動が意味不明なため、ポインタの処理はちゃんと書けていません

どなたか正しい書き方をご教授いただけないでしょうか
よろしくお願いします

Comments

[bochan2]

質問頂きありがとうございます。
この書き方だと再帰関数は並列実行されないと思います。
紙に実行順をメモしながら実装してはいかがでしょうか？

[bochan2]

数秒考えてみたんですが、単純に10000円から枚数を確定させてけばできると思います

[l_h_l_h]

ありがとうございます
しかし出力が複数行われてしまうのですが、それはどうしてでしょうか……
一万円から確定させる方法は後ほど試させていただきます
ありがとうございます

Answer 1

ヌルポインタへのアクセスが発生しています。

bool solve(long long x,long long y,long long z,long long n,long long Y){
...
long long *ans_x=0,*ans_y=0,*ans_z=0;
...
*ans_x=x;
*ans_y=y;
*ans_z=z;

また、ここのans_xyzとmain関数のans_xyzは全くの別物です。
変数の使い方及びポインタの使い方を再確認しましょう。

書いてみた

TLEを回避するのにそれなりに苦労しましたが、再帰でAC取りました。

#include <iostream>


struct Answer {
    int yen_10000;
    int yen_5000;
    int yen_1000;
    
    bool is_valid() { 
        return yen_10000 != -1;
    }
    
    void print() {
        std::printf(
            "%d %d %d\n",
            yen_10000, yen_5000, yen_1000
        );
    }
};

struct Cond {
    bool use_10000 = true;
    bool use_5000  = true;
    bool use_1000  = true;
};


// n枚で1000*y円作る組み合わせを返す
Answer solve(const int n, const int ky, Cond cond) {
    //
    if(n == 0 && ky == 0) {
        return {0, 0, 0};
    }
    if(ky == 0) {
        return {-1, -1, -1};
    }
    if(ky == n) {
        return {0, 0, n};
    }
    
    //
    if(cond.use_10000) {
        for(int num = ky / 10; num >= 0; --num) {
            auto ans = solve(
                n - num, ky - num*10,
                {false, true, true}
            );
            if(ans.is_valid()) {
                ans.yen_10000 += num;
                return ans;
            }
        }
    }
    if(cond.use_5000) {
        for(int num = ky / 5; num >= 0; --num) {
            auto ans = solve(
                n - num, ky - num*5,
                {false, false, true}
            );
            if(ans.is_valid()) {
                ans.yen_5000 += num;
                return ans;
            }
        }
    }
    
    return {-1, -1, -1};
}

int main(void) {
    int N, Y;
    std::cin >> N >> Y;

    solve(N, Y/1000, {}).print();
}

提出結果

競プロには不慣れなので、無駄な処理をいっぱい書いていると思いますが。

---

自由に解いて良いなら、こう。

#include <cstdio>

int main(void) {
    int N, Y;
    if(std::scanf("%d %d", &N, &Y) != 2)	return 1;

    int D = Y / 1000 - N;
    for(int a = 0; a <= N; ++a) {
        if(10000 * a > Y)   break;

        int tmp = D - 9*a;
        if(tmp % 4 == 0) {
            int b = tmp / 4;
            int c = N - a - b;
            
            if(b < 0)   continue;
            if(c < 0)   continue;
            
            std::printf("%d %d %d\n", a, b, c);
            return 0;
        }
    }

    std::printf("-1 -1 -1\n");
}

提出結果

Comments

[l_h_l_h]

ありがとうございます
すみません、ポインタを追加したのは本当に最後の最後で、ポインタを実装する前から挙動がよくわからず、そこのコードは適当に書いてしまいました（そもそもポインタが正しく動くかどうかも試せないので……）
変数が別物の件についてはご指摘の通りですね
コードを修正してから質問投稿すべきでした 申し訳ありません
ポインタについては、solve関数でmain関数のx,y,zのアドレスを指して書き換えていく、という認識なのですが、引き渡す変数をポインタ（&xで渡して*xで受け取る）にしてしまうと再帰がうまく動かないので、そこでも詰まってしまっています

[LouiS0616]

再帰で解いてみました。

Answer 2

コンテストだと最初のコード書いた後で知って、コード削って用件を満たした感じに書き換えた。スリムにした。AtCoderアカウントもってないので提出してない。書き逃げ野郎です。

#include <stdio.h>

int b[] = { 5, 2, 0 };

int solve(int n, int *r) {

int i, _n = r[0] + r[1] + r[2];

if ( _n == n) return 1;
if (_n < n) return 0;

for (i=2; i>=0; i--) {
if (b[i] != 0 && r[i] >= b[i]) {
r[i] -= b[i];
r[i+1]++;
return solve(n, r);
}
}

return 0;
}

int main(void){

int Y, N, a[]={0,0,0};

if (2 != scanf ("%d %d", &N, &Y)) return 1;

a[0] = Y /= 1000;

if (!solve(N, a)) a[2]=a[1]=a[0]=-1;
printf ("%d %d %d\n", a[2], a[1], a[0]);
return 0;
}

最初に暇を持て余して書いたコード、アプローチは最小紙幣から両替して大きい方へ探索する。両替なので金額は変動しない、故に紙幣枚数だけで分岐。紙幣の種類と額面は任意に増やせる感じで書いてた。５００円札とか、２０００円札とかね。
コンテスト要件をしらず、コマンドラインから引数を得る、しかも逆順（笑）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>

/* solverと返す値とその説明文
*/
int solver(const int bill, int *result);
enum {
RVAL_MATCH,
RVAL_LACKBILL,
RVAL_USEUP,
RVAL_RUNATIC,
};

char * msg[] = {
"金額と枚数のマッチ",
"紙幣枚数不足",
"組み合わせが尽きた",
"無理だ！ルナティック経済",
};

/* 設定項目

貴方の生活圏によって変えましょう。

RADIX: 入力基数
UNIT: 最小紙幣額面
KIND_OF_BILLS: 紙幣の種類

const struct {
value: 紙幣の額面を最小紙幣額面で割った値
exchange: 一つ上の紙幣への両替に必要な枚数（0は両替不可）
}

動作に必要な条件
bills配列には、紙幣額面の小さい物から設定すること。

五百円札があった時代なら、こんな風かもね。

#define UNIT 500
#define KIND_OF_BILLS 4

const struct { ...  } bills[KIND_OF_BILLS] = {
  { 500/UNIT, 2},
  {1000/UNIT, 5},
  {5000 ...
};
                                                                        */

#define RADIX 10
#define UNIT 1000
#define KIND_OF_BILLS 3

const struct {
int value;
int exchange;
} bills[KIND_OF_BILLS] = {
{ 1000/UNIT, 5},
{ 5000/UNIT, 2},
{10000/UNIT, 0}
};

enum {AMOUNT, NBILL, NUM_OF_ARGS};

int main(int argc, char **argv){

int i, in[NUM_OF_ARGS], surplus, ret_val;
int result[KIND_OF_BILLS];
char *endp;

if (--argc != NUM_OF_ARGS) {
return fputs ("Usage:\taout [amount] [in[NBILL]]\n", stderr);
}

/* 入力から変数を得る
/
errno = 0;
for (i=0; i<NUM_OF_ARGS; i++) {
in[i] = strtol (++argv, &endp, RADIX);
if (errno != 0||*argv == endp||in[i] == LONG_MAX||in[i] == LONG_MIN) {
exit(EXIT_FAILURE);
}
}

/* 金額調整

単位金額で割る事で考慮不要な下数桁の連続する'0'を消し、端数捨て。
                                                                        */

surplus= in[AMOUNT] % UNIT;
in[AMOUNT] = in[AMOUNT] / UNIT;

fprintf (stderr, "%s下記の金額で探す\n\n金額 %d円を、紙幣 %d枚で表現する。\n\n",
(surplus)?"端数金額は無視、":"", in[AMOUNT]*UNIT, in[NBILL]);

/* 金額をすべて一番少ない紙幣に両替して、探索開始
/
memset (result, 0, KIND_OF_BILLSsizeof(result));
result[0] = in[AMOUNT]/bills[0].value;

/* 狂気の経済世界からやってきた人は再帰関数に入れない

1,000円x4枚で、3,000円にできる世界からやって来たんですね、あなた
                                                                        */

ret_val = (in[NBILL] > in[AMOUNT]) ? RVAL_RUNATIC : solver(in[NBILL], result);
fprintf (stderr, "%s\n", msg[ret_val]);

return EXIT_SUCCESS;
}

int solver(const int nbill, int *result) {

int i, _nbill = 0;

/* 枚数の計算と、経過出力(最終メッセージと併せて結果の出力にも兼用)
/
for (i=KIND_OF_BILLS-1; i>=0; i--) {
_nbill += result[i];
fprintf (stderr, " %8d x %d", result[i], bills[i].valueUNIT );
}
fputc ('\n',stderr);

/* 枚数&金額が一致、又は紙幣不足
*/
if ( _nbill == nbill) {
return RVAL_MATCH;
}
else if (_nbill < nbill) {
return RVAL_LACKBILL;
}

/* 紙幣超過

現時点で保持する最大額面の紙幣を、一つ上の額面の紙幣に両替していく
                                                                          */

for (i=KIND_OF_BILLS-1; i>=0; i--) {
if (bills[i].exchange != 0 && result[i] >= bills[i].exchange) {
result[i] -= bills[i].exchange;
result[i+1]++;
return solver(nbill, result);
}
}

/* 組み合わせが尽きた
*/
return RVAL_USEUP;
}

Answer 3

一万円から、求めるのが確かに簡単ですね。

1. まず、10,000で割った数を一万円札の数とする。(整数演算)
2. 余りを 5,000で割った数を五千円札の数とする。

.... 以下、同様 (二千円はどうする?)

とすれば、他の貨幣も OKと思ったが、ドルとかの クォーターがある場合だと、別解の方がよい場合がありそうなのはどうしたものか?