+ Ответить в теме
Показано с 1 по 4 из 4

Тема: Задача про приключения лягушонка Crazy Frog

  1. #1
    dummy
    coder
    olya1994 is on a distinguished road
    Регистрация
    13.11.2014
    Возраст
    23
    Сообщений
    10
    Вес репутации
    0

    По умолчанию Задача про приключения лягушонка Crazy Frog

    Всем привет! Помогите пожалуйста решить хитрую задачку! у самой ничего не получается..Заранее огромное Вам спасибо!!! Задача решается через вектора..

    Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на N*N (N<=50) клеток, находится один комар весом aij (вес комара – натуральное число <= 50), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

    Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.

    Входные данные

    Первая строка входного файла INPUT.TXT содержит число N. Следующие N строк содержат по N чисел aij, разделенных пробелами.

    Выходные данные

    В выходной файл OUTPUT.TXT выведите целое число – вес съеденных комаров.

    Примеры

    INPUT.TXT OUTPUT.TXT
    3
    8 2 1
    1 2 6
    2 7 2 14
    5
    8 2 1 2 3
    1 2 6 2 4
    2 7 2 3 4
    1 3 2 4 4
    1 3 4 3 1 19

  2. По умолчанию

     
    Хотите избавиться от рекламы? Зарегистрируйтесь
  3. #2
    Moderator Куратор
    system architect
    Romeo is on a distinguished road Аватар для Romeo
    Регистрация
    02.03.2004
    Адрес
    Крым, Севастополь
    Возраст
    36
    Сообщений
    3,057
    Вес репутации
    20

    По умолчанию Re: Задача про приключения лягушонка Crazy Frog

    Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.
    Entites should not be multiplied beyond necessity @ William Occam
    ---
    Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
    ---
    Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

  4. #3
    dummy
    coder
    olya1994 is on a distinguished road
    Регистрация
    13.11.2014
    Возраст
    23
    Сообщений
    10
    Вес репутации
    0

    По умолчанию Re: Задача про приключения лягушонка Crazy Frog

    Цитата Сообщение от Romeo Посмотреть сообщение
    Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.
    Огромное спасибо Вам! Я думаю возможно такой алгоритм!?
    1 цикл - перебираем столбцы исходной матрицы
    2 цикл - перебираем массив сумм
    3 цикл - перебираем столбец исходной матрицы (для каждого значения в массиве сумм ищем в столбце лучший вариант)

  5. #4
    system architect somewhere will become famous soon enough somewhere will become famous soon enough Аватар для somewhere
    Регистрация
    31.08.2006
    Адрес
    71 RUS
    Возраст
    35
    Сообщений
    1,837
    Вес репутации
    16

    По умолчанию Re: Задача про приключения лягушонка Crazy Frog

    Очевидно комары будут съедаться в основном из верхних строк, т.к. чем меньше номер строки, тем большее число клеток мы сможем охватить. Наверное было бы неплохо предварительно значения в матрице с весом комаров построчно поделить на номер строки, тем самым узнав реально эффективный вес. А дальше строим допустимые маршруты и считаем суммы. Имхо только перебором, т.к. комбинаторика на лицо.
    It's a long way to the top if you wanna rock'n'roll

+ Ответить в теме

Похожие темы

  1. Задача
    Сформировать массив из положительных элементов той строки матрицы А размерности n×n, где обнаружен наибольший элемент этой матрицы.
    от bleene в разделе задачи на Паскале и Delphi
  2. Задача
    помогите пожалуйста с задачей ____ Написать функцию проверки упорядоченности элементов списка.
    от gremt в разделе Delphi и Pascal
  3. Задача
    В универе сдаём зачёт,у меня вот такое задание: Реализовать в Паскале. 1) Решить методом Крамера систему ур-ней: { a11x1+a12x2+a13x3=b1 {...
    от Alenochka в разделе Решите мне задачку

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения