Чт, 17.08.2017, 11:01
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

   
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Сторінка 1 з 211232021»
Модератор форуму: Ktara, Bandalak, НІКОЛЯ, volevikt 
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Олімпіадні задачі. (розв’язування олімпіадних задач.)
Олімпіадні задачі.
Ковальчук_Олександр Дата: Вт, 20.11.2007, 21:07 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3616
Нагороди: 17
Рейтинг: 192
Шановні учасники форуму! Скоро районна олімпіада по інформатиці. Допоможіть мені та іншим вчителям інформатикам, які погано розуміються на задачах олімпіадного рівня, підвищити свої знання в області програмування.

Увага! При публікуванні розв’язку обов’язково, окрім самої паскаль-програми писати математичну модель задачі і роз’яснювати ваш розв’язок максимально зрозуміло. Бо із самого тексту програм, не завжди все зрозуміло для пересічного інформатика. 


[admin]Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!!


Відредаговано: W-w-W - Пт, 08.01.2016, 00:28
Ковальчук_Олександр Дата: Вт, 20.11.2007, 21:45 | Повідомлення № 2
Ветеран спілкування
Повідомлень: 3616
Нагороди: 17
Рейтинг: 192
Задача 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 Дата: Вт, 05.02.2008, 17:45 | Повідомлення № 3
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
[Приклад вхідного та вихідного файлів:
Brick.dat
2
6 8 10
5 5 5
Brick.sol
21]
Числа в примере реальные?
Ковальчук_Олександр Дата: Вт, 05.02.2008, 23:14 | Повідомлення № 4
Ветеран спілкування
Повідомлень: 3616
Нагороди: 17
Рейтинг: 192
Quote (dpi)
Числа в примере реальные?

Реальні. Умова записана правильно.
dpi Дата: Пт, 14.03.2008, 15:37 | Повідомлення № 5
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Будем решать.
Вот только не решил с чего начать
Первая мысль рекурсия, вторая - динамическое пр-е. третья отсортировать по размерам оснований (с учетом высоты) и сложить высоты.
Какой то из этих вариантов (да/нет - для экономии времени...)?

Додано (14.03.2008, 14:37)
---------------------------------------------
Продолжайте тему.
Я решать передумал. (Достал интересную книгу.)

Bandalak Дата: Пт, 14.03.2008, 15:45 | Повідомлення № 6
Лідер форуму
Повідомлень: 5269
Нагороди: 35
Рейтинг: 247
Quote (Ковальчук_Олександр)
Цеглина (Brick). Нехай є нескінченна кількість прямокутних цеглин розмірами (Xі, Yі, Zі),

Мені тут не подобається слово "нескінчена". Краще сказати, що є n цеглин, 1<= n <= 50.

Quote (dpi)
Числа в примере реальные?

Наведіть розрахунки, як у Вас вийшло 21, у мене виходить 15.
Varkan Дата: Пн, 17.03.2008, 13:59 | Повідомлення № 7
Викладач ВУЗу
Повідомлень: 425
Нагороди: 0
Рейтинг: 6
Цікаво а шо робити з такими цеглинами:
3 7 5
5 5 5
SLKuty Дата: Чт, 11.12.2008, 00:46 | Повідомлення № 8
Монтажер
Повідомлень: 805
Нагороди: 6
Рейтинг: 103
Відбулася районна олімпіада ось задачі
організатори напевно щось переплутали і 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 Дата: Ср, 06.05.2009, 22:26 | Повідомлення № 9
Новий користувач
Повідомлень: 2
Нагороди: 0
Рейтинг: 0
Ребята помогите пожайлуста написать програму в Паскале
Знаходження правильних послідовностей

Будемо розглядати послідовності круглих, квадратних і фігурних дужок. Серед усіх таких послідовностей виділимо правильні — ті, котрі можуть бути отримані за такими правилами:
1) порожня послідовність правильна;
2) якщо А и В правильні, то й АВ правильна;
3) якщо А правильна, то {А}, [А] і (А) правильні.
Приклад. Послідовності (), [[]], {}, [({})[]()][] - правильні, а послідовності ], )(, (], (}[){] — не є правильними.
Розробити алгоритм і написати програму перевірки за час, що не перевершує константи, помноженої на її довжину, того, що введена з клавіатури послідовность буде правільною.

Заранее спасибо! [img]http://informatics.at.ua/sml/1.gif[/img]

alex Дата: Ср, 06.05.2009, 22:42 | Повідомлення № 10
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
На мою думку це задача на правильне розміщення дужок. ЇЇ розвязок можливий за один прохід ( оптимальність алгоритму N де N кількість символів в стрічці.) Використовуєм стек. Кожен раз аналізуємо взятий символ та символ в вершині стеку. Взятий символ поміщаєм в стек , в випадку коли він є відкритою дужкою, або в вершині знаходиться
відкрита дужка яка не відповідає взятій закритій. В іншому випадку один сивол знищуємо з стека.
Якщо по закінченні проходу по стрічці стек пустий то стрічка вірна в іношу випадку ні.
Розвязок цієї задачі є в кожній біль менш пристойній книжці з основ алгоритмізаціїї для учнів та студентів ВУЗу.
swetikccc Дата: Ср, 06.05.2009, 23:45 | Повідомлення № 11
Ветеран спілкування
Повідомлень: 3770
Нагороди: 23
Рейтинг: 336
Quote (Bandalak)
Наведіть розрахунки, як у Вас вийшло 21, у мене виходить 15.

6+10+5=21

Додано (06.05.2009, 22:45)
---------------------------------------------

Quote (Bandalak)
Мені тут не подобається слово "нескінчена". Краще сказати, що є n цеглин, 1<= n <= 50.

Тут грає роль тільки кількість типу цеглин(правда при умові що тип меньше кількості) а це й досягаеться безкінченністю


Відредаговано: swetikccc - Ср, 06.05.2009, 23:54
dpi Дата: Чт, 07.05.2009, 00:33 | Повідомлення № 12
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (alex)
На мою думку це задача на правильне розміщення дужок.

Можно и так:
просматриваем строку
если встречается открытие - заносим в стек
если встречается закрытие, снимаем со стека
если скобки одного вида, просматриваем строку дальше
иначе выход из алгоритма - скобки расставлены не правильно
если стек в конце пуст - "правильно"
иначе - нет
Перед снятием вершины стека проверять не пуст ли он!!!
swetikccc Дата: Чт, 07.05.2009, 08:47 | Повідомлення № 13
Ветеран спілкування
Повідомлень: 3770
Нагороди: 23
Рейтинг: 336
Quote (dpi)
если встречается закрытие, снимаем со стека

Если конечно соответствует вершине, иначе выход
(Давайте обьяснять и для не спецов)
alex Дата: Чт, 07.05.2009, 09:26 | Повідомлення № 14
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Quote (dpi)
третья отсортировать по размерам оснований (с учетом высоты) и сложить высоты.

Такий спосіб не дасть розвязку так як необхідно щоб виконцвалась ще одна умова

Умова :верхня цеглина може бути поставлена на нижню, якщо розміри двох сторін верхньої цеглини строго менші відповідних розмірів нижньої.

Повно перебірний варіант має оптимальність 3* N !. Де N кількість цеглин. Кожна цеглина може давати приріст в висоту або x або y або z.
формуємо масив [1..3,1..n]. Генеруємо всі можливі перестановки.
Кожну перестановку аналізуємо по принципу: Рухаємося зліва направо поки не порушиться вимога для піраміди або не закінчаться цеглини і накопичуємо значення висоти.
По закінченню проходу перевіряємо чи не більша знайдена висота за попередню. Якщо більша то запамятовуємо знайдене значення висоти.
Зрозуміло що такий розвязок не отримує повний бал.
Розвязок задачі методом динамічного програмування дивіться на сайті OLYMP.VINNICA.UA. Архів районних олімпіад з інформатики.

Відредаговано: alex - Чт, 07.05.2009, 14:17
swetikccc Дата: Чт, 07.05.2009, 12:51 | Повідомлення № 15
Ветеран спілкування
Повідомлень: 3770
Нагороди: 23
Рейтинг: 336
Quote (alex)
або не закінчаться цеглини

Як може закінчитися безкінечність?
Тут потрібно розглядати кількість типів цеглин


Відредаговано: swetikccc - Чт, 07.05.2009, 12:57
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Олімпіадні задачі. (розв’язування олімпіадних задач.)
Сторінка 1 з 211232021»
Пошук:


© Форум інформатиків України, 2007-2017.