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

Маленькие лошадки
Автор valergrad, 14 лет назад, По-русски
Задача с СГУ
http://acm.sgu.ru/problem.php?contest=0&problem=225.
Суть  задачи вкратце - сколько есть способов расставить на доске n*n k не бьющих друг друга лошадей. n и k до 10. Решается суд я по всему дп по профилю.
После  нескольких часов попыток сдать эту задачу без прекалка, возник  вопрос - а существует ли такое решение вообще? Может мы совместными усилиями его придумаем? Предлагаю помериться  временем расчета на максимальном тесте .
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Навскидку для каждой строчки (столбца) у нас есть 1024 профиля. Матрица возможных переходов - 1024*1024. Переход обрабатывается за миллион операций. В итоге - 10 000 000 операций. Должно прокатить.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вы не учитываете, что коняшки бьют сразу на 2 строчки вперед.
    Т.е. если тупо влоб, то профилей 1024^2, а матрица переходов вообще 1024^3
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда я последний раз изучал сабмиты по этой задаче, ни одного не было с временем >0. Так что, по всей видимости, никто её так не сдал. Я не помню, сколько на моей машине работала моя программа, но кажется, раза в 2 больше макстеста.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На форуме вы написали что в 10 раз больше :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ))) значит и правда в 10 раз ) ну это существенная поправка ))))
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Возможно там тупо домашнее задание. Всего 100 вариантов ввода/вывода если я не ошибаюсь.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, k не до 10, а до 100 (до n*n). Тысяча вариантов.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Я просмотрел сабмиты по этой задаче - и нашел один честный, без прекалка :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да... по честному ее жесть сдавать. сейчас ее умял до 0.55 с (на моем компе сколько работает на макс тесте). TLE178 на сервере.

делаем ставки, господа - запинаю в 0.5 или нет :D
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ужал что мог. TLE183 на g++ и TLE181 vs8c++. на моей машине 2.7 ГГц работает 0.44-0.48 (от случая зависит).

    продолжаем маразм :D
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

мое решение работает 2 секунды на моём пне 2.4 гц

на тимусе секунду. на сгу тл 122


→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    о, на тимусе тоже эта задача есть?)) а можно ссылочку?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      нет, я её как сокобан заслал, чтобы время померять
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ясно)) хитро:)

        ну, я тоже как сокобан заслал - 0.125. только, думаю, это сам компилятор так круто прооптимизировал, потому что n и k там получились константы.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          круто, выложи свой код.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            http://slil.ru/28981299

            только там черт ногу сломит :D если надо будет - потом комментарии допишу
            → Ответить