Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
1

Нахождение кол-ва A + B <= C без переполнений разрядов(испр)

15.02.2021, 23:29. Показов 647. Ответов 13
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Всем привет, можете подсказать алгоритм решения к этой задаче:
Посчитайте количество пар целых неотрицательных чисел (a, b) таких, что a + b ≤ C. И при сложении a + b не будут появляться переполнения разрядов.

Вводится число 1 <= C <= 109, нужно вывести кол-во пар a и b.

Код для дебага:
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

#include <bits/stdc++.h>
using namespace std;
 
bool check(int a,int b) {
    while(a > 0 && b > 0) {
        if( a % 10 + b % 10 > 9) {
            return false;
        }
        a /= 10, b /= 10;
    }
    return true;
}
int main() {
    int c;
    cin >> c;
    int a,b;
    int ans = 0;
    for(int i = 0;i <= c;i++) {
        for(int j = 0;j + i <= c;j++) {
            if(check(i,j) == true && i + j <= c) {
                ans++;
            }
        }
    }
    cout << ans;
}
PS: не работает на тестах больше 105. асимптотика примерно O(n2 * 10).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 15.02.2021, 23:29
Ответы с готовыми решениями:

Нахождение кол-ва A + B <= C без переполнений разрядов
Всем привет, можете подсказать алгоритм решения к этой задаче: Посчитайте количество пар целых...

Подсчёт и вывод кол-ва разрядов равных нулю.
Помогите пожалуйста написать код для CommandButton в Visual Basic. Задача следующая: Дано...

Преобразование чисел (кол-во разрядов>64) в двоичный формат
Условие задачи: На планете Роботов очень не любят десятичную систему счисления, поэтому они...

Нахождение кода Грея для 32-х разрядов
помогите, пожалуйста, написать для лабораторной программу нахождения кода Грея для 32-х разрядов....

13
Заблокирован
15.02.2021, 23:41 2
Цитата Сообщение от derwes Посмотреть сообщение
PS: не работает на тестах больше 105. асимптотика примерно O(n2 * 10).
Ты ответы, не связанные с перебором, не смотрел, штоли?
0
Заблокирован
15.02.2021, 23:47 3
Нахождение кол-ва A + B <= C без переполнений разрядов(испр)
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
15.02.2021, 23:49  [ТС] 4
Ну к большим тестам у меня просто нет доступа, но у маленьких тестов я нашел подозрительную закономерность в разнице текущего ответа и прошлого
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

c = 0 | ans = 1 | ans - ansbefore = 1 т.к. нету ansbefore
c = 1 | ans = 3 | ans - ansbefore = 2
c = 2 | ans = 6 | ans - ansbefore = 3
c = 3 | ans = 10 | ans - ansbefore = 4
c = 4 | ans = 15 | ans - ansbefore = 5
c = 5 | ans = 21 | ans - ansbefore = 6
c = 6 | ans = 28 | ans - ansbefore = 7
c = 7 | ans = 36 | ans - ansbefore = 8
c = 8 | ans = 45 | ans - ansbefore = 9
c = 9 | ans = 55 | ans - ansbefore = 10
c = 10 | ans = 57 | ans - ansbefore = 2
c = 11 | ans = 61 | ans - ansbefore = 4
c = 12 | ans = 67 | ans - ansbefore = 6
c = 13 | ans = 75 | ans - ansbefore = 8
c = 14 | ans = 85 | ans - ansbefore = 10
c = 15 | ans = 97 | ans - ansbefore = 12
c = 16 | ans = 111 | ans - ansbefore = 14
c = 17 | ans = 127 | ans - ansbefore = 16
c = 18 | ans = 145 | ans - ansbefore = 18
c = 19 | ans = 165 | ans - ansbefore = 20
c = 20 | ans = 168 | ans - ansbefore = 3
c = 21 | ans = 174 | ans - ansbefore = 6
c = 22 | ans = 183 | ans - ansbefore = 9
c = 23 | ans = 195 | ans - ansbefore = 12
c = 24 | ans = 210 | ans - ansbefore = 15
c = 25 | ans = 228 | ans - ansbefore = 18
c = 26 | ans = 249 | ans - ansbefore = 21
c = 27 | ans = 273 | ans - ansbefore = 24
c = 28 | ans = 300 | ans - ansbefore = 27
c = 29 | ans = 330 | ans - ansbefore = 30
c = 30 | ans = 334 | ans - ansbefore = 4
c = 31 | ans = 342 | ans - ansbefore = 8
c = 32 | ans = 354 | ans - ansbefore = 12
c = 33 | ans = 370 | ans - ansbefore = 16
c = 34 | ans = 390 | ans - ansbefore = 20
c = 35 | ans = 414 | ans - ansbefore = 24
c = 36 | ans = 442 | ans - ansbefore = 28
c = 37 | ans = 474 | ans - ansbefore = 32
c = 38 | ans = 510 | ans - ansbefore = 36
c = 39 | ans = 550 | ans - ansbefore = 40
0
Заблокирован
15.02.2021, 23:54 5
хз, правильно или нет........

Нахождение кол-ва A + B <= C без переполнений разрядов(испр)
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
15.02.2021, 23:59  [ТС] 6
При 10 выводит 66? Просто весь прикол в том, что если просто кол-во вариантов a + b <= c, то это действительно (c + 2)(c + 1) / 2, но тут еще нельзя чтобы были переполнения разрядов тобеж 6 + 14 = 20 - нельзя, но 5 + 14 = 19 - можно
Все варианты для C - 10
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

i = 0 j = 0
i = 0 j = 1
i = 0 j = 2
i = 0 j = 3
i = 0 j = 4
i = 0 j = 5
i = 0 j = 6
i = 0 j = 7
i = 0 j = 8
i = 0 j = 9
i = 0 j = 10
i = 1 j = 0
i = 1 j = 1
i = 1 j = 2
i = 1 j = 3
i = 1 j = 4
i = 1 j = 5
i = 1 j = 6
i = 1 j = 7
i = 1 j = 8
i = 2 j = 0
i = 2 j = 1
i = 2 j = 2
i = 2 j = 3
i = 2 j = 4
i = 2 j = 5
i = 2 j = 6
i = 2 j = 7
i = 3 j = 0
i = 3 j = 1
i = 3 j = 2
i = 3 j = 3
i = 3 j = 4
i = 3 j = 5
i = 3 j = 6
i = 4 j = 0
i = 4 j = 1
i = 4 j = 2
i = 4 j = 3
i = 4 j = 4
i = 4 j = 5
i = 5 j = 0
i = 5 j = 1
i = 5 j = 2
i = 5 j = 3
i = 5 j = 4
i = 6 j = 0
i = 6 j = 1
i = 6 j = 2
i = 6 j = 3
i = 7 j = 0
i = 7 j = 1
i = 7 j = 2
i = 8 j = 0
i = 8 j = 1
i = 9 j = 0
i = 10 j = 0
Всего - 57
0
Заблокирован
16.02.2021, 00:08 7
Цитата Сообщение от derwes Посмотреть сообщение
нельзя чтобы были переполнения разрядов тобеж 6 + 14 = 20 - нельзя, но 5 + 14 = 19 - можно
Пояснительную бригаду мне...
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
16.02.2021, 00:12  [ТС] 8
Цитата Сообщение от derwes Посмотреть сообщение
Посчитайте количество пар целых неотрицательных чисел (a, b) таких, что a + b ≤ C. И при сложении a + b не будут появляться переполнения разрядов.
Тип 6 и 4 в одном разряде дают переполнение в некст разряд и там + 1, если столбиком складывать то магия происходит

Добавлено через 2 минуты
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
16.02.2021, 00:13  [ТС] 9
смогу ли я сегодня картинку приложить
Миниатюры
Нахождение кол-ва A + B <= C без переполнений разрядов(испр)  
0
Заблокирован
16.02.2021, 00:14 10
Цитата Сообщение от derwes Посмотреть сообщение
Тип 6 и 4 в одном разряде дают переполнение в некст разряд и там + 1, если столбиком складывать то магия происходит
Ну я хз. У меня в примере числа 6, 4 и остальные любые занимают ровно по 32 разряда. Не больше и не меньше. Чтобы не вызвать переполнение я использовал под результат 64-разрядную переменную.

Зачем складывать числа столбиком, когда у тебя есть комп?
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
16.02.2021, 00:15  [ТС] 11
разряд это в смысле единицы десятки сотни и т.д.
0
Заблокирован
16.02.2021, 00:19 12
Цитата Сообщение от derwes Посмотреть сообщение
разряд это в смысле единицы десятки сотни и т.д.
В цифровой электронике этого нет. Вся информация хранится, обрабатывается и передаётся только в двоичном виде. И слово "переполнение" в программировании имеет чёткий смысл - когда в результате операции результат перестаёт помещаться в тип переменной, отведённой под него.
0
Сижу думаю
3 / 3 / 0
Регистрация: 11.08.2019
Сообщений: 70
16.02.2021, 00:22  [ТС] 13
Ну тут соре, что не объяснил. Нужно найти кол-во a + b, что бы при так сказать сложении каждый разряд(десятки единицы сотни и т.д.) не давал переполнения.
Пример переполнения(математического): 14 + 6 = 20 переполнение в разряде единиц. 191 + 9 = 200 переполнение в разряде единиц, которое даёт переполнение в десятках.
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
17.02.2021, 20:02 14
derwes, Нашел закономерность, могу поделиться, если актуально. На пальцах, ибо в код заворачивать лень.
Кликните здесь для просмотра всего текста

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

/*
? 104
[0, 100)    55^2 * (+1) * (1)
[100, 104)  55^0 * (+1+2+3+4) * (2)
[104, 104)  55^0 * (+1) * (2*5)
= 3025 + 20 + 10 = 3055
 
 
? 234
[0, 200)    55^2 * (+1+2) * (1)
[200, 230)  55^1 * (+1+2+3) * (3)
[230, 234)  55^0 * (+1+2+3+4) * (3*4)
[234, 234)  55^0 * (+1) * (3*4*5)
= 9075 + 990 + 120 + 60 = 10245
 
 
? 876
[0, 800)    55^2 * (+1+2+3+4+5+6+7+8) * (1)
[800, 870)  55^1 * (+1+2+3+4+5+6+7) * (9)
[870, 876)  55^0 * (+1+2+3+4+5+6) * (9*8)
[876, 876)  55^0 * (+1) * (9*8*7)
= 108900 + 13860 + 1512 + 504 = 124776
 
 
? 1635
[0, 1000)       55^3 * (+1) * (1)
[1000, 1600)    55^2 * (+1+2+3+4+5+6) * (2)
[1600, 1630)    55^1 * (+1+2+3) * (2*7)
[1630, 1635)    55^0 * (+1+2+3+4+5) * (2*7*4)
[1635, 1635)    55^0 * (+1) * (2*7*4*6)
= 166375 + 127050 + 4620 + 840 + 336 = 299221
 
 
? 3157
[0, 3000)       55^3 * (+1+2+3) * (1)
[3000, 3100)    55^2 * (+1) * (4)
[3100, 3150)    55^1 * (+1+2+3+4+5) * (4*2)
[3150, 3157)    55^0 * (+1+2+3+4+5+6+7) * (4*2*6)
[3157, 3157)    55^0 * (+1) * (4*2*6*8)
= 998250 + 12100 + 6600 + 1344 + 384 = 1018678
*/
0
17.02.2021, 20:02
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 17.02.2021, 20:02
Помогаю со студенческими работами здесь

Нахождение суммы цифр числа от старших разрядов
Я понимаю, что это должно быть очень просто, но я только начал учить VB (учусь в школе). Мне задали...

Нахождение кол-ва символов
3адача.форма,поле ввода,текст.поле и кнопка. по нажатию на кнопку в т.поле должно вывод кол-во...

Как "n" кол-во чисел, записанные по порядку, разбить "n" кол-во строк? (Без использования массива) C++
Сначала вводится с клавиатуры кол-во чисел. Далее с помощью цикла for выводятся рандомные значения...

Проверить, как изменилось количество разрядов в числе M по сравнению с количеством разрядов числа N
Выручайте....Дано натуральное число N. Определить M=N!. Проверить, как изменилось количество...

выявлять числа, у которых сумма чётных разрядов равна сумме нечётных разрядов
помогите решить задачку: До получения исла равного 0 выявлять числа, среди последовательносьти из...

Проверить как изменится количество разрядов в числе M по сравнению с количеством разрядов числа N
Дано натуральное число N. Определить M=N! Проверить как измениться количевство разрядов в числе M...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru