Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 01.07.2022 01:18:01 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
За останніх 4000 років не була одомашнена жодна нова тварина.
Події
ПнВтСрЧтПтСбНд
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):
AVATARna3ar
AVATARAndrew_Makar
AVATARSnyder133
AVATARjar4uk
AVATARpolina_p
AVATARgrandmaster
AVATARSvitlana
AVATARlas777vegas
AVATARsv
AVATARBoduk02

Перегляд теми
ACM Контестер | Змагання | Онлайн змагання
Сторінка 6 з 11 << < 3 4 5 6 7 8 9 > >>
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 02:40
як і казав, косметичні правки і задача 4В готова і проходить всі тести

Ну тоді вже я і розкажу свій спосіб розвязання цієї задачі, за один прохід
Сортуємо, хто б сумнівався :) , за якоюсь координатою, нехай Ох.
На початку маємо два набори точок, ті що зліва і ті що справа, відповідно їх перед тим потрібно правильно ініціалізувати. Над цими наборами можемо виконувати такі операції: додати нову точку, видалити існуючу точку, взнати мінімум по Оу і взнати максимум.
Ми будемо пробігатись тільки по різним Хксам, тобто обробляти порціями.
Для певної порції, що має координати Хі, працюємо так. Спочатку всі точки із цієї порції викидаємо із масива що справа (доречі, це я якраз забув зробити), далі пробігаємось по всім точкам і дивимось чи може бути дана точка стартовою, всю потрібну інформацію ми можемо отримати із двох наборів. Потім докидуємо до лівого набору дану порцію.
Ось це посуті і весь алгоритм.

Тепер тільки вся складність яку б то таку структуру організувати, щоб легко можна було дадавати елементи, видаляти і знаходити мін та макс.
Позну із set<pair<int,int> >, тільки тут перший аргумент буде координата Оу, а другий Ох. Додавати легко і видаляти також. Вся красота сета у тому, що він завжди є посортований, тому якщо ми беремо перший елемент, то він є мінімальним, а якщо останній, то він максимальний. Тому всі потрібні операції виконуються зі складністю O(log(N)).
Але як я говорив раніше, цей спосіб трошки на пару мегабайть, не вклавсі у память.

Інший спосіб це мати посортований масив координат Yків, і знати для кожної точки, де його відповідна координата Yк у даному масиві. Коли видаляємо, то ми просто помічаємо, що ця позиція не використовується. Далі коли нам потрібно знайти мінімальний Yк, то ми рухаємось поки не знайдемо, координату, яка поки використовується. Так ми тільки один раз пробіжимось по даному масиві.
Ця штука порівняно до самого алгоритму виглядає занадто складною, але користь її у тому, що зручний алгоритм не довелось змінювати.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 03:06
Hу в мене як згадувалося вже, одне сортування для масиву і чотири цикли по різних напрямках.
Я більше часу сидів, щоб сортування нормальне написати(переписати) і пришвидшити ввід. В результаті сортування вийшло набагато швидше за стандартне, тому задачка пройшла із запасом.
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 10:33
Остап нагадав дуже гарний спосіб - дивитись на форум, на Польський форум (http://www.konkurs.adb.pl/user.phtml?op=cforum). Там вони (учасники) тести викладають.
Після такого провалу, тепер я точно буду звірятись, але то не означає, що у них у всіх правильні відповіді.
Змінив(ла) webmaster, 25-04-2010 11:00
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 11:04
LeBron написав:
з оф. правил контесту, змініть хтось час в новині на сайті, бо не співпадає.

виправив, дякую
6-ий тур починається
26 квітня - 17:00
по середньоєвропейському часі
Змінив(ла) webmaster, 25-04-2010 11:05
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 12:40
Ага, я вже на гриби звірявся - все сходилося, тільки чомусь на системних не зійшлося:)
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 12:54
DixonD написав:
Ага, я вже на гриби звірявся - все сходилося, тільки чомусь на системних не зійшлося:)

Вже хтось з поляків на форумі питався, як то так - в нього все з форуму пройшло, а на системці 2/10...


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 13:09
Прикол, в тому, що в мене деякі зі системних на компі сходяться, які в них були фейл. Я думаю, то шось з виведенням і різними компіляторами...
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 13:11
Здаю "козла" - вибиває на семплі "WA:Read 4.0982041311, expected 0.0000000000". :o
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 13:55
оце так я і зробив!!!!!
взяв тести до задачі МАА із форуму і створив задачу у нас на сайті під номером 2000

щоб спробувати свій розвязок достатньо відправити його на задачу із номером 2000, помер потрібно вписати у поле "Задача"


звісно тести можуть бути не правильні і на даний час там тільки малі тести, якщо хтось хоче додати ще тести, то відправте мені тест на brus07[at]gmail[dot]com
Змінив(ла) DixonD, 25-04-2010 16:42
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 14:57
та вся детективна історія із нелегальним перетином і подальною департацією Леброна на Україну наштовхнула на одну думку:
кожну задачу можна сабмітити 20 разів максимум, а якщо ще нелегально у Польщі посабмітити, то виходить 40 разом
контрабанда
:)

Звісно це все проти правиль змагання!
Змінив(ла) webmaster, 25-04-2010 15:00
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 15:13
Ні, максимум можна посабмітити 40*k раз, де k-кількість створених ботів:D
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 16:14
webmaster написав:
та вся детективна історія із нелегальним перетином і подальною департацією Леброна на Україну наштовхнула на одну думку:
кожну задачу можна сабмітити 20 разів максимум, а якщо ще нелегально у Польщі посабмітити, то виходить 40 разом
контрабанда
:)

Звісно це все проти правиль змагання!

Мене ще не вивезли.

webmaster написав:
оце так я і зробив!!!!!
взяв тести до задачі МАА із форуму і створив задачу у нас на сайті під номером 2000

щоб спробувати свій розвязок достатньо відправити його на задачу із номером 2000, помер потрібно вписати у поле "Задача"

Це для лінивих, які тести з форуму вручну провірити не можуть. Я взагалі розслабився, здавати ж можна до завтрашньої ночі:) зараз той циферблад тестую, чи коректно працює, і чи я всі константи правильно вбив, а за карту другу ще й не берусь дуже. За А взагалі не берусь ніяк.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 17:50
З'явились результати за 4 раунд
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 25-04-2010 18:13
Вітаю з футболкою!:)
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 19:28
Я теж! Цікаво, чи за місце в 256 потім ще одну дадуть, чи ні (я того в правилах не вичитав).


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 19:54
Як вони миттєво реагують! Прийшла відповідь на моє
Hello. I have a problem with participating in this competition.

на пошту,
We will do it before publishing the final ranking. Stay tuned. :)

Best wishes,
Szymon Acedański



Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 25-04-2010 21:41
LeBron написав:
Я теж! Цікаво, чи за місце в 256 потім ще одну дадуть, чи ні (я того в правилах не вичитав).


Минулого року я дістав дві футболки.


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 21:52
DixonD написав:
Вітаю з футболкою!:)

класно, 2 нещасних бали, що я набрав за 4 тур, конвертнулись у Футболку, гарний курс у Польщі.
Ура!!!!
Змінив(ла) webmaster, 25-04-2010 21:52
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 26-04-2010 00:00
Додав задачу 2001
це 5B - WYS

П.С. після завершення змагання, ці задачу будуть видалені, оскільки ми не маємо права публікувати задачі і не претендуємо на авторство, це просто використавуємо даний сервіс як тестувальку систему
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 26-04-2010 00:59
Цитата з форуму:
Ja nie umiem albo czytać, albo liczyć: ile koszulek zostało wylosowanych po
każdej rundzie, a ile być powinno?

Czy organizatorzy indeksują tablice tak jak używane przez nas języki
programowania, od zera? ;-)

:D
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Сторінка 6 з 11 << < 3 4 5 6 7 8 9 > >>
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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