Уральская региональная командная олимпиада по программированию 2012

12 лет назад, # ^ |

Я и не знал. Вставили бы в название слово "школьная".

→ Ответить

Sultan

12 лет назад, # |

Контест уже завершился, так что можно обсуждать задачи. Как решалась G?

→ Ответить

hydrastuff

12 лет назад, # ^ |

Храним остаток от деления данного числа на каждое простое не большее 47, восстановление ответа по КТО.

→ Ответить

Sultan

12 лет назад, # ^ |

Можно поподробнее про КТО?

→ Ответить

12 лет назад, # ^ |

Вам в помощь статья на е-максе и Кормен (страница 979).

→ Ответить

12 лет назад, # ^ |

Я эту КТО не знаю. Хотя прочитав задачу, открыл статью на википедии, хотя мне это никак не помогло. Там для каждого простого множителя можно линейное модулярное уравнение решить и тогда тоже получается. А как делать через китайцев?

→ Ответить

KADR

12 лет назад, # ^ |

+11

Пусть мы знаем, что искомое число дает остаток m_i от деления на простое число p_i. Тогда найти число можно так:

void merge(ll &ans, ll &mod, int rem, int nmod) {
    while (ans % nmod != rem) ans += mod;
    mod *= nmod;
}

...

ll ans = 0, mod = 1;
for (int i = 0; i < n; ++i) {
    merge(ans, mod, m[i], p[i]);
}
cout << ans << endl;

→ Ответить

12 лет назад, # ^ |

Вау. У тебя ведь выходит то же самое, что и у меня. Надо найти такой коэффициент при произведении всех предыдущих простых (чтобы для них остаток не изменился), что и на данное число будет нужный остаток.

Эта теорема говорит, что такое у нас всегда получится?:)

→ Ответить

ant.ermilov

12 лет назад, # ^ |

Эта теорема говорит, что всё однозначно по модулю произведения p_i(в общем случае, по модулю их НОК).

→ Ответить

12 лет назад, # ^ |

спасибо, круто:)

→ Ответить

12 лет назад, # ^ |

+13

Нужно было китайцам пересчитать свою армию. А народу куча. Тогда они и решили: выстроить всех в шеренгу по два, по три, по пять и т. д. И каждый раз посчитать остаток. Так и сосчитали.

→ Ответить

kb.

12 лет назад, # ^ |

+38

Можно совсем просто: поддерживаем остаток от деления на произведение всех простых до 47. Оно влезает в 64 бита. Теперь, если мы хотим узнать ответ по другому модулю, который, очевидно, будет являться делителем нашего, просто выведем наш остаток от деления на произведение, взятый по новому модулю.

→ Ответить

12 лет назад, # ^ |

Читаю и думаю: "Какой же я идиот, писал восстановление по КТО при наличии такого простого и при этом очевидного(!) решения".

P.S. Поздравляю с выигранным контестом.

→ Ответить

http://acm.timus.ru/monitor.aspx?id=125

12 лет назад, # ^ |

Есть ссылка на результаты официальных участников?

→ Ответить

ant.ermilov

12 лет назад, # ^ |

→ Ответить

aropan

12 лет назад, # |

А что в H на 23 тесте? Это там где две полоски пересечь надо.

→ Ответить

12 лет назад, # ^ |

Насчет непосредственно 23 теста не знаю, но если Вы скинете код — может быть, я пойму, где у Вас баг.

→ Ответить

Tinkturianec

12 лет назад, # ^ |

просто ранодомный тест, даже без параллельных отрезков...

→ Ответить

aropan

12 лет назад, # ^ |

А до этого были рандомные? Ведь до 23 дошло как-то...

→ Ответить

12 лет назад, # ^ |

Попробуйте устранить дробную арифметику из своего решения там, где это возможно. Мне кажется, все проблемы из-за нее.

P.S. Я в своем решении использовал дробную арифметику только при подсчете ответа, и то я его считал без пересечений прямых (ниже я про это уже писал).

→ Ответить

BekzhanKassenov

12 лет назад, # |

J решалась комбинаторикой?

→ Ответить

12 лет назад, # ^ |

Тупо перебираем все тройки, в которые входит Холден, получается чистый квадрат.

→ Ответить

NikitaPogodin

12 лет назад, # ^ |

Можно и за константу: разобрать случаи, когда m == n/3, m — n/3 == 1 и m — n/3 > 1. Для каждого случая смотрим: teddyhater ли Холден; плюс случай, когда m < n/3. Получаем 7 вариантов ответа, которые довольно легко считаются. Код: http://pastebin.com/N16dDbMr

→ Ответить

12 лет назад, # ^ |

Понятно, что можно. Вот только зачем?)

→ Ответить

NikitaPogodin

12 лет назад, # ^ |

Мне почему-то в голову пришло это решение :) Разобрать случаи тоже несложно, в общем-то, так что оно имеет право на жизнь.

→ Ответить

12 лет назад, # ^ |

Осмелюсь возразить. Посмотри на монитор: сколько времени у тебя заняло решение за константу и сколько у меня — за квадрат. Плюс с какой попытки ты это решение запихал. В контесте из 12 халяв это решает.

→ Ответить

NikitaPogodin

12 лет назад, # ^ |

Я решал контест слегка не серьезно, насчет времени — там имелись отвлекающие факторы. Попытки это да, я последний случай криво разобрал и получил Wa12, например. В целом, не буду спорить, что решение перебором придумать и написать проще.

→ Ответить

_dangerous_

12 лет назад, # |

+11

Урал, ты ли это? такой халявный контест, чем это вызвано?

→ Ответить

12 лет назад, # ^ |

Это был школьный контест.

→ Ответить

olpetOdessaONU

12 лет назад, # ^ |

+20

Обычно на УРКОПах есть над чем подумать. Вспомнить хотя бы прошлый-позапрошлый год. Сегодня я даже пожалел, что командой сели решать.

→ Ответить

_dangerous_

12 лет назад, # ^ |

-11

для каких-то неполноценных школьников. в прошлом году этот же контест был куда интереснее

→ Ответить

12 лет назад, # ^ |

У них на контесте только одна команда все решила, я бы на месте организаторов по поводу баланса не расстраивался.

→ Ответить

MrJigan1488

12 лет назад, # |

Как задачи B и I решались?

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

В B разбирал случаи, l-1 > max(m, n) — неудача, k = 1 легко, при k >= 4 ответ всегда есть (квадратики размера (l-1)x(l-1)), иначе l = 2 возможно только при n > 1 и m > 1; если же l > 2, то хватит двух букв (шахматное замощение с клеткой 1x(l-1) или (l-1)x1).

I делал динамикой по размеру госбюджета, переход за k, сложность O(nk).

→ Ответить

MrJigan1488

12 лет назад, # ^ |

Спасибо!

А можно чуть подробнее про пересчёт динамики?

→ Ответить

12 лет назад, # ^ |

Храним пары dp1[i] и dp2[i] — сколько бюджета удастся распилить соответственно первому и второму игроку. Перебираем ход первого от 1 до k, пусть j. Если i — j < 0, то первый выгадывает m миллиардов, а второй ничего. Иначе первый получает j + dp2[i — j], а второй — dp1[i — j]. Максимизируем по всем j выигрыш первого, при равенстве минимизируем выигрыш второго. Ответ — dp1[n].

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

У меня было две динамики: dp1[i] — количество денег, которое получит игрок, делающий ход первым, при том, что размен бюджета равен i, dp2[i] — количество денег, которое получит игрок, делающий ход вторым. Соответственно, мы максимизируем первую динамику и по возможности минимизируем вторую. Выбираем базу динамики как dp1[0] = dp2[0] = 0 (если в бюджете денег нет, то никто ничего не получит). Далее проходим i в порядке возрастания и перебираем j. Для фиксированного i и фиксированного j имеем: если j > i, то dp1[i] = m, dp2[i] = 0 (мы запросили больше денег, чем есть в бюджете), в противном случае — dp1[i] = dp2[i — j] + j, dp2[i] = dp1[i — j] (мы взяли j миллиардов из бюджета и передали ход оппоненту).

UPD. Опоздал :).

→ Ответить

perec1970

12 лет назад, # |

Как же решалась задача H? Может кто поделится мыслями. Спасибо.

→ Ответить

12 лет назад, # ^ |

Если отрезки параллельны, то ответ или 0, или -1. Нужно аккуратно посмотреть на проекции концов одного отрезка на прямую, содержащую другой отрезок, и наоборот. Иначе проводим через концы отрезков четыре прямые, пересекаем, считаем площадь четырёхугольника.

→ Ответить

perec1970

12 лет назад, # ^ |

А ответ 0 когда они совпадают? А -1 когда на параллельных прямых? И зачем нам смотреть на проекции? Если можно поподробнее расскажите. Спасибо.

→ Ответить

12 лет назад, # ^ |

Когда они совпадают, ответ как раз -1.

Если проекция левого конца первого отрезка попадает либо внутрь, либо в левый конец второго, то ответ -1. Если проекция правого конца первого отрезка попадает либо внутрь, либо в правый конец второго, то ответ -1. То же самое наоборот. Иначе 0.

→ Ответить