open System

let rec gcd a b = if b = 0 then a else gcd b (a % b)

let isPrime n =
    if n < 2 then false
    else
        [2 .. int (sqrt (float n))]
        |> List.forall (fun i -> n % i <> 0)

let getDivisors n =
    [1 .. n]
    |> List.filter (fun i -> n % i = 0)

let getPrimeDivisors n =
    getDivisors n
    |> List.filter isPrime

let getDigits n =
    n.ToString().ToCharArray()
    |> Array.map (fun c -> int c - int '0')
    |> Array.toList

let task1 seq1 seq2 =
    let arr1 = Array.ofList seq1
    let arr2 = Array.ofList seq2
    let m = arr1.Length
    let n = arr2.Length
    
    let dp = Array2D.create (m + 1) (n + 1) 0
    
    for i in 1 .. m do
        for j in 1 .. n do
            if arr1.[i-1] = arr2.[j-1] then
                dp.[i, j] <- dp.[i-1, j-1] + 1
            else
                dp.[i, j] <- max dp.[i-1, j] dp.[i, j-1]
    
    let rec buildLCS i j acc =
        if i = 0 || j = 0 then acc
        elif arr1.[i-1] = arr2.[j-1] then
            buildLCS (i-1) (j-1) (arr1.[i-1] :: acc)
        elif dp.[i-1, j] > dp.[i, j-1] then
            buildLCS (i-1) j acc
        else
            buildLCS i (j-1) acc
    
    buildLCS m n []

let task2 inputList =
    let list1 = inputList |> List.filter (fun x -> x % 2 = 0) |> List.map (fun x -> x / 2)
    let list2 = list1 |> List.filter (fun x -> x % 3 = 0) |> List.map (fun x -> x / 3)
    let list3 = list2 |> List.map (fun x -> x * x)
    let list4 = list3 |> List.filter (fun x -> List.contains x list1)
    let list5 = [list2; list3; list4] |> List.collect id |> List.distinct
    (list1, list2, list3, list4, list5)

let task3 n =
    [1 .. n]
    |> List.collect (fun x -> 
        [x .. n / x]
        |> List.filter (fun y -> x * y = n)
        |> List.map (fun y -> 
            let d = gcd x y
            (x / d, y / d)))
    |> List.distinct

let task4 inputList =
    inputList
    |> List.collect (fun a ->
        inputList
        |> List.collect (fun b ->
            inputList
            |> List.filter (fun c -> a < b && b < c && a*a + b*b = c*c)
            |> List.map (fun c -> (a, b, c))))

let task5 inputList =
    inputList
    |> List.filter (fun x ->
        let primeDivisors = getPrimeDivisors x
        primeDivisors
        |> List.forall (fun p -> 
            inputList |> List.exists (fun y -> y <> x && y % p = 0)))

let task6 tupleList =
    tupleList
    |> List.filter (fun (a,b,c,d,e) -> [a;b;c;d;e] |> List.forall (fun x -> x >= 0 && x <= 9))
    |> List.sort
    |> List.map (fun (a,b,c,d,e) -> a*10000 + b*1000 + c*100 + d*10 + e)

let task7 inputList =
    let average = (inputList |> List.sum |> float) / (float inputList.Length)
    let belowAverage = inputList |> List.filter (fun x -> float x < average)
    let evenPositions = inputList |> List.mapi (fun i x -> if i % 2 = 0 then Some x else None) |> List.choose id
    
    let parameterP x =
        let divisors = getDivisors x
        divisors
        |> List.filter (fun d ->
            let isInEvenPos = evenPositions |> List.exists (fun ep -> ep % d = 0)
            let isNotInBelowAvg = belowAverage |> List.forall (fun ba -> ba % d <> 0)
            isInEvenPos && isNotInBelowAvg)
        |> List.sum
    
    inputList
    |> List.sortBy parameterP

let task8 inputList =
    let allDigits = inputList |> List.collect getDigits
    let digitFreq = allDigits |> List.groupBy id |> List.map (fun (d, ds) -> (d, List.length ds))
    let totalFreq = allDigits.Length
    let threshold = totalFreq / 2
    let frequentDigits = digitFreq |> List.filter (fun (_, freq) -> freq > threshold) |> List.map fst
    
    inputList
    |> List.map (fun x ->
        let digits = getDigits x
        let validDigits = digits |> List.filter (fun d -> List.contains d frequentDigits)
        if validDigits.IsEmpty then 0.0
        else (validDigits |> List.sum |> float) / (float validDigits.Length))

let task9 inputList =
    let rec sumPrevious lst acc =
        match lst with
        | [] -> []
        | x::xs -> acc :: sumPrevious xs (acc + x)
    
    let prefixSums = sumPrevious inputList 0
    let squares = inputList |> List.map (fun x -> x * x) |> Set.ofList
    
    inputList
    |> List.mapi (fun i x ->
        let sumPrev = if i = 0 then 0 else prefixSums.[i-1]
        let isGreaterThanSum = x > sumPrev
        let isPerfectSquare = inputList |> List.exists (fun y -> y * y = x)
        let isDivisibleByAll = if i = 0 then true else inputList.[0..i-1] |> List.forall (fun y -> x % y = 0)
        
        if isGreaterThanSum && isPerfectSquare && isDivisibleByAll then
            let greaterCount = inputList |> List.filter (fun y -> y > x) |> List.length
            Some (x, sumPrev, greaterCount)
        else None)
    |> List.choose id

let task10 (inputList: int list) =
    let indices = [0 .. inputList.Length - 1]
    
    let list2 = 
        indices
        |> List.filter (fun i ->
            inputList
            |> List.exists (fun x ->
                inputList
                |> List.exists (fun y -> x <> y && x * y = inputList.[i])))
    
    let list3 =
        indices
        |> List.filter (fun i ->
            inputList
            |> List.exists (fun x ->
                inputList
                |> List.exists (fun y ->
                    inputList
                    |> List.exists (fun z -> x <> y && y <> z && x <> z && x + y + z = inputList.[i]))))
    
    let list4 =
        indices
        |> List.filter (fun i ->
            let divisors = inputList |> List.filter (fun x -> inputList.[i] % x = 0)
            divisors.Length = 4)
    
    (list2, list3, list4)

let showMenu() =
    printfn "\n=== Меню задач ==="
    printfn "1. Наибольшая общая подпоследовательность"
    printfn "2. Кортеж из пяти списков с преобразованиями"
    printfn "3. Кортежи для факторизации числа"
    printfn "4. Пифагоровы тройки"
    printfn "5. Элементы со всеми простыми делителями в списке"
    printfn "6. Сортировка кортежей с преобразованием в числа"
    printfn "7. Сортировка по сумме специфических делителей"
    printfn "8. Среднее арифметическое частых цифр"
    printfn "9. Фильтрация по трем условиям"
    printfn "10. Кортеж из трех списков номеров"
    printfn "0. Выход"
    printf "Выберите задачу: "

let runTask taskNumber =
    match taskNumber with
    | 1 ->
        printfn "Задача 1: Наибольшая общая подпоследовательность"
        let seq1 = [1; 2; 3; 4; 5]
        let seq2 = [2; 3; 5; 7]
        let result = task1 seq1 seq2
        printfn "Последовательность 1: %A" seq1
        printfn "Последовательность 2: %A" seq2
        printfn "Наибольшая общая подпоследовательность: %A" result
    
    | 2 ->
        printfn "Задача 2: Кортеж из пяти списков"
        let inputList = [6; 9; 12; 15; 18; 21]
        let (list1, list2, list3, list4, list5) = task2 inputList
        printfn "Исходный список: %A" inputList
        printfn "Список 1 (четные/2): %A" list1
        printfn "Список 2 (список1, делящиеся на 3, /3): %A" list2
        printfn "Список 3 (квадраты списка2): %A" list3
        printfn "Список 4 (список3, встречающиеся в списке1): %A" list4
        printfn "Список 5 (объединение 2,3,4): %A" list5
    
    | 3 ->
        printfn "Задача 3: Кортежи для факторизации"
        let n = 12
        let result = task3 n
        printfn "Число N = %d" n
        printfn "Кортежи (a,b): %A" result
    
    | 4 ->
        printfn "Задача 4: Пифагоровы тройки"
        let inputList = [3; 4; 5; 6; 8; 10; 12; 13; 15]
        let result = task4 inputList
        printfn "Исходный список: %A" inputList
        printfn "Пифагоровы тройки: %A" result
    
    | 5 ->
        printfn "Задача 5: Элементы со всеми простыми делителями в списке"
        let inputList = [6; 10; 15; 21; 30]
        let result = task5 inputList
        printfn "Исходный список: %A" inputList
        printfn "Элементы со всеми простыми делителями в списке: %A" result
    
    | 6 ->
        printfn "Задача 6: Сортировка кортежей"
        let tupleList = [(7,3,4,5,6); (2,3,4,6,7); (2,3,4,5,6); (4,3,1,0,4)]
        let result = task6 tupleList
        printfn "Исходные кортежи: %A" tupleList
        printfn "Отсортированные числа: %A" result
    
    | 7 ->
        printfn "Задача 7: Сортировка по параметру P"
        let inputList = [12; 18; 24; 30; 36]
        let result = task7 inputList
        printfn "Исходный список: %A" inputList
        printfn "Отсортированный по параметру P: %A" result
    
    | 8 ->
        printfn "Задача 8: Среднее арифметическое частых цифр"
        let inputList = [145; 247; 456; 789]
        let result = task8 inputList
        printfn "Исходный список: %A" inputList
        printfn "Средние значения частых цифр: %A" result
    
    | 9 ->
        printfn "Задача 9: Фильтрация по трем условиям"
        let inputList = [1; 2; 4; 8; 16; 32]
        let result = task9 inputList
        printfn "Исходный список: %A" inputList
        printfn "Элементы, удовлетворяющие условиям: %A" result
    
    | 10 ->
        printfn "Задача 10: Кортеж из трех списков номеров"
        let inputList = [2; 4; 6; 8; 12; 16]
        let (list2, list3, list4) = task10 inputList
        printfn "Исходный список: %A" inputList
        printfn "Номера элементов - произведения двух других: %A" list2
        printfn "Номера элементов - суммы трех других: %A" list3
        printfn "Номера элементов, делящихся на 4 элемента: %A" list4
    
    | _ ->
        printfn "Неверный номер задачи!"

[<EntryPoint>]
let main argv =
    let mutable shouldContinue = true
    
    while shouldContinue do
        showMenu()
        
        match Console.ReadLine() with
        | "0" -> 
            shouldContinue <- false
            printfn "До свидания!"
        | input ->
            match Int32.TryParse(input) with
            | true, taskNumber when taskNumber >= 1 && taskNumber <= 10 ->
                printfn ""
                runTask taskNumber
                printfn "\nНажмите Enter для продолжения..."
                Console.ReadLine() |> ignore
            | _ ->
                printfn "Пожалуйста, введите число от 0 до 10."
    
    0