Перший тур
Розв’язки задач відправляти з 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).
Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне результату гри.
Приклад
BINARY.DAT
|
BINARY.SOL
|
19
|
28
|
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-тій системи. Числа йдуть у порядку неспадання.
У першому рядку виведіть шукане число (якщо розв’язків кілька - виведіть будь-яке з них), а у другому рядку - суму, яку при називанні телеведучим числа доведеться виплатити в якості виграшу.
Приклади
LOTAREYA.DAT
|
LOTAREYA.SOL
|
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111
|
011
6
|
1 1 10
100
0
|
7
0
|
Умови завдань в форматі МS Word cкачати |