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

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

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

в общем наткнулся на задачу и не могу решить, обидно даже, ведь решал и потяжелее, а сейчас в голову ничего кроме простого долгого перебора не приходит, ну и там чуть чуть улучшенные варианты основанные на переборе.
вводится число, число денег, необходимо вывести либо да либо нет.
да - если это число при любом делении на купюры достоинствами 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++

#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++

#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++

if(otv)

Аналогично

C++

1	if(otv && otv1!=i)

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

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

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

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

C++

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, тогда новичку будет трудно

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

@Krock21rus 88 / 84 / 31 Регистрация: 18.11.2013 Сообщений: 390
		1
	Задача на комбинаторику 19.02.2015, 00:00. Показов 2099. Ответов 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	2
	Сообщение было отмечено Krock21rus как решение Решение Может, попробовать решить это как задачу о рюкзаке, в котором число предметов неограниченно? 1

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	19.02.2015, 09:27	4
	Сообщение от Ilot Внимательно читайте условия задачи. В указанной постановке любое четное число можно представить как сумму заданных пар. ??? Сообщение от Krock21rus при любом делении Попробуйте поделить справедливо 6 = 5+1 1

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

@Krock21rus 88 / 84 / 31 Регистрация: 18.11.2013 Сообщений: 390
	19.02.2015, 17:00 [ТС]	6
	Сообщение от senich Может, попробовать решить это как задачу о рюкзаке, в котором число предметов неограниченно? можно подробнее? тут просто чётные не пойдут, ясно что числа которые от одной купюры до этой купюры*2 автоматически не подходят, но вот как узнать другие числа, которые подходят 0

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

@Krock21rus 88 / 84 / 31 Регистрация: 18.11.2013 Сообщений: 390
	13.04.2015, 20:04 [ТС]	10
	Сообщение от 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) { что-то } что читается как: если ответ это истина, тогда делаем что-то на быстром просмотре кода эта конструкция, лично для меня, читается и понимается быстрее, чем сокращённая 0

8-BITOV
	13.04.2015, 21:00 #11
	Не по теме: Сообщение от Krock21rus обычный новичОк не поймёт Если в "обычном новичке" видеть полного дебила, тогда, пожалуй, вы и правы. Но я, как-то, о наших новичках составил лучшее мнение...:) 0

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

Решение