Google code jam. Qualification Round 2010.

Решил вчера поучаствовать в отборочном раунде code jam. Раунд состоял из трех достаточно простых задач, мне хватило терпения только на первые две, хотя как решать третью я тоже понял :)

Первая задача, snaper chain – самая простая, достаточно понять, что состояние snapper-ов в цепочке после K щелчков, будет эквивалентно двоичному представлению числа K. Вот мое решение на F#:

open System
open System.IO

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()

let inputSeq:seq<int*int> = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let lst = line.Split(' ')
        yield int lst.[0], int lst.[1]
    }

// write the output file
let snapperState n k =
    let l = 2 <<< n - 1
    let m = k % l
    match l - 1 = m with
    | true  -> "ON"
    | false -> "OFF"

let mutable caseIx = 1
for n, k in inputSeq do
    let line = sprintf "Case #%d: %s" caseIx <| snapperState n k
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Вторая задача, fair warning – намного сложнее. Суть задачи – в следующем, у нас есть набор чисел – t1, t2,.. tn. Нужно найти такое значение y, для которого справедливо условие – (Y + ti) mod T = 0, для любого i < n. Причем, T – должно быть максимально возможным. Помимо этого, исходные данные могут содержать большие числа, так и написано:

64 bits will not save you. You have been warned.

Я использовал следующий алгоритм – сначала массив чисел ti сортируется, затем – нормализуется (из каждого элемента вычитается значение минимального элемента); далее, вычисляется наибольший общий делитель элементов массива(функция gcdv), в результате чего мы получаем значение T, после чего достаточно легко рассчитать значение Y. Вот мое решение:

open System
open System.IO
open System.Numerics

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()
printfn "N: %d" testsNum

let inputSeq = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let strlst = line.Split(' ').[1..]
        let intlst = Array.map (fun x -> BigInteger.Parse(x)) strlst
        yield intlst
    }

let gcd a b = BigInteger.GreatestCommonDivisor(a, b)

let gcdv vals = Array.reduce gcd vals
            
let getDiff events = 
    if Array.length events < 2 then
        failwith "error in getDiff, events array is to small"
    Array.sortInPlace events
    let min = events.[0]
    min, Array.map (fun x -> x - min) events.[1..]

let (|Length|) arr = Array.length arr

let mutable caseIx = 1

for events in inputSeq do

    let result =
        match events with
        | Length 0
        | Length 1 -> 0I
        | _ -> 
            let min, diff = getDiff events 
            let factor = gcdv diff
            if min % factor = 0I then 0I
            else factor - (min % factor)

    let line = sprintf "Case #%d: %s" caseIx <| result.ToString()
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Кстати, сразу после начала раунда я обнаружил что на моем домашнем компьютере нет ни Visual Studio, ни интерпретатора python-a, даже несчастного с++ компиялтора нет. Вышел из положения скачав F# CTP, код набирал в vim. F# interpreter – очень удобная штука, я его использовал в интерактивном режиме, в качестве REPL, а так-же для запуска своей писанины :)