| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 12:15 |
|
|
Поточна ситуація:
КНУ - 7
ХНУ - 7
КНУ - 6
...
ЛНУ - 4 |
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 12:16 |
|
|
|
Команди ЛНУ мають 4, 3 та 3 задачі відповідно. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 12:21 |
|
|
|
7in4es здають 5 задачу та мають 474 хвилини штрафного часу. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 12:47 |
|
|
H: Дана послідовність чисел a1, a2, ..., an (n <= 1000, ai < 2^63). Необхідно визначити найменше таке X, що для кожного аі існує такий інтервал цілих чисел [y, y + ai - 1] сума чисел якого рівна X. Відомо, що якщо відповідь існує, то вона є меншою ніж 2^63.
Нехай для деякого числа а його інтервал починається з числа b, тоді
2*X = (a + b)*(a + b - 1) - b(b - 1) = a*a + a*(b + b - 1).
Звідси видно, що 2*Х ділиться на всі аі:
2*Х = alpha*lcm(2, a1, a2, .,., an);
Далі
ai + bi + bi - 1 = alpha*(lcm/ai);
2*bi = alpha*(lcm/ai) - ai + 1;
Оскільки bi > 0, то з останньої рівності можна зробити висновок про нижнє обмеження на alpha та його парність чи неіснування.
Змінив(ла) Shef, 13-10-2012 13:05 |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 12:48 |
|
|
|
Доробки львівських команд станом на 2:47 - 5, 4, 4. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 13:01 |
|
|
|
7in4es здають 6 задачу та виходять на 7 місце. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 13:09 |
|
|
|
Almost_The_Elephants здають 5 та 6 задачі та виходять на 10 місце! |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 13:26 |
|
|
|
Команда з Бухаресту здає 8 задачу та виходить на перше місце! |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 13:32 |
|
|
J; Є набір (до 1000) фарб та до 50,000 правил перетворення двох фарб у третю. Вам даний набір вихідних фарб. Для кожного запиту потрібно сказати мінімальну кількість перетворень необхідну щоб отримати заданий колір.
З умови не зрозуміло, що мається на увазі під перетворенням кольорів. Тобто чи після виконання перетворення ми отримуємо необмежену кількість нової фарби чи тільки кількість, яку ми можемо використати тільки для одного іншого перетворення.
У першому випадку видається, що для задачі не існує поліноміального розв'язку. Інакше ми можемо використати алгоритм Дейксри. Судячи з невдалих спроб учасників друге припущення є невірним. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 13:33 |
|
|
|
Almost_The_Elephants здають задачу А та мають доробок у 7 задач. Ще одна задача буде хорошою заявкою на вихід до фіналу. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 14:08 |
|
|
|
За годину до кінця змагань дві команди мають по 8 задач. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 14:25 |
|
|
|
Три команди мають по 8 задач. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 14:36 |
|
|
За пів години до завершення змагань:
9. Almost_The_Elephants - 7
11. NULP_Prime - 7
13. 7in4es - 6
27. Tuck_Yeah! - 5
68. Liberior - 1 |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 14:36 |
|
|
|
Монітор заморожено за 30 хвилин до кінця змагань. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 14:47 |
|
|
Задача F: На інтервалі [1, n] (n < 42^42) необхідно знайти число з найбільшою кількістю дільників. Причому X не повинно ділитися на деяке Р (Р < 1,000,000,007).
Розглянемо деяке Х = p1^a1 * p2^a2 * ...
Кількість дільників F(X) = (a1 + 1)*(a2 + 1)*...
Далі
ln(X) = a1*ln(p1) + a2*ln(p2) + ...
ln(F(X)) = ln(a1 + 1) + ln(a2 + 2) + ...
Оскільки добуток перших 42 простих чисел більший ніж 42^42, то є сенс розглядати тільки перші 42 простих числа. Також не складно бачити, що a1 >= a2 >= ...
Якщо ми збільшимо на одиницю деяке ai, то ln(X) збільшиться на ln(pi), а ln(F(X)) збільшиться на ln(ai + 1) - ln(ai). Можна розглянути відносний приріс [ ln(ai + 1) - ln(ai) ]/ln(pi) та щоразу збільшувати степінь для того простого числа, яке має найбільший поточний такий приріст. Проте це не гарантує оптимальності отриманого розв'язку через неочевидне закінчення подібної процедури. Також принаймні для одного простого дільника вхідного параметра Р степінь його входження в Р має бути більшим ніж степінь входження в результат.
Поки питання існування точного розв'язку для задачі є під питанням. |
|
|
| Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 13-10-2012 15:32 |
|
|
За попередніми результатами чотири команди розв'язали по 8 задач:
1. КНУ
2. КНУ
3. ХНУ
4. Команда з Бухаресту
|
|
|
Birthday(s):
