Задача на комбинаторику

@Krock21rus · Регистрация: 18.11.2013

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

в общем наткнулся на задачу и не могу решить, обидно даже, ведь решал и потяжелее, а сейчас в голову ничего кроме простого долгого перебора не приходит, ну и там чуть чуть улучшенные варианты основанные на переборе.
вводится число, число денег, необходимо вывести либо да либо нет.
да - если это число при любом делении на купюры достоинствами 1,2,5,10,50,100,500,1000,5000 можно поделить поровну и нет в противном случае.
таких чисел, как я предполагаю, мало.
к примеру это число 4, т.к. при всех возможных комбинациях можно поделить на 2 и 2(1+1 и 1+1, 1 и 2, 2 и 2)
следующее число это 24, там такая же ситуация.
входное число до 100000, что даёт знать, что решение тут долговатое.
помогите с идеей пожалуйста, у меня пока-что простой перебор.

@senich · 19.02.2015, 07:36

Может, попробовать решить это как задачу о рюкзаке, в котором число предметов неограниченно?

Ilot · 19.02.2015, 09:00

C++
1
2
3
4
5
6
7
#include <iostream>
int main(){
    unsigned N; std::cin >> N;
    if(N & 1) std::cout << "no\n";
        else  std::cout << "yes\n";
    return 0;
}

Внимательно читайте или переписывайте условия задачи. В указанной постановке любое четное число можно представить как сумму заданных пар.

Байт · 19.02.2015, 09:27

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

Внимательно читайте условия задачи. В указанной постановке любое четное число можно представить как сумму заданных пар.

???

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

при любом делении

Попробуйте поделить справедливо 6 = 5+1

Ilot · 19.02.2015, 09:30

Байт, ну да. Мой косяк.

@Krock21rus · 19.02.2015, 17:00 **[ТС]**

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

Может, попробовать решить это как задачу о рюкзаке, в котором число предметов неограниченно?

можно подробнее?

тут просто чётные не пойдут, ясно что числа которые от одной купюры до этой купюры*2 автоматически не подходят, но вот как узнать другие числа, которые подходят

@senich · 19.02.2015, 17:17

http://informatics.mccme.ru/mo... php?id=815

@Krock21rus · 21.02.2015, 13:53 **[ТС]**

вот кстати решение, ото я его сделал, а вам показать не показал
оно просто использует жадный алгоритм, то есть пытается выдать сумму наибольшими купюрами, и считает чтобы одинаковых купюр было чётное кол-во:

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
#include <iostream>
 
using namespace std;
 
const int bankn=9;
 
int main()
{
    int bank[bankn] = {1,2,5,10,50,100,500,1000,5000};
    int n;
    bool otv = false;
    int otv1=-1;
    cin >> n;
    while(n!=0)
    {
        for(int i=bankn-1;i>=0;i--)
        {
            if(n-bank[i]>=0)
            {
                n-=bank[i];
                if(otv==true && otv1!=i)
                {
                    cout << "NO";
                    return 0;
                }
                otv1=i;
                if(otv)
                {
                    otv=false;
                }
                else
                {
                    otv=true;
                }
                break;
            }
        }
    }
    if(otv==true)
    cout << "NO";
    else
    cout << "YES";
}

@zss · 21.02.2015, 14:04

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

if(otv==true)

Масло - масляное (истинно ли что, otv имеет значение Истина).

C++
1
if(otv)

Аналогично

C++
1
 if(otv && otv1!=i)

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

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

if(otv)
{
otv=false;
} else
{
otv=true;
}

записывается одной строкой

C++
1
otv=!otv;

@Krock21rus · 13.04.2015, 20:04 **[ТС]**

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

if(otv==true)
Масло - масляное (истинно ли что, otv имеет значение Истина).
Код C++
1
if(otv)
Аналогично
Код C++
1
if(otv && otv1!=i)
Добавлено через 3 минуты
Цитата Сообщение от Krock21rus Посмотреть сообщение
if(otv)
{
otv=false;
} else
{
otv=true;
}
записывается одной строкой
Код C++
1
otv=!otv;

думаю это всего лишь стиль программирования, суть от этого не изменится, только обьём кода

Я как-то изучал mysql, и там было сказано что это язык программирования высокого уровня, т.к. там можно перевести запросы и понять их, после этого я начал часто прочитывать свой код
к примеру с этим же otv:

if(otv)
{
что-то
}
это:
если(ответ)
тогда что-то
обычный новичёк не поймёт, да и если тебе не вбилось в голову что любое значение, если оно не 0 в конструкции if означает true, то ты тоже не поймёшь, поэтому я предпочитаю
if(otv==true)
{
что-то
}
что читается как:
если ответ это истина, тогда делаем что-то
на быстром просмотре кода эта конструкция, лично для меня, читается и понимается быстрее, чем сокращённая

8-BITOV · 13.04.2015, 21:00

Не по теме:

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

обычный новичОк не поймёт

Если в "обычном новичке" видеть полного дебила, тогда, пожалуй, вы и правы. Но я, как-то, о наших новичках составил лучшее мнение...:)

@Krock21rus · 13.04.2015, 21:28 **[ТС]**

честно говоря мне 15 лет всего, и я ещё в 9 классе, и многие мои одноклассники как-раз новички которые не понимают if(otv)
если будет otv иметь тип int, тогда новичку будет трудно

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. На мобильном - сканируйте QR-код. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@Krock21rus 88 / 84 / 31 Регистрация: 18.11.2013 Сообщений: 390

	Задача на комбинаторику 19.02.2015, 00:00. Показов 2254. Ответов 11 Метки нет (Все метки) в общем наткнулся на задачу и не могу решить, обидно даже, ведь решал и потяжелее, а сейчас в голову ничего кроме простого долгого перебора не приходит, ну и там чуть чуть улучшенные варианты основанные на переборе. вводится число, число денег, необходимо вывести либо да либо нет. да - если это число при любом делении на купюры достоинствами 1,2,5,10,50,100,500,1000,5000 можно поделить поровну и нет в противном случае. таких чисел, как я предполагаю, мало. к примеру это число 4, т.к. при всех возможных комбинациях можно поделить на 2 и 2(1+1 и 1+1, 1 и 2, 2 и 2) следующее число это 24, там такая же ситуация. входное число до 100000, что даёт знать, что решение тут долговатое. помогите с идеей пожалуйста, у меня пока-что простой перебор. 0

@senich 63 / 63 / 77 Регистрация: 22.11.2012 Сообщений: 241 Записей в блоге: 1
	19.02.2015, 07:36
	Сообщение было отмечено Krock21rus как решение Решение Может, попробовать решить это как задачу о рюкзаке, в котором число предметов неограниченно? 1

Ilot $Эксперт по математике/физике$ 2224 / 1426 / 420 Регистрация: 16.05.2013 Сообщений: 3,646 Записей в блоге: 6
	19.02.2015, 09:30
	Байт, ну да. Мой косяк. 0

@senich 63 / 63 / 77 Регистрация: 22.11.2012 Сообщений: 241 Записей в блоге: 1
	19.02.2015, 17:17
	http://informatics.mccme.ru/mo... php?id=815 1

@Krock21rus 88 / 84 / 31 Регистрация: 18.11.2013 Сообщений: 390
	13.04.2015, 21:28 [ТС]
	честно говоря мне 15 лет всего, и я ещё в 9 классе, и многие мои одноклассники как-раз новички которые не понимают if(otv) если будет otv иметь тип int, тогда новичку будет трудно 0

Задача на комбинаторику

Решение