Лидеры рейтинга

ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

379

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Советник

378

Россия, Санкт-Петербург


ID: 401888

puporev

Профессор

216

Россия, Пермский край


ID: 405338

vovaromanov.jr

1-й класс

130


ID: 400669

epimkin

Профессионал

112


ID: 242862

Hunter7007

Мастер-Эксперт

30

Россия, Омск


ID: 137394

Megaloman

Мастер-Эксперт

26

Беларусь, Гомель


8.10.2

13.10.2021

JS: 2.10.2
CSS: 4.6.0
jQuery: 3.6.0
DataForLocalStorage: 2021-10-19 15:16:08-standard


Создание программ на языках C и C++.

Администратор раздела: CradleA (Мастер-Эксперт)

Консультация онлайн # 160424

Раздел: С / С++
Автор вопроса: Аршавин Александр Абрамович
Дата: 14.02.2009, 06:47 Консультация закрыта
Поступило ответов: 2

Добрый день!
Вот у меня тут задали ещё задачи по комбинаторики.
Помогите решить, пожалуйста!

Первая задача:

Великий комбинатор


В результате очередной хитроумной комбинации у Остапа Бендера и его компаньонов - K детей лейтенанта Шмидта оказалось X рублей пятирублевыми банкнотами. И вот дело, как водится, дошло до дележа...

Шура Балаганов предложил "по справедливости", т.е. всем поровну. Паниковский порешил себе отдать половину, а остальным "по заслугам". Каждый из K детей лейтенанта предложил что-нибудь интересное. Однако, у Великого Комбинатора имелось свое мнение на этот счет...

Ваша же задача состоит в нахождении количества способов разделить имеющиеся деньги между всеми участниками этих славных событий: K детьми лейтенанта Шмидта и Остапом Бендером.

Входные данные:

Во входном файле INPUT.TXT записаны целые числа X (0 <= X <= 500) и K (0 <= K <= 100). Естественно, что число X делится на 5. Да и при дележе рвать пятирублевые банкноты не разрешается.

Выходные данные:

В выходной файл OUTPUT.TXT выведите одно целое число - количество способов дележа.
Примеры:
input.txt: 15 2
output.txt: 10

Второя задача:

Шаблоны


Шаблоном размера n назовем строку длины n, каждый из символов которой входит в множество {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, ?}. Шаблоны преобразуются в строки из цифр по следующим правилам:
• символы от 0 до 9 могут быть преобразованы только сами в себя;
• символ a может преобразован в любой из символов 0,1, 2, 3;
• символ b может преобразован в любой из символов 1,2,3,4;
• символ c может преобразован в любой из символов 2,3,4,5;
• символ d может преобразован в любой из символов 3,4,5,6;
• символ e может преобразован в любой из символов 4,5,6,7;
• символ f может преобразован в любой из символов 5,6,7,8;
• символ g может преобразован в любой из символов 6,7,8,9;
• символ ? может преобразован в любой из символов от 0 до 9;

Даны два шаблона: p1 и p2. Рассмотрим множество S1 строк, которые могут быть получены из p1 по описанным правилам, и множество S2 строк, которые могут быть получены из p2. Необходимо найти количество строк, входящих в оба этих множества.

Входные данные:

Первая строка входного файла INPUT.TXT содержит шаблон p1, вторая — шаблон p2. Шаблоны имеют одинаковый положительный размер, не больше 9.

Выходные данные:

В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры:
1.
input.txt:
???
abc
output.txt: 64
2.
input.txt:
???
000
output.txt: 1
3.
input.txt:
abc
999
output.txt: 0

Третья задача:
Две кучки камней


У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.

Входные данные:

В первой строке входного файла INPUT.TXT записано число N – количество камней (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы камней W1, W2 , … WN (1 ≤ Wi ≤ 105).

Выходные данные:

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух кучек.
Примеры:
1.
input.txt:
5
5 8 13 27 14
output.txt: 3

Спасибо большое!!!! smile

Ответ # 243630 от Ross
Здравствуйте, Аршавин Александр Абрамович!

Решение последней задачи.

Приложение:


Ross

Посетитель
14.02.2009, 15:48
Ответ # 243654 от Micren
Здравствуйте, Аршавин Александр Абрамович!
Решение 2й задачи:

Приложение:


Micren

Посетитель
15.02.2009, 03:17
Мини-форум консультации # 160424
неизвестный

1

= общий =    14.02.2009, 16:13

7
21 1 16 11 5 18 21
Этот тест выдаёт неправильный ответ на вашей программе.
Должно выводить 1

Ross

2

= общий =    14.02.2009, 16:24

Но алгоритм верный...
А как их разложить чтобы было 1?

неизвестный

3

= общий =    14.02.2009, 16:32

21+21+5=47 и 18+16+11+1=46 => 47-46=1

Ross

4

= общий =    14.02.2009, 18:35

Тогда так:

Код
#include <algorithm>
#include <vector>
#include <fstream>
#include <limits>

using namespace std;

class Application
{
public:
    Application(int argc, char** argv)
    {
    }

    void Run()
    {
        vector<int> stones = GetDataFromFile("INPUT.TXT");

        ofstream oFile("OUTPUT.TXT", ios::trunc);
        oFile << Dissolve(stones);
        oFile.close();
    }

    vector<int> GetDataFromFile(const char* fileName)
    {
        vector<int> stones;

        ifstream iFile(fileName);
        if (iFile.fail())
        {
            // return empty array if file reading fails.
            return stones;
        }

        int N, weight;
        iFile >> N;
        for (int i = 0; i<N; ++i)
        {
            iFile >> weight;
            stones.push_back(weight);
        }
        iFile.close();

        return stones;
    }

    int Dissolve(const vector<int> stones)
    {
        int mindelta = numeric_limits<int>::max();
        // bruteforce
        DissolveRecursive(stones, 0, stones.size(), 0, 0, mindelta);
        return mindelta;
    }

    void DissolveRecursive(const vector<int>& stones, int i, int N,
        int wheap1, int wheap2, int& mindelta)
    {
        if (i == N)
        {
            mindelta = min(abs(wheap1 - wheap2), mindelta);
            return;
        }

        DissolveRecursive(stones, i + 1, N, wheap1 + stones[i], wheap2, mindelta);
        DissolveRecursive(stones, i + 1, N, wheap1, wheap2 + stones[i], mindelta);
    }

};

void main(int argc, char** argv)
{
    Application app(argc, argv);
    app.Run();
}

Micren

5

= общий =    15.02.2009, 08:16

Можно и так.

Код
#include <fstream>
#include <algorithm>

using namespace std;

class Found:exception{};

int minDiff,target,Count,*Heap;

void solve(int start,int diff)
{
	int adiff=abs(diff);
	if(adiff<minDiff)minDiff=adiff;
	if(adiff==target)throw Found();
	if(diff<0)return;
	for(int i=start;i<Count;i++)solve(i+1,diff-Heap[i]*2);
}

int calc()
{
	sort(Heap,Heap+Count);
	target=minDiff%2;
	try
	{
		solve(0,minDiff);
	}
	catch (Found){}
	return minDiff;
}

int main()
{
	ifstream in("INPUT.TXT");
	ofstream out("OUTPUT.TXT");
	in>>Count;
	Heap=new int[Count];
	for(int i=0;i<Count;i++)
	{
		int t;
		in>>t;
		minDiff+=Heap[i]=t;
	}
	out<<calc()<<endl;
	delete []Heap;
	return 0;
}

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Лучшие эксперты раздела

Зенченко Константин Николаевич

Старший модератор

Рейтинг: 122

Gluck

8-й класс

Рейтинг: 61

Коцюрбенко Алексей Владимирович

Старший модератор

Рейтинг: 48

CradleA

Мастер-Эксперт

Рейтинг: 2

Лысков Игорь Витальевич

Мастер-Эксперт

Рейтинг: 0

Асмик Гаряка

Советник

Рейтинг: 0