Submission #169350

---

Source Code Expand

import std.algorithm;
import std.array;
import std.bigint;
import std.container;
import std.conv;
import std.exception;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

import std.functional;

version = C;

T[] readlnSome(T)(){
    return array(readln().split().map!(a => to!T(a))());
}


T readlnOne(T)(){
    return to!T(readln().split()[0]);
}


void main()
{
  version(A)
  {
    auto ns = readlnSome!uint[0 .. 2];
    writeln(ns[1] - ns[0] + 1);
  }

  version(B)
  {
    uint[string] tb;
    foreach(i; 0 .. readlnOne!uint)
        tb[readlnOne!string] += 1;
    
    Tuple!(string, uint)[] arr;
    foreach(k, v; tb)
        arr ~= tuple(k, v);
    arr.sort!"a[1] > b[1]"();
    writeln(arr[0][0]);
  }

  version(C)
  {
    immutable N = readlnOne!uint;

    uint[] cn;
    foreach(i; 0 .. N)
        cn ~= readlnOne!uint;

    auto idx = iota(cn.length).array;

    uint calc(in size_t[] idx){
        bool[] tbl = new bool[idx.length];

        foreach(i, e; idx){
            if(i != idx.length - 1)
                foreach(j, a; idx[i+1 .. $])
                    if(cn[a] % cn[e] == 0)
                        tbl[j + i + 1] = !tbl[j + i + 1];
        }

        //writeln(tbl);

        return reduce!"a + !b"(0, tbl);
    }

    //writeln(cn);
    //writeln(idx);
    real sum = 0;
    uint cnt;
    do{
        sum += calc(idx);
        ++cnt;
        //writeln(idx);
    }while(nextPermutation(idx));

    //writeln(idx);
    writefln("%.6f", sum / cnt);
  }
}

bool nextPermutation(alias less="a<b", BidirectionalRange)
                    (ref BidirectionalRange range)
    if (isBidirectionalRange!BidirectionalRange &&
        hasSwappableElements!BidirectionalRange)
{
    // Ranges of 0 or 1 element have no distinct permutations.
    if (range.empty) return false;

    auto i = retro(range);
    auto last = i.save;

    // Find last occurring increasing pair of elements
    size_t n = 1;
    for (i.popFront(); !i.empty; i.popFront(), last.popFront(), n++)
    {
        if (binaryFun!less(i.front, last.front))
            break;
    }

    if (i.empty) {
        // Entire range is decreasing: it's lexicographically the greatest. So
        // wrap it around.
        range.reverse();
        return false;
    }

    // Find last element greater than i.front.
    auto j = find!((a) => binaryFun!less(i.front, a))(
                   takeExactly(retro(range), n));

    assert(!j.empty);   // shouldn't happen since i.front < last.front
    swap(i.front, j.front);
    reverse(takeExactly(retro(range), n));

    return true;
}

Submission Info

Judge Result