 |
Вітаю Вас, Гість · RSS |
 |
Всеукраїнська олімпіада з інформатики (програмування)
| |
kom_adm |
Дата: Tu, 20.11.2007, 20:07 | Повідомлення № 1 |
Ветеран спілкування
Повідомлень: 3767
| Шановні учасники форуму! Скоро районна олімпіада по інформатиці. Допоможіть мені та іншим вчителям інформатикам, які погано розуміються на задачах олімпіадного рівня, підвищити свої знання в області програмування.
Увага! При публікуванні розв’язку обов’язково, окрім самої паскаль-програми писати математичну модель задачі і роз’яснювати ваш розв’язок максимально зрозуміло. Бо із самого тексту програм, не завжди все зрозуміло для пересічного інформатика.
[admin]Шановні форумчани!!!!! Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!![/admin]
|
|
| |
kom_adm |
Дата: Tu, 20.11.2007, 20:45 | Повідомлення № 2 |
Ветеран спілкування
Повідомлень: 3767
| Задача 1. (Із минулорічної олімпіади). Цеглина (Brick). Нехай є нескінченна кількість прямокутних цеглин розмірами (Xі, Yі, Zі), кожен з яких може орієнтуватися довільно так, що будь-які дві сторони є основою, а остання - висотою. Ваша задача - написати програму, що знаходить максимальну висоту башти, яку можна побудувати з цих цеглин. При цьому верхня цеглина може бути поставлена на нижню, якщо розміри двох сторін верхньої цеглини строго менші відповідних розмірів нижньої. Технічні умови: Вхідний файл Brick.dat містить число n - кількість типів цеглин (1<= n <= 50), а далі n стрічок по три цілих числа 1<=(Xі, Yі, Zі)<= 65000 - розміри кожного типу цеглин. Вихідний файл Brick.sol містить єдине число - висоту найвищої башти. Приклад вхідного та вихідного файлів: Brick.dat 2 6 8 10 5 5 5 Brick.sol 21
|
|
| |
dpi |
Дата: Tu, 05.02.2008, 16:45 | Повідомлення № 3 |
Досвідчений вчитель
Повідомлень: 1438
| [Приклад вхідного та вихідного файлів: Brick.dat 2 6 8 10 5 5 5 Brick.sol 21] Числа в примере реальные?
|
|
| |
kom_adm |
Дата: Tu, 05.02.2008, 22:14 | Повідомлення № 4 |
Ветеран спілкування
Повідомлень: 3767
| Quote (dpi) Числа в примере реальные? Реальні. Умова записана правильно.
|
|
| |
dpi |
Дата: Fr, 14.03.2008, 14:37 | Повідомлення № 5 |
Досвідчений вчитель
Повідомлень: 1438
| Будем решать. Вот только не решил с чего начать Первая мысль рекурсия, вторая - динамическое пр-е. третья отсортировать по размерам оснований (с учетом высоты) и сложить высоты. Какой то из этих вариантов (да/нет - для экономии времени...)?Додано (14.03.2008, 14:37) --------------------------------------------- Продолжайте тему. Я решать передумал. (Достал интересную книгу.)
|
|
| |
Bandalak |
Дата: Fr, 14.03.2008, 14:45 | Повідомлення № 6 |
Лідер форуму
Повідомлень: 6386
| Quote (Ковальчук_Олександр) Цеглина (Brick). Нехай є нескінченна кількість прямокутних цеглин розмірами (Xі, Yі, Zі), Мені тут не подобається слово "нескінчена". Краще сказати, що є n цеглин, 1<= n <= 50. Quote (dpi) Числа в примере реальные? Наведіть розрахунки, як у Вас вийшло 21, у мене виходить 15.
|
|
| |
Varkan |
Дата: Mo, 17.03.2008, 12:59 | Повідомлення № 7 |
Викладач ВУЗу
Повідомлень: 425
| Цікаво а шо робити з такими цеглинами: 3 7 5 5 5 5
|
|
| |
SLKuty |
Дата: We, 10.12.2008, 23:46 | Повідомлення № 8 |
Монтажер
Повідомлень: 833
| Відбулася районна олімпіада ось задачі організатори напевно щось переплутали і 4 задача сама проста виявилася я її за 15 хв зробив там всього 7 рядочків а третя досить цікава вже другий день її роблю 1. Трикутник.(10 балів) За введеними величинами двох сторін трикутника і кута між ними визначити, чи є трикутник рівностороннім, рівнобедреним чи прямокутним (друге і третє може бути "одночасно). Для визначення третьої сторони використати теорему косинусів: с =a2+b -2*a*b*cos(z), де z - кут між сторонами а і Ь. З клавіатури вводяться три додатних дійсних числа: а та Ь - сторони трикутника, z - кут між ними в градусній мірі. Результатом програми має бути або одне із повідомлень: «рівносторонній», «рівнобедрений», «прямокутний» або два повідомлення: «рівнобедрений» «прямокутний» або повідомлення «трикутник довільний» Вхідні дані: Вихідні дані: 3 3 60 рівносторонній 18 18 ЗО рівнобедрений 178 178 90 рівнобедрений прямокутний 34.2 29 121 трикутник довільний 2. Число(20 балів) Задано натуральне число N (1<N<2000000000). Знайти найменше та найбільше число, яке складається з тих самих цифр та у такій самій кількості, що і N З клавіатури вводиться N Результатом програми має бути два числа: в першому рядку: найменше число Вхідні дані: Вихідні дані: 2385 2358 8532 3. Задача «Virus» (ЗО балів) (Примітка: якщо задача розв'язана без використання файлів, сума балів зменшується на 20%) На полі розміром п*п (п<=500) розміщено т (І<=т<=10) вірусів. В кожен момент часу вірус заражує 4 сусідні з ним клітинки. Положення вірусів задано координатами клітинок на полі. Визначити, яка найменша кількість моментів часу потрібна, щоб віруси заразили усе поле. Вхідні дані: у першому рядку вхідного файлу virus.dat знаходяться два числа через пробіл - п та т . Наступні т рядків містять координати вірусів - по два числа через пробіл. Вихідні дані: єдиний рядок файлу virus.sol містить число - кількість моментів часу. 4. Послідовність (40 балів) Послідовність з латинських літер будується так. Спочатку послідовність порожня. На кожному наступному кроці послідовність подвоюється, після чого до неї ліворуч дописується наступна літера латинського алфавіту (a, b, с, d, є ,...). Нижче подано перші кроки побудови послідовності. Крок 0. Послідовність порожня. Крок 1. а Крок 2. baa Крок 3. cbaabaa Крок 4. dcbaabaacbaabaa Потрібно написати програму, яка визначає символ, який стоїть на N-тому місці в послідовності після М-того кроку. Вхідні дані: з клавіатури вводяться числа N та М Вихідні дані: на екран виводиться літера латинського алфавіту Наприклад, для N=6, М=4 це буде літера Ь.
|
|
| |
staikin |
Дата: We, 06.05.2009, 21:26 | Повідомлення № 9 |
Новий користувач
Повідомлень: 2
| Ребята помогите пожайлуста написать програму в Паскале Знаходження правильних послідовностей Будемо розглядати послідовності круглих, квадратних і фігурних дужок. Серед усіх таких послідовностей виділимо правильні — ті, котрі можуть бути отримані за такими правилами: 1) порожня послідовність правильна; 2) якщо А и В правильні, то й АВ правильна; 3) якщо А правильна, то {А}, [А] і (А) правильні. Приклад. Послідовності (), [[]], {}, [({})[]()][] - правильні, а послідовності ], )(, (], (}[){] — не є правильними. Розробити алгоритм і написати програму перевірки за час, що не перевершує константи, помноженої на її довжину, того, що введена з клавіатури послідовность буде правільною. Заранее спасибо! [img]http://informatics.at.ua/sml/1.gif[/img]
|
|
| |
alex |
Дата: We, 06.05.2009, 21:42 | Повідомлення № 10 |
Активний учасник
Повідомлень: 586
| На мою думку це задача на правильне розміщення дужок. ЇЇ розвязок можливий за один прохід ( оптимальність алгоритму N де N кількість символів в стрічці.) Використовуєм стек. Кожен раз аналізуємо взятий символ та символ в вершині стеку. Взятий символ поміщаєм в стек , в випадку коли він є відкритою дужкою, або в вершині знаходиться відкрита дужка яка не відповідає взятій закритій. В іншому випадку один сивол знищуємо з стека. Якщо по закінченні проходу по стрічці стек пустий то стрічка вірна в іношу випадку ні. Розвязок цієї задачі є в кожній біль менш пристойній книжці з основ алгоритмізаціїї для учнів та студентів ВУЗу.
|
|
| |
swetikccc |
Дата: We, 06.05.2009, 22:45 | Повідомлення № 11 |
Ветеран спілкування
Повідомлень: 4208
| Quote (Bandalak) Наведіть розрахунки, як у Вас вийшло 21, у мене виходить 15. 6+10+5=21 Додано (06.05.2009, 22:45) --------------------------------------------- Quote (Bandalak) Мені тут не подобається слово "нескінчена". Краще сказати, що є n цеглин, 1<= n <= 50. Тут грає роль тільки кількість типу цеглин(правда при умові що тип меньше кількості) а це й досягаеться безкінченністю
Відредаговано: swetikccc - We, 06.05.2009, 22:54 |
|
| |
dpi |
Дата: We, 06.05.2009, 23:33 | Повідомлення № 12 |
Досвідчений вчитель
Повідомлень: 1438
| Quote (alex) На мою думку це задача на правильне розміщення дужок. Можно и так: просматриваем строку если встречается открытие - заносим в стек если встречается закрытие, снимаем со стека если скобки одного вида, просматриваем строку дальше иначе выход из алгоритма - скобки расставлены не правильно если стек в конце пуст - "правильно" иначе - нет Перед снятием вершины стека проверять не пуст ли он!!!
|
|
| |
swetikccc |
Дата: Th, 07.05.2009, 07:47 | Повідомлення № 13 |
Ветеран спілкування
Повідомлень: 4208
| Quote (dpi) если встречается закрытие, снимаем со стека Если конечно соответствует вершине, иначе выход (Давайте обьяснять и для не спецов)
|
|
| |
alex |
Дата: Th, 07.05.2009, 08:26 | Повідомлення № 14 |
Активний учасник
Повідомлень: 586
| Quote (dpi) третья отсортировать по размерам оснований (с учетом высоты) и сложить высоты. Такий спосіб не дасть розвязку так як необхідно щоб виконцвалась ще одна умова Умова :верхня цеглина може бути поставлена на нижню, якщо розміри двох сторін верхньої цеглини строго менші відповідних розмірів нижньої. Повно перебірний варіант має оптимальність 3* N !. Де N кількість цеглин. Кожна цеглина може давати приріст в висоту або x або y або z. формуємо масив [1..3,1..n]. Генеруємо всі можливі перестановки. Кожну перестановку аналізуємо по принципу: Рухаємося зліва направо поки не порушиться вимога для піраміди або не закінчаться цеглини і накопичуємо значення висоти. По закінченню проходу перевіряємо чи не більша знайдена висота за попередню. Якщо більша то запамятовуємо знайдене значення висоти. Зрозуміло що такий розвязок не отримує повний бал. Розвязок задачі методом динамічного програмування дивіться на сайті OLYMP.VINNICA.UA. Архів районних олімпіад з інформатики.
Відредаговано: alex - Th, 07.05.2009, 13:17 |
|
| |
swetikccc |
Дата: Th, 07.05.2009, 11:51 | Повідомлення № 15 |
Ветеран спілкування
Повідомлень: 4208
| Quote (alex) або не закінчаться цеглини Як може закінчитися безкінечність? Тут потрібно розглядати кількість типів цеглин
Відредаговано: swetikccc - Th, 07.05.2009, 11:57 |
|
| |
© Форум інформатиків України, 2007-2022.  |