Защищенная ось от Касперского и гражданин со справками

[A_I]

Исходные условия - операционка от лаборатории Касперского, (кто не в курсе, - с претензией на наноядерность, жесткий реал тайм, и, самое главное - "кибериммунитет").
Но это для предисловия.
А вот дальше их "хэдхантеры" для вливания в дружный коллектив разработчиков этой самой оси предлагают решить, в частности, следующую задачку, которая как мне кажется решения не имеет, либо с условиями они что-то попутали:

Гражданин обращается за справками c1, c2, …, cN в различные конторы k1, k2, …, km. Начальный набор справок, которые гражданин имеет на руках может быть непустым. Целевых справок, которые требуется получить гражданину, может быть несколько. Конторы могут обладать состоянием в отношении обращающегося, например, если гражданин уже подавал справки c1, с2 и с3 в контору k1, то контора переходит в состояние, когда она может выдать гражданину справку с4. При этом поданные в контору справки ему не возвращаются. Для получения справок гражданин подает заявление в контору. Заявление на получение справки может быть подано, если выполнены условия конторы (набор справок, которые надо подать в контору для получения следующей справки). Если какая-либо из целевых справок не получена, и при этом возможностей для подачи заявлений нет, это означает, что гражданин не достиг своей цели.
Требуется:
Определить, что целевые справки в принципе можно получить при заданных правилах работы контор
Составить алгоритм получения целевых справок, гарантирующий, если это в принципе возможно, получение всего целевого набора справок
Составить такой алгоритм получения целевых справок, чтобы количество обращений гражданина в конторы было бы минимальным

[ozheredov]

A_I
Справки в одной конторе упорядочены? Т.е. чтобы получить справку $c_k$, необходимо и достаточно получить $c_1, c_2, ..., c_k_-_1$? Или для получения c4 может потребоваться c1 и с2, а для c1 потребуется с124, с346 и c865?

[A_I]

ozheredov в сообщении #1558656 писал(а):

A_I
Справки в одной конторе упорядочены? Т.е. чтобы получить справку $c_k$, необходимо и достаточно получить $c_1, c_2, ..., c_k_-_1$? Или для получения c4 может потребоваться c1 и с2, а для c1 потребуется с124, с346 и c865?

Это всё, что есть в условии.
Но, насколько я понимаю, всё-таки упорядочены, иначе задача вообще не понятной становится.

-- 27.06.2022, 22:08 --

Тут вообще, они видимо так тестируют образ мышления "прогеров - ядерщиков для ОС" . В смысле, что условия задачи где-то напоминают работу ядра ОС (прерывания, приоритеты, многозадачность и проч. "плюшки")..

[ozheredov]

A_I в сообщении #1558657 писал(а):

насколько я понимаю, всё-таки упорядочены

Если это так, то задача = детский сад. Представьте себе настолку, где есть фишки и ими надо ходить по кружочкам ок, метро - представьте метро. Есть линия, начинающаяся со станций с1, c2, c3, и нужно добраться до станций с12, c23 и c36 (это набор справок из одной конторы). Ясно, что алгоритм тривиален, а его число шагов определяется станцией из набора, наиболее удаленной от начала линии. Ну и остальными конторами то же самое, и если алгоритм не параллелится, то общее число шагов это просто сумма.

[A_I]

Как я понял, нужно сначала вообще доказать, что при таких правилах работы контор можно получить любое количество справок (но, очевидно, не более чем количество самих контор), имея изначально на руках также любое количество справок, в том числе и "пустое" количество, то есть, не имея их вообще.

[ozheredov]

A_I

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

-- Дайте мне справку из конторы А и справку из конторы B, чтобы мы (контора В) могли дать следующую справку.
-- Не могу, я уже отдал ее в А для того, чтобы получить от них справку, которая нужна была вам (т.е. В).

Может быть такое?

[A_I]

ozheredov в сообщении #1558671 писал(а):

Может быть такое?

Вот-вот.. Мне кажется, что в условиях слишком много слов с неопределенным контекстом типа "может, могут" и т.п.
Например,:
"Конторы могут обладать состоянием в отношении обращающегося, например, если гражданин уже подавал справки c1, с2 и с3 в контору k1, то контора переходит в состояние, когда она может выдать гражданину справку с4."
Надо ли это понимать математически строго, - "могут обладать, но могут и не обладать.." и "может выдать, но может и не выдать..." ?
Т.е., только здесь надо рассмотреть уже четыре возможных варианта - "обладает - выдаст", "не обладает - выдаст", "обладает - не выдаст", "не обладает - не выдаст".
И так - много где. При некоторых возможных вариантах задача вообще теряет смысл. Либо становится неразрешимой.
По видимому, надо за них самостоятельно "дополнить" условия, чтобы она приобрела "божеский" вид..

[eugensk]

Задача выглядит вполне понятной. Есть состояние системы, точка в $S \times V$, где $S= \{ (s_1, s_2, ..., s_n) \}$ состояния контор, $V= \{ (v_1, v_2, ..., v_m) \}$ сколько экземляров справок на руках. Есть функции $f_i : S \times V \to S \times V, i=1..n$. Есть начальная точка $(S_0,V_0)$. Есть определенное множество финальных точек $F\subset S \times V$. Вопрос: есть ли такая композиция $f_i$ что образ начальной точки пересекается с $F$?
Можно строить такой образ в прямом порядке, можно двигаться в обратном, т.е. расширять множество $F$ объединяя со всеми прообразами $f_i^{-1}(F)$, сделав столько итераций, пока не перестанет расти, или не включит начальную точку. Всё выглядит просто. Эффективно реализовать это дело конечно будет сложно.

ps Пока не перестанет расти в пересечении с каким-то ограничивающим множеством, конечно. Ограничивающее множество это сколько справок можно унести без тележки.

[upgrade]

A_I в сообщении #1558654 писал(а):

обращается за справками c1, c2, …, cN в различные конторы k1, k2, …, km

A_I в сообщении #1558654 писал(а):

если гражданин уже подавал справки c1, с2 и с3 в контору k1

Он и подает и получает одни и те же справки, конторы и получают и выдают одни и те же справки? Т.е. это такой обмен справками?