コンテストテーマ解説-【Japan 2002 Kanazawa】シュレッダー

【Japan 2002 Kanazawa】シュレッダー
あなたが今新しい紙くず機の設計を担当していることを説明します.一般的な紙くずの機会は紙を小さく切って、読みにくくなります.あなたが設計した新しい紙くず機には以下の特徴があります.

1.      ，            ，                       。
2.                 。
3.                              。

一例を挙げると、以下の図に示すように、ここでは、ターゲット数が50であり、入力紙片の数が12346であると仮定する画像を書く.紙くずは4枚に切り、それぞれ1、2、34、6を含む.このようにこれらの数の和は43(=1+2+34+6)であり,これはすべての分割方式の中で50を超えず,最も50に近い分割方式である.また、例えば、1、23、4、6に分割するのは正しくありません.このような総和は34(=1+23+4+6)であり、さっき得られた結果43より小さいからです.12,34,6に分割するのも正しくありません.この場合の総和は52(=12+34+6)であり、50を超えているからです.3つの特別なルールがあります.

1.               ，         。
2.        ，                 ，           。
3.                       。             。  ，      15，        111，                 ，      1 11     11 1，      ，            。

このような紙くず機を設計するには、まず簡単なプログラムを書いてこのプリンタの仕事をシミュレートする必要があります.2つの数を与えて、1つ目は目標数で、2つ目は紙片の数を入力して、あなたは紙片に対する粉砕機の分割方式を与える必要があります.
入力入力には複数のデータが含まれ、各グループには1行が含まれます.各行には2つの正の整数が含まれており、それぞれ目標数と入力紙片の数を表しています.既知の入力保証:両方の数は0で始まることはなく、両方の数は最大6つの数字しか含まれていません.入力の最後の行には、入力の終了を示す2つの0が含まれます.各入力データのセットを出力し、対応する出力を出力します.3つの異なる出力結果があります.

sum part1 part2 ...
rejected
error

1つ目の結果は、1.各partjは、切断された紙片の数である.partjの順序は,入力紙片上の元の数に数字が現れる順序と一致する.2.sumは、カットされた紙片の数の和、すなわちsum=part 1+part 2+…第1の結果で隣接する2つの数の間を1つのスペースで区切る.どのようにカットしても、分割した紙片の数の和が目標数より大きい場合は、「error」を印刷します.同じ最適結果を得るには、さまざまなカット方法がある場合は、「rejected」を印刷します.
サンプル入力

50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0

サンプル出力

43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected

問題の解析という問題は直接見ると非常に複雑で、方法を考え出すのは容易ではありません.私たちはプログラムを書きながら考えを整理したほうがいいです.まず外層の循環です.テーマの入力には具体的なグループ数が与えられていないため,forループで書くのは不便であるため,while無限ループ(do-whileは推奨しない)を選択した.しかし、プログラムをこのまま進めることはできません.問題の入力に終わり条件が与えられています.終了条件に基づいて,入力が0の場合にbreakでループを終了すればよい(return 0で直接プログラムを終了することもできる).
また入力です.テーマは整数を入力するということですが、intで保存する必要はありません.#includeのstring(文字列)タイプにはサブストリングを探すための関数substrが含まれていることを知っています.本題に連絡すると、分割をすべてのサブストリングを見つけることができると理解できます.そこで、著者らはintで分割する数を保存するのではなく、stringで保存することを選択しました.注意stringはcinでしか読み込めません.
次に変数を定義します.具体的には以下の通りです.

 1.      （  ，sum、begin    0，Q         ，    ）：
 sum(int)-        ；
 begin(int)-            ；
 Q(bool)-                              
 2.     ：
ma(map< long,int >)-            ，       ，          ；
a(int)-   ；
ans(int)-        ，            ；
num(string)-       ；
can(bool)-                     ；
vec(vector< int >)-                   （  ）；
size(int)-               

著者らは関数を書き,2つの用途を持っていることを見ました.1つは、すべての分割スキームにおける合計が所定数よりも小さい最大数、すなわち、出力において条件が満たされたときに出力される最初の数を探し出すことである.別の用途を区別するために,著者らはQで表す.この用途のマークはfalseです.まず、分割が完了したか否かを判断するif文であり、このときの分割が必要な位置の下付きが最後の数であれば、分割は完了する.ここまで実行すると,2つの用途に違いがあるため,著者らはQで区別し,Q=falseの場合,ma中の現在分割された合計出現回数+1を,現在の最大結果を保存する.さらにforサイクルで切断の長さを順次列挙し,beginからサブストリングを取り出してzc(string)に格納し,intタイプに移行してzcnum(int)に格納する.次に、次の検索を行います.もう1つの用途は,条件を満たす分割結果を見つけた後,この答えを分割するスキームを見つけることである.最初のif判定とforサイクル終了時のみ、最初の用途と区別する:1.if文でQ=true(第2のスキーム)であれば,このときの結果が最終的な答えであるかどうかを再判断する必要がある.もしそうなら、canの値を変えて、逆戻りします.2.for文でQ=trueの場合、検索完了後にcanがtrue(スキーマが見つかったかどうか)であるか否かを判断し、もし、vecに格納する.注意vecが格納した答えは逆シーケンスです.
最後にメインプログラムのwhileループを見てみましょう.手順は簡単です:1.グローバル変数を初期化します.2.入力;3.呼び出し関数4.判断結果——1回目の呼び出しで適切な答えが見つからなかった場合は「error」.最大結果が2回以上現れた場合は「rejected」である.最大結果が1回しか現れない場合は、関数を呼び出し、シナリオを見つけ、逆シーケンスで出力します.
余談ですがchar配列はsscanfでintタイプに変換できることは知っていますが、stringをintに変換するにはどうすればいいですか?stringという内部関数を探してc_を見つけることができますstrの関数は、現在のstring文字列のchar配列形式を返し、sscanfでintタイプに変換できます.
プログラムサンプル

#include
#include
#include
#include
#include
#include
using namespace std;
int size,a,ans;
map<long,int> ma;
string num;
bool can;
vector<int> vec;
void flag(int sum,int begin,bool Q)
{
    if(sum>a) return;
    if(begin==size)
    {
        if(!Q)
        {
            ma[sum]++;
            ans=max(ans,sum);
        }
        else
            if(sum==ans) can=true;
        return;
    }
    for(int i=1;i<=size-begin;i++)
    {
        string zc=num.substr(begin,i);
        int zcnum;
        sscanf(zc.c_str(),"%d",&zcnum);
        flag(sum+zcnum,begin+i,Q);
        if(can && Q)
        {
            vec.push_back(zcnum);
            return;
        }
    }
}
int main()
{
    while(true)
    {
        ans=-1e8;
        can=false;
        ma.clear();
        vec.clear();
        scanf("%d",&a);
        cin>>num;
        if(!a && num=="0") break;
        size=num.length();
        flag(0,0,0);
        if(ans<0) printf("error
");
        else
            if(ma[ans]==1)
            {
                printf("%d",ans);
                flag(0,0,1);
                for(int i=vec.size()-1;i>=0;i--)
                    printf(" %d",vec[i]);
                printf("
");
            }
            else printf("rejected
");
    }
    return 0;
}