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

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

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

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


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


Відредаговано: W-w-W - Чт, 07.01.2016, 23:28
Bandalak Дата: Нд, 05.02.2017, 23:07 | Повідомлення № 271
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Цитата Zelenskiy ()
Я б задачу А робив без рядків.


Трішки підлизав Вашу програму.
Знайшов одну логічну помилку. Початкове значення max у Вас було 0, а треба поставити max:=len і не перед, а після рядка перевірки першого символа, інакше неправильно працюватиме, коли весь текст міститиме єдиний символ 'a', або 'h'.
Вона видасть 0, коли треба 1.



Запускається без проблем у середовищі Free Pascal 3.0. Пробував на простих прикладах.
Шкода, що сервер з цими задачами не буде вже доступним, щоб ми її протестували!
Bandalak Дата: Нд, 05.02.2017, 23:46 | Повідомлення № 272
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
А ось спробував написати варіант програми з довгим рядком, використовуючи тип AnsiString, як пропонував нам пан gromko.


Виявляється, вхідний файл з рядком, довшим від 256 символів не можна створювати прямо в середовищі ФріПаскаль. Треба створювати такий файл у блокноті!

У цьому варіанті розв'язку можна обійтися і без наперед заданої кількості символів n.
Просто замість Readln(n) написати n:=length(smih).
Oxana_cher Дата: Пн, 06.02.2017, 09:44 | Повідомлення № 273
Місцева кадра
Повідомлень: 392
Нагороди: 2
Рейтинг: 44
А задачу В разбирать будем?
Мой ребенок на олимпиаде, сам не понимая что делает, набрал на ней 75 баллов.

Цитата Bandalak ()
Шкода, що сервер з цими задачами не буде вже доступним, щоб ми її протестували!

Кого просить, что-бы сервер опять запустили?
Пилипчук_О_П Дата: Пн, 06.02.2017, 13:32 | Повідомлення № 274
Ветеран спілкування
Повідомлень: 3870
Нагороди: 30
Рейтинг: 346
Цитата Oxana_cher ()
А задачу В разбирать будем?

Послідовність дробів, про яку йдеться в задачі, - зростає. Тому послідовно обчислюємо чисельники і знаменники, скорочуємо за потреби і перевіряємо, чи не перевищили другого дробу.
Bandalak Дата: Пн, 06.02.2017, 13:40 | Повідомлення № 275
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Цитата Пилипчук_О_П ()
перевіряємо, чи не перевищили другого дробу

Чому "Не перевищили"? По умові задачі, ніби, повинно стати рівним другому дробу.

Якщо різниця між чисельником і знаменником стала 1, аж тоді треба дивитися, чи він не перевищує другий дріб, якщо перевищує - треба зупинитися і вивести 0, все-одно дріб вже ніколи не скоротиться. А якщо стане рівним другому - вивести кількість операцій.
Прикріплення: 3116448.jpg(134Kb)
Пилипчук_О_П Дата: Пн, 06.02.2017, 14:51 | Повідомлення № 276
Ветеран спілкування
Повідомлень: 3870
Нагороди: 30
Рейтинг: 346
Цитата Bandalak ()
Якщо різниця між чисельником і знаменником стала 1, аж тоді треба дивитися, чи він не перевищує другий дріб

До цього теж потрібно перевіряти, чи не перевищили. Якщо перевищили - виводимо 0.
А коли різниця стане 1 - можна оптимізувати, замінивши перебір простим розрахунком.

Трохи збиває з толку "магічне" число 105 в умовах задач. Я не зразу зорієнтувався, що мало бути 105. :(


Відредаговано: Пилипчук_О_П - Пн, 06.02.2017, 14:52
Bandalak Дата: Пн, 06.02.2017, 15:06 | Повідомлення № 277
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Це, якщо у другому дробі різниця між чисельником і знаменником 1, інакше на початку можна і не перевіряти.
swetikccc Дата: Пн, 06.02.2017, 15:16 | Повідомлення № 278
Ветеран спілкування
Повідомлень: 3957
Нагороди: 28
Рейтинг: 370
А іншим, для зрозумілості?
Якщо перший дріб більший за інший виводимо зразу 0 (при виконанні операцій)
Ось розбір знайшов
В умові сказано що a < b. Давайте подивимось що відбувається якщо збільшується а і б. (a + 1) / (b + 1) > a / b. Це випливає з: (a + 1)b > (b + 1)a. Тобто після кожної виконаної операції значення дроба буде зростати. І воно зростатиме до тих пір, доки дріб не стане дорівнювати одиниці. Тому в результаті таких операцій даний дріб коли-небудь стане більше або буде дорівнювати шуканому дробу. Рішення задачі зводиться до того, що до дробу потрібно застсосовувати описану операцію і знаходити найбільший спільний дільник чисельника і знаменника. Цей процес продовжується до тих пір, доки перший дріб не стане більше чи дорівнювати другому. Якщо дроби стануть рівними то потрібно вивести кількість виконаних операцій, інакше програма має вивести 0.

Перша
В задачі був даний рядок з латинських букв і потрібно було знайти довжина найбільшого підрядка який складається з літер 'a' i 'h', які чергуються.
Часткове рішення:
Для кожної початкової позиції порахуємо довжину сміху. Просто йдемо по рядку і перевіряємо що зустрічаються тільки потрібні букви і вони чергуються. Це рішення працює за n^2 і набирає ~42 бали.

Повний бал набирався методом двох вказівників. Порахуємо довжину сміху з початкової позиції - нехай це якийсь відрізок [1, r]. Наступна позиція з якої є сенс дивитись це позиція r + 1. Робимо нашу позицію r + 1 - "початковою". І так далі доки r <= n.Асиптотика цього рішення O(n), яке і набирає 100 балів.


Відредаговано: swetikccc - Пн, 06.02.2017, 18:03
gromko Дата: Пн, 06.02.2017, 18:13 | Повідомлення № 279
Лінуксоїд
Повідомлень: 2671
Нагороди: 26
Рейтинг: 343
Цитата Bandalak ()
А ось спробував написати варіант програми з довгим рядком, використовуючи тип AnsiString
Відкрию "секрет" - використавши директиву компілятора {$H+} тип string буде застосовуватись як AnsiString
Пилипчук_О_П Дата: Пн, 06.02.2017, 18:20 | Повідомлення № 280
Ветеран спілкування
Повідомлень: 3870
Нагороди: 30
Рейтинг: 346
Цитата swetikccc ()
І воно зростатиме до тих пір, доки дріб не стане дорівнювати одиниці.

Тобто дуже довго :)
swetikccc Дата: Пн, 06.02.2017, 18:54 | Повідомлення № 281
Ветеран спілкування
Повідомлень: 3957
Нагороди: 28
Рейтинг: 370
Цитата Пилипчук_О_П ()
Тобто дуже довго
Цікаво якщо взяти дріб 1/2, коли він стане 1?
Bandalak Дата: Пн, 06.02.2017, 19:10 | Повідомлення № 282
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Він стане 1 при N -> до безмежності.
Bandalak Дата: Пн, 06.02.2017, 19:14 | Повідомлення № 283
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Цитата swetikccc ()
Перша
В задачі був даний рядок з латинських букв і потрібно було знайти довжина найбільшого підрядка який складається з літер 'a' i 'h', які чергуються.
Часткове рішення:
Для кожної початкової позиції порахуємо довжину сміху. Просто йдемо по рядку і перевіряємо що зустрічаються тільки потрібні букви і вони чергуються. Це рішення працює за n^2 і набирає ~42 бали.

Повний бал набирався методом двох вказівників. Порахуємо довжину сміху з початкової позиції - нехай це якийсь відрізок [1, r]. Наступна позиція з якої є сенс дивитись це позиція r + 1. Робимо нашу позицію r + 1 - "початковою". І так далі доки r <= n. Асиптотика цього рішення O(n), яке і набирає 100 балів.

Щось я не зрозумів, а те рішення що ми тут вище розглядали не набере 100 балів? Чому? По часу не пройде?
Що значить "Це рішення працює за n^2 і набирає ~42 бали."?
" Асиптотика цього рішення O(n), яке і набирає 100 балів."???

ЯК ДОБИТИСЯ, ЩОБ СЕРВЕР ЗНОВУ ВІДКРИЛИ ДЛЯ РОБОТИ НАД ПОМИЛКАМИ?
Zelenskiy Дата: Пн, 06.02.2017, 20:44 | Повідомлення № 284
Часто заходить...
Повідомлень: 37
Нагороди: 1
Рейтинг: 10
На нашому обласному вебінарі по підготовці пообіцяли запустити сервер для довиконання задач (минулого року так робили). Коли ж мій учень попросив після завершення забрати папірець з логіном і паролем (для того, щоб попрацювати з сервером після перезапуску), то на нього подивилися як на злочинця. Попри те, що час олімпіади завершився.
Bandalak Дата: Нд, 12.02.2017, 00:20 | Повідомлення № 285
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Шановні панове, у кого олімпіада відбувалася у два тури, викладіть будь-ласка завдання другого туру. Тому що у деяких областях обмежилися одним туром, але цікаво знати, що було у другому турі!
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Олімпіадні задачі. (розв’язування олімпіадних задач.)
Сторінка 19 з 21«121718192021»
Пошук:


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