1. Проґресiя
Арифметичною проґресією називають послідовність, у якій різниця двох послідовних елементів стала.
Завдання
Створiть програму sequence.*, що з даної множини n натуральних чисел вибере елементи арифметичної проґресiї найбiльшої довжини з додатною рiзницею.
Вхідні дані
Файл sequence.dat мiстить (n + 1) натуральне число, кожне з яких не перевищує 500000. Перше з них — n, а наступнi — рiзнi n натуральних чисел.
Вихідні дані
Кожен рядок файла sequence.res має мiстити у вказаному порядку кiлькiсть членiв шуканої арифметичної проґресiї, її найменший перший член та її рiзницю — по одному варiанту вiдповiдi в кожному рядку в порядку зростання першого члена, а для однакових перших членiв — у порядку зростання рiзницi проґресiї.
Приклади
| sequence.dat | sequence.res |
|---|---|
| 4 1 5 6 3 | 3 1 2 |
| 8 1 5 10 3 6 8 18 30 | 3 1 2 3 6 2 3 6 12 |
2. Поверхня куба
Координати вершин куба дорiвнюють 0 або натуральному d. На поверхнi куба розташовано замкнену ламану без самоперетинiв, що має n вершин. Координати всiх вершин цiєї ламаної — невiд'ємнi цiлi числа.
Завдання
Створiть програму cubesurf.* для визначення площі фіґур, обмежених ламаною на поверхні куба.
Вхідні дані
Файл cubesurf.dat мiстить у вказаному порядку натуральнi числа d, n, де d < 109, n < 105, i послiдовнiсть n трiйок координат вершин цiєї ламаної у порядку обходу ламаної. Для кожної вершини спочатку вказано абсцису x, потiм — ординату y, потiм — аплiкату z.
Вихідні дані
Файл cubesurf.res має містити у порядку неспадання подвоєнi площi фiґур, на якi ламана розбиває поверхню куба.
Приклад
| cubesurf.dat | cubesurf.res |
|---|---|
| 1000 3 1 0 0 0 1 0 0 0 1 | 3 11999997 |
3. Код Грея
Кодом Грея називають непозиційну систему запису цілих натуральних чисел за допомогою двох символів 0 та 1 таким чином. Нуль кодують послідовністю нулів. При зростанні цілого числа:
наймолодший 1-ий розряд у послідовності символів змінюють у такій послідовності: 0, 1, після чого у наступний 2-й розряд записують 1, а наймолодший розряд змінюють уже у протилежному порядку;
два наймолодші розряди змінюють у такому порядку: 00, 01, 11, 10, після чого у 3-ій розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку: 10, 11, 01, 00;
три наймолодші розряди змінюють у такому порядку: 000 , 001, 011, 010, 110, 111, 101, 100, після чого у 4-ий розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку:100, 101, 111, 110, 010, 011, 001, 000 (див. таблицю, у якій подано коди Грея послідовностями по 4 символи для цілих чисел від 0 до 15 включно) … ;
k наймолодших розряди змінюють у порядку, визначеному попередніми кроками, після чого у наступний (k + 1)-ий розряд записують 1, а молодші розряди змінюють уже у протилежному порядку ... .
| Десяткова позиційна система числення | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Двійковий код | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| Код Грея | 0000 | 0001 | 0011 | 0010 | 0110 | 0111 | 0101 | 0100 | 1100 | 1101 | 1111 | 1110 | 1010 | 1011 | 1001 | 1000 |
Коди Грея двох послідовних натуральних чисел відріняються лише в одному розряді. Цю властивість використовують для збільшення надійності роботи системи оптичних фотодіодів при встановленні кута повороту дисків-носіїв інформації.
Завдання
Визначте коди Грея для послідовних невід'ємних цілих чисел.
Вхідні дані
Файл gray.dat натуральне число n, що не перевишує 21.
Вихідні дані
Файл gray.res має містити коди Грея довжини n (по одному в кожному рядку) послідовних невід'ємних цілих чисел від 0 до 2n– 1 включно.
Приклад
| gray.dat | gray.res |
|---|---|
| 2 |
00 01 11 10 |