На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Результаты провереи опубликованы на сайте олимпиады. Открыта он-лайн проверка на полном наборе тестов. в 12.02.в 17-00 - обсуждение задач в чате www.vinnica.ua/netoi
Поза форумом
===ODDSUM===
Задача очевидно є узагальненням відомої задачі, де треба знайти максимальну суму, але не ставиться вимоги щодо обов’язкової непарності. Відома задача розглянута у багатьох книжках; зокрема (але не тільки) — Порублёв–Ставровский, задача 13.1 (стор. 347—351).
Дана задача (з вимогою непарності) потребує такого розширення відомої задачі: для кожної клітинки пам’ятати не просто максимальну суму, з якою можна дістатися до даної клітинки від верхнього ряду, а дві величини —максимально можливу непарну та максимально можливу суми, з якими можна дібратися до даної клітинки від верхнього ряду. Оскільки можлива ситуація, коли абсолютно всі шляхи від верхнього ряду до деяких клітинок мають лише парну або лише непарну суму, то для деяких клітинок якась одна з цих величин може бути невизначеною. Один із можливих способів боротися з цим — вважати, що неможливі суми дорівнюють «мінус нескінченності».
Поза форумом
=== ABACABA ===
Слова довжиною до 2 включно розглядаємо окремими if-ами.
Для всіх довжин починаючи з 3 формуємо масив N[2..50][‘A’..‘C’][‘A’..‘C’], де N[i][s1][s2] — кількість слів, що мають довжину $i$ й прочинаються з пари символів s1s2. При i=2 маємо N[2][‘A’][‘A’] = N[2][‘A’][‘B’] = N[2][‘A’][‘C’] = N[2][‘B’][‘A’] = N[2][‘B’][‘B’] = N[2][‘B’][‘C’] = N[2][‘C’][‘A’] = N[2][‘C’][‘B’] = N[2][‘C’][‘C’] = 1. Далі (для більших i) заповнюємо цей масив за правилом N[i][s1][s2] := N[i–1][s2][‘A’] + N[i–1][s2][‘B’] + N[i–1][s2][‘C’], АЛЕ у випадку s1=s2 пропускаємо відповідний доданок (один з трьох).
Крім того, за згаданим тривимірним масивом формуємо одновимірний N_TOT[1..50], де N_TOT[1] = 3, надалі N_TOT[i] = N[i][‘A’][‘A’] + N[i][‘A’][‘B’] + N[i][‘A’][‘C’] + N[i][‘B’][‘A’] + N[i][‘B’][‘B’] + N[i][‘B’][‘C’] + N[i][‘C’][‘A’] + N[i][‘C’][‘B’] + N[i][‘C’][‘C’] визначає загальну кількість слів відповідної довжини. Тепер, якщо вхідні дані — номер, то пройшовши по цьому масиву встановлюємо, якої довжини слово (такої, щоб N_TOT[1] + N_TOT[2] + … + N_TOT[len–1] < input_data_idx <= N_TOT[1] + N_TOT[2] + … + N_TOT[len–1] + N_TOT[len]). Аналогічно, яещо вхідні дані — слово довжини len, то встановлюємо, що до номера цього слів серед слів довжини len треба додати сумарну довжину всіх коротших слів N_TOT[1] + N_TOT[2] + … + N_TOT[len–1]. Так прийшли до того, що знаємо, яка довжина і що треба розв’язати суто всередині слів цієї довжини.
Коли шукаємо номер за словом, беремо перші дві букви цього слова й рахуємо сумарну кількість слів що починаються на словниково більш ранні пари (наприклад, слово починається з CB, то додаємо N[len][‘A’][‘A’] + N[len][‘A’][‘B’] + N[len][‘A’][‘C’] + N[len][‘B’][‘A’] + N[len][‘B’][‘B’] + N[len][‘B’][‘C’] + N[len][‘C’][‘A’]), після чого відкидаємо перші дві літери (краще робити це НЕ через delete(s,1,2), а шляхом зсуву поточної позиції). Для скороченого слова міркуємо аналогічно, але ще кілька додаткових if-ів повинні пропускати пари, які разом з раніше відкинутою утворюють 3 або 4 підряд однакові літери.
Коли шукаємо слово за номером, діємо аналогічно: якщо номер (після вищеописаного відкидання усіх слів меншої довжини) менший-рівний N[len][‘A’][‘A’], значить слово починається з ‘AA’; якщо більше, ніж N[len][‘A’][‘A’], але менше рівне, ніж N[len][‘A’][‘A’] + N[len][‘A’][‘B’], значить слово починається з ‘AB’, і так далі. Для не-першої пари букв знов-таки доводиться враховувати, які саме букви вибрані в попередніх позиціях, і пропускати пари, які разом з раніше відкинутою утворюють 3 або 4 підряд однакові літери.
Звичайно, ЧАСТИНУ балів можна набрати й просто генеруючи слова мови послідовно (через розгляд послідовних чисел у трійковій системі числення з відкиданням тих, що не задовольняють умові задачі, або рекурсивно, де факт відсутності повторень одного символа більш ніж два рази підряд перевіряється перед відповідним рекурсивним викликом), доки не дійдемо до вказаного номера / слова.
Поза форумом
=== EFRACTIONS ===
звиняйте, формули посипалися, виправлено нашвидкуруч
Я пропоную розв’язувати, спираючись на послідовні рекурсії з послідовним збільшенням дозволеної глибини. Тобто, спочатку спробувати рекурсивно знайти розкладення у один доданок, якщо не вдалося — спробувати рекурсивно знайти розкладення у два доданки, якщо не вдалося — спробувати рекурсивно знайти розкладення у три доданки, якщо не вдалося — спробувати рекурсивно знайти розкладення у чотири доданки, і т. д.
Реалізується все це через рекурсивну функцію з параметрами depth_allowed, a, b, min_znam.
• depth_allowed — дозволена глибина; рекурсія не може заглиблюватися далі, ніж на вказану кількість рівнів і завдяки цьому розбиватиме звичайний дріб на суму не більш ніж depth_allowed штук доданків вигляду 1/k.
• A, b — чисельник та знаменник дробу, який треба розкласти (на зовнішньому рівні рекурсії a та b дорівнюють вхідним даним задачі, на глибших залежать від того, які доданки вже вибрані на зовнішніх рівнях, за формулою ).
• min_znam — використовується, зокрема (але не тільки) для того, щоб на глибших рівнях рекурсії розглядалися лише доданки, знаменники яких строго більші за знаменники попередніх доданків (коли на поточному рівні обрано знаменник d, на глибшому повинні бути значення хоча б d+1). Крім того, коли треба подати (a/b) , нема сенсу розглядати в якості кандидатів у знаменники числа, менші (заокруглене догори(b/a)) .
Крім того, у значній мірі ЗАВДЯКИ depth_allowed, можна ставити і верхнє обмеження на можливі значення кандидатів у знаменники: нема сенсу розглядати значення, більші (заокруглене догори(b * depth_allowed/a)) .
Дещо несподівано виявляється, що пошук розкладень в середньому працює помітно швидше, якщо перебирати можливих кандидатів у знаменники не в порядку зростання, а у порядку спадання, від (заокруглене догори(b * depth_allowed/a)) до max(заокруглене догори(b/a) , min_znam).
Відредаговано Ilya Porublyov (2011-02-12 17:14:28)
Поза форумом
=== CRYSTAL ===
Досить очевидний приклад пошуку в ширину
Поза форумом
можна скачати свій сорс?
хочеться перевірити задачу.
Щось стрельнуло в голову і написав в ODDSUM integer а не longint
набрав 30 балів
хочу глянути скільки б пішло з longint.
Поза форумом
zasqzasq написав:
можна скачати свій сорс?
хочеться перевірити задачу.
Щось стрельнуло в голову і написав в ODDSUM integer а не longint
набрав 30 балів
хочу глянути скільки б пішло з longint.
По ідеї, ваші розв"язки повинні були у вас залишитися (на край, на машині, де ви писали). Але в будь-якому випадку ПОВНИЙ архів олімпіади (всі тести, роботи всіх учасників, результати виконання всії тестів) буде доступний для завантаження днями.
Поза форумом
ок
Поза форумом
“Затверджую”
Начальник управління освіти і науки
Вінницької обласної державної адміністрації
_____________ І. Д. Івасюк
15 лютого 2011 р.
Рішення
спільного засідання оргкомітету та журі Всеукраїнської Інтернет - олімпіади з інформатики NetOI-2010
Восьма Всеукраїнська учнівська Інтернет-олімпіада з інформатики проведена згідно з наказом МОН України № 638 від 06.11.02 “Про проведення Всеукраїнських Інтернет-олімпіад з базових дисциплін” з жовтня 2010 р. до 12 лютого 2011 р. в 3 тури. Всього в олімпаді брало участь 1012 учасників з усіх регіонів України. Четвертий, “real-time” фінальний тур, до якого було допущено 79 школярів з 16 регіонів України, що набрали прохідний бал в попередніх турах, проведено згідно з наказом МОН України «Про проведення Всеукраїнської учнівської Інтернет-олімпіади з інформатики у 2010/2011 навчальному році» №53 від 24.01.11. Олімпіада проводилася з використанням технічних можливостей вузла Інтернет фізико-математичної гімназії №17 м. Вінниці та створеної на його базі лабораторії інформаційних та комунікаційних технологій. Для проведення олімпіади застосовувалось спеціальне програмне забезпечення, що функціонує в мережі Інтернет, забезпечує організацію обміну інформацією між учасниками та журі та можливість автоматизованої перевірки робіт учасників, зокрема - самостійну перевірку в режимі on-line.
Списки учасників, умови задач та інші матеріали олімпіади доступні в мережі Інтернет на сайті олімпіади http://www.olymp.vinnica.ua, завдання олімпіади можливо перевірити самостійно в будь-який час, що виключає апеляції та є корисним з навчальною метою.
Розглянувши результати олімпіади та технічні протоколи, згенеровані системою проведення олімпіади (вони також доступні на сайті), журі та оргкомітет на своєму спільному засіданні
ВИРІШИЛИ:
1.1 Визнати переможцями олімпіади серед школярів України та нагородити дипломами 1 ступеня таких учнів:
Мостового Андрія, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Нагіна Сергія, учня 10 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Здомського Івана, учня 11 класу Чорнопотоківської ЗОШ І-ІІІ ст., с. Чорний Потік Івано-Франківської області
1.2 Визнати переможцями олімпіади серед школярів України та нагородити дипломами 2 ступеня таких учнів:
Фурка Романа, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Рубаненка Романа, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Герасиміва Віталія, учня 10 класу Роздільської загальноосвітньої школи I-III ступенів Львівської області;
Лук’янця Валентина, учня 10 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Швеця Михайла, учня 11 учня ліцею інформаційних технологій, м.Дніпропетровськ ;
Бевзу Максима, учня 11 класу Липовецької загальноосвітньої школа I-III ступенів №2, Липовець Вінницької області;
1.3 Визнати переможцями олімпіади серед школярів України та нагородити дипломами 3 ступеня таких учнів:
Оришича Сергія, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Хоцина Романа, учня 9 класу ліцею «Колеж» м. Донецьк;
Кушніренка Романа, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Придія Ріхарда, учня 10 класу Українського фізико-математичного ліцею Київського національного університету ім. Т. Шевченка м. Києв;
Бабкіна Владислава, учня 10 класу ліцею інформаційних технологій м. Дніпропетровськ;
Будіченка Владислава, учня 10 класу ліцею інформаційних технологій м. Дніпропетровськ;
Василіва Євгена, учня 11 класу Українського фізико-математичного ліцею Київського національного університету ім. Т. Шевченка м. Києв;
Мельника Романа, учня 11 класу гімназії м. Ужгород;
Лавриненка Марка, учня 11 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
2.Просити Центральний оргкомітет Всеукраїнських учнівських Інтернет - олімпіад вирішити питання участі переможців, що вибороли 1 та 2 місця (як це передбачено “Положенням про Всеукраїнські Інтернет - олімпіади з базових дисциплін”) в 4-му етапі Всеукраїнської олімпіади з інформатики поза квотою регіону, а саме:
Здомського Івана, учня 11 класу Чорнопотоківської ЗОШ І-ІІІ ст., с. Чорний Потік Івано-Франківської області;
Швеця Михайла, учня 11 учня ліцею інформаційних технологій, м.Дніпропетровськ ;
Бевзу Максима, учня 11 класу Липовецької загальноосвітньої школа I-III ступенів №2, Липовець Вінницької області;
Нагіна Сергія, учня 10 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Герасиміва Віталія, учня 10 класу Роздільської загальноосвітньої школи I-III ступенів Львівської області;
Лук’янця Валентина, учня 10 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Мостового Андрія, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Фурка Романа, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Рубаненка Романа, учня 9 класу ліцею інформаційних технологій м. Олександрія Кіровоградської області;
Голова журі, О.Д. Азаров
д.т.н., професор,
заслужений працівник освіти України,
директор ІнІТКІ ВНТУ
Заст. голови оргкомітету, О. О. Білик
к.т.н., проректор ВІПОПП
Директор ФМГ№17 м. Вінниці, В. С. Сапіга
член оргкомітету,
заслужений працівник освіти України
Системний адміністратор Ю. Я. Пасіхов
вузла PMG17, заст. голови журі,
заслужений учитель України
14.02.2011 м. Вінниця
Поза форумом