АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Ограничение по памяти 64M байт

Читайте также:
  1. Infinite USB Memory – флешка с безлимитным объемом памяти 03.03.2010 16:00 Максим Мишенев
  2. V. Различие в отношении к прошлому опыту между образами памяти и образами воображения
  3. БЛУЖДАНИЯ БЕЗ ПАМЯТИ
  4. Бюджетное ограничение и его уравнение. Наклон бюджетной линии, факторы её сдвига.
  5. В) ограничением доходов и накоплений в семьях уровнем, заведомо достаточным для жизни, но не позволяющим паразитировать на чужом труде.
  6. ВАЛИНОР: Тропы памяти
  7. Величина, обратная емкости памяти
  8. во Всероссийской Вахте Памяти
  9. Вопрос 16. Ограничение дееспособности.
  10. ВОСКРЕШЕНИЕ В ПАМЯТИ
  11. Выделение памяти для структур.
  12. Глава VII. ПРЕКРАЩЕНИЕ И ОГРАНИЧЕНИЕ ПРАВ НА ЗЕМЛЮ

Reconstructing the evolutionary relationships among species is one of major subjects in biology. Typically, each species is presented by a sequence over four nucleotide types: A, C, G, and T. A nucleotide mutation is said to be happened at position i between two sequences X = (x1, …, xl) and Y = (y1, …, yl) if xi ≠ yi. The distance between two sequences X and Y is calculated as the total number of nucleotide mutations between them. There are n contemporary species, which are labeled from 0 to n -1. The evolutionary relationships among species are depicted by a binary rooted tree where n leaves represent n contemporary species, internal nodes represent ancestor species, and branch lengths represent distances between species (see figure below). This tree can be represented in text form using brackets as ((0,1),((3,4),2)).

Since nucleotide sequences are not available for ancestor species, our task is to determine one nucleotide sequence for each ancestor species such that the tree length (total branch lengths) is minimized.

Вход

The first line containing two integers n and l (n <= 1000, l <= 100) indicating the number of contemporary species and the length of nucleotide sequences, respectively. The i -th line of the following n lines contains the nucleotide sequence of the contemporary species labeled i -1. The last line contains the text representation of the tree topology.

Выход

Write an integer number indicating the minimum length of the tree.


1 | 2 | 3 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)