-3

私はこの問題をやろうとしていましたが、それを受け入れることができませんでした、その入力が大きいので、文字列でそれを取ると思いましたが、それでも私は間違った答えを得ています。問題の説明はこちらBISHOPS

これが私のコードです：

#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>

using namespace std;

int main()
{
    string s;
    int z;
    cin>>s;
    z = s.length();
    int i;
    vector<int>v;
    int arr[z];
    for(i=0;i<z;i++)
    {
        arr[i] = (s[i]-'0');
    }

    if ((arr[0] == 0 || arr[0] ==  1) && z == 1)
    {
        printf("%d",arr[0]);
    }
    else
    { 
        int carry = 0;
        for(i=z-1;i>=0;i--)
        {
            int x = (carry + 2*arr[i])%10;
            v.push_back(x);
            carry = ( 2*arr[i] )/10;
        }
        if(carry > 0)
        {
            v.push_back(carry);
        }

        int t = v.size();
        int g=0;
        if(v[g] >=2)
        {
            v[g] = v[g]-2;
        }
        else
        {
            v[g] = 8;
            g++;
            while(v[g] == 0)
            {
                v[g] = 9;
                g++;
            }
            v[g] = v[g] -1;
        } 


        if(v[t-1] == 0)
        {
            for(i=t-2;i>=0;i--)
                {
                    printf("%d",v[i]);
                }
        }
        else
        {
            for(i=t-1;i>=0;i--)
            {
                printf("%d",v[i]);
            }
        }
    }

        return 0;
}

質問は、nxnチェス盤の問題で攻撃不可能な最大の司教を見つけることです。すべてのチェス盤の1x1を除いて、攻撃不可能な最大の司教は2 * n-2になるので、私は正しいと思います。しかし、それでもspojは間違った答えを出します。

4

1 に答える 1

2

より大きいすべての入力に対して整数オーバーフローがありますINT_MAX:

int y=0,i,z;
z = s.length();
for(i=0;i<z;i++)
{
    y = y*10 + (s[i]-'0');
}

入力を に変換しようとしています。これは通常、2147483647 = 2 31 -1に等しいint符号付き 32 ビット型です。入力がそれよりも大きい場合は常に、10 桁目でオーバーフローが発生します (ちなみに、これは未定義の動作です)。INT_MAX

それよりも大きい 10 100までの数値を表現/処理する方法が必要です。C または C++ の標準整数型は、それを処理するのに十分な幅はありません。独自の big-integer 型を展開する必要があります (SPOJ はおそらくコードを GMP とリンクしていないため)。この問題では、非常に単純なもので十分に機能します。

于 2012-06-03T14:21:01.693 に答える