3

CodinGame.comでこの問題を解決していたところ、最後のテスト ケース (非常に大きなテスト ケース) のシステム テストに合格するコードを書くことができました。しかし、ラップトップでコンパイルすると、コードがマシンから提供した 57330892800 の代わりに 0 の出力が得られます。Visual Studio 2012 Express と Dev C++ 4.9.9.2 の両方でコンパイルしました。

再帰関数を使用したため、スタック メモリが不足していた場合、スタック オーバーフロー エラーが発生すると予想していましたが、エラーはなく、何も出力されず、出力は 0 でした。サイトのマシン？スタックオーバーフローであるとは思えないので、これを引き起こした原因は何ですか?

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<vector>

using namespace std;
typedef long long LONG;


string X[]={".-","-...","-.-.","-..",
            ".","..-.","--.","....",
            "..",".---","-.-",".-..",
            "--","-.","---",".--.",
            "--.-",".-.","...","-",
            "..-","...-",".--","-..-",
            "-.--","--.."};
map<string, int> dict;

string morse(const string ret){
        string s;
        for(char c : ret) s+=X[c-'A'];
        return s;
}

LONG decode(int start, string &word, vector<LONG> &mem){
        if(start == word.size()) return 1;
        else if(mem[start] != -1) return mem[start];

        LONG res = 0;
        string s;
        for(int i=0; i<19*4 && start+i<word.size(); i++){
                s+=word[start+i];
                auto curr = dict.find(s);
                if(curr!=dict.end()) res+=curr->second*decode(start+i+1, word, mem);
        }
        mem[start]=res;
        return res;
}

int main(){
        string word;
        cin>>word;
        int n; cin>>n;
        for(int i=0; i<n; i++){
                string s;
                cin>>s;
                dict[morse(s)]++;
        }
        vector<LONG> mem(word.size(), -1);
        cout<<decode(0, word, mem)<<endl;
}
4

2 に答える 2

7

私はあなたのコードを最小限のプログラムに落とし込むことができたと思います:

#include<iostream>
#include<string>

using namespace std;

int main(){
        string word;
        cin>>word; // or getline(cin, word);
        cout << word.size() << endl;
}

テスト ケース入力ファイルの結果:

  • Codinggame (with test=4) では、9884(予想どおり) 印刷されます。
  • 私のパソコンで、ソース ファイルを " prog" という名前のバイナリにコンパイルした後、ターミナル コマンドライン (コンソール) から:
    1. ./progファイルからテキストをコピーしてコンソールに貼り付けると、出力されます（4095悪い）。
    2. 代わりに実行./prog < Test_4_input.txtすると、印刷されます9884（良い）。

1. (IDE からプログラムを起動し、テキストを「コンソール」タブに貼り付ける) と同等のことを行ったと仮定しますが、Codingame は 2. のように「動作」し、ここで説明する問題が発生しました: Linux 端末入力: 読み取り端末からのユーザー入力は、4095 文字の制限で行を切り捨てます(読み取りバッファーには 4096 バイトのサイズ制限があるようです (そして改行文字に最後の 1 つを使用するため、4095 で切り捨てられます))。

編集：私がそれを見つけた方法について：

あなたと同じように、私は IDE (Eclipse) でプログラムを実行し、ファイルの内容を組み込みの入力コンソールにコピー アンド ペーストすることから始めました0。そこで、コードの微調整と IDE でのデバッグを開始しました。

最初にグローバルカウンター(0 に初期化) を追加し、関数が呼び出された回数を確認するために、 の最初の行でインクリメントdecodeされ、最後に出力されました。mainその最終的な価値はCodinggame にありましたが、私の IDE1254だけでした。そのため、インクリメントの直後に条件付きブレークポイント を設定し(条件: カウンター == 541)、デバッガーを起動してコードにステップ インしたところ、ループが早期に終了したことがわかりました。次に、ローカル変数を調べたところ、.of があることに気付きました。4096 マイナス 1で 2 のべき乗なので、私はそれが「おかしい」と感じました。あなたが見るときのように、あなたは知っています。541
decodewordsize40954096255
そこで、テキスト エディタを開いて、入力ファイルの最初の行だけをコピーして貼り付けたところ、その長さが 4095 ではなく 9884 であることがわかりました。今、問題を感じ始めていました。そこで、コードを上に示した最小限のテスト ケースに落としてから、コマンド ライン ターミナルに切り替えてチェックし (Codinggame が を使用して Bash テスト スクリプトを表示していることを確認しましたsolution < in$test.txt)、Web を少し検索して同様の問題への参照を見つけました。 （上記のリンクされた質問のように）。「パズルが解けました。」

うまくいけば、それがあなたの将来の問題を自分で解決するのに役立つでしょう:)

于 2013-09-05T11:16:56.110 に答える
0

あなたの場合、 start ==0 と mem[start] == 0 だと思うので、初めて呼び出されたときにデコードは 0 を返します。

デコード関数の先頭に次の 2 行を追加して、該当するかどうかを確認します。

cout << start;
if(mem[start] != -1) return mem[start];
于 2013-09-04T22:28:40.850 に答える