Сайт підготовки до олімпіади з інформатики

Переведення чисел з однієї системи числення в іншу

Переведення чисел в різних системах числення

На приклад, якщо потрібно перемножити числа 101 і 1001 в двійковій системі, то він спочатку ці числа переводить в десяткову систему таким чином :

(101)₂=1*2²+0*2¹+1*2⁰=4+0+1=5

(1001)₂=1*2³+0*2²+0*2¹+1*2⁰=8+0+0+1=9

Після чого множення чисел 5 і 9 Вася з легкістю виконує в десятковій системі числення і отримує число 45. Далі виконує переведення з десяткової системи числення в двійкову. Для цього потрібно ділити число 45 на 2 ( порядок системи числення ), запам'ятовує залишки від ділення, до тих пір поки в результаті не залишиться число 0:

Відповідь складається з одержаних залишків від ділення шляхом їх запису в зворотному  порядку . Таким чином одержуємо результат : (101)₂ * (1001)₂ = (101101)₂.

1. Задача. Перевести число з  будь-якої системи числення в будь-яку іншу.

Протестувати самостійно

2. Задача  BINARY

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

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

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

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 19₁₀ = 1×2⁴+0×2³+0×2²+1×2¹+1×2⁰ в двійковій  системі запишеться як 10011₂). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри буде число 1×2⁴+1×2³+1×2²+0×2¹+0×2⁰ = 28.

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

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

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

Приклад

3. Задача  Нулі

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

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

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

Необхідно написати програму для знаходження кількості N-значних чисел в системі числення за основою K, таких що їхній запис не буде містити двох нулів підряд.

Формат вхідних даних.

Єдиний рядок вхідного файлу ZEROS.DAT містить два натуральних числа N та K, 2 <= K <= 10, N + K <= 18.

Формат вихідних даних.

Єдиний рядок вихідного файлу ZEROS.SOL повинен містити одне натуральне число - розв'язок задачі.

Приклад.

ZEROS.DAT:

4 2

ZEROS.SOL:

5

4. Задача. Міжнародна конференція

Вас найняли для того, щоб визначити місця дипломатів за столом обговорень міжнародної конференції. На конференцію запрошено по одному дипломату з N різних країн світу. Ко­жен дипломат знає від однієї до п'яти мов. Дип­ломати, які не знають спільної мови, не можуть розмовляти один з одним. До того ж, деякі краї­ни проголосили, що не будуть підтримувати дипломатичних стосунків з деякими іншими, тобто представники цих країн не будуть роз­мовляти один з одним. Ваше завдання полягає в розробці програми DIPLOMAT.pas/.c/.cpp, що визначає місця за столом для дипломатів таким чином, щоб кожен мав можливість розмовляти з обо­ма своїми сусідами, які сидять ліворуч та пра­воруч від нього.

Стіл, що використовується, - круглий і розрахований на N персон (N£20). Дипломат може спілкуватися з дипломатом, який сидить ліво­руч, однією мовою, а з дипломатом, що сидить праворуч, - іншою.

Технічні вимоги:

Вхідний файл: DIPLOMAT. DAT.

Вихідний файл: DIPLOMAT. SOL.

Програма: diplomat.pas/.c/.cpp

Формат вхідних даних. У першому рядку текстового файла DIPLOMAT. DAT - число N. Далі - N рядків, по одному рядку на диплома­та. Кожен рядок - послідовність слів. Сусідні слова відокремлені пробілом. Кожне слово - це послідовність великих латинських літер. Перше слово - код країни - складається з трьох літер. Друге слово має довжину від 1 до 5 літер і являє собою перелік мов, якими може спілкуватися дипломат. Кожна мова позначена однією літерою. Далі - список з не більш ніж N трилітерних слів - кодів країн, з якими уряд дипломата підтримує дипломатичні стосунки.

Формат вихідних даних. До файла DIPLOMAT. SOL треба вивести список дипломатів у порядку розміщення за столом (по одному дипломату в рядку). Кожен рядок складається з трьох слів: перше - код мови, якою дипломат може спілкуватися з сусідом ліворуч, друге - код країни дипломата, третє - код мови для спілкування з сусідом праворуч. Мож­ливе існування кількох розв'язків. Вам по­трібно знайти один. Якщо розв'язку не існує, то ваша програма має видати таке повідомлен­ня: «NO  SOLUTION EXIST»

Приклад:

Домашні задачі

1. Прості числа (решето Ератосфена).

2. Супер прості числа.