Nim
TopCoder SRM 785
Time Limit: 1s, Memory Limit: 64MiB
Ели и Крис играят на разновидност на играта Ним. Нейните правила са следните. Пред двамата играчи има N купчинки с камъчета. Броят камъчета в купчинките е, съответно, A1, A2, ... AN. Играчите се редуват, като на всеки ход вземат по едно или повече камъчета от избрана от тях купчинка. Задължително е всички взети камъчета на даден ход да са от една и съща купчинка. Играчът, който вземе последното камъче, побеждава.

Ели започва първа, поради което Крис подозира, че приятелката ѝ има предимство. Затова момичето е решило скришом да добави камъчета в някои (потенциално всички или никоя) от купчинките, така че да може да победи дори ако Ели играе оптимално. По-формално, нека X1, X2, … XN са цели, неотрицателни числа. Крис добавя X1 камъчета в първата купчинка, X2 камъчета във втората купчинка и т.н. При започване на играта купчинките съдържат (A1 + X1), (A2 + X2), ... (AN + XN) камъчета.

Момичето не иска нещата да изглеждат подозрителни, затова цели броят на всички добавени камъчета да е възможно най-малък. Можете ли да определите колко допълнителни камъчета ще ѝ трябват?
Вход
На първия ред на стандартния вход ще бъде зададено едно цялото число N – броят купчинки. На втория ред ще бъдат зададени N цели числа A1, A2, …, AN – броят камъчета във всяка от купчинките, преди Крис да добави допълнителните.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния брой допълнителни камъчета (сума от X1, X2, …, XN), така че Крис да може да победи. Гарантирано е, че това винаги е възможно.
Ограничения
  • 2 ≤ N ≤ 100
  • 1 ≤ Ai ≤ 1,000,000,000
Примерен Вход Примерен Изход
6 42 13 123 55 666 17 480
Едно възможно решение е, например, X1 = 0, X2 = 11, X3 = 389, X4 = 73, X5 = 6, X6 = 1.
Макар и да има и решения с други X1 ... X6, най-малката тяхна сума е 480.
Мрън!