Заннятя 1 (07.09.2016) Печать
Добавил(а) Administrator   
07.09.16 00:00

Заннятя 1 (07.09.2016)

 Завдання  1 (http://kpi-open.org/tasks/ )

Недобросовісний МЕНЕДЖЕР

Менеджер транспортної компанії таємно співпрацює з постачальником палива і зацікавлений в максимальному його витраті. Як йому скласти маршрутну карту відвідування вантажівкою N міст, розташованих уздовж однієї траси на однаковій відстані одне від одної, таким чином, щоб витрата палива був найбільшим?

Формат вхідного файлу

Вхідний файл складається з одного рядка, що містить три цілих числа, відокремлених один від одного пробілом: N - кількість міст (10 <= N <= 25000), D - відстань між містами, F - витрата палива на одиницю шляху.

 Формат вихідного файлу

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

Введення

Виведення

12 1 5

 

125 5 10

 

325 5 1

 


 

Завдання 2

https://www.e-olymp.com/uk/problems/2669

Поворот

Задано масивn×m. Потрібно повернути його за годинниковою стрілкою на90градусів.

Вхідні дані

У першому рядку задано натуральні числаnтаm(1n,m50). У наступнихnрядках записано поmневід'ємних чисел, які не перевищують109- сам масив.

Вихідні дані

Виведіть перевернутий масив у форматі вхідних даних.

Ліміт часу1секунда

Ліміт використання пам'яті64MiB

Вхідні дані #1

3 4
1 2 3 4
5 6 7 8
9 10 11 12

Вихідні дані #1

4 3
9 5 1
10 6 2
11 7 3
12 8 4


 

Завдання 3

https://www.e-olymp.com/uk/problems/1378

Фібоначчієва система числення

Як відомо, послідовність Фібоначчі починається з двох чисел 0 та 1 і кожен наступний член послідовності отримується як сума двох попередніх. Наприклад, третій член послідовності це 1 (1=1+0), четвертий - 2 (2=1+1), п'ятий - 3 (3=2+1) і т.д.

i

0

1

2

3

4

5

6

7

8

9

Fib(i)

0

1

1

2

3

5

8

13

21

34

Рисунок 1 - Перші числа послідовності Фібоначчі

Ця послідовність проявляється дуже часто і у нашому житті і у природі та має велике значення. А чи знаєте Ви, що всі додатні цілі числа можна подати як суму чисел з послідовності Фібоначчі? Більше того, всі натуральні числа можна подати за допомогою послідовності Фібоначчі, причому без повторень. Наприклад: 13 може бути подано за допомогою вказаної множини як {13}, {5,8} або {2,3,8} а 17 подано як {1,3,13} або {1,3,5,8}. Так як всі числа мають цю властивість (може у Вас є бажання довести це?), то цей набір є гарним способом для його використання у якості "бази" (основи системи числення) для подання чисел. Але, як ми бачили вище, деякі числа можуть бути подані більш ніж одним способом сумою чисел з послідовності Фібоначчі. Як нам вийти з цієї ситуації? Дуже просто! Для цього достатньо накласти обмеження, що при поданні числа не можна використовувати два сусідніх елементи з послідовності Фібоначчі! Це обмеження поясюється тим, що сума двох сусідніх членів послідовності Фібоначчі сама є членом послідовності Фібоначчі.

Тепер, коли нам відомо все сказане вище, ми можемо запропонувати гарний спосіб подавння довільного цілого додатнього числа. Для цього ми будемо використовувати двійкову послідовність (лише нулів та одиниць). Наприклад, 17 = 1 + 3 + 13 (ми повинні пам'ятати, що не можна використовувати два послідовних числа Фібоначчі). Будемо використовувати нуль у запису, якщо чергове число з послідовностіи Фібоначчі не використовується, і одиницю для тих, що використовуються. Тоді, 17 = 100101 (ведучі нулі повинні бути відсутні). На рисунку 2детально показано, як отримано цей запис і що означають нулі та одиниці у наведенному вище запису. Для кращого розуміння цієї схеми звернемо увагу на той факт, що не використання двох сусідніх чисел Фібоначчі означає, що двійкова послідовність не буде мати двох одиниць, що йдуть підряд. Використовуючи наведене подання числа, ми будемо говорити, що ми використовуємо Фібоначчієву систему числення і записувати його як 17 = 100101 (fib).

17=

1

0

0

1

0

1

13+3+1=

13

8

5

3

2

1

Рисунок 2 - Пояснення подання числа 17 у Фібоначчієвій системі числення

Ваша задача полягає у запису задного десяткового числаув Фібоначчієвій системі числення.

Вхідні дані

У першому рядку вхідних даних задано єдине натуральне число N, яке вказує на кількість прикладів у тесті (1 ≤ N ≤ 500).

Наступні N рядків містять по одному додатньому цілому числу, яке не перевищує 100 000 000. Числа можуть бути подані у довільному порядку.

Вихідні дані

Ви повинні вивести по одному рядку для кожного з N чисел, отриманих у вхідних даних, у наступному форматі: "DEC_BASE = FIB_BASE (fib)". DEC_BASE це задане оригінальне число у десятковій системі числення, а FIB_BASE відповідно - його подання у Фібоначчієвій системі числення. Зразок виведення наведено у прикладі вихідних даних.

Ліміт часу 1 секунда

Ліміт використання пам'яті 64 MiB

Вхідні дані

10

1

2

3

4

5

6

7

8

9

10

Вихідні дані

1 = 1 (fib)

2 = 10 (fib)

3 = 100 (fib)

4 = 101 (fib)

5 = 1000 (fib)

6 = 1001 (fib)

7 = 1010 (fib)

8 = 10000 (fib)

9 = 10001 (fib)

10 = 10010 (fib)