|
Добавил(а) Гісь Ігор Володимирович
|
|
03.10.12 09:20 |
|
Задача 2. Task2
Перевірити правильність виразу NoNoN =N за заданими чотирма числами a, b,c,d, які підставляємо замість N (N<=100), а о – може бути однією з операцій o(+ - *).
Вхідний файл Task2.in містить рядок з трьох цілих чисел.
Вихідний файл Task2.out містить рядок з відповіддю у вигляді YES або NO. |
|
Готуємось до олімпіади з інформатики 2013-2014 н.р. (додаток 1) |
 |
 |
 |
|
Добавил(а) Гісь Ігор Володимирович
|
|
16.10.13 10:48 |
|
додаток 1
Готуємось до олімпіади з інформатики
2013-2014 н.р.
|
Форма проведення
|
Представлення
|
|
Теоретичний тур
|
Описати алгоритм та написати програмний код розв’язку задач
|
|
Практичний тур
|
http:://192.168.0.199/new-register?constent_id=1
зареєструватися в системі
логін: Прізвище та ім’я (англійською мовою)
пароль записати
Ввести ім’я учасник: Прізвище, ім’я, клас
Підтвердити реєстрацію
|
Задача 1. «Фотокартка» (PHOTO) – 10 балів.
Учень на новенькому кольоровому струменевому принтері учень надрукував фотографії зроблені у свій день народження. Розмір фото AxB cм. Роздільна здатність принтера R точок на дюйм (1 дюйм = 2,54 см).
Завдання
Визначити скільки пікселів містить надруковане фото?
Вхідні дані
Перший рядок містить два дійсні числа, які задають розмір фотокартки. Останній рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить шукану кількість мегапікселів на фотографії, як дійсне число з двома знаками після коми.
Приклад
|
input.txt
|
output.txt
|
|
2.54
2.54
1000
|
1.00
|
Задача 2. «Клас» – 20 балів.
На початку навчального року класний керівник між учнями класу поділила N зошитів та M олівців. Скільки учнів в класі, якщо відомо їх не менше ніж K і кожний з учнів отримав однакову сумарну кількість зошитів та олівців.
Вхідні дані
Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить знайдену кількість шкіл. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.
Приклад
|
input.txt
|
output.txt
|
|
92
138
25
|
46
|
Задача 3. «День народження» – 30 балів.
Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.
Вхідні дані
Перший рядок містить загальну кількість учнів, натуральне число N.
В наступних рядках кількість розданих цукерок.
Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.
Приклад
|
input.txt
|
output.txt
|
|
5
3
1
2
4
3
|
3 2
|
Задача 4. Дорога в гімназію -40 балів.
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити хоча б довжину найкоротшої дороги від доми до школи.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість точок на карті.
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії,,
Наступні рядків задають карту намальованих дорігпочаткова та кінцева точка.
Вихідні дані:
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги.Якщо дороги немає вивести "no".
Приклади:
|
input.txt
|
output.txt
|
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
|
|
|
|
Добавил(а) Гісь Ігор Володимирович
|
|
19.12.12 10:00 |
| Лексичний пербір |
Перебір з поверненням |
|
Лексичний перебір
1.Повернемось до перебору:
а). Ми мали: 1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
б). А якщо ми маємо
3,8,7
Як утворити всі можливі перестановки?
1. Утворити перестановки 1,2,3 і використати їх як індексний масив.
в) Маємо 1,1,2
1,2,1
2,1,1
2. Побудуємо лексичний перебір для довільних елементів масиву
X=3 2 4 2 4 3 1
а) Рухаємось справа наліво. Крок вперед можна зробити, якщо наступне число більше за попереднє. Ми зупинилися перед числом 2. Це число потрібно помітити.
б) Рухаємось справа наліво. Крок вперед можна зробити, якщо число менше за знайдене число(2). Ми зупинилися перед числом 3. Це число потрібно помітити.
в) Переставляємо знайдені числа.
г) Запишемо числа, розміщені після першого знайденого в зворотному порядку.
|
Перебір з поверненням
Розглянемо метод розв’язку цілого ряду переборних задач на прикладі відомої задачі про тури, які треба розставити на шахівниці так, щоб вони не били один одного. Для наочності візьмемо дошку 3х3 клітинки і розставляти будемо відповідно 3 тури. З відомих формул комбінаторики випливає, що ми будемо мати 3!=6 варіантів розміщень. Очевидно. що при будь-якім розміщенні на кожній горизонталі і на кожній вертикалі повинно бути по одній турі. При відомій вправності і фантазії 3 тури можна ще розставити “вручну” . Ну, а вісім чи більше ( на відповідній дошці, звичайно)? Важкувато...Спробуємо перекласти цю задачу на плечі машини.
Нехай ми маємо два покажчики - стрілки ðñ
Одна з них указує на горизонталь дошки, інша - на вертикаль. Ставимо першу туру і покажчики, як показано на малюнку, і переміщаємо горизонтальний покажчик на одну позицію вправо. Пробуємо ставити в клітинку, на яку вказують покажчики. Але це зробити не можна. Піднімаємо вертикальний покажчик на одну позицію нагору. Клітка, на яку вказують покажчики, не бита, можна ставити туру. Переміщаємо горизонтальний покажчик на одну клітинку вправо. Знову пробуємо поставили туру туди, куди вказує покажчик, але клітка бита.
Піднімаємо вертикальний покажчик на одну позицію вгору. Клітка вільна, ставимо туру, горизонтальний покажчик вийде за межі дошки.
Це ознака того, що дане розміщення довершене. Виводимо результат і повертаємо горизонтальний покажчик на одну позицію вліво, вертикальний покажчик установлюємо на туру в даній вертикалі і намагаємося підняти туру, на яку він указує . Вільних кліток немає. Знімаємо туру, горизонтальний покажчик уліво на одну позицію, а вертикальний поміщаємо на ту горизонталь, де є тура в даній вертикалі.
Намагаємося знову підняти туру, на яку вказує покажчик. Це можливо. Піднімаємо її і горизонтальний покажчик на 1 позицію вправо, а вертикальний - на 1.
`
Пробуємо помістити туру по покажчиках, якщо немає - піднімаємо вертикальний наверх, поки не знайдемо не биту клітку. Ставимо туру, і знову горизонтальний покажчик піде на одну позицію вправо. Готове чергове розміщення.
Знову після виведення результату повернемо горизонтальний покажчик на одну позицію вправо , а вертикальний установимо на туру в цій вертикалі і спробуємо підняти туру, на яку він указує. Вільних кліток немає. Знімаємо туру і, перемістивши горизонтальний покажчик ще раз вправо , вертикальний виставляємо проти тури у відповідній вертикалі і намагаємося підняти її. У нас знову нічого не вийде, ми знімаємо і цю туру і переміщаємо горизонтальний покажчик ще лівіше, а вертикальний - на туру в стовпці, на який вказує горизонтальний покажчик. Пробуємо підняти її. Це зробити вдається. Повторюємо всі ці дії , при цьому, якщо горизонтальний покажчик виходить за межі дошки вправо, виводимо розміщення, а ознакою того, що всі комбінації вже були, стане те, що горизонтальний покажчик вийде за межі дошки вліво.
Виберемо структуру даних. Поле представимо у виді матриці A[n:n], де N кількість кліток у кожній горизонталі і вертикалі ( та й тур у нашому випадку теж N). Якщо в даній клітинці немає тури - A[і,j]=0 , а якщо є то A[і,j]=1. Ще нам знадобляться дві змінні цілого типу для збереження в них значення покажчиків П_В и П_Г.
Для конструювання алгоритму на високому рівні деталізації нам необхідно мати такі процедури і функції:
ПОСТАВ_І_ВПРАВО - ставить туру в клітинку з заданими координатами і переміщає горизонтальний покажчик на одну позицію вправо , а вертикальний установлює на першу позицію (процедура)
ЗНІМИ_І_ВЛІВО - знімає туру з даної клітки і переміщає горизонтальний покажчик на одну позицію вліво , вертикальний покажчик встановлює в позицію тури, на яку тепер указує горизонтальний покажчик ( процедура )
ПРАВИЛЬНА_КЛІТИНКА - логічна функція. Повертає істина, якщо туру можна поставити в дану клітку, і хибно, якщо поставити в клітинку не можна.
ВЛІВО - переміщає горизонтальний покажчик на одну позицію вліво і установлює вертикальний покажчик на туру в цій вертикалі (процедура).
ВИВЕДЕННЯ - виводить на екран результат (процедура)
Тепер наш алгоритм може бути представлений так:
алг Пошук_з_поверненням
поч
для і від 1 до n
нц
для j від 1 до n
нц
A[і,j] :=0
кц
кц
П_Г:=1
П_В:=1
ПОСТАВ_І_ВПРАВО П_В:= П_В+1
поки П_Г<>0
пц поки ( не ПРАВИЛЬНА_КЛІТИНКА ) і (П_Г < n+1)
пц
П_В:=П_В+1
кц
якщо П_В < n+1
то ПОСТАВ_І_ВПРАВО
інакше ЗНІМИ_І_ВЛІВО
все
якщо П_Г =n+1
то ВИВЕДЕННЯ
ВЛІВО
все
кц
до П_Г=0
кін
|
|
|
Практикум з розв'язування задач |
|
|
|
|
Добавил(а) Administrator
|
|
22.10.14 02:00 |
|
Ремонт кораблів (DOCKS)
На судоремонтний завод для докового ремонту одночасно прийшло N кораблів. В док на ремонт може зайти тільки одне судно. Необхідний час стоянки в доці для кожного судна різний. Після ремонту судно одразу йде в рейс.
Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний.
Формат вхідних даних:
У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1£N£10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).
Формат вихідних даних:
Вихідний файл повинен містити послідовність чисел – номери кораблів, у тому порядку, в якому вони заходять у док.
Між числами має бути по одному проміжку. Наприкінці рядка проміжок не ставте.
Приклад вхідних та вихідних даних:
|
DOCKS.DAT
|
DOCKS.RES
|
|
3
3 6
1 12
2 4
|
2 3 1
|
Працівники (STAFF)
(XVІІ Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)
На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.
Існують правила, за якими визначається, чи можна обробляти деталь на певному верстаті.
$11) Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.
$12) У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.
Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.
Напишіть програму STAFF, яка за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.
Формат вхідних даних:
Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.
Формат вихідних даних:
Єдиний рядок вихідного файлу STAFF.RES має містити ціле число – максимальну можливу кількість працівників заводу.
Приклад вхідних та вихідних даних:
Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станку B – деталі 2 та 4. Інших варіантів послідовності обробки немає.
Затори на дорогах (JAMMING)
Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).
Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.
Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S.
Формат вхідних даних:
Вхідний файл містить єдине число S (1£S£10000) – задана відстань.
Формат вихідних даних:
Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур.
Достеменно відомо, що кількість цифр у відповіді не перевищує 700.
|
JAMMING.DAT
|
JAMMING.RES
|
|
2
|
4
|
Приклад вхідних та вихідних даних:
Кубики (CUBES)
(XV Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)
Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.
Напишіть програму CUBES, що отримує на вхід фронтальну та праву проекції фігури та визначає мінімальну та максимальну кількість кубиків, яку можна було б використати для побудови фігури із заданими проекціями.
Формат вхідних даних:
У першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та К, що задають розміри проекцій (1≤ N, M, K ≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені прогалиною. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітинку проекції, 1 — заповнену.
Формат вихідних даних:
У єдиному рядку вихідного файлу CUBES.SOL повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями.
Приклад вхідних та вихідних даних:
|
CUBES.DAT
|
CUBES.RES
|
|
2 2 3
1 0
1 1
0 0 1
1 1 1
|
4 7
|
|
|
Последнее обновление 30.03.15 09:16 |
|