Блог пользователя HolyInq

SNSS 2012 R2b
Автор HolyInq, 12 лет назад, По-русски

закончился.
Как по-нормальному переформулировать А и как аккуратно решать С(я, наверное, умею двумя тернарниками с бинпоиском, но это треш)?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

A: будем разбивать вещи на классы.

Изначально все вещи в одном классе. После первого угадывания, на которое тратится Cnk шагов, у нас уже есть два класса: вещи, которые попали в итоге в набор, и все остальные вещи. Каждое следующее угадывание также разбивает каждый из имеющихся классов на две части: в одной части оказываются вещи, которые попали в последний набор, а в другой — которые не попали. Заметим, что непустых классов в каждый момент времени, очевидно, не больше, чем вещей.

Теперь нам приходит следующий запрос. Для каждого названия вещи мы знаем, было ли оно в первом запросе, было ли во втором, ..., было ли в предыдущем. Эта информация однозначно задаёт класс вещи, а никакой другой информации у нас на этот момент нет.

Значит, мы теперь знаем, что в ответ на запрос нужно положить ci вещей класса i; мы рассматриваем те и только те i, для которых ci > 0. А всего у нас, скажем, fi вещей каждого класса i. Тогда, очевидно, количество способов выбрать набор равно Cf1c1·Cf2c2·.... Поскольку никакой информации, кроме "набор не подходит", мы в процессе их перебора не получим, это число и нужно прибавить к ответу.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

В C у меня прошло такое решение:

  • перевести координаты в декартовы,
  • построить отрезок между заданными точками,
  • поставить на нём равномерно миллион точек,
  • каждую из них спроецировать на сферу (просто поделив координаты на длину её радиус-вектора),
  • перевести координаты обратно в угловые и
  • проследить за крайними значениями.
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    на контесте не успел написать, сейчас сдал в дорешивание: просто разбиваем шарик сеткой и запускаем поиск пути.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А кто-нибудь придумал клевое точное решение?

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        У меня довольно простое "точное" решение:

        Найти угол плоскости геодезической к Oxy довольно просто — посчитаем векторное произведение векторов к точкам, посчитаем угол между результатом и плоскостью Oxy (sin alpha = abs(z) / length) — он будет отличаться от искомого угла на pi / 2. Теперь если сумма lat1 + lat2 >= 0, то это может быть верхней точкой, если меньше — то нижней. Для того, чтобы проверить, лежит ли эта точка на кратчайшем пути посмотрим на проекцию того самого произведения на плоскость Oxy. Если это точка — мы движемся по экватору и все понятно. Если нет — продолжим этот вектор до прямой. Если проекции конечных точек лежат по разную сторону — то да, надо брать, если нет — то просто выводим концы

        → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Если долгота отличается на 180, то путь проходит через полюс и ответ понятен. А иначе ответ, это широты на концах пути.

        UPD: меня тут убедили, что решение неправильное:(

        → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Интересно, что за 5-ый тест такой в E...

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

кто-нибудь кроме меня, решил D бинпоиском по ответу + поток? или там какой-то конструктив или несложная жадина?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Пытался, но получил ТЛ. Зааксептил поток, запускающийся на последовательно увеличивающемся графе.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      странно, я использовал мэп строк сетов, несколько сетов, каждый раз граф заново перестраивал, и тем не менее — зашло

      → Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

F. Помещения на судне.

Похакайте меня, пожааааалуйста...

	while (gets(a[n++]));
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; a[i][j + 1]; j++)
			ans += a[i][j] == '+' && a[i + 1][j] == '|' && a[i][j + 1] == '-';

UPD. WA5

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я примерно такую же вещь пытался пропихать. Но у меня был все время WA 5. Хотя там заходил тупейший DFS.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится 
    +--+-+-+-+-+
|  | | | | |
+-++++++++-+
| | | | |  |
+-+-+-+-+--+
    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      ааааа, я задумывался на то, что могут ли два плюса рядом стоять, но увы фантазия подвела... очевидное же...

      ans +=
	a[i][j] == '+' && 
	(a[i + 1][j] == '|' || a[i + 1][j] == '+') && 
	(a[i][j + 1] == '-' || a[i][j + 1] == '+');

      UPD. OK

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Можно было так: для каждого плюса вычислим, вершиной какого числа прямоугольников он является. Если плюс в углу — то одного, если на стороне — то двух, если внутри — то четырёх, если со всех сторон "-" и "|", и двух иначе. Теперь делим на четыре и получаем ответ.

    → Ответить