Задача тижня 30.01.12 – 05.02.12
Масовий забіг
Учасникам масового забігу перед стартом були видані нагрудні знаки з номерами, що відповідають порядку їх реєстрації. Після забігу вони склали ці знаки в ряд один за одним у порядку свого прибуття на фініш, утворивши таким чином N-розрядне число.
1. Створіть програму, яка за заданим N обчислює кількість учасників забігу k. Реалізуйте перевірку правильності заданого значення N:
Вхідні дані
Значення N (кількість розрядів числа) – натуральне число не більше за 2147483647, вводиться з клавіатури.
Вихідні дані
Значення k (кількість учасників забігу) – натуральне число, виводиться на екран.
Якщо значення N є помилковим, вивести значення k, яке дорівнює -1.
2. Заповніть тестову таблицю за результатами роботи програми
| № | N | k |
| 1 | 9 | 9 |
| 2 | 10 | -1 |
| 3 | 11 | 10 |
| 4 | 1 | |
| 5 | 189 | |
| 6 | 2893 | |
| 7 | 30001 | |
| 8 | 788888889 | |
| 9 | 2147483644 | |
| 10 | 2147483647 |
Аналіз розв’язку задачі «Масовий забіг»
Розглянемо спочатку алгоритм, який надіслав Юрій Дончик.
Якщо число, яке склали учасники забігу, не перевищує 9, то усі номери однорозрядні, і кількість учасників дорівнює N. Подальше збільшення кількості учасників означає перехід до дворозрядних номерів, останній з яких – 99. Нескладно обчислити, що номери 99-ти учасників складуть число довжиною в N=189 цифр. Аналогічні міркування можна продовжувати для тризначних, чотиризначних і т.д. номерів.
Узагальнимо наведений алгоритм, забезпечивши обчислення констант у циклі. Спосіб обчислення рубіжних констант стає більш прозорим, якщо послідовно віднімати з N кількість цифр, яку утворюють однорозрядні, дворозрядні, трирозрядні і т.д. номери.
…………………………………………………
Розглянутий підхід було застосовано в розв’язках авторів під псевдонімами forsh3 і RomaN. Але звернемо увагу на суттєвий момент: формулюючи умову циклу, слід запобігти виходу значення арифметичного виразу за межі чотирибайтного цілого. Саме це ми і передбачили, записавши умову у вигляді N div i > p.
Іншим способом розв’язку задачі є послідовне віднімання від заданого N кількості цифр у номерах учасників забігу, починаючи з першого, доки різниця не стане нульовою, і тоді кількість учасників знайдено, або від’ємною, і тоді слід вивести значення -1. Але такий підхід потребує виконання комп’ютером значно більшої кількості операцій.
Тестова таблиця з результатами роботи програми:
| № | N | k |
| 1 | 9 | 9 |
| 2 | 10 | -1 |
| 3 | 11 | 10 |
| 4 | 1 | 1 |
| 5 | 189 | 99 |
| 6 | 2893 | 1000 |
| 7 | 30001 | 7777 |
| 8 | 788888889 | 99999999 |
| 9 | 2147483644 | -1 |
| 10 | 2147483647 | -1 |
Журі оцінило надіслані розв’язки наступним чином:
| № | Учасник | Кількість балів |
| 1 | RomaN | 4 |
| 2 | Макс Синкевич | 2 |
| 3 | Kolgatin Andrey | 4 |
| 4 | Юрий Дончик | 4 |
| 5 | SERGEY | 2 |
| 6 | forsh3 | 3 |
