Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 18.08.2022 22:32:49 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Два, здавалось би, діаметрально протилежні свята, - Хеловін та Католицьке Різдво, дивним чином пов'язані. Кожен, хто хоч трішки знайомий з системами числення, знає, що 31 oct=25 dec.
Події
ПнВтСрЧтПтСбНд
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31

Birthday(s):
AVATARM@rk_o_LNU
AVATARIhor_Borachok

Перегляд теми
ACM Контестер | Змагання | ACM SouthEastern European Region
Сторінка 1 з 2 1 2 >
Автор SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 09:16
Цього року вже вдруге півфінал світу проходить паралельно на двох сайтах - Вінницькому та Бухарестському. У змаганнях приймають участь аж 5 львівських команд.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 09:26
Офіційний сайт змагань http://acm.ro/
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:19
Поточні результати https://olimp.vntu.edu.ua/standings
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:28
Найпростішою видається задача С, яку вже розв'язали 26 команд.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:34
У задачі С дано стрічку з числами від 1 до 2^K (K = 21) та необхідно виконати 21 згортань, в результаті чого числа будуть розташовані одне поверх іншого. Як результат потрібно вивести верхніх 1024 числа.

Власне через невелику кількість чисел, що необхідно вивести, задача є досить простою. Ми можемо працювати з тією частиною стрічки, яка буде зверху, якщо проаналізувати операції, починаючи з останньої.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:36
Через 35 хвилин змагань 4 команди розв'язали по 4 задачі. Львів'яни поки мають тільки по одній.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:42
Задача І: Дано дерево (до 50000 вершин) зі зваженими ребрами. Для кожної вершини необхідно знайти найбільшу відстань до деякої іншої вершини.

Задачу можна розв'язати знайшовши найдовшу та другу найдовшу відстань від вершини до листка (відстань вниз) та рекурсивно обрахувавши відповіді для кожної вершини (знаючи найдовшу відстань через батька - відстань вверх).
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:42
Дві команди КНУ мають по 3 задачі. Досить хороший темп на початку змагань.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 10:55
7in4es здають другу задачу та поки займають 10 місце в загальному заліку.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:00
У попередньому повідомленні "задача С" потрібно читати як "задача Е", яка не є найпростішою, тим не менше не видається дуже складною.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:01
За годину на верхівці турнірної таблиці команда КНУ з 4 задачами.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:09
Задача G: Є n (до 10000) послідовних моментів часу. В кожен момент міфічний герой задача Джо може купити довільну кількість ензиму, з якого він готує ліки. Термін придатності ензиму h (< 10000) моментів. Також для кожного моменту відома ціна одиниці ензиму. У кожен момент Джо має прийняти одиницю ензиму для якого ще не вийшов термін придатності.

Задачу можна розв'язати аналізуючи ціни ензиму починаючи від найдешевшої. Тоді для всіх ще вільних моментів де цей ензим ще буде придатним до вживання ми купуємо даний ензим. Технічна реалізація може буде здійснена на основі системи множин, що не перетинаються.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:13
Задача С: Необхідно знайти кількість простих чисел на інтервалі [n, m] (n < m < 10,000,000). Розв'язується звичайнісіньким решетом Ератосфена. Найпростіша задача змагань.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:14
Лідери змагань мають 5 вирішених задач.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:17
Команди ЛНУ;

7in4es - 3 problems, 8 place
Almost_The_Elephants - 1 problem
Tuck_Yeah! - 1 problem

Команди політехніки:

NULP_Prime - 1 problem
Liberior - 0 problems
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:34
B: Є послідовність 2*n (n <= 100,000) чисел. Якщо два числа стоять поруч, вони зникають, а послідовність природні чином звужується. Вам дозволяється міняти місцями сусідні числа. Необхідно визначити мінімальну кількість операцій необхідну для знищення усієї послідовності.

Очевидно, якщо одне з чисел Х стоїть між числами Y, а інше є назовні інтервалу (тобто ми маємо щось на кшталт ...Y...X...Y...X...), то ми маємо витратити одну операцію для того щоб поміняти X та Y місцями. Отже нам потрібно порахувати кількість таких пар. Очевидно, що знайдена кількість буде достатньою та оптимальною.

Зробити вищесказане можна наступним чином. Для кожного числа (скажімо X) потрібно порахувати кількість таких Y, що тільки один Y розміщений між двома X. За допомогою двох дерев відрізків ми можемо легко обчислити суму за час O(n*log(n)).
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:43
Перші три місця поки займають команди КНУ, зробивши 6, 5 та 5 задач відповідно.
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:57
А: Маємо граф з n (n <= 10000) вершинами та послідовність ступенів (кількість ребер інцидентних до кожної з них). Кожен елемент послідовності не перевищує 1000. Потрібно побудувати довільний граф, що задовольняє таким умовам, або встановити, що такого не існує.

Алгоритм Hakimi та теореми угорця Erdos стануть в пригоді. Оберемо вершину з найбільшим ступенем інцидентності та ставимо ребра до наступних з найбільшим ступенем вершин. Якщо подібна побудова завершиться успішно, то ми отримаємо результат, інакше відповіді не існує.

Орієнтовна кількість необхідних обчислень n*log(n) + 1000*n;
Змінив(ла) Shef, 13-10-2012 14:28
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 11:59
Дві години змагань позаду.

7in4es займають 10 місце, маючи 4 задачі у своєму доробку (B, C, G, I).
Надіслати приватне повідомлення
Автор RE: SEERC 2012
Shef
Головний Адміністратор

Повідомлень: 291
Зареєстрований: 20.04.07
Опубліковано 13-10-2012 12:14
D: Дана таблиця маршрутизації мережевого обладнання та набір запитів. Кожен запис у таблиці - це маска та довжина префікса. Для кожного запиту потрібно визначити запис з найдовшим префіксом, що співпадає. Досить оригінальним є відсутність обмежень, хоча в умові сказано "a few milion packets".

Розв'язати задачу можна побудувавши дерево на основі таблиці маршрутизації та обирати найглибшу відповідну вершину для кожного запиту. Складність є лінійно залежною від кількості записів у таблиці та кількості запитів.
Надіслати приватне повідомлення
Сторінка 1 з 2 1 2 >
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 1
На сайті немає зареєстрованних користувачів

Користувачів: 4,739
новачок: Grem
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
22,683,325 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100