Консультации Портала - Консультация #160424

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

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

14.02.2009, 06:47

0.00 руб.

0 7 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

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

Обсуждение

Неизвестный

14.02.2009, 15:48

общий

это ответ

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

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

Приложение:
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

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

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

int heap1, heap2;
Dissolve(stones, heap1, heap2);

ofstream oFile("OUTPUT.TXT", ios::trunc);
oFile << abs(heap1 - heap2);
oFile.close();
}

private:
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;
}

void Dissolve(const vector<int>& stones, int& heap1, int& heap2)
{
vector<int> stonesSortedDesc(stones);
sort(reverse_iterator<vector<int>::iterator>(stonesSortedDesc.end())
,reverse_iterator<vector<int>::iterator>(stonesSortedDesc.begin()));

heap1 = heap2 = 0;
for (vector<int>::const_iterator i = stonesSortedDesc.begin();
i != stonesSortedDesc.end(); ++i)
{
if (heap1 <= heap2)
{
heap1 += *i;
}
else
heap2 += *i;
}
}

};

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

Неизвестный

14.02.2009, 16:13

общий

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

Неизвестный

14.02.2009, 16:24

общий

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

Неизвестный

14.02.2009, 16:32

общий

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

Неизвестный

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();
}

Неизвестный

15.02.2009, 03:17

общий

это ответ

Здравствуйте, Аршавин Александр Абрамович!
Решение 2й задачи:

Приложение:
#include <fstream>
#include <string>
#include <map>

using namespace std;

typedef unsigned int uint;
typedef string::iterator iterstr;

const char tChars[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','?'};
const uint tCharsNum=sizeof(tChars)/sizeof(tChars[0]);
const string tStr[tCharsNum]={"0","1","2","3","4","5","6","7","8","9","0123","1234","2345",
"3456","4567","5678","6789","0123456789"};
map<char,string> tMap;

void initialize()
{
for(uint i=0;i<tCharsNum;i++)
{
tMap[tChars[i]]=tStr[i];
}
}

uint charsIntersecting(char ch1,char ch2)
{
string tStr1=tMap[ch1],tStr2=tMap[ch2];
uint count=0;
for(iterstr it=tStr1.begin();it!=tStr1.end();it++)
{
count+=tStr2.find(*it)!=string::npos;
}
return count;
}

int main()
{
initialize();
ifstream in("INPUT.TXT");
ofstream out("OUTPUT.TXT");
string str1,str2;
getline(in,str1);
getline(in,str2);
unsigned int intersecting=0;
if (str1.length()&&str2.length())
{
intersecting=1;
for(iterstr it1=str1.begin(),it2=str2.begin();it1!=str1.end()&&it2!=str2.end();it1++,it2++)
{
intersecting*=charsIntersecting(*it1,*it2);
}
}
out<<intersecting<<endl;
return 0;
}

Неизвестный

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;
}

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

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