Перший тур

Розв’язки задач відправляти з 27.09 по 10.10.2010 р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

1. Задача BINARY (20 балів)

Ім’я вхідного файлу: BINARY.DAT

Ім’я вихідного файлу: BINARY.SOL

Максимальний час роботи на одному тесті: 3с

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число (19)10 = 1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 в двійковій системі запишеться як (10011)2). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

…

і результатом гри буде число 1*2^4+1*2^3+1*2^2+0*2^1+0*2^0 = 28.

Оскільки придумана гра з числами все більше займає уяву учня, відволікаючи тим самим його від навчання і підготовки до олімпіади, Вас просять написати програму, яка б допомогла Дімі отримувати результат гри без важких ручних обчислень.

Вхідний файл містить одне ціле число N (0<=N<=32767).

Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне результату гри.

Приклад

2. Задача LOTAREYA (100 балів)

Ім’я вхідного файлу: LOTAREYA.DAT

Ім’я вихідного файлу: LOTAREYA.SOL

Максимальний час роботи на одному тесті: 4с

На телеканалі 1+1 щотижня проводиться наступна лотерея. Протягом тижня учасники роблять свої ставки. Кожна ставка полягає в називанні будь-якого M-значного числа в системі числення з основою K (тобто, кожний учасник називає M цифр, кожна з яких лежить в діапазоні від 0 до K-1). Нуль на початку числа допускаються.
У деякий момент прийом ставок на поточний розіграш завершується, і після цього ведучий в телеефірі називає виграло число (це також M-значне число в K-тій системі числення). Після цього ті телеглядачі, у кого перша цифра їх числа збіглася з першою цифрою числа, названого ведучим, отримують виграш у розмірі A1 гривні. Ті, у кого співпали перші дві цифри числа - отримують A2 гривні (при цьому якщо у гравця збіглася друга цифра, але не збіглася перша, він не отримує нічого). Аналогічно вгадали перші три цифри отримують A3 рублів. І так далі. Вгадали всі число повністю отримують AM гривні. При цьому якщо гравець вгадав t перших цифр, то він отримує At гривні, але не отримує призи за вгадування t-1, t-2 і т.д. цифр. Якщо гравець не вгадав першу цифру, він не отримує нічого.
Напишіть програму, яка за відомим ставками, зробленим телеглядачами, знаходить число, яке має назвати телеведучий, щоб фірма-організатор розіграшу виплатила в якості виграшів мінімальну суму. Для вашої зручності ставки, зроблені гравцями, вже впорядковані за неспаданням.

У першому рядку вхідного файлу  задаються числа N (кількість телеглядачів, які зробили свої ставки 1<= N<=100000), M (довжина чисел 1<=M<=10) і K(основа системи числення 2<=K<=10). У наступному рядку записані M чисел A1, A2, ..., AM, які задають виграші в разі збігу тільки першою, перших двох, ... , всіх цифр (1<=A1<=A2<=...<=AM<=100000). У кожному з наступних N рядків записано по одному M-значну числу K-тій системи. Числа йдуть у порядку неспадання.

У першому рядку виведіть шукане число (якщо розв’язків кілька - виведіть будь-яке з них), а у другому рядку - суму, яку при називанні телеведучим числа доведеться виплатити в якості виграшу.

Приклади

Умови завдань в форматі МS Word cкачати