글 읽기 - 반례를 찾고 있습니다

daddy0h 4년 전 0

두 수의 부호가 같은 경우는 모두 통과하고 있는데, 부호가 다른 경우는 모두 틀렸습니다가 나와서 반례를 찾고 있습니다.

부호가 다른 경우

어느 쪽에 -가 있는지 기록합니다.
부호가 없는 문자열들로 입력을 바꿉니다.
절대값이 더 큰 문자열이 앞쪽에 있도록 만들어 줍니다.
문자열 길이가 짧은 문자열 크기만큼 한지리씩 계산해서 문자열 뒤에 붙여 줍니다.
길이가 긴 문자열에서 계산하지 않은 나머지 부분에서 carry들을 확인해서 문자열 뒤에 붙입니다.
문자열을 뒤집습니다.
문자열 앞쪽에 0 이 나오는 부분을 제거 합니다.
문자열이 모두 제거된 경우에는 "0"를 반환합니다.
더 큰 문자열의 부호를 반영해서 반환합니다.

시험해본 입렵들

10 -10

-10 10

1 -10

10 -1

1 -11

-11 1

10 -10000

-10000 10

/// https://www.acmicpc.net/problem/15740

/// -10^10000 <= A,B <= 10^10000
/// print A+B

#include <bits/stdc++.h>

using namespace std;

string big_plus(string str1, string str2)
{
    string str1_rev, str2_rev;
    string ret_str;
    int ret_flag=0;

    if(str1[0] == '-')
    {
        str1_rev = str1.substr(1);
        reverse(str1_rev.begin(), str1_rev.end());
        str2_rev = str2.substr(1);;
        reverse(str2_rev.begin(), str2_rev.end());
        ret_flag = -1;
    }
    else
    {
        str1_rev = str1;
        reverse(str1_rev.begin(), str1_rev.end());
        str2_rev = str2;
        reverse(str2_rev.begin(), str2_rev.end());
    }

    int size_a = str1_rev.size();
    int size_b = str2_rev.size();

    if(size_a > size_b)
    str2_rev.resize(size_a, '0');
    else if(size_b > size_a)
    str1_rev.resize(size_b, '0');

  /// plus string_a + string_b
    int x, y, car=0, ret=0;
    for(int idx=0; idx< str1_rev.size(); ++idx)
    {
        char t_char;

        x= str1_rev[idx] - '0';
        y= str2_rev[idx] - '0';
        ret = (x+y+car) % 10;
        car = (x+y+car) / 10;
        t_char = '0'+ret;
        ret_str += t_char;
    }
    /// handle last carry
    if(car == 1)
        ret_str += '1';

    reverse(ret_str.begin(), ret_str.end());

    if(ret_flag == -1)
        ret_str = "-"+ret_str;

    return ret_str;
};

bool isSmaller(string str1, string str2)
{
	int size_a = str1.size();
	int size_b = str2.size();
	bool s_flag = true;

	if (size_a < size_b)
    {
		return true;
    }
	else if (size_a > size_b)
    {
		return false;
    }
    else
    {
        for (int i=0; i<size_a; i++)
        {
            if (str1[i]-'0' <= str2[i] -'0')
            {
                continue;
            }
            else
            {
                s_flag = false;
                break;
            }
        }
        return s_flag;
    }
}

string big_sub(string str1, string str2)
{
    int str1_flag=0, str2_flag=0, ret_flag=0;
    string str1_rev, str2_rev, ret_str;

    if(str1[0] == '-')
    {
        str1_flag = -1;
        str1_rev = str1.substr(1);
        str2_rev = str2;
    }
    else if(str2[0] == '-')
    {
        str2_flag = -1;
        str1_rev = str1;
        str2_rev = str2.substr(1);
    }

    ret_flag = str1_flag;
    if (isSmaller(str1_rev, str2_rev))
    {
        swap(str1_rev, str2_rev);
        ret_flag = str2_flag;
    }

	int size_a = str1_rev.size();
	int size_b = str2_rev.size();
	int diff = size_a - size_b;

	// Initially take carry zero
	int carry = 0;
	char t_char;

    for(int id= size_b-1; id >= 0; --id)
    {
        int x = str1_rev[id+diff] - '0';
        int y = str2_rev[id] - '0';
        int sub = x - y - carry;
        if( sub < 0)
        {
        sub = sub+10;
        carry = 1;
        }
        t_char = '0' + sub;
        ret_str += t_char;
    }

    for(int id= size_a - size_b -1; id >= 0; --id)
    {
        int x = str1_rev[id] - '0';
        int sub = x - carry;
        if( sub < 0)
        {
        sub = sub+10;
        carry = 1;
        }
        t_char = '0' + sub;
        ret_str += t_char;
    }

    reverse(ret_str.begin(), ret_str.end());

    int zpos=0;
    for(int id=0; id<ret_str.size(); ++id)
    {
        if(ret_str[id] == '0') zpos++;
        else if(ret_str[id] != '0') break;
    }

    string tmp = ret_str.substr(zpos);
    ret_str = tmp;

    if(ret_str.size() == 0)
        return "0";

    if(ret_flag == -1)
        ret_str = "-"+ret_str;

    return ret_str;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string str_a, str_b, ret_str;
    cin >> str_a >> str_b;

    if(str_a[0] == '-' && str_b[0] == '-')
    {
        ret_str = big_plus(str_a, str_b);
    }
    else if (str_a[0] != '-' && str_b[0] != '-')
    {
        ret_str = big_plus(str_a, str_b);
    }
    else
    {
        ret_str = big_sub(str_a, str_b);
    }

    cout << ret_str << "\n";

    return 0;
}

daddy0h 4년 전 0

자답입니다.

9876543210 -1234567890

7531975320

correct: 8641975320

carry를 없는 경우에 다시 0으로 초기화 시켜야 하는 부분이 빠져 있었습니다.

- 채점 %가 화면에 100%를 넘어서 104%까지 나타납니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾고 있습니다

daddy0h 4년 전 0

daddy0h 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말