asyan.org
добавить свой файл
1 2
Задача 1 CREAT Протилежністю до числа x назвемо число, в якому всі цифри числа x стоять в зворотному порядку, причому нулі зліва опускаються. Наприклад, протилежністю до числа 4375 є число 5734, а протилежністю до числа 7830 - 387. Назвемо k-творцем таке число, яке в сумі з його числом-протилежністю дає число k. Наприклад, у числа 222 є всього два числа k-творці: 111 і 210, а у числа 1050 є дев'ять k-творців чисел: 129, 228, 327, 426, 525, 624, 723, 822, 921. Написати програму, яка для даного числа k визначає усі числа, що є k-творцями.

Вхідні дані: У вхідному файлі Creat.dat записане одне натуральне число k (1 ≤k ≤ 106).

Результати: У вихідний файл Creat.res через пропуск треба записати усі числа, що є k-творцями, якщо такі існують. Якщо чисел k-творців не виявлено, у вихідний файл треба записати слово ″not″.

Приклади



Creat.dat

Creat.res

1

222

111 210

2

1050

129 228 327 426 525 624 723 822 921


Задача 2 EVEN Написати програму, яка визначає найменше натуральне число x, при множенні якого на дане число k (1 ≤ k ≤ 10255) одержиться парне число.

Вхідні дані : У файлі Even.dat записане єдине число k.

Результати: У файлі Even.res записати число x, якщо число k ‒ парне, то x = 1.

Приклади:

Even.dat: 123456789123456789 Even.res: 2

1234567891234567894 Even.res: 1
Задача 3 IPAD Основним параметром або ідентифікатором кожного комп'ютера в мережі є його IP-адреса, наприклад: 254.0.127.12. Дано число N − набір із k арабських цифр (4≤k≤12) без пропусків чи інших розділових знаків, наприклад: 254012712, причому, зліва нулі відсутні.

a) Написати програму, яка визначає, чи можлива IP-адреса, що містить дані цифри у вказаному порядку.

Вхідні дані: У файлі Ipad.dat записано число N.

Результати: У файлі Ipad.res записати слово yes або no.

б) Написати програму, яка визначає всі можливі IP-адреси з кількістю цифр, що містять дані цифри у вказаному порядку з не більшою 12 кількістю цифр. При відсутності варіантів файл Ipad.res повинен бути пустим.

Вхідні дані: У файлі Ipad.dat записано число N.

Результати: У файлі Ipad.res записати всі можливі шукані IP-адреси, кожна в окремому рядку.

Приклади вхідного та вихідного файлів:

Ipad.dat

Ipad.res (а)

Ipad.res (б)

1898422239

Yes

189.84.22.239

189.84.222.39

Задача 4. DEC. Написати програму, яка для двох введених натуральних чисел (чисельник і знаменник дробу, кожне в діапазоні 1..1000) визначає точне значення цього дробу в десятковому записі.

Вхідні дані: У файлі Dec.dat через пропуск записано два натуральні числа ‒ чисельник та знаменник дробу.

Результати: У файлі Dec.res записати єдине число ‒ одержаний періодичний дріб.

Приклад:

Dec.dat




Dec.res

5 7




0,(714285)


^ ВКАЗІВКИ ДО РОЗВ’ЗУВАННЯ ЗАДАЧ
Задача 1 CREAT (25 балів) Протилежністю до числа x назвемо число m, в якому всі цифри числа x стоять в зворотному порядку, причому нулі зліва опускаються. Наприклад, протилежністю до числа 4375 є число 5734, а протилежністю до числа 7830 - 387. Назвемо k-творцем таке число, яке в сумі з його числом-протилежністю дає число k, тобто x + m = k. Наприклад, у числа 222 є всього два числа k-творці: 111 і 210, а у числа 1050 є дев'ять k-творців чисел: 129, 228, 327, 426, 525, 624, 723, 822, 921. Написати програму, яка для даного числа k визначає усі числа, що є k-творцями.

Вхідні дані: У вхідному файлі Creat.dat записане одне натуральне число k (1 ≤k ≤ 108).

Результати: У вихідний файл Creat.res через пропуск треба записати усі числа, що є k-творцями, якщо такі існують. Якщо чисел k-творців не виявлено, у вихідний файл треба записати слово ″not″.

Приклади



Creat.dat

Creat.res

1

222

111 210

2

1050

129 228 327 426 525 624 723 822 921


Вказівки до розв′язування

Розв′язування задачі зводиться до циклічного визначення протилежності кожного з натуральних чисел x (1 ≤ x k), визначення суми x + m та перевірки, чи x + m = k. Залишається тільки забезпечити виведення чисел x, якщо вони існують.

Задача має перший рівень складності, вона може бути доступною всім учасникам олімпіади районного рівня. Порушення обмеження для k (1 ≤k ≤ 108) приводить до недопустимого збільшення часу тестування розв′язку.

Тести по складності практично рівноцінні, за винятком двох останніх, які передбачають дуже велику кількість чисел − k-творців (405 та 900 відповідно).


Тести

1

2

3

4

5

6

7

8

9

10

Бали

2

2

2

2

2

2

2

2

4

5
Оцінки тестів:


Задача 2 EVEN (35 балів) Написати програму, яка визначає найменше натуральне число x, при множенні якого на дане число k (1 ≤ k ≤ 10255) одержиться парне число.

Вхідні дані : У файлі Even.dat записане єдине число k.

Результати: У файлі Even.res записати число x, якщо число k ‒ парне, то x = 1.

Приклади:

Even.dat: 123456789123456789 Even.res: 2

1234567891234567894 Even.res: 1

Вказівки до розв′язування

Дуже велике обмеження для числа k (10255) для складності не має значення, адже у програмі цілком можна обійтись роботою з рядковими даними, адже згідно ознаки подільності на 2 достатньо проаналізувати останню цифру, яку можна ″вирізати″ з рядка та перетворити в число стандартною Pascal-процедурою Val(s,v,code). Складність задачі прихована в тому, що в умові число k може бути не тільки цілим, а й десятковим дробом, наприклад: 236,12345. Тоді, підрахувавши p − кількість десяткових знаків, можна одержати ціле число k×10p. Далі потрібно застосувати написане вище стосовно цілих чисел k. Але множник 10p. при цьому може виявитись не найменшим, якщо добуток k×10p закінчується парною цифрою 4 чи 8. Тоді необхідно провести додатковий аналіз числа, що складається із двох чи трьох останніх цифр добутку k×10p, щоб дізнатись, чи можна множник 10p замінити, наприклад, на 5×10p-1. У порівнянні із задачею Creat ця задача дещо складніша в реалізації (другий рівень складності), тому повне тестування дасть можливість отримати 35 балів.


Тести

1

2

3

4

5

6

7

8

9

10

11

12

Бали

1

1

2

2

2

2

3

4

4

4

5

5
Оцінки тестів:

Задача 3 IPAD (50 балів) Основним параметром або ідентифікатором кожного комп'ютера в мережі є його IP-адреса, наприклад: 254.0.127.12. Дано число N − набір із k арабських цифр (4≤k≤12) без пропусків чи інших розділових знаків, наприклад: 254012712, причому, зліва нулі відсутні.

a) Написати програму, яка визначає, чи можлива IP-адреса, що містить дані цифри у вказаному порядку (45 балів).

Вхідні дані: У файлі Ipad.dat записано число N.

Результати: У файлі Ipad.res записати слово yes або no.

б) Написати програму, яка визначає всі можливі IP-адреси з кількістю цифр, що містять дані цифри у вказаному порядку з не більшою 12 кількістю цифр. При відсутності варіантів файл Ipad.res повинен бути пустим (50 балів).

Вхідні дані: У файлі Ipad.dat записано число N.

Результати: У файлі Ipad.res записати всі можливі шукані IP-адреси, кожна в окремому рядку.

Приклади вхідного та вихідного файлів:

Ipad.dat

Ipad.res (а)

Ipad.res (б)

1898422239

Yes

189.84.22.239

189.84.222.39

Вказівки до розв′язування

Для обох варіантів задач перший етап розв′язування очевидний – необхідно визначити, чи можливо побудувати IP-адресу, розставивши в певних місцях між даними цифрами крапки. Іншими словами слід згенерувати із даних цифр, беручи їх послідовно, чотири числа в межах 0-255, пам′ятаючи, що ці числа можуть мати від однієї до трьох цифр, причому перша зліва з них міститись у діапазоні 0..0, у випадку, коли перша цифра дорівнює 2, наступні цифри повинні бути в діапазоні 0..5, а коли перша цифра дорівнює 0, друга та третя цифри повинні бути відсутні.

Такий підхід (урахування значень цифр числа, залежно від позиції) при практичній реалізації може бути трудомістким як на стадії написання програмного коду, так і на стадії відлагодження програми. Крім того, його природніше реалізувати з використанням рекурсії, що впливає на швидкодію і використання пам′яті. Виходячи з невеликої кількості цифр у даному наборі (обмежена числом 12) можна реалізувати циклічну програму з використанням методу повного перебору, що й зроблено в авторському розв′язку. Цей метод дозволяє прирівняти обидва наведені варіанти (а) та б)) по складності. Загальний рівень складності цієї задачі у порівнянні із задачами №№ 1,2 можна вважати третім, тому правильний розв′язок оцінено 50 балами. Варіант а) оцінено 45 балами лише тому, що перебір варіантів може бути зупинений при виявленні першої IP-адреси, хоча на час виконання це суттєво не вплине.

Оцінки тестів:


Тести

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Бали

1

1

1

1

1

2

2

3

3

3

3

3

3

4

4

5

5

5


Задача 4.


следующая страница >>