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

Автор agul, 13 лет назад, По-русски
Сегодня прошел полуфинал ВКОШП (Сибирская группа).

Подскажите, как нужно было решать задачу B (условие в ней, ИМХО, уродское было).

Могу объяснить остальные задачи, если нужно.
  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
На правах троллинга.

Как человек, в прошлом увлекавшийся астрономией, могу сказать, что я хочу немедленно развидеть условие задачи B по следующим причинам:

1) Оригинальный подход к понятию звёздной величины
2) Радиусы звёзд в один парсек
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    3) Плоский мир.
    4) Закрытие звезды приводит не к сложению яркостей, будет видна первая звезда с собственной яркостью.
    5) Частичное накрывание звезд приведет к очень сложной модели, отличной от среднего арифметического (будет рассеивание на границе).
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится
       Надеюсь сообщество простит за маленький опус - я просто пофантазировал, в каком состоянии автор мог писать условие этой задачи.
       Что получилось - оценивайте сами.
    ...

    …Как-то доцент Вася Пупкин пошёл в тайгу за грибами, захватив с собой фоторужье – если повезёт, то устрою лосиную фотоохоту, - подумал он.

    … В сумрачном лесу то и дело раздавались громкие зазывающие крики лося-самца, ему иногда вторили приближающиеся к нему с разных сторон лосихи. Временами их крики перекрывались и если они звучали с одной стороны, то усиливались.

    - Эх, жаль я с собой радиотелескоп не захватил… Вот записал бы эту песню любви - классная задача получилась бы для юных программистов, - подумал Вася и в этот момент неосторожно наступил на прошлогоднюю сухую ветку, разломавшуюся со звуком, не уступавшим по громкости громким лосиным призывам. Чуть не выразившись совсем другими словами, Вася понял, что пора ретироваться, иначе лось примет его за своего и сделал шаг назад в направлении планировавшегося отступления.  Но как и следовало ожидать, опять наступил на ту же самую злополучную ветку…

    Сделать ещё один шаг Вася уже не успел, так как вдруг взлетел в небо и из глаз посыпалась куча маленьких звёзд – это хозяин тайги сочным ударом рогов довольно своеобразно выразил своё приветствие незваному гостю.

    Пришёл в себя Вася минут через 5-10 от неожиданного компресса – это всё тот же лось тщательно его облизывал. Увидев, что у двуногого раскрылись глаза, лось вдруг человеческим голосом произнес: Надеюсь ты сам знаешь, что дальше делать нужно?. Повернувшись, чтобы уходить, лось, вдруг словно что-то вспомнив, добавил: Да, ну и сам понимаешь куда попадёшь, если кому-то расскажешь о нашей встрече после чего гордо удалился.

    Через месяц Васе пришлось сочинять задачку для турнира по программированию и он  решил написать задачку о лосях, но, вспомнив последние слова хозяина тайги, тут же уверенной рукой на листке вывел название задачи:

    Звёздное небо

     

     

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Внимание, вопрос. Какого цвета мухоморы крайне не рекомендовали употреблять в пищу Васе Пупкину, автору задачи про звезды? Время.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а почему во многих задачах не указаны ограничения?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Особенно доставляет J. Если N = 10101010000, K = N + 1 то ответ умещается в 32-разрядной целое число.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Такие задачи.
    Мы задавали вопрос: "Какое ограничение на N в задаче B?"
    Нам ответили: "Очень маленькое". И сразу стало абсолютно все понятно. Мы сидели, тупили, а они прямо по полочкам все разложили.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да, хотелось бы про задачу Б послушать, мы жутко лоханулсь с задачей Д, получили ВА3, потом ТЛ4, второпях забыли поставить завершение ДФСа, поставили return; если текущая вершина=n, получили ТЛ3, ну не смешно?) потом решили сразу проверять есть ли из текущей вершины дорога в Н, если да, то сравнивали с пред. ответом, иначе всех соседей перебирали, но блин, забыли поставить return; если все таки есть дорога до Н, думаю в этом ошибка, а времени оставалось 2 минуты, когда последний раз отсылали. Думаю, если бы не потеря 30 минут (проблемс с интернетом были), то ее бы мы решили.Не знаю почему, у сокомандников не шла задача С, хотя потом прочитал условие после контеста-легкая, не знаю, что они ее не решили). Могли бы быть с 8 задачами а не с 6:(  Так же хотел бы узнать про задачу J.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Хотелось бы послушать еще немного рассказа как не сдать задачку shortest-path для N <= 100.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А фиг знает, проверили код на несколько раз, но хоть убей не могли найти ошибку. Я себе исходник брать не стал, так как это не моя тема, но будет интересно посмотреть твой код решения, потом сравнить с нашим.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хотя если тут нет павлодарцев, то наверное внятного 100%ного решения не услышим. Но идея мне кажется такова(мне не хватило знаний про касательные): при вводе ищем ближайшую точку к началу координат, если получили равный квадрат расстояния(квадрат, чтоб корни не извлекать), то сопоставляем в какой четверти лежит и сравниваем по знаку КроссПродакты. Потом находим две точки касания этой окружности с лучами, исходящими из центра координат. Далее перебираем все звезды для каждой смотрим: если центр лежит между двумя этими лучами, образующими касательную, проверяем пересекает ли какая то прямая эту окружность, если да, то a++, b+=яркость этой звезды, если же центр лежит м/у лучами, и никакой луч не пересекает эти окружности, то яркость первой звезды (пусть будет с) увеличим на яркость проверяемой нами. Когда прошли весь цикл ans=(с+b)/(a+1). Верно ли я мыслю?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ты условие можешь объяснить? например, что делать в этом случае.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        обозначим номерами по мере удаления от вершины угла: 
        я1,я2,я3,я4
        ответ=((я1+я3+я4)+я2)/2
        если нет, то значит я неправильно понял задачу
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А, я рисовать не умею.
          Имеется ввиду звезда С, полностью закрытая парой (A,B) и не закрытая ни А ни В
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я как раз таки и предлагаю решение, чтобы смотреть только на самую ближнюю звезду, А по твоим обозначением, как я понял.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Я один прочитал ВАЗ как название машины?