Какое решение понятнее проще - судить сторонним наблюдателям.
На мой взгляд, решение на Хацкеле без поллитра не прочитать :-)

А теперь важные моменты.
Изюминка задачки в том, что пространство решений небольшое, и все их можно заранее просчитать и занести в таблицу, а при считывании входных данных из файла просто сразу выводить ответы. Иначе для больших входных наборов можно просто пролететь по времени.

И вот - внимание - мне очень-очень интересно, как из такой ситуации будут выкручиваться хацкелисты... Состояний нет, запомнить заранее ответы нельзя, разве что написать программу-генератор константной таблицы, которую потом засунуть в исходник? Или придется функциональщикам применять closures - без состояний никуда :-)

А ведь есть еще задачи на динамическое программирование. Они по структуре своей рекурсивны, вот бы где ФП развернуться, но увы - опять нужно запоминать промежуточные результаты в каких-либо переменных. Опять closures? :-)

Ответ на »сообщение 3264« (Илья Ермаков)
___________________________
Увы, тут форум режет форматирование табуляцией...
С сохранением форматирование смотрите здесь:
http://forum.oberoncore.ru/viewtopic.php?t=409

Ответ на »сообщение 3258« (Geniepro)
___________________________

Ответ на »сообщение 3255« (Руслан Богатырев)
___________________________
Ну вот, я так и знал! :о))
Ну что ж, нужно привлекать добровольцев, или даже назначать их... :о)

Вот и решение на Компонентном Паскале подоспело :-)
Для ввода-вывода/создания экзешника использовал олимпиадную подсистему Info21olimp от Информатики-21.

MODULE OlimpBlood;

IMPORT In := Info21olimpIn, Out := Info21olimpOut, Strings;

CONST
(* аллели *)
aA = 0; aB = 1; aO = 2;
(* группы крови *)
gA = 0; gAB = 1; gB = 2; gO = 3;
rP = 4; rM = 5;

TYPE
CorrelateMap = ARRAY 4, 4 OF SET;

VAR
directMap: CorrelateMap; (* карта решений в прямом направлении
directMap[группаРод1, группаРод2] = множество возможностей для ребенка *)
inverseMap: CorrelateMap; (* карта решений в обратном направлении
inverseMap[группаРод1, группаРебенка] = множество возможностей для родителя2 *)
strMap: ARRAY ORD({gA, gAB, gB, gO, rP, rM})+1 OF ARRAY 128 OF CHAR;
(* карта отображения решений SET -> string *)

PROCEDURE Alleles (group: INTEGER): SET;
(* IN группа крови RETURN состав аллелей *)
BEGIN
CASE group OF gA: RETURN {aA, aO} | gAB: RETURN {aA, aB}
| gB: RETURN {aB, aO} | gO: RETURN {aO}
END
END Alleles;

PROCEDURE GroupAbilities (alleles1, alleles2: SET): SET;
(* IN аллели род1, аллели род2 RETURN возможные типы крови ребенка *)
VAR g: INTEGER;
res: SET;
BEGIN
res := {};
FOR g := gA TO gO DO
CASE g OF
| gA: IF (aA IN alleles1 * alleles2) OR (* AA *)
(aA IN alleles1) & (aO IN alleles2) OR (* AO *)
(aO IN alleles1) & (aA IN alleles2) (* OA *) THEN
INCL(res, gA)
END
| gAB: IF (aA IN alleles1) & (aB IN alleles2) OR (* AB *)
(aB IN alleles1) & (aA IN alleles2) (* BA *) THEN
INCL(res, gAB)
END
| gB: IF (aB IN alleles1 * alleles2) OR (* BB *)
(aB IN alleles1) & (aO IN alleles2) OR (* BO *)
(aO IN alleles1) & (aB IN alleles2) (* OB *) THEN
INCL(res, gB)
END
| gO: IF (aO IN alleles1 * alleles2) (* OO *) THEN
INCL(res, gO)
END
END
END;
RETURN res
END GroupAbilities;

PROCEDURE InitDirectMap;
VAR g1, g2: INTEGER;
BEGIN
FOR g1 := gA TO gO DO
FOR g2 := gA TO gO DO
directMap[g1, g2] := GroupAbilities(Alleles(g1), Alleles(g2))
END
END
END InitDirectMap;

PROCEDURE InitInverseMap;
VAR g1, gx: INTEGER;
PROCEDURE FillCell;
VAR g2: INTEGER;
BEGIN
FOR g2 := gA TO gO DO
IF gx IN directMap[g1, g2] THEN
INCL(inverseMap[g1, gx], g2)
END
END
END FillCell;
BEGIN
FOR g1 := gA TO gO DO
FOR gx := gA TO gO DO
FillCell
END
END
END InitInverseMap;

PROCEDURE ResusAbilities (r1, r2: INTEGER): SET;
(* IN резус род1, резус род2 RETURN возможные резусы ребенка *)
BEGIN
IF (r1 = rM) & (r2 = rM) THEN RETURN {rM}
ELSE RETURN {rP, rM}
END
END ResusAbilities;

PROCEDURE ResusInverseAbilities (r1, rx: INTEGER): SET;
(* IN резус род1 резус ребенка RETURN возможные резусы второго родителя *)
BEGIN
IF (rx = rP) & (r1 = rM) THEN RETURN {rP}
ELSE RETURN {rM, rP}
END
END ResusInverseAbilities;

PROCEDURE SolveDirect (g1, r1, g2, r2: INTEGER): SET;
(* IN группа и резус каждого родителя RETURN возможные типы крови ребенка *)
BEGIN
RETURN directMap[g1, g2] + ResusAbilities(r1, r2)
END SolveDirect;

PROCEDURE SolveInverse (g1, r1, gx, rx: INTEGER): SET;
(* IN группа и резус род1 группа и резус ребенка RETURN возможные типы крови второго родителя *)
BEGIN
RETURN inverseMap[g1, gx] + ResusInverseAbilities(r1, rx)
END SolveInverse;

PROCEDURE ExtractCase (IN s: ARRAY OF CHAR; OUT groups, resuses: ARRAY OF INTEGER);
VAR i, j: INTEGER;
PROCEDURE ReadElem;
BEGIN
CASE s[i] OF
| '?': groups[j] := -1
| 'A': IF s[i+1] = 'B' THEN groups[j] := gAB; INC(i, 2) ELSE groups[j] := gA; INC(i) END
| 'B': groups[j] := gB; INC(i)
| 'O': groups[j] := gO; INC(i)
END;
CASE s[i] OF
| '?': resuses[j] := -1
| '+': resuses[j] := rP
| '-': resuses[j] := rM
END;
INC(i); INC(j)
END ReadElem;
BEGIN
i := 0; j := 0;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem;
WHILE s[i] = " " DO INC(i) END; ASSERT(s[i] # 0X, 20); ReadElem
END ExtractCase;

PROCEDURE BloodToStr (g, r: INTEGER; OUT str: ARRAY OF CHAR);
BEGIN
CASE g OF gA: str := "A" | gAB: str := "AB" | gB: str := "B" | gO: str := "O" END;
CASE r OF rP: str := str + "+" | rM: str := str + "-" END
END BloodToStr;

PROCEDURE AbilitiesToStrEnd (ab: SET; OUT str: ARRAY OF CHAR);
VAR i0, g, cnt: INTEGER;
s: ARRAY 4 OF CHAR;
BEGIN
i0 := LEN(str$);
cnt := 0;
FOR g := gA TO gO DO
IF g IN ab THEN
IF rP IN ab THEN INC(cnt); BloodToStr(g, rP, s); str := str + ", " + s END;
IF rM IN ab THEN INC(cnt); BloodToStr(g, rM, s); str := str + ", " + s END
END
END;
IF cnt = 0 THEN
str[i0] := 0X; str := str + "IMPOSSIBLE"
ELSIF cnt = 1 THEN
str[i0] := 0X; str := str + s
ELSE
str[i0] := "{"; str := str + "}"
END
END AbilitiesToStrEnd;

PROCEDURE InitStrMap;
VAR a: INTEGER;
BEGIN
FOR a := 0 TO ORD({gA, gAB, gB, gO, rP, rM}) DO
AbilitiesToStrEnd(BITS(a), strMap[a])
END
END InitStrMap;

PROCEDURE SolveCase (IN istr: ARRAY OF CHAR; OUT ostr: ARRAY OF CHAR);
VAR groups: ARRAY 3 OF INTEGER;
resuses: ARRAY 3 OF INTEGER;
res: SET;
s: ARRAY 4 OF CHAR;
BEGIN
ExtractCase(istr, groups, resuses);
IF (groups[0] # -1) & (groups[1] # -1) THEN
res := SolveDirect(groups[0], resuses[0], groups[1], resuses[1]);
BloodToStr(groups[0], resuses[0], s);
ostr := s$;
BloodToStr(groups[1], resuses[1], s);
ostr := ostr + " " + s + " ";
AbilitiesToStrEnd(res, ostr)
ELSIF groups[0] # -1 THEN
res := SolveInverse(groups[0], resuses[0], groups[2], resuses[2]);
BloodToStr(groups[0], resuses[0], s);
ostr := s$ + " ";
AbilitiesToStrEnd(res, ostr);
BloodToStr(groups[2], resuses[2], s);
ostr := ostr + " " + s
ELSIF groups[1] # -1 THEN
res := SolveInverse(groups[1], resuses[1], groups[2], resuses[2]);
ostr := "";
AbilitiesToStrEnd(res, ostr);
BloodToStr(groups[1], resuses[1], s);
ostr := ostr + " " + s;
BloodToStr(groups[2], resuses[2], s);
ostr := ostr + " " + s
END
END SolveCase;

PROCEDURE Do;
VAR s, outs: ARRAY 256 OF CHAR;
line: INTEGER;
end: BOOLEAN;
PROCEDURE GetLine;
VAR i: INTEGER;
BEGIN
IF ~In.done THEN
end := TRUE
ELSE
INC(line);
i := 0; In.Char(s[0]);
WHILE In.done & (s[i] # 0DX) & (s[i] # "E") DO
INC(i); In.Char(s[i])
END;
IF s[i] = "E" THEN
end := TRUE
END;
s[i] := 0X; IF In.done THEN In.Char(s[i+1]) END
END
END GetLine;
BEGIN
end := FALSE; line := 0;
GetLine;
WHILE ~end DO
Strings.IntToString(line, outs);
outs := "Case " + outs + ":" + " ";
Out.String(outs);
SolveCase(s, outs);
Out.String(outs); Out.Ln;
GetLine
END
END Do;

PROCEDURE Main* ;
BEGIN
In.Open('blood.in'); Out.Open('blood.out'); Do
END Main;

PROCEDURE Test* ;
BEGIN
In.Open("blood.in"); Out.Open(""); Do
END Test;

BEGIN
InitDirectMap;
InitInverseMap;
InitStrMap
END OlimpBlood.

Ответ на »сообщение 3262« (Eugene)
___________________________

Значительная часть задач просто этого не требует - мне вот после окончания ВУЗа не то, что высшая математика ни разу не потребовалась, но и из алгоритмов сложнее QuickSort/двоичного поиска ничего не применял.

А Вы никогда не задавались вопросом, почему не применяли? Попробуйте...

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

Корпоративный сектор -- основной поставщик финансовых потоков в индустрию ПО, давно смекнул, что тот же коробочный софт -- утопичный путь. Он работает только для массового рынка (а сейчас со скрипом). А на корпоративном нужен заказной и полузаказной софт, а также слой сервиса, который дает основу другим бизнес-моделям и защищает инвестиции от пиратства. Сейчас нередко программные системы отдают за так: стоит только информационное сопровождение. Это надежнее, если важна именно критическая информация, изменяемая во времени и требующая больших людских ресурсов на актуализацию. Пример для России -- справочно-правовые системы.

Далее инициируется потребность тех, кто может и готов платить (надо только их запугать/убедить). Так появился небезызвестный офшорный аутсорсинг, куда и стекаются сейчас основные финансы и где Индия впереди планеты всей. Ситуацию 6-летней давности по России можно понять, напр., по той статье, которую писал для "Открытых систем", собрав круглый стол руководителей лидеров экспортной заказной разработки ПО: http://www.osp.ru/os/2001/07-08/180316/ и http://www.osp.ru/os/2001/07-08/180332/

В России промышленное производство ПО концентрируются либо в компаниях-офшорниках, либо в "системных интеграторах", окучивающих местных крупных заказчиков. В остальном это кустарное производство (если классифицировать характер с точки зрения производства). В нем ценится: UI, информационный слой (БД), простейшая интеграция с учетом сетевой работы. Да и офшорники раньше большей частью "красили заборы" у западных гигантов, пока не заработали авторитет и их не стали допускать до нутра бизнес-процессов и критических вещей, подлежащих автоматизации. Но калибр отечественных компаний хилый: -- 500-1000 человек. Процесс их слияния слабенький. Это не позволяет браться за масштабные проекты (притом что команды по 20-30 человек на годы подвисают на обслуживании "постоянников"), а потому затрудняет темпы роста.

Что печально, именно такой крен в индустрии ПО содействует катастрофической ситуации с подготовкой кадров в высшей школе, о которой говорил Вирт в "Потерянной дороге" -- http://www.inr.ac.ru/~info21/texts/2002-06-Aarhus/ru.htm

Рынку нужны архитекторы или плиточники-облицовщики. Так-то.

Ответ на »сообщение 3240« (Руслан Богатырев)
___________________________
Доброго времени суток!

Небольшой offtopic
Тот же Митричев блестяще умеет справляться с решением алгоритмических задач. А в условиях жесткого прессинга по времени умеет это, пожалуй, лучше всех в мире. Что неоднократно уже доказывал. Это феномен, уникум, выросший на традициях советской математической школы. Вот, что надобно продвигать в народные массы, тем более для страны, которая хочет превратиться из экспортера полезных ископаемых в центр интеллектуального производства.
Рад за Петра. Но как представитель "народных масс" (рядовой программист) что-то
сомневаюсь в пользе продвижения традиций советской математической школы в эти самые массы.
Значительная часть задач просто этого не требует - мне вот после окончания ВУЗа
не то, что высшая математика ни разу не потребовалась, но и из алгоритмов сложнее
QuickSort/двоичного поиска ничего не применял.

Наши ведущие ИТ-СМИ пока поглощены другими важными событиями: Sony подключает владельцев PlayStation 3 к сети Folding@Home, Интернет-магнат попал за решетку...
И эта страна хочет превратиться в центр интеллектуального производства?

С уважением,

Насчет морального "устаревания Паскаля".

Вспоминаю переписку с одним из членов технического комитета ACM ICPC от нашей страны. Паскалиста по образованию. Когда речь зашла об аргументации, то я упоминал рейтинг TIOBE, единственный известный мне постоянно ведущийся рейтинг популярности языков, методика которого более-менее понятна и позволяет проверять результаты независимо. По популярности уже были дебаты в "Мыслях об Обероне". Но, думаю, для тех, кто следит за нынешним обсуждением, эта информация не будет излишней.

Просто регулярно можно слышать, что Паскали давно списали в утиль. А как эту чушь опровергнуть? Это один из объективных инструментов анализа, позволяющий ежемесячно отслеживать тенденции популярности.

Вот рейтинг TIOBE на март: http://www.tiobe.com/tiobe_index/index.htm

Из Паскалей в 20-ке лучших фигурирует Delphi. Он хоть и продолжает падать, но все еще на 12-м месте, не так уж сильно отставая от C#. Если интересуют функциональные языки, то их доля составляет по TIOBE 0.8% с годовым приростом 0.2. По остальным см. таблицу:

Category                  Mar 2007  Delta Mar 2006 
Object-Oriented Languages  52.3%    +0.9% 
Procedural Languages      45.3%    -1.8% 
Logical Languages          1.7%      +0.8% 
Functional Languages      0.8%      +0.2%

В сфере мониторинга 100 языков.

Ответ на »сообщение 3258« (Geniepro)
___________________________

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

Идеологи XP? :)

По-моему, я уже как-то рассказывал, что когда в МАИ мы работали с Кроносом (советский 32-разрядный Lilith, точнее, с его в вариантом виде платы для Электроники-60), раздобытым с большим трудом, то поневоле вынуждены были использовать единственный компьютер. На дворе был, если не ошибаюсь, 1988 г. Нас в команде тогда было трое, при этом один "рулил" (писал код, не вдаваясь в детали), другой был штурманом (сидел за плечом, излагал тактический замысел), а третий отдыхал (смотрел за двумя другими, иногда что-то уточняя). Через 30-40 минут происходила смена пилота (как в командных велосипедных гонках), на его место садился штурман, а наблюдатель становился штурманом. И так по кругу. Но это для обычного режима. Когда что-то делалось особо ответственное, то смены происходили исходя из усталости (замыленности глаза) и с учетом того, у кого что лучше получается. Главным забойщиком был Игорь Егоров, главный программист в известном проекте игрового симулятора "Ил-2 Штурмовик".

Ответ на »сообщение 3258« (Geniepro)
___________________________

--Паскаль, на котором наши преимущественно писали, исключили из "элиты" по причине "моральной старости".
-- Логично было бы тогда исключить и Си - он ведь ровесник Паскаля.

Тут проблемы глубже. Кто генеральный спонсор? IBM. Какую цель ставит IBM помимо продвижения своей марки в среде подрастающей интеллектуальной элиты? Самую прагматичную -- отбор кадров: как признавались участники, регулярно в ходе финалов бывают встречи с представителями IBM, headhunter'ы работают на полную катушку.

Далее. На каждом компьютере ставится унифицированная операционная среда, которая включает в себя ОС и системы программирования "высочайше разрешенных" языков. Раз IBM, значит, никак не Windows. А что? (напоминает известный анекдот: Кто у меня родился? Мальчик? Нет? А кто?). Итак, это Linux. Для Linux из Паскалей использовался вариант Kylix, который давно фирмой Borland позабыт-позаброшен. Наши его как-то там подмазывали под новые версии Red Hat Linux, но проблемы постоянно всплывают. Формально именно это является поводом к исключению, а реально -- самому техническому комитету писать решения задач и проверять то, в чем они "не-копенгаген", как-то не хочется. Да и сами спонсоры никаких, разумеется, возражений не имеют. Им-то Паскаль Борланда на что сдался? Другое дело Eclipse, в котором сидят C/C++ и Java. Плюс что-то там Россия обнаглела совсем, медали гребет лопатой, надо и с другими поделиться, а то чемпионаты будут дискредитированы (как в свое время советская шахматная школа задавила всех). А эти русские и в Java с C++ разберутся.

Кстати, тот же КП есть в реализации для Eclipse. Но это еще нужно пробивать (причем и черех наши команды, и через функционеров и через членов технического комитета, подсобрав при этом хотя бы союзников из других стран -- что о-о-чень проблематично). В конце 2005 г. питерцы из звездных команд СПбГУ ИТМО крутили-вертели BlackBox, он им понравился. Но что толку -- пробивать-то это надо через технический комитет, а там BlackBox не пройдет (нужен под Linux, да в идеале под Eclipse). А это только GPCP/Eclipse австралийцев -- http://www.plas.fit.qut.edu.au/gpcp/IDE.aspx

P.S. Вообще-то, подробный "разбор полетов" по чемпионату 2005 г. я уже проводил: http://www.osp.ru/pcworld/2005/05/170171/
Полная версия есть на europrog.ru: http://www.europrog.ru/paper/acm2005.pdf

Ответ на »сообщение 3255« (Руслан Богатырев)
___________________________

Пусть будут Oberon/КП и Haskell.
Кстати, а почему еще и Delphi к этому не подключить, раз мы в Королевстве это обсуждаем и тут немало спецов по этому языку?

Согласен с Вами.

Кстати, конкретно ту задачку "Problem A+. Consanguine Calculations", как мне кажется, идеально было бы решать на Прологе. Хотя на Хаскелле с его list comprehensions решилось тоже довольно просто.


Паскаль, на котором наши преимущественно писали, исключили из "элиты" по причине "моральной старости".

Логично было бы тогда исключить и Си - он ведь ровесник Паскаля.


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

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


Сожалею, но, заварив кашу, я, как обычно, "умываю руки".

Ну вот, я так и знал! :о))
Ну что ж, нужно привлекать добровольцев, или даже назначать их... :о)

Ответ на »сообщение 3256« (Руслан Богатырев)
___________________________

Заморожено оно после окончания 4-го часа (т.е. примерно в районе 4*60-240-й минуты).

Сорри, надо читать: 4*60=240-й минуты.