/** * Use the Chinese Remainder Theorem. * Turn the problem into a set of congruences k=a_1 mod n, k=a_2 mod n-1, k=a_3 mod n-2 ... k=a_n mod 1 * Where a_i is the position of the each person after preceding people have been removed from the list. * * @author Finn Lidbetter */ fun gcd(a: Long, b: Long): Long { if (b == 0L) { return a } return gcd(b, a % b) } fun lcm(a: Long, b: Long): Long { return (a / gcd(a, b)) * b } fun extendedEuclidean(a: Long, b: Long): LongArray { if (b == 0L) { return longArrayOf(1L, 0L, a) } val result = extendedEuclidean(b, a % b); return longArrayOf(result[1], result[0] - a / b * result[1], result[2]) } fun main() { val n = readln().toInt() val order = readln().toCharArray().map { it -> it - 'A' } var used = BooleanArray(n) { false } var a = LongArray(n) { 0L } for ((index, person) in order.withIndex()) { var usedBeforeCount = 0L for (i in 0..person - 1) { if (used[i]) { usedBeforeCount++ } } a[index] = person - usedBeforeCount used[person] = true } val m = LongArray(n) { index -> (n - index).toLong() } var currAns = a[0] var currMod = m[0] for (i in 1..n-1) { val result = extendedEuclidean(currMod, m[i]) val x1 = result[0] val divisor = result[2] if ((a[i] - currAns) % divisor != 0L) { println("NO") return } currAns = currAns + (((x1 * (a[i] - currAns)) / divisor) % (m[i] / divisor)) * currMod val tmpMod = currMod * m[i] / divisor if (currAns >= tmpMod || currAns < 0) { currAns %= tmpMod if (currAns < 0) { currAns += tmpMod } } currMod = lcm(currMod, m[i]) } println("YES") println(currAns) }