На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Еще одна задача , Помогите решить задачу
    Помогите решить задачу.
    Надо только идея решения без исходников.
    Условие:


    Входной файл: input.txt
    Выходной файл: output.txt
    Время на тест: 20 секунд

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

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

    Входные данные
           Первая строка файла исходных данных с именем input.txt содержит длину начальной последовательности N (N- четное и 2<=N<=100). Далее следуют N строк, в каждой из которых содержится одно число. Эти числа задают начальные значения, записанные на доске в порядке слева направо. Числа на доске не превышают 200.

    Выходные данные
           Когда игра заканчивается, ваша программа должна записать результат игры в в файл с именем output.txt. Файл содержит два числа, записанные в одной строке. Первое число задает сумму чисел, выбранных первым игроком, второе число - сумму чисел, выбранных вторым игроком.

    Пример ввода и вывода
    input.txt
    6
    4
    7
    2
    9
    5
    2

    output.txt
    15 14


    Сообщение отредактировано: Krishkinn -
      А тут особо сложного ничего нет -- динамическое программирование. Подпоследовательности рассматривать в обратном порядке, от последнего оставшегося на доске числа. Первые сабмиты решений обычно заваливались на последовательности из 200 единиц, хде перебирать не надо, но получался очень большой перебор. Вторые -- на последовательности 200 раз по 200 smile.gif
        чего тут переберать, если нам в условии сказано
        Цитата
        Krishkinn, 25.12.03, 13:01
        Второй игрок играет наилучшим образом

        След. в анализе нам придется написать функцию, которая делает выбор аппонента. Этой же функцией можно делать и свой ход.
        А при всем богатстве выбора особой альтернативы у нас нет:

        пример тот что выше:
        6
        4
        7
        2
        9
        5
        2

        либо 6 либо 2. Если 6 то противнику оставляем 4 и 2, Если 2 то оставляем 6 и 5.
        Разница в первом варианте 6-2=4 во втором 2-5=-3 выбираем 6.

        получили
        (6:0)
        4
        7
        2
        9
        5
        2
        либо ( 4 ? 7 : 2 ), ( 2 ? 4 : 5 )

        4-7=-3, 2-5=-3, берем скажем первое 4

        и т.д.
          Чего-чего... :) Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение. Так уж оно устроено :)

          А вообще, ПЕРВОЕ, что нужно сделать после получения более-менее работоспособного решения, ето проверить, как оно работает на всяких вырожденных и екстремальных входных данных, допустимых по условию задачи. Я как составитель нескольких олимпиадных задач (да и все мне известные составители тоже :)) _всегда_ делал такие тесты. :)
            Цитата
            Visitor, 29.12.03, 09:33
            Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение.


            Тобишь что бы удостовериться, что на втором ходу я сделал правильный выбор, тобишь
            взял 4, мне нужно перерыть всю! последовательность до конца, причем на каждой такой развилке удваивать кол-во перебора оставшихся чисел.

            При написании ответа у меня в голове бродили мысли что может быть такая вырожденная последовательность, например для таких, выше, данных неполучилось собрать наименьшую сумму если таким подходом выбирать число дающее минимальное приращение суммы. Хотя я не уверен что вообще возможно первому игроку собрать наименьшую сумму. Во всяком случае этот алгоритм можно назвать эвристическим, а не переборным. И он точно не подвиснет на 200 единицах :) Потому что не имеет рекурсии.
            Цитата
            Visitor, 29.12.03, 09:33
            Я как составитель нескольких олимпиадных задач


            А вот это интересно :) хотел бы почитать условие, надеюсь это не N-мерные кубы ? ;)
              Не надо перерывать всю... Я ж говорю -- динамическое программирование. Если ты знаешь свои и противника оптимальные ходы и ожидаемый результат на (всех) подпоследовательностях длины 5, ты достаточно просто определишь их для подпоследовательностей длины 6...

              ВТОРЫЕ почти правильные сабмиты решений вылетали обычно из-за того, что разрядности используемых промежуточных переменных не хватало для хранения промежуточных результатов. Хотя здесь, вроде бы, ето составитель предусмотрел, и такого еффекта быть не должно... Мы своих не жалели :)

              Задачи... Вот, оказывается, в инете отчет разместили по одному из мероприятий :)
              http://rtf.ustu.ru/OL_HTM/Olymp.htm
              Сообщение отредактировано: Visitor -
                Игра имеет всего N^2 состояний.
                Строим таблицу и заполняем от конечных к начальным.
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0497 ]   [ 15 queries used ]   [ Generated: 21.05.24, 06:21 GMT ]