Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 27.11.2022 06:15:55 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Код: ... float x = 1e8; while (x > 0) --x; ... може дати зациклення, використовуйте double. (Це тому, що через малу точність float операція "--x" не змінює x)
Події
ПнВтСрЧтПтСбНд
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

Birthday(s):
AVATARCornell258
AVATARJackson724
AVATARVovhik

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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:16
Задача 4В-MAP-Map
Була собі Джейн....
Дано N (N<=1млн) точок на площині і потрібно сказати скільки є серед них стартових точок. Стартова - це така, що існує 4 інших точок, одна з яких лежить строго "знизу зліва", друга - "знизу справа", третя - "зверху зліва", четверта - "зверху справа" відносно даної.

Задача 4А-EWA-Evacuation
Дано орієнтований граф (максимум 1000вершин) ми можемо добратись від вершини 1 до вершини N (остання) будь якими шляхами, але щоб довжина його не перевищувала 3 кроки. І потрібно "вбити" декілька доріг, щоб ми не змогли добрати до останньої вершини за 3 кроки і звісно потрібно вибрати найменшу кількість доріг.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 25-04-2010 01:17
І знову я забуваю писати лонгінт =( через інтегер тільки 5 балів.
Ашку я навіть не пробував писати. Мав ідею, але її було дуже важко реалізовувати(навіть в думках ) )


_______47____
Змінив(ла) MoRZe, 25-04-2010 01:23
zasqzasq 556061949 Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:20
Вже є результати.
У мене цей тур просто провальний
4В - дала тільки 2 бали, все решта ВА, поки навіть не здогадуюсь чому
4А - на декількох тестах навіть пройшла, а загалом вийшло із 0 балів
Отже, мій доробок за 4 тур 2 бали
і разом маю 46.
Змінив(ла) webmaster, 25-04-2010 01:20
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 01:21
webmaster написав:
Вже є результати.
У мене цей тур просто провальний
4В - дала тільки 2 бали, все решта ВА, поки навіть не здогадуюсь чому
4А - на декількох тестах навіть пройшла, а загалом вийшло із 0 балів

Нипиши розбір:) :)
А якщо серйозно, то кинь мені код, я гляну, якщо можна. І в топкодерівському челенджі потренуюсь, і заодно гляну, чи в нас алгоритми співпали.
webmaster написав:
Отже, мій доробок за 4 тур 2 бали
і разом маю 46.

А в мене, коли разом з двох таблиць в одну зішкребуть, повинно бути 44.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 01:23
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
alt
Користувач

Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07
Опубліковано 25-04-2010 01:26
webmaster написав:
Вже є результати.
У мене цей тур просто провальний
4В - дала тільки 2 бали, все решта ВА, поки навіть не здогадуюсь чому
4А - на декількох тестах навіть пройшла, а загалом вийшло із 0 балів
Отже, мій доробок за 4 тур 2 бали
і разом маю 46.


В мене теж провал, хоча і очікуваний
4В - майже все ВА/ТЛ, 1 бал
4А - тупий розвязок набрав 3 бали

в сумі 43
alt.ua 488129151 alt (Uzhgorod NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:30
у кого тупіший

Я зробив само звичайний максфлов, тільки що глубину (дижвну шляху) обмежив до 3.
Виглядає дуже навіть правильно, але через аж таку примітивність на інтуїтивному рівні зрозуміло, що не правильний цей розв'язок, хоча на даний час я не можу навести котраргумент.

У кого там прошла задача 4В, напишіть розбір, Ви маєте повне моральне право.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 25-04-2010 01:33
А десь можна попробувати здати задачу 4В?
Хочу глянути чи з лонгінотм все пройде.


_______47____
zasqzasq 556061949 Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 01:35
Зараз буде вам розбір, спочатку челенджу код Руслана, потім завантажую тести до А щоб подивитись на розбиття по асимптотиках, а далі буде і розбір. Тільки от я її в неті найти не можу:( Напевно є десь на китайцях. На яких - треба всі перебирати, я не пам'ятаю. А ті 200 задач, які в мене там здані, передивився - її там нема, значить, може, я й не там здавав...


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:36
MoRZe написав:
А десь можна попробувати здати задачу 4В?
Хочу глянути чи з лонгінотм все пройде.

можна скачати тести:
http://konkurs.adb.pl/ua/user.phtml?op=zasoby
і можна буде спробувати здати тут:
http://main.edu.pl/user.phtml?op=zadania&c=22010&lang=en
Змінив(ла) webmaster, 25-04-2010 01:38
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:44
MoRZe написав:
І знову я забуваю писати лонгінт =( через інтегер тільки 5 балів.

А можна детальніше?
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 25-04-2010 01:47
В мене в системі integer чотирьохбайтовий, а в них , як і в інших - двохбайтовий.
Через це числа > 32768 стають відємними і в мене ВА.

Ти про це питався, чм про алгоритм?


_______47____
zasqzasq 556061949 Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 01:47
alt написав:
В мене теж провал, хоча і очікуваний
4В - майже все ВА/ТЛ, 1 бал
4А - тупий розвязок набрав 3 бали

в сумі 43

Тупий - це повний перебір? Чи потоки/жаднік? Бо тупий (най-найтупіший) здається більше 1 не набирає (тести вже скачав).

webmaster, для економії часу поки що не шукав якоїсь ідейної помилки, а просто завалив той сорс першим-ліпшим тестом. Скинув на пошту.

webmaster написав:
А можна детальніше?

Вже було в цій темі, на першій сторінці здається. В делфі обидва типи 4байтові, а в фрішці інтегер "вкорочений". Але якщо така помилка, то певно теж був повний розв'язок. Чекаєм результати провірки, а я поки що напишу розбір.


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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 01:58
Суть задачі В така: спочатку сортуєм всі точки за однією з координат. Хай буде - за іксом. Звичайним кусортом. Далі викладу найпростішу ідейно реалізацію алго, можна в 1 прохід, але це потребує попередньої обробки і трохи тупо. Тому буде в 2.
Проходимся масивом зліва направо, і на кожному кроці дивимось, чи серед всіх точок, які строго лівіше від даної, максимум ігреків більший за ігрек поточної, а мінімум - менший. Якщо ні - ставим прапорець, що вона не підходить. Якщо у вас булевий прапорець - молодці, а в мене, як завжди
flag[i]:=1;


...як і завжди, з лонгінтами для флагу:)

Потім те саме робим у "дзеркальному варіанті", проходячи масив справа наліво (тобто у зворотньому напрямі). Максимум і мінімум зберігаєм в звичайній змінній (е... в двох, але якщо ви шарите... можете впхати в одну). Якщо на одній лінії (по іксах в нашому випадку) завжди не більше 1 точки, то "всі, які строго лівіше"="всі, які в відсортованому масиві зліва".

Може виникнути проблема, коли маємо кілька точок на одній лінії (наприклад, на х=10 є 3 точки, і як нам знати, коли можна значення якоїсь давати в мін/макс, а коли ще ні, бо воно не буде вірним, адже ми далі розглядатимем точку на цій самій лінії і можем одержати неправильний результат, хибно позитивний, так би мовити). Це вирішується просто, заводим ще по "тимчасовій" змінній на мінімум і максимум, і будем там зберігати значення, а в основну перекидати тільки тоді, коли х[i]!=x[i-1] (або і+1, коли будем в іншу сторону йти), зрозуміло, що за умови, коли це треба робити, тобто коли мінімум для даних іксів менший за мінімум взагалі, аналогічно для максимуму.

Після всього цього проходимось булями (чи лонгінтами, як в мене), і рахуємо трушки/фолси/одинички/слоників - в залежності від реалізації. Маємо відповідь.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 02:04
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
alt
Користувач

Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07
Опубліковано 25-04-2010 01:59
LeBron написав:
alt написав:
В мене теж провал, хоча і очікуваний
4В - майже все ВА/ТЛ, 1 бал
4А - тупий розвязок набрав 3 бали

в сумі 43

Тупий - це повний перебір? Чи потоки/жаднік? Бо тупий (най-найтупіший) здається більше 1 не набирає (тести вже скачав).


Тупий - це подумав 10 хв, пописав 10 хв, протестив на семплі - сабміт :)
alt.ua 488129151 alt (Uzhgorod NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 25-04-2010 02:02
Я робив все, як і ти, але без прапорців.
Думав як написати всю фізику. Через це за залік - 3. =(
Вчителька побачила лишні листочки на парті.
Скачав тести,.. працюють. Значить проблема була з лонгінтом.
Вже другий раз забув через що втратив 13 балів =(


_______47____
zasqzasq 556061949 Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 02:04
я знайшов де у мене помилка у задача 4В
дуже тупа
у мене вийшло, що я відносно одної осі мав не стругу нерівність, тобто я міг перевіряти деякі точки, що лежать на цій самій прямій що і поточка "стартова"
ех жалко, все ж правильно робив, а це проста помилка
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 02:06
MoRZe написав:
Я робив все, як і ти, але без прапорців.
Думав як написати всю фізику. Через це за залік - 3. =(
Вчителька побачила лишні листочки на парті.
Скачав тести,.. працюють. Значить проблема була з лонгінтом.
Вже другий раз забув через що втратив 13 балів =(

Угу. А я через це втратив ще декілька годин, які міг витратити на підготовку до ЗНО. Як напишу балів так на 160 оцю саму фізику, то потім буде "привід для гордості":(


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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 02:10
6 26 April - 17:00 GMT+1 27 April - 24:00 GMT+1 2 2
- з оф. правил контесту, змініть хтось час в новині на сайті, бо не співпадає.

ще б на 6ий тур дали свічку. Або дві. Мені вистачить, за А не берусь, хай би хоч В були зручні...


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 02:14
webmaster написав:
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді

webmaster написав:
У кого там прошла задача 4В, напишіть розбір, Ви маєте повне моральне право.

LeBron написав:
Суть задачі В така:....

Ой я трохи під емоціями затупив, а ти мене підтримав
:)
Не потрібно була давати розбору, але вже пізно.
Змінив(ла) webmaster, 25-04-2010 02:14
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 02:17
webmaster написав:
webmaster написав:
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді

webmaster написав:
У кого там прошла задача 4В, напишіть розбір, Ви маєте повне моральне право.

LeBron написав:
Суть задачі В така:....

Ой я трохи під емоціями затупив, а ти мене підтримав
:)
Не потрібно була давати розбору, але вже пізно.

Він сильно допоможе в розв'язуванні 5 раунду?.. +я здав, ти майже здав, MoRZe майже здав... Хто ще сюди полізе??? Хто не здав, бо не придумав - тому не допоможе. А хто "трошки плуганув" - тому хай буде... для чіткого оформлення думки.
edit - точно! Я забув про Шефа!!! От хто може сюди випадково зайти! І за рахунок цієї допомоги сильно покращити своє становище...


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 02:21
LeBron LeBron Надіслати приватне повідомлення
Сторінка 5 з 11 << < 2 3 4 5 6 7 8 > >>
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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