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

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

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

Сообщение Evgen » 14.02.2019 04:10:21

Добрый вечер всем! Опять обращаюсь к вам за помощью. не могу решить задачи.
Вот условие (по-моему с раздела комбинаторики.):
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магистралей каждая из которых соединяет два города
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение iskander » 14.02.2019 12:39:39

Evgen, какие конкретно у вас проблемы с первой задачей?
На первый взгляд она вполне себе решается простым перебором.
Вторая задача похоже на максимальный поток, почитайте.
Как дела с решетом Эратосфена?
iskander
постоялец
 
Сообщения: 183
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение Evgen » 14.02.2019 15:55:40

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 и подсчитать количество не знаю
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение iskander » 14.02.2019 17:34:53

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

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

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

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

Сообщение скалогрыз » 14.02.2019 17:54:57

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

задача на комбинаторику.
но ты простой дай ему то, что он хочет
Код: Выделить всё
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.
скалогрыз
долгожитель
 
Сообщения: 1690
Зарегистрирован: 03.09.2008 02:36:48

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

Сообщение iskander » 14.02.2019 18:26:15

скалогрыз писал(а):дай ему то, что он хочет

Он же должен сам хоть какой-нибудь вариант предложить.
А иначе какой смысл?
iskander
постоялец
 
Сообщения: 183
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение скалогрыз » 14.02.2019 19:07:33

iskander писал(а):А иначе какой смысл?

чтобы он получил зачёт, очевидно. Ты же не веришь в том, что он здесь образования ради?
я думаю, что решение с рекурсией завернут, с обоснованием "слишком долго работает", но имеет смысл попробовать
скалогрыз
долгожитель
 
Сообщения: 1690
Зарегистрирован: 03.09.2008 02:36:48

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

Сообщение iskander » 14.02.2019 19:16:12

Он школьник, задачки решает из спортивного интереса, собирается участвовать в олимпиадах.
Я думаю от него как раз и ждут решения с рекурсией.
iskander
постоялец
 
Сообщения: 183
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение скалогрыз » 14.02.2019 19:35:09

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

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

По второй задаче не понятно как выбираются города A и B. (откуда и куда везти)
скалогрыз
долгожитель
 
Сообщения: 1690
Зарегистрирован: 03.09.2008 02:36:48

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

Сообщение Дож » 14.02.2019 19:48:06

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

viewtopic.php?f=1&t=42600&start=15#p151342
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 798
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение скалогрыз » 14.02.2019 19:51:16

Дож писал(а):viewtopic.php?f=1&t=42600&start=15#p151342

убедил. Всё равно - дайте ему код!
а если, что ему будет непонятно, то он спросит.
скалогрыз
долгожитель
 
Сообщения: 1690
Зарегистрирован: 03.09.2008 02:36:48

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

Сообщение iskander » 14.02.2019 19:53:40

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

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

Но торопиться не стоит.
iskander
постоялец
 
Сообщения: 183
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение скалогрыз » 14.02.2019 19:55:33

iskander писал(а):Но торопиться не стоит.

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

Добавлено спустя 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
скалогрыз
долгожитель
 
Сообщения: 1690
Зарегистрирован: 03.09.2008 02:36:48

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

Сообщение Дож » 14.02.2019 21:22:12

скалогрыз, можете ли описать ваш алгоритм в общем случае, а не на примере?
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 798
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение скалогрыз » 14.02.2019 22:07:53

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

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

След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

Рейтинг@Mail.ru