Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 01.07.2022 01:03:38 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Коти махають своїми хвостами, коли стоять перед вибором, при цьому одне бажання блокує інше. Наприклад, якщо кіт стоїть в дверному отворі, і хоче вийти, а на вулиці йде дощ, хвіст гойдатиметься із-за внутрішнього конфлікту. Кіт хоче вийти, але не хоче промокнути. Як тільки він прийме рішення (залишитися удома, або вийти під дощ), хвіст негайно припинить розгойдуватися.
Події
ПнВтСрЧтПтСбНд
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 Контестер | Змагання | Онлайн змагання
Сторінка 8 з 11 << < 5 6 7 8 9 10 11 >
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 01:13
Ramzes2 написав:
5B - MAA - 10
5B - WYS - 9

і у WYS якась дивна бага:
wiersz 11: wczytano EOLN, a oczekiwano '000000'

Завантаж і глянь, що там таке і чого виводить пустий рядок. Тести порівняно малі (6мб).


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 01:13
Ramzes2 написав:
5B - MAA - 10
5B - WYS - 9

і у WYS якась дивна бага:
wiersz 11: wczytano EOLN, a oczekiwano '000000'

нічого не вивела твоя прога мабуть

спробуй тест
1
0 6 0000000

я думаю там таке, бо більше немає тесту, щоб такий результат потрібно було вивести
Змінив(ла) webmaster, 27-04-2010 01:15
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ramzes2
Користувач

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 27-04-2010 01:20
та я вже поняв свою багу, тупа, нічого низькорівневими оптимізаціями страдати...
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 01:23
5B - WYS

Динаміка. Стан: кількість ще можливих перетворень (нехай Х) і найкращий результат, при виконанні рівно N-X перетворень.
тобто вже тільки на цей момент маємо складність K*N.

Далі потрібно як із даного стано вибрати всі найкращі переходи у наступні можливі стани. Варіантів як це зробити є повна купа, але потрібно якнайшвидший.
Я зробив так. Спочатку зробив прекалк, що по якому я знаю, що для заданої маски (встановлений біт на І-ій позиції означає, що у нас є хоча б одна чифра І) і кількості переходів ми кажемо яку букву на яку потрібно замінити, щоб був найкращий результат.
Далі виходить, що для даного стану ми перебираємо всі можливі переходи (їх доречі тільки 6) і звіряємо чи ми отримали кращий результат ніж вже був записаний у цій позиції.
Отже, загальна складність становить
K*N*6*10 = 50*200000*6*10=600000000 = 600млн ,
що не так вже і добре, ну ще трохи оптимізацій, які можливо скоротили час у два разі, ще далі трошки знущання над кодом, щоб його ще пришвидшити, врезультаті
1.17s/2.00s
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 01:24
5A-TER
Зробив просто мінімакс, без будь-яких оптимізацій, врезультаті 8 тестів пройшов, але жодної групи не пройшов.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 27-04-2010 01:26
В мене 0 (0_о).
Всюди РЕ.
process exited due to signal 8 Floating point exception (SIGFPE)
Що це може означати?

Це може бути через те, що я стрінгом зчитував?


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 01:40
MoRZe написав:
Floating point exception (SIGFPE)

та ж пише, що проблема із дійсним числом, деталі можна почитати тут:
http://ru.wikipedia.org/wiki/SIGFPE
Змінив(ла) webmaster, 27-04-2010 01:40
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
MoRZe
Користувач

Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09
Опубліковано 27-04-2010 01:42
Я бачив, що дійсне число, але я їх не використовую.
Хіба шо стрічка в стрінг не помістилася...


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 01:54
webmaster написав:
MoRZe написав:
Floating point exception (SIGFPE)

та ж пише, що проблема із дійсним числом, деталі можна почитати тут:
http://ru.wikipedia.org/wiki/SIGFPE

Як пише на вікі, то SIGFPE - це ціла група, до якої входять і оперції із цілими числами
FPE_INTDIV Целочисленное деление на нуль
...

тобто це всі арифметичні операції будуть при помилці давати такий сигнал
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 02:18
webmaster написав:
Питання по задачі 6B - BAJ - Byton tree
такий тест можливий?
3
0 1 1
0 2 3
0 4 5


і яка відповідь має бути на такий тест?
3
1
0 10 10
1
0 10 10
2
1
0 1 1
1
0 2 2

ідея цього тесту у тому, що маємо три гіляки, на одній маємо дві такі що можемо окремо зрізати десь на потчаку і залишаться дві, які можна зрізати пізніше але разом.
Хочу пересвідчитись чи правильно я зрозумів умову.
Дякую.


і ще трошки змінений тест
3
1
0 10 10
1
0 10 10
2
1
0 10 10
1
0 2 2



І про флуд:
ця гілка форуму стала найбільшою B)
Змінив(ла) webmaster, 27-04-2010 02:21
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 27-04-2010 02:53
webmaster написав:
Питання по задачі 6B - BAJ - Byton tree
такий тест можливий?
3
0 1 1
0 2 3
0 4 5



3

і яка відповідь має бути на такий тест?
3
1
0 10 10
1
0 10 10
2
1
0 1 1
1
0 2 2



3

і ще трошки змінений тест
3
1
0 10 10
1
0 10 10
2
1
0 10 10
1
0 2 2



2

Ktoś potwierdzi? :D


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

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

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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 14:02
Задач
6B - FIR
у нашій системі має номер
2002
поки декілька ручних тестів і один із форуму, але він примітивний
може хтось зробить декілька гарних тестів?
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 15:11
webmaster написав:
Задач
6B - FIR
у нашій системі має номер
2002
поки декілька ручних тестів і один із форуму, але він примітивний
може хтось зробить декілька гарних тестів?

додав генеровані мною тести
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 15:30
webmaster написав:
Задач
6B - FIR
у нашій системі має номер
2002
поки декілька ручних тестів і один із форуму, але він примітивний
може хтось зробить декілька гарних тестів?

Хи:) Дай мені сорс розв'язку, я нагенерю. Бо мені навіть писати її лінь... Я щось не бачу там розв'язку без спецструктур... От друга В - проста... І свічена, я її навіть колись тому й писав, що проста.

P.S. А не така і проста. Як завжди, облом, бо колись я її з одним додатковим обмеженням писав. А тут цього обмеження нема. Так що певно я кину це все і піду відпочивати, тиждень я поки що не втягую навіть "з чаєм, канапками й ногами на дивані". Бо я думав, що в домашніх умовах аж настільки простіше, ніж на очних змаганнях.



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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 17:07
І знову питання по задачі 5B - BAJ - Byton tree
Тест:
2
2
0 1 1
0 2 2
2
0 1 1
0 2 2

Відповідь наскільки розумію 3.

Але якщо у нас є ще одна гілка:
2
0 2 2
2
2
0 1 1
0 2 2
2
0 1 1
0 2 2

то тут мабуть так само відповідь 3, спочатку два разі зрізати гілки із часом 1, а потім ціле дерево.

І трохи інакший тест:
2
0 1 1
2
2
0 1 1
0 2 2
2
0 1 1
0 2 2

то тут спочатку потрібно всі одиничні зрізати, що буде 3 кроки, а потім одним махов всі двійки, тобто разом 4.

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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 17:49
webmaster написав:
І знову питання по задачі 5B - BAJ - Byton tree
Тест:...
хтось підтвердить чи я правильно думаю?

Згідно з моїм розумінням умови задачі - саме так.


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

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 27-04-2010 18:52
LeBron написав:
webmaster написав:
І знову питання по задачі 5B - BAJ - Byton tree
Тест:...
хтось підтвердить чи я правильно думаю?

Згідно з моїм розумінням умови задачі - саме так.


Potwierdzam B)


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

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 27-04-2010 23:05
шось якесь затишшя, а залишилось лише дві години...
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 23:16
Ramzes2 написав:
шось якесь затишшя, а залишилось лише дві години...

Я на контест забив, а більше флудити нікому, всі солідні дорослі дядьки. Зараз ще напишу собі щось на 1 бал і йду спати... Той бал дасть мені (якщо він ще буде) шанс десь так 1-1.5% (хоча може більше, не знаю, скільки людей здаватимуть щось в останньому турі) перевершити махінацію з курсами обміну, яка вдалась Брюсові.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Сторінка 8 з 11 << < 5 6 7 8 9 10 11 >
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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