Әр түрлі жануарлардың ДНК тізбектеріне қызығып, Арманда келесі сұрақ пайда болды: екі жануардың ДНҚ-сын қалай ұқсас деп айта аламыз? Осы мақсатта ол жаңа формула ойлап тапты және оны ұқсастық коэффициенті деп атады. Ол былай есептеледі:

• Ең алдымен, бірінші жануардың ДНҚ-сы \(r\) жолы, ал екінші жануардың ДНҚ-сы \(s\) жолы деп алайық. Екі жол да бос емес және тек 'A', 'C', 'G' және 'T' әріптерінен тұрады;

• Бірінші, біз \(\text{LCS}(r, s)\) мәнін есептейміз. \(\text{LCS}\) (*Longest Common Subsequence) дегеніміз — екі жолдың ең ұзын ортақ ішкі жолы*, яғни \(r\) жолынан және \(s\) жолынан кейбір символдарды жою арқылы алуға болатын ең ұзын жолдың ұзындығы. Мысалы, \(\text{LCS}(\text{GTA}, \text{CAT}) = 1\) («A» және «T») және \(\text{LCS}(\text{ACTAG}, \text{TAAG}) = 3\) («TAG»);

• Содан кейін, \(\text{LCS}(r, s)\) мәнін \(|r| + |s|\) мәніне — бастапқы жолдардың ұзындықтарының қосындысына бөлеміз. Алынған сан ұқсастық коэффициенті болады.

Осылайша, «GTA» және «CAT» ұқсастық коэффициенті \(1 / (3 + 3) = 0.1666\ldots\) болады, ал «ACTAG» және «TAAG» ұқсастық коэффициенті \(3 / (5 + 4) = 0.3333\ldots\) болады.

Арман өзінің формуласын нағыз ДНК тізбектеріне қолдануға тырысты. Бірақ ол бір проблемаға тап болды — ДНК тізбектері өте өте ұзын болуы мүмкін! Бақытымызға орай, Арман ерекше қасиеті бар ДНК жұбын тапты — олар периодты түрде өздерін-өздері қайталайды. Яғни, бірінші ДНҚ тізбегі \(r + \ldots + r\) болады, ал екіншісі \(s + \ldots + s\) болды, мұндағы \(r\) және \(s\) — салыстырмалы түрде қысқа жолдар.

ДНК-лар соншалықты ұзын, Арман \(s\) және \(t\) олардың ішінде қанша рет қайталанатынын да білмейді! Ол \(r\) жолы \(x\) рет, ал \(s\) жолы \(y\) рет қайталанады деп болжауды шешті. Сөйтіп ол барлық мүмкін \((x, y)\) жұптары үшін ұқсастық коэффициенттерін есептеп шығады және солардың арасындағы ең үлкен санды бастапқы ДНҚ жұбының ұқсастық коэффициенті ретінде жазады.

Ресми түрде, жауап былай есептеледі:

• Барлық мүмкін \(x, y > 0\) шартына сай келетін \((x, y)\) жұптары үшін, Арман \(\underbrace{r + \ldots + r}_{x\ \text{рет}}\) және \(\underbrace{s + \ldots + s}_{y\ \text{рет}}\) жолдарының ұқсастық коэффициентін қағазға жазады;

• Барлық жазылған мәндердің арасында Арман ең үлкен мәнді табады. Бұл мән ДНК тізбектерінің ұқсастық коэффициенті болады.

Арман бұл процестің ең жылдам емес екенін тез түсінді, сондықтан ол жауапты сізден сұрап тұр. Оған көмектесіңіз!

Енгізу

Бірінші жолда \(r\) жолы (\(1 \le |r| \le 200\)) беріледі.

Екінші жолда \(s\) жолы (\(1 \le |s| \le 200\)) беріледі.

Екі жол да тек 'A', 'C', 'G' және 'T' әріптерінен тұрады.

Шығару

Бір нақты сан шығарыңыз — \(r + \ldots + r\) және \(s + \ldots + s\) ДНҚ тізбектерінің ұқсастық коэффициенті. Бұл сан жоғарыда сипатталған әдіспен есептеледі.

Сіздің жауабыңыз дұрыс деп есептеледі, егер оның абсолютті немесе салыстырмалы қатесі \(10^{-9}\) мәнінен аспаса. Ресми түрде, егер сіздің жауабыңыз \(a\), ал қазылар алқасының жауабы \(b\) болса, онда сіздің жауабыңыз қабылданады, егер және тек егер \(\frac{|a-b|}{\text{max}(1,|b|)} \le 10^{-9}\).

Бағалау жүйесі

Мысалдар

Енгізу 1

AC
CA

Жауап 1

0.500000000000

Енгізу 2

CAT
TAG

Жауап 2

0.333333333333

Енгізу 3

ACTAG
TAAG

Жауап 3

0.333333333333

Ескертпелер

Бірінші мысалды қарастырайық.

• \((x, y) = (2, 2)\) жұбы үшін «ACAC» және «CACA» ұқсастық коэффициенті \(3 / 8 = 0.375\) болады;

• \((x, y) = (3, 4)\) жұбы үшін «ACACAC» және «CACACACA» ұқсастық коэффициенті \(5 / 14 = 0.3571\ldots\) болады;

• \((x, y) = (5, 5)\) жұбы үшін «ACACACACAC» және «CACACACACA» ұқсастық коэффициенті \(9 / 20 = 0.45\) болады;

• Егер дәл осылай қалған \((x, y)\) жұптарының жауаптарын есептеуді жалғастырсақ, максималды ұқсастық коэффициенті \(0.5\) болады.