Автор |
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мб).
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
Автор |
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 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
Ramzes2
Користувач
Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07 |
Опубліковано 27-04-2010 01:20 |
|
|
та я вже поняв свою багу, тупа, нічого низькорівневими оптимізаціями страдати...
|
|
Автор |
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 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 27-04-2010 01:24 |
|
|
5A-TER
Зробив просто мінімакс, без будь-яких оптимізацій, врезультаті 8 тестів пройшов, але жодної групи не пройшов. |
|
Автор |
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 |
|
Автор |
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 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
MoRZe
Користувач
Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09 |
Опубліковано 27-04-2010 01:42 |
|
|
Я бачив, що дійсне число, але я їх не використовую.
Хіба шо стрічка в стрінг не помістилася...
_______47____ |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 27-04-2010 01:54 |
|
|
Як пише на вікі, то SIGFPE - це ціла група, до якої входять і оперції із цілими числами
FPE_INTDIV Целочисленное деление на нуль
...
тобто це всі арифметичні операції будуть при помилці давати такий сигнал |
|
Автор |
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
І про флуд:
ця гілка форуму стала найбільшою
Змінив(ла) webmaster, 27-04-2010 02:21 |
|
Автор |
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?
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 27-04-2010 13:38 |
|
|
вже є результати 5 туру
жодного українця із максимум балів не лишилось
і поляки молодці попадали добряче, хоча їм там стільки, так як китайців на ТС |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 27-04-2010 14:02 |
|
|
Задач
6B - FIR
у нашій системі має номер
2002
поки декілька ручних тестів і один із форуму, але він примітивний
може хтось зробить декілька гарних тестів? |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 27-04-2010 15:11 |
|
|
webmaster написав:
Задач
6B - FIR
у нашій системі має номер
2002
поки декілька ручних тестів і один із форуму, але він примітивний
може хтось зробить декілька гарних тестів?
додав генеровані мною тести |
|
Автор |
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 |
|
Автор |
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.
хтось підтвердить чи я правильно думаю? |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
Опубліковано 27-04-2010 17:49 |
|
|
webmaster написав:
І знову питання по задачі 5B - BAJ - Byton tree
Тест:...
хтось підтвердить чи я правильно думаю?
Згідно з моїм розумінням умови задачі - саме так.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 27-04-2010 18:52 |
|
|
LeBron написав:
webmaster написав:
І знову питання по задачі 5B - BAJ - Byton tree
Тест:...
хтось підтвердить чи я правильно думаю?
Згідно з моїм розумінням умови задачі - саме так.
Potwierdzam
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
Ramzes2
Користувач
Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07 |
Опубліковано 27-04-2010 23:05 |
|
|
шось якесь затишшя, а залишилось лише дві години... |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
Опубліковано 27-04-2010 23:16 |
|
|
Ramzes2 написав:
шось якесь затишшя, а залишилось лише дві години...
Я на контест забив, а більше флудити нікому, всі солідні дорослі дядьки. Зараз ще напишу собі щось на 1 бал і йду спати... Той бал дасть мені (якщо він ще буде) шанс десь так 1-1.5% (хоча може більше, не знаю, скільки людей здаватимуть щось в останньому турі) перевершити махінацію з курсами обміну, яка вдалась Брюсові.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|