Задача на длинную арифметику

@dx3n · Регистрация: 15.06.2020

Студворк — интернет-сервис помощи студентам

Всем привет

. Помогите пожалуйста решить задачу на длинную арифметику.

Условие:
Число задаётся группами подряд идущих в десятичной записи цифр. То есть число 111 задаётся как 3 1, число 2020 — как 1 2 1 0 1 2 1 0, число 222 233 как 4 2 2 3. Отметим, что длина группы должна быть максимальной, то есть запись 2 2 2 2 2 3 в последнем случае является некорректной. Вводятся два числа в вышеуказанном формате. Требуется вывести их сумму в том же формате.

Ввод:
Первая строка входных данных содержит целое число N1 — количество групп одинаковых цифр в записи первого слагаемого (1 ≤ N1 ≤ 100). i-я из последующих N1 строк содержит по два целых числа ni и di (1 ≤ ni ≤ 1018, 0 ≤ di ≤ 9). Гарантируется, что соседние di всегда различны, d1 ≠ 0 и сумма всех ni не превосходит 1018.
Далее в аналогичном формате задаётся второе слагаемое.

Вывод:
Выведите сумму в том же формате, в котором заданы слагаемые.

Примеры:
Ввод ->
3
2 2
3 3
9 9
1
1 1
Вывод ->
4
2 2
2 3
1 4
9 0

@nonedark2008 · 20.06.2020, 18:38

Сообщение от dx3n

Помогите пожалуйста решить задачу на длинную арифметику.

А с чем у тебя сложности?

Сообщение от dx3n

Число задаётся группами подряд идущих в десятичной записи цифр.

Это по своей сути сжатие алгоритмом RLE. Тебе нужно разжать два числа, сложить и результат сжать обратно. Так как числа у тебя не особо большие, то длинную арифметику можно сделать в самом примитивном виде, примеры можно найти через поиск.

@rembor · 20.06.2020, 19:08

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n = int(input())
s1 = ''
for i in range(n):
    c,d = map(int,input().split())
    s1 += ("%d"%d)*c
x = int(s1)
m = int(input())
s2 = ''
for i in range(m):
    c,d = map(int,input().split())
    s2 += ("%d"%d)*c
y = int(s2)
a = "%d"%(x+y)
count = []
 
i = 0
while (i  < len(a)):
    c = 0
    s = a[i]
    while ((i < len(a)) and a[i] == s):
        c += 1
        i += 1
    count.append((c,s))
print(len(count))
for i in count:
    print(*i)

Добавлено через 1 минуту
re на третьем тесте

@dx3n · 20.06.2020, 19:31 **[ТС]**

nonedark2008, в этом то и вся сложность. Такое решение не проходит по времени. Про RLE я то знаю и это и была моя первая идея)

@nonedark2008 · 20.06.2020, 19:50

dx3n, а какие у тебя ограничения по времени?
У тебя числа размером максимум n=1018. Сложность сложения O(n), разжатие/сжатие RLE O(n). Если упираешься во время, значит что-то и перечисленного ты выполняешь неэффективно.
Код показать можешь?

@dx3n · 20.06.2020, 20:21 **[ТС]**

Может немного косячно, но как-то вот так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import math
 
def make_num(n : int):
    answer = 0
    for i in range(n):
        ni, di = map(int, input().split())
        for i in range(ni):
            answer *= 10
            answer += di
    return answer
 
a = int(input())
num1 = make_num(a)
b = int(input())
num2 = make_num(b)
 
num3 = num1 + num2
digits = int(math.log10(num3)) + 1
dictionary = {}
count = 0
for i in range(digits):
    if num3 % 10 not in dictionary:
        dictionary[num3 % 10] = 1
        count += 1
    else:
        dictionary[num3 % 10] += 1
    num3 //= 10
 
print(count)
 
answer = []
for i in dictionary:
    answer.append([dictionary[i], i])
answer = answer[::-1]
 
for i in answer:
    print(" ".join(map(str, i)))

@TheCalligrapher · 20.06.2020, 20:23

Сообщение от nonedark2008

Тебе нужно разжать два числа, сложить и результат сжать обратно.

Совсем не обязательно вот так вот изолировать эти этапы. Сложение - операция последовательная, цифра за цифрой. Нет никакой сложности решить задачу не производя явной распаковки.

@nonedark2008 · 20.06.2020, 20:34

Сообщение от dx3n

Может немного косячно, но как-то вот так:

Я слишком плохо знаю Python, чтобы судить об эффективности твоего кода.

Сообщение от dx3n

Python
1
2
3
4
5
6
7
for i in range(digits):
    if num3 % 10 not in dictionary:
        dictionary[num3 % 10] = 1
        count += 1
    else:
        dictionary[num3 % 10] += 1
    num3 //= 10

Крайне подозрительный цикл. В dictionary будет записано не более 10 элементов. Задача предполагает, что результат может быть намного длиннее.

Добавлено через 2 минуты

Сообщение от TheCalligrapher

Нет никакой сложности решить задачу не производя явной распаковки.

Да, конечно. Но при решении таких задач обычно начинают с решение "в лоб", а уже потом, если потребуется, занимаются оптимизациями.

@TheCalligrapher · 20.06.2020, 20:36

Сообщение от nonedark2008

Да, конечно. Но при решении таких задач обычно начинают с решение "в лоб", а уже потом, если потребуется, занимаются оптимизациями.

А я бы сказал, что даже наоборот: распаковка в данном случае - ненужная трудоемкая операция как с реализационной, так и с вычислительной точки зрения. Решение прямо на RLE - это и есть решение "в лоб", а не оптимизация.

@dx3n · 20.06.2020, 20:45 **[ТС]**

nonedark2008, я понял проблему этого кода. Он будет считать цифры в общей сложности. Но там возможны моменты когда будет число вида 111111.....222222222....111111111 и тогда решение ломается

@nonedark2008 · 20.06.2020, 21:40

Сообщение от dx3n

Он будет считать цифры в общей сложности.

Да так и есть. На раз ты упираешься во время выполнения, то простым исправлением ошибки ты не отделаешься.

Я на плюсах собрал некоторое решение, может оно наведен тебя на мысли. Особо я его, конечно, не тестировал.

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
using num_t = vector<pair<int, int>>;
 
num_t readNum()
{
    num_t v;
    int n;
    cin >> n;
    v.reserve(n);
    
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
 
    return v;
}
 
int getDig(const num_t &num, int &pos, int &count)
{
    if (count > 0)
    {
        --count;
        return num[pos].second;
    } if (pos > 0)
    {
        --pos;
        count = num[pos].first;
        return getDig(num, pos, count);
    }
    else
        pos = -1;
 
    return 0;
}
 
int main()
{
    auto a = readNum();
    auto b = readNum();
    num_t res;
 
    int a_pos = a.size(), a_count = 0;
    int b_pos = b.size(), b_count = 0;
 
    int res_dig = 0;
    int res_count = 0;
    int res_carry = 0;
    while (a_pos != -1 || b_pos != -1)
    {
        int a_dig = getDig(a, a_pos, a_count);
        int b_dig = getDig(b, b_pos, b_count);
 
        int dig = a_dig + b_dig + res_carry;
        res_carry = dig >= 10;
        dig %= 10;
 
        if (dig != res_dig && res_count)
        {
            res.emplace_back(res_count, res_dig);
            res_count = 1;
        }
        else 
            ++res_count;
 
        res_dig = dig;
    }
 
    if (res_dig != 0)
        res.emplace_back(res_count, res_dig);
 
    cout << res.size() << '\n';
    for (auto it = res.rbegin(); it != res.rend(); ++it)
    {
        cout << it->first << ' ' << it->second << '\n';
    }
}

Идея простая. Считываем два числа как есть. Далее по порядку извлекаем разряды из чисел, суммируем, учитывая перенос, и параллельно подсчитываем количество повторяющихся символов в результате.

@dx3n · 21.06.2020, 01:52 **[ТС]**

nonedark2008, спасибо за код я обязательно над этим подумаю)

Добавлено через 3 часа 37 минут
nonedark2008, на ваш код пишет TL

@nonedark2008 · 21.06.2020, 04:38

Сообщение от dx3n

на ваш код пишет TL

А что обозначают TL и RE?

@Kuzia domovenok · 21.06.2020, 05:19

Сообщение от nonedark2008

У тебя числа размером максимум n=1018.

это он так 10 в степени 18 пишет

@nonedark2008 · 21.06.2020, 06:30

Сообщение от Kuzia domovenok

это он так 10 в степени 18 пишет

Если это так, то значит нужно складывать напрямую блоками.

@AnyKey · 21.06.2020, 09:19

dx3n, а где тестится эта задача?

@dx3n · 21.06.2020, 10:10 **[ТС]**

TL - time limit. Программа выполняется дольше максимального времени.

@nonedark2008 · 21.06.2020, 17:41

dx3n, тогда вот такой вариант с суммированием по блокам:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
using num_t = vector<pair<uint64_t, int>>;
 
num_t readNum()
{
    num_t v;
    int n;
    cin >> n;
    v.reserve(n);
    
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
 
    return v;
}
 
void appendNum(num_t& num, const pair<uint64_t, int>& val)
{
    if (!num.empty() && num.back().second == val.second)
        num.back().first += val.first;
    else if (val.first)
        num.push_back(val);
}
 
void processSumBlock(num_t &res, uint64_t size, int sum, int& carry)
{
    appendNum(res, { 1, (sum + carry) % 10 });
    size -= 1;
    carry = (sum + carry) >= 10;
    sum += carry;
 
    appendNum(res, { size, sum % 10 });
}
 
int main()
{
    auto a = readNum();
    auto b = readNum();
    num_t res;
 
    auto aIt = a.rbegin();
    auto bIt = b.rbegin();
 
    int resCarry = 0;
 
    while (aIt != a.rend() && bIt != b.rend())
    {
        uint64_t size = min(aIt->first, bIt->first);
        int sum = aIt->second + bIt->second;
 
        aIt->first -= size;
        bIt->first -= size;
 
        if (!aIt->first)
            ++aIt;
        if (!bIt->first)
            ++bIt;
 
        processSumBlock(res, size, sum, resCarry);
    }
 
    while (aIt != a.rend())
    {
        processSumBlock(res, aIt->first, aIt->second, resCarry);
        ++aIt;
    }
    while (bIt != b.rend())
    {
        processSumBlock(res, bIt->first, bIt->second, resCarry);
        ++bIt;
    }
 
    if (resCarry)
        processSumBlock(res, 1, 0, resCarry);
 
    cout << res.size() << '\n';
    for (auto it = res.rbegin(); it != res.rend(); ++it)
        cout << it->first << ' ' << it->second << '\n';
}

@rembor · 21.06.2020, 19:01

nonedark2008, а тут уже неправильный ответ на третьем тесте

@nonedark2008 · 21.06.2020, 20:27

Сообщение от nonedark2008

int a, b;

Как минимум вот тут должно быть uint64_t a; int b;.
Возможно, я еще какие-то граничащие случаи не рассмотрел. Уже как-то не интересно их выискивать.

Новые блоги и статьи Все статьи Все блоги /
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Данные берутся из. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git

@dx3n 0 / 0 / 0 Регистрация: 15.06.2020 Сообщений: 64

	Задача на длинную арифметику 20.06.2020, 18:13. Показов 2508. Ответов 22 Метки длинная арифметика с++ (Все метки) Всем привет. Помогите пожалуйста решить задачу на длинную арифметику. Условие: Число задаётся группами подряд идущих в десятичной записи цифр. То есть число 111 задаётся как 3 1, число 2020 — как 1 2 1 0 1 2 1 0, число 222 233 как 4 2 2 3. Отметим, что длина группы должна быть максимальной, то есть запись 2 2 2 2 2 3 в последнем случае является некорректной. Вводятся два числа в вышеуказанном формате. Требуется вывести их сумму в том же формате. Ввод: Первая строка входных данных содержит целое число N1 — количество групп одинаковых цифр в записи первого слагаемого (1 ≤ N1 ≤ 100). i-я из последующих N1 строк содержит по два целых числа ni и di (1 ≤ ni ≤ 1018, 0 ≤ di ≤ 9). Гарантируется, что соседние di всегда различны, d1 ≠ 0 и сумма всех ni не превосходит 1018. Далее в аналогичном формате задаётся второе слагаемое. Вывод: Выведите сумму в том же формате, в котором заданы слагаемые. Примеры: Ввод -> 3 2 2 3 3 9 9 1 1 1 Вывод -> 4 2 2 2 3 1 4 9 0 0

@dx3n 0 / 0 / 0 Регистрация: 15.06.2020 Сообщений: 64
	20.06.2020, 19:31 [ТС]
	nonedark2008, в этом то и вся сложность. Такое решение не проходит по времени. Про RLE я то знаю и это и была моя первая идея) 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	20.06.2020, 19:50
	dx3n, а какие у тебя ограничения по времени? У тебя числа размером максимум n=1018. Сложность сложения O(n), разжатие/сжатие RLE O(n). Если упираешься во время, значит что-то и перечисленного ты выполняешь неэффективно. Код показать можешь? 0

@dx3n 0 / 0 / 0 Регистрация: 15.06.2020 Сообщений: 64
	20.06.2020, 20:45 [ТС]
	nonedark2008, я понял проблему этого кода. Он будет считать цифры в общей сложности. Но там возможны моменты когда будет число вида 111111.....222222222....111111111 и тогда решение ломается 0

@dx3n 0 / 0 / 0 Регистрация: 15.06.2020 Сообщений: 64
	21.06.2020, 01:52 [ТС]
	nonedark2008, спасибо за код я обязательно над этим подумаю) Добавлено через 3 часа 37 минут nonedark2008, на ваш код пишет TL 0

@AnyKey 264 / 183 / 87 Регистрация: 03.05.2020 Сообщений: 790
	21.06.2020, 09:19
	dx3n, а где тестится эта задача? 0

@dx3n 0 / 0 / 0 Регистрация: 15.06.2020 Сообщений: 64
	21.06.2020, 10:10 [ТС]
	TL - time limit. Программа выполняется дольше максимального времени. 0

@rembor 0 / 0 / 0 Регистрация: 01.04.2020 Сообщений: 36
	21.06.2020, 19:01
	nonedark2008, а тут уже неправильный ответ на третьем тесте 0