Олимпиадные задачи

[Evgen]

Добрый вечер всем! Опять обращаюсь к вам за помощью. не могу решить задачи.
Вот условие (по-моему с раздела комбинаторики.):
1. SMS должна иметь длину N и состоять из букв A,B,C и не должна иметь подстроки S которая может иметь буквы A и B. Найдите, сколько вариантов SMS существует
В первой строке задано целое N - длина SMS. Вторая строка - S слово, которое не длжно быть в SMS.
Ограничения 1≤n≤16, Строка s состоит с символов A и B, а ее длина не превішает 16. (Вход - 7; AA/ Виход-1224)

2. Андрей должен перевезти товар с города A в город B. (Существует N городов, каждий с которых имеет магистраль в каждый город). Через каждую магистраль можна провести разное максимальное количество товара. Необходимо выяснить, какое максимальное количество товара можна провести с города A в город B. (тут кажется графы)
Вход:
1 строка N, A, B
Следующие N-1 cтроки – ai,bi,ci (номера первого и второго городов с двусторонней дорого и максимальное количество товара, которое можно провезти)
НПР
Вход
3 1 3
1 2 4
2 3 3
Выход
3

Добавлено спустя 8 часов 12 минут 39 секунд:
Извените, во второй задаче ошибка в условии: существует N городов и N-1магистралей каждая из которых соединяет два города

[iskander]

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

[Evgen]

Iskandtr, спасибо что меня помните. Решето для больших чисел не идет (добавлять библиотеки которых нет в паскале нельзя), надо делать задачю поблочно (не получается)
Простые числа.
Ограничения: 1 сек., 256 МiБ. Найти количество простых чисел на промежутке[A,B].
Данные:В єдинственной строке дано 2 целых числа –A и B.
Ограничения
1≤A≤10^12, A≤B, B−A≤2·10^6

А теперь про первую задачу. Общее количество SMS (N по 3) - 3^N =2187, а как вичесть строку S и подсчитать количество не знаю

[iskander]

добавлять библиотеки которых нет в паскале нельзя

Они там и не нужны.

Общее количество SMS (N по 3) - 3^N =2187, а как вичесть строку S и подсчитать количество не знаю

Мне почему-то кажется что в задаче по программированию общее решение от вас не требуют, поэтому я и предлагал перебор.
Идея простая - перебираете все возможные варианты и по ходу перебора отбрасываете запрещенные строки.
Поскольку длина строки заранее неизвестна, сделать это с помощью вложенных циклов не удастся.
Но есть еще рекурсия. Вы умеете писать рекурсивные процедуры/функции?

[скалогрыз]

Но есть еще рекурсия. Вы умеете писать рекурсивные процедуры/функции?

задача на комбинаторику.
но ты простой дай ему то, что он хочет

Код: Выделить всё

program specialolympics1;

{$ifdef fpc}{$mode delphi}{$H+}{$endif}

var
  MAX : integer;
  sub : string;
  n   : string;
  r   : integer;

function Naiti(var n: string; i: integer): Integer;
var
  k : integer;
begin
  if i>MAX then begin
    if Pos(sub, n) = 0 then Naiti := 1
    else Naiti := 0
  end else begin
    k := 0;
    n[i]:='A';
    k := k + Naiti(n, i+1);
    n[i]:='B';
    k := k + Naiti(n, i+1);
    n[i]:='C';
    k := k + Naiti(n, i+1);
    Naiti := k;
  end;
end;


begin
  assign(input, 'input.txt'); Reset(input);
  readln(MAX);
  readln(sub);

  SetLength(n, MAX);
  r:=Naiti(n, 1);
  writeln(r);

  close(input);
end.

[iskander]

дай ему то, что он хочет

Он же должен сам хоть какой-нибудь вариант предложить.
А иначе какой смысл?

[скалогрыз]

А иначе какой смысл?

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

[iskander]

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

[скалогрыз]

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

откуда такая инфа?

По второй задаче не понятно как выбираются города A и B. (откуда и куда везти)

[Дож]

откуда такая инфа?

viewtopic.php?f=1&t=42600&start=15#p151342

[скалогрыз]

viewtopic.php?f=1&t=42600&start=15#p151342

убедил. Всё равно - дайте ему код!
а если, что ему будет непонятно, то он спросит.

[iskander]

По второй задаче не понятно как выбираются города A и B. (откуда и куда везти)

Вход:
1 строка N, A, B
Следующие N-1 cтроки – ai,bi,ci (номера первого и второго городов с двусторонней дорого и максимальное количество товара, которое можно провезти)

Но торопиться не стоит.

[скалогрыз]

Но торопиться не стоит.

всё... теперь понял!
нашёл кстати алготестер. цікава штука!

Добавлено спустя 40 минут 3 секунды:
как решать первую комбинаторно.
нужно из общего числа возможных (3^n) вычитать те комбинации, где встречаются слово.

например:
кол-во букв (n=)3, а слово, которое нужно исключать это "B"
тогда всего комбинаций будет (3^n = 3^3) = 27.
возможные варианты вхождения слова это:

Код: Выделить всё

Bxx - всего таких вариантов 9 ( т.е. 3^2)
xBx - таких вариантов тоже 9, но нужно учесть те, которые мы уже учли в (Bxx), т.е. 
        минус количество вариантов BBx (которе равно 3^1)
        т.е. в итоге вариантов xBx = 9 - 3 = 6
xxB - таких вариантов тоже 9, но нужно учесть те, которые мы уже учли в вариантах (Bxx и xBx) 
         минус количество вариантов BxB = 3^1
         минус количество вариантов xBB = 3^1 минус количество вариантов (BBB - а он такой один)
         т.е. таких вариантов xxB = 9 - 3 - 2  = 4

итог. кол-во возможных вариантов: 27 - 9 (вида Bxx) - 6 (вида xBx) - 4 (вида xxB) = 8

[Дож]

скалогрыз, можете ли описать ваш алгоритм в общем случае, а не на примере?

[скалогрыз]

скалогрыз, можете ли описать ваш алгоритм в общем случае, а не на примере?

их всех возможных случаев, нужно исключить те, которые включают в себя искомое слово.
Т.е. нам нужно найти кол-во комбинаций, которые это слово включают.
Слово может начинатся с 1ого символа, 2го и так далее до N-length(слова)
При этом, при подсчёте вариантов для каждой позиции нужно исключать возможные повторения, которые были подсчитаны на предыдущих шагах (чтобы не вычесть их дважды).
...Как-то так.