Есть такая задача:

Один чел заработал свои деньги деланием неких круговых спортивных установок. Tакая установка представляет из себя круг на котором расставлены разные спортивные тренажёры, например турник(T) и штанга(Ш).
Чтобы потренироваться нужно обойти круг и позаниматься с нужным тренажёром, т.е не обязательно заниматься со всеми тренажёрами (можно пропускать), при этом нельзя идти назад и турник-штанга и штанга-турник считаются разными комбинациями.

Вот например тренажёры расположены в таком порядке:
TШTШ

Значит на этом круге можно так тренироваться:
T, Ш, TШ, ШT, TT, ШШ, TШT, ШTШ, TTШ,TШШ, TШTШ = 11 возможностей

И вот этот чел хочет побить рекорд и сделать самый большой тренировочный круг по своей самой любимой книге . Для этого он уже присвоил тренажёрам буквы.

Задание: подсчитать сколько разных упражнений возможно будет делать на этом круге(книга есть и она занимает гдето 5 KБ). Tак как число получится слишком большим, надо показать только первые и последние 100 цифр.


Mеё решение:

Предположим что в книге не 5 тысяч букв, а только 7:

"БАВБВАГ" = Строка1

1. делаем ещё одну строку где все буквы из строки1 имеются только один раз:
"БАВГ" = Строка2

2. теперь считаем когда буквы в строке1 встречаются первый раз. Получается:
[0] {1,2,3,7} (1 - Б, 2 - А, 3 -В, 7 = Г)

3. отходим на один символ вперёд и делаем тоже самое:
[1] {2,3,4,7}

4. и так далее до 7 символа. В конце концов получается массив:

[0] {1,2,3,7}
[1] {2,3,4,7}
[2] {3,4,6,7}
[3] {4,5,6,7}
[4] {5,6,7}
[5] {6,7}
[6] {7}
[7] {}

5. теперь складываем всё это таким образом:

[7] {} = 0 (в нутри массива ничего нет)
[6] {7} = 1 + 0 = 1 (в массиве одно число + то что в массиве [7])
[5] {6,7} = 2 + 1 + 0 = 3 (в массиве два числа + то что в массивах 6 и 7)
[4] {5,6,7} = 3 + 3 + 1 + 0 = 7 (в массиве два числа + то что в массивах которые лежат в 4 массиве)
[3] {4,5,6,7} = 4 + 7 + 3 + 1 + 0 = 15
[2] {3,4,6,7} = 4 + 15 + 7 + 1 + 0 = 27
[1] {2,3,4,7} = 4 + 27 + 15 + 7 + 0 = 53
[0] {1,2,3,7} = 4 + 53 + 27 + 15 + 0 = 99

И того получается 99 возможностей потренироватся.


Задача взята из немецкой олимпиады по информатике за 05/06 год. Я хотел уже в этом году поучаствовать, но мне сказали что типа 15 лет - малой ещё. Вот хочу в следующем году попробовать чёнить занять, а пока стараюсь сделать все задачи за этот год для подготовки.

Если кто вдуг дочитал до конца , то скажите плз самый ли быстрый мой алгоритм или есть быстрее? Очень интересно узнать!

| Сообщение посчитали полезным:

Насколько я понял это задача по элементам комбинаторики, но ты так написал - фиг поймешь, в чем заключается смысл реализации этой задачи, нужен правильный ответ, прога, которая считает, или что?
Думаю, что без формул и обьяснений такого решения не достаточно, я бы назвал это решением методом научного тыка.
http://do.rksi.ru/library/courses/ms/tema2_1.dbk http://do.rksi.ru/library/courses/ms/tema2_1.dbk

-----
Research is my purpose

| Сообщение посчитали полезным:

Error_Log
Спасибо что ответил!

Насколько я понял это задача по элементам комбинаторики
да, так оно и есть

ты так написал - фиг поймешь
извини, объяснять я не умею...

в чем заключается смысл реализации этой задачи, нужен правильный ответ, прога, которая считает, или что?
нужна прога, которая считает

Думаю, что без формул и обьяснений такого решения не достаточно, я бы назвал это решением методом научного тыка.
Вот в том то и дело что я формулы не нашёл, ни в нете ни в мат. справочниках. Ведь число возможных комбинаций зависит не только от того сколько в строке букв, но и от того как они в этой строке расставлены. Например в строке "ААББ" возможны 9 комбинаций а в "АБАБ" 11. Не представляю как формула может это учитывать.

rep0A пишет:
[4] {5,6,7} = 3 + 3 + 1 + 0 = 7 (в массиве два числа + то что в массивах которые лежат в 4 массиве)
опечатался, (в массиве три числа + то что в массивах которые лежат в 4 массиве)

| Сообщение посчитали полезным:

rep0A пишет:
5. теперь складываем всё это таким образом:

[7] {} = 0 (в нутри массива ничего нет)
[6] {7} = 1 + 0 = 1 (в массиве одно число + то что в массиве [7])
[5] {6,7} = 2 + 1 + 0 = 3 (в массиве два числа + то что в массивах 6 и 7)
[4] {5,6,7} = 3 + 3 + 1 + 0 = 7 (в массиве два числа + то что в массивах которые лежат в 4 массиве)
[3] {4,5,6,7} = 4 + 7 + 3 + 1 + 0 = 15
[2] {3,4,6,7} = 4 + 15 + 7 + 1 + 0 = 27
[1] {2,3,4,7} = 4 + 27 + 15 + 7 + 0 = 53
[0] {1,2,3,7} = 4 + 53 + 27 + 15 + 0 = 99

Дочитал до конца, целый день осмысливал, но так и не понял =(

| Сообщение посчитали полезным:

Как обычно, информатика сводится к задачкам по дискретной математике и комбинаторике из серии кратчайшего остова дерева и на тему так называемых "жадных алго"...

-----
Я медленно снимаю с неё UPX... *FF_User*

| Сообщение посчитали полезным:

Klajnor пишет:
Дочитал до конца, целый день осмысливал, но так и не понял =(

Попробую пояснить.

Вот возьмём строку "АБАБ":

4 {} (последний всегда пустой, можно не учитывать}
3 {4} = 1
2 {3,4} = 2 + 1 (+0) = 3
1 {2,3} = 2 + 3 + 1 = 6
0 {1,2} = 2 + 6 + 3 = 11

Считая наоборот мы постоянно отодвигаемся на одну букву назад.

Например если бы была только одна (последняя) буква "Б", то была бы возможна только одна комбинация(массив 3). Если бы их было две "АБ" то возможны были бы уже 2 + 1 = 3 комбинации(массив 2). Mы решаем 2 + 1 потомучто 2 это сами буквы "А" и "Б" по отдельности, а один это комбинация с буквой "Б" : "АБ".
Отходим ещё на один символ назад, получается "БАБ" теперь возможны 2 + 3 + 1 = 6 комбинации(массив 1). 2 это буквы "Б" и "А" (первая и вторая), 3 это комбинации с буквой "А":
"БА", "БАБ" "АБ"
и один это опять комбинация с буквой "Б" : "ББ".

Отходим ещё на один символ назад (уже "АБАБ") и делаем тоже самое:
2 это сами буквы "А" и "Б", 6 это комбинации с первой "Б" и три это комбинации со второй "А".

Tак вот и получаются 11 комбинаций ;)
Скажи если чтото не понятно...

| Сообщение посчитали полезным:

rep0A пишет:
Tак вот и получаются 11 комбинаций ;)
Скажи если чтото не понятно... - как посчитать я понял =) Но я не понял почему это работает =( Хотя на нескольких примерах считал - всё сходилось!

| Сообщение посчитали полезным:

Вот ссылка на раздел Комбинаторика и переборные алгоритмы. Мне как то помогло решить свою проблему.
Там есть ещё решение алимпиадных задач.

algolist.manual.ru/maths/combinat/index.php

-----
Никто не знает столько, сколько не знаю я

| Сообщение посчитали полезным:

rep0A

Твой способ я честно говоря не до конца понял, еще помедитирую Мне пришло в голову пока только следующее:


#include <stdio.h>

const int length = 7;

int main() {

int substr_count = 0;
int letter_count[4] = {0,0,0,0};
char string[length] = {'B','A','C','B','C','A','D'}; //строка "БАВБВАГ - 99
//char string[length] = {'A','B','A','B'}; //строка АБАБ" - 11

for(int i=0;i<length;i++) {
int diff = substr_count + 1 - letter_count[string[i]-'A'];
substr_count+=diff;
letter_count[string[i]-'A']+=diff;
}

printf("%d",substr_count);

return 0;
}


Вполне может быть, что это то же самое, что и твой вариант. По крайней мере ответы 11 и 99 совпадают.

P.S. На олимпиаде теперь есть ограничение снизу по возрасту? В мое время еще только сверху было

| Сообщение посчитали полезным:

rep0A

Интересная задачка, если время будет тоже погляжу как можно решить.

P.S.
Вот тут я вспомнил что тоже тут задачку когда-то запостил: http://www.exelab.ru/f/action=vthread&topic=1302&forum=2&p age=-1
Потренируйся если есть время

| Сообщение посчитали полезным:

Klajnor пишет:
Но я не понял почему это работает
Почему работает ещё никто не понял... даже я...

Stiver пишет:
Мне пришло в голову пока только следующее
Ты крут! Сейчас протестировал, так твой алго быстрее и жрёт меньше памяти!

Stiver пишет:
На олимпиаде теперь есть ограничение снизу по возрасту?
Нет нету, но до 16 лет попадаешь в другую группу и как мне сказали должен делать другую программу(всего одну). В этом году нужно например оочень простую игру написать.

arnix пишет:
Потренируйся если есть время
Сейчас посмотрим

| Сообщение посчитали полезным:

rep0A

На самом деле твоя задача является хорошим примером так называемого dynamic programming. Для интереса можешь попробовать сделать еще одну (которую я в свое время по заказу нашего химика делал).

Нужно написать программу, которая считала бы количество изомерных алканов для заданного количества атомов углерода. То есть у нас есть атомы С, каждый из которых может быть соединен с одним, двумя, тремя или четырьмя другими такими же атомами. Циклы не разрешены. В итоге должна получится естественно только одна молекула, то есть соединение должно быть связным. Нужно для n атомов посчитать все возможные способы их соединения.

Например: для 2х атомов - одна возможность, для 3х - 1, 4 - 2, 5 - 3, 6 - 5, 10 - 75, 20 - 366319.

| Сообщение посчитали полезным:

rep0A пишет:
Почему работает ещё никто не понял... даже я... - я почти понял =) А как-же ты тогда придумал такой алгоритм, если не понимаешь, как он работает =)


Stiver пишет:
letter_count[string[i]-'A']+=diff;

Stiver, твой алгорит пока них*я не понял. Надо будет подумать на досуге

| Сообщение посчитали полезным:

Klajnor пишет:
А как-же ты тогда придумал такой алгоритм, если не понимаешь, как он работает
Ну я в принципе понимаю, но не представляю себе как тот бред который у меня в голове можно перевести на нормальный русский язык.

Stiver пишет:
то есть соединение должно быть связным

А не мог бы ты пояснить что есть связное соединение, а что нет? Или линк дать где про это можно почитать.

| Сообщение посчитали полезным:

rep0A пишет:
Ну я в принципе понимаю, но не представляю себе как тот бред который у меня в голове можно перевести на нормальный русский язык - вот я так-же понимаю твой алгоритм =)

| Сообщение посчитали полезным:

arnix

Может не очень красиво, но работает:

#include <stdio.h>

const int work_count = 4;

int main() {

int A[work_count] = {3, 2, 5, 1};
int B[work_count] = {4, 12, 2, 4};
int C[work_count] = {1, 2, 6, 7};

int result = A[0] + B[0];
int diffB, diffC;
for(int i = 0; i<work_count; i++) {
result += C[i];
if(i < 3) {
diffB = A[i+1] - B[i];
diffC = B[i+1] - C[i];
if(diffB> 0) {
result += diffB;
diffB = 0;
}
if(diffC > 0) {
result += diffC;
diffC = 0;
}
}
}

printf("%d \n\n",result);

return 0;
}

| Сообщение посчитали полезным:

Подброшу ещё задачку, мб интересно будет.
Условие: Есть матрица размера m на n. Из одного угла матрицы приходим в другой - по диагонали. Причем, так, что ходы возможны (если нужно придти из левого нижнего угла в правый верхний) только в право и вверх. Дорожками являются не сами клетки-элементы матрицы, а их соединения.
Задача: Нужно найти формулу подсчета количества путей.

Короче, на листе в клетку условие выглядит лучше, чем в тексте =)

-----
Я медленно снимаю с неё UPX... *FF_User*

| Сообщение посчитали полезным:

rep0A пишет:
arnix

Может не очень красиво, но работает:

OK, Вечером когда буду дома посморю, и приведу своё решени тоже, и у меня есть еще одна интересная задача, если ты еще не устал могу тоже привести (+ моё решение)

| Сообщение посчитали полезным:

Stiver

Наконец-то понял что такое изомерные алканы и как их считать(читал тут http://www.chemistry.ssu.samara.ru/chem2/u231_1.htm ). Интересная задачка, спасибо.

AlexZ

Я тебя правильно понял?



Красные точки, это от куда до куда нужно дойти. Синяя линия это первый путь, красная - второй.

arnix пишет:
если ты ещё не устал могу тоже привести
Нет не устал. Приведи, буду очень благодарен.

rep0A пишет:
if(i < 3) {
Чтото я ступил. Надо if(i < work_count-1) {

| Сообщение посчитали полезным:

arnix
тоже тут задачку когда-то запостил ...

Если проекты делаются по порядку (первый целиком, потом второй целиком и т.д.), то rep0A привел решение. Задачу можно значительно усложнить, сказав что группы могут выполнять проекты в любой последовательности и найти надо минимальное время, за которое они все проекты обработают. Если не ошибаюсь, тогда это будет вариант так называемой "проблемы рюкзака" (knapsack problem).

AlexZ
Задача: Нужно найти формулу подсчета количества путей.

Стандартная формула из комбинаторики

rep0A
Наконец-то понял что такое изомерные алканы и как их считать(читал тут)

Точно, именно так. По твоему линку это объяснено значительно лучше, чем смог бы объяснить я

| Сообщение посчитали полезным:

Stiver пишет:
Если проекты делаются по порядку (первый целиком, потом второй целиком и т.д.), то rep0A привел решение. Задачу можно значительно усложнить, сказав что группы могут выполнять проекты в любой последовательности и найти надо минимальное время, за которое они все проекты обработают. Если не ошибаюсь, тогда это будет вариант так называемой "проблемы рюкзака" (knapsack problem).


Да, тогда действительно усложнится, rep0A, вот моё решение (см. аттач) на C++, Pascal, и ASM (Fasm).

2 rep0A

А теперь задачка которую я обещал
В файле INPUT.TXT даётся информация вроде этой:

7
1 0 1 0 1 1 0
1 1 1 0 0 1 1
0 0 1 0 0 1 0
0 0 0 0 0 0 0
1 1 1 1 1 0 0
1 0 0 1 0 1 0
1 1 0 0 0 0 1

На первой строчке число N (3<N<=50), потом следует матрица размероом (N,N), в матрице есть только нули и единицы. Задача: Поменять знак некоторых единиц так, чтобы после этого сумма всех строк и колонок была -1, 0 или 1. Ну и писать новую матрицу в файл OUTPUT.TXT, вот его содержимое для приведённого выше массива:

1 0 -1 0 1 -1 0
-1 -1 1 0 0 1 1
0 0 1 0 0 -1 0
0 0 0 0 0 0 0
-1 1 -1 1 -1 0 0
1 0 0 -1 0 1 0
1 1 0 0 0 0 -1


e34e_empl.rar.zip

| Сообщение посчитали полезным:

rep0A
Попробую сразу примером. Если рисуешь 4 совмещённые клетки, и идёшь из нижнего левого угла в правуй верхний, то пути будут такими (H - горизонтально; V - вертикально):
1) HHVV
2) HVHV
3) VHHV
4) HVVH
5) VHVH
6) VVHH
Только матрица возможна размеров m n а здесь всего 2x2.

-----
Я медленно снимаю с неё UPX... *FF_User*

| Сообщение посчитали полезным: