| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 06:18 |
|
|
Problem E:
Задано числа Y та L (до 1е18).
Необхідно знайти таку найбільшу основу числення В, таку що
Y в системі В має тільки цифри 0-9 та
(запис Y в системі В) в десятковій системі є не меншим L. |
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:21 |
|
|
Минуло 25 хвилин змагання,
Вже відкрито 3 задачі ( C, E, L )
Вже 37 команд мають по однійзадачі, та 2 команди мають по 2 - це Ніжній Новгород та МГУ. |
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 06:31 |
|
|
Problem L:
Дано до 1е6 дисків.
Для кожного диску відомий розмір та новий розмір.
Необхідно відформатувати всі диски зберігши всю попередню інформацію.
Відповідь - мінімальний додатковий розмір диску потрібний для цього!
Розвязок:
Бінарний пошук,
для кожного значення спочатку розглядаємо диски для яких розмір збільшується,
а потім ті для яких зменшується. |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09 |
| Опубліковано 19-05-2016 06:36 |
|
|
Всім привіт!
В нас 6та година ранку, проте морально Львів з хлопцями! Успіху! |
  ![mylyanyk.ivan [Lviv_NU]](../themes/Brasil-Fusion/forum/yahoo.gif)
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:38 |
|
|
45 хвилин змагання були досить динамічними..
90 команд вже мають по задачі,
З них 15 команд мають по 2,
а Шанхай рішив вже 3 задачі та посів 1 сходинку.
З українських команд лиже Запоріжжя має 1 задачу (C) |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:40 |
|
|
|
Відкрито вже 6 задач ( B, C, E, G, K, L ) |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 06:42 |
|
|
Problem G:
Дано до 2000 відрізків.
Всі відрізки паралельні ОХ.
Жодні два відрізки не мають спільних точок.
Необхідно знайти таку не паралельну ОХ пряму,
для якої сума довжин заданих відрізків, що вона перетинає буде максимальною.
Обмеження часу виконання 10 секунд.
Розвязок:
А) Всі задані відрізки лежать на одній прямій
(тоді відповідь - максимальна з довжин відрізків)
В) Кожна така пряма може бути змінена так, що вона буде проходити
принаймні через два кінці заданих відрізків.
Складність O(N^3) |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 06:51 |
|
|
|
Львівська команда здає задачу С! |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:51 |
|
|
Година змагання позаду.
Відкрито поки що всі тіж 6 задач.
Понад 100 коман розв'язали задачу С,
напевно всі команди крім ЛНУ!?
За словами тренера це така тактика, сподіваємось.
3 команди мають по 4 задачі, це СПбГУ, МІТ та Шанхай.
Межа команд з 2 задачами на 35 позиції,
десятка кращих має 3 та більше.
|
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:52 |
|
|
|
Нарешті, поки я писав ЛНУ сдали задачу С здругої спроби |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 06:55 |
|
|
Українські команди посідають
26 сходинку з 2 задачами КНУ
65, з однією ЗНТУ
114 (поки що!) ЛНУ
Хлопцям треба наздоганяти...
Змінив(ла) AI, 19-05-2016 07:13 |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 07:07 |
|
|
|
74 хвилина змагання и вже 7 команд мають 4 задачі )) |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:11 |
|
|
Problem K:
Задана стрічка (до 10 000 символів) наступної структури:
-містить до 100 груп (до 100 символів ' у групі)
-між кожною групою є ненульова кількість інших символів відмінних від '
Cтрічка рівня 1: ' + X + ' (X = приймні один символ, Х не містить символів '
Cтрічка рівня К: K символів ' + X + К символів ' (X = послідовність стрічок рівня K-1 які можливо розділені довільною кількістю символів відмінних від ' включно з початком та кінцем послідовності)
Необхідно знайти максимальний рівень заданої стрічки
Розвязок: динамічне програмування
Стани:
- початок, кінець, 0-1 (неповна група), кількість у неповній групі
- почотак, кінець
Значення: бітова маска можливих рівнів для стрічки чи послідовності стрічок що визначає стан |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:11 |
|
|
|
Пінгвіни здають задачу Е! |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 07:15 |
|
|
Трохи порішали наші команди,
КНУ з 3 задачами на 24 позиції,
ЛНУ з 2 задачами на 55,
ЗНТУ з однією на 77 місці |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:26 |
|
|
|
Наші здали L! |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
AI
Користувач
Повідомлень: 127
Звідки: Donetsk National University
Зареєстрований: 15.10.10 |
| Опубліковано 19-05-2016 07:31 |
|
|
100 хвилин позаду,
відкрито 8 задач.
Але в однієї команди найбільше 6, це команда Токио.
КНУ та ЛНУ мають по 3 задачі та посідають відповідно 31 та 34 місця.
ЗНТУ поки що так і має одну задачу.
Змінив(ла) AI, 19-05-2016 07:33 |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:43 |
|
|
Problem B:
Дано орієнтований граф з N < 5000 вершинами та M < 50000 дорогами.
Перші B вершин необхідно розбити на S кластерів.
Для кожного кластера необхідно знайти суму відстаней від кожної вершини
до фіксованої вершини у графі (фіксованої для усіх кластерів) та
відстаней від фіксованої вершини до кожної вершини кластера.
Цю суму необхідно помножити на кількість вершин у кластері - 1.
Таким чином ми отримаємо значення для кластера.
Необхідно мінімізувати суму значень кластерів.
Розвязок:
Знайти відстані від та до фіксованої вершини для кожної вершини.
Впорядкувати вершини за сумою відстаней.
Динамічним програмуванням знайти відповідь до задачі.
Стан: кількість вершин, кількість вершин у кластері.
Значення: сумарне значення для кластерів. |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:48 |
|
|
|
Львівяни здають В! |
|
|
| Автор |
RE: ACM ICPC World Finals 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 19-05-2016 07:48 |
|
|
|
Також вони мають одну неуспішну спробу по G |
|
|
Birthday(s):
