GD Star Rating
loading...

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

Текст задачи в комментах, кому лень логиниться по ссылке (на английском, естественно).

32 Responses to Чуваки.

  1. NnaSm:

    There areK pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 toN; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
    A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.

    At anypoint of time, the decreasing radius property of all the pegs must be maintained.

    Constraints:
    1<= N<=8
    3<= K<=5

    Input Format:
    N K
    2nd line contains N integers.
    Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
    3rd line denotes the final configuration in a format similar to the initial configuration.

    Output Format:
    The first line contains M – The minimal number of moves required to complete the transformation.
    The following M lines describe a move, by a peg number to pick from and a peg number to place on.
    If there are more than one solutions, it’s sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

    Sample Input #00:

    2 3
    1 1
    2 2

    Sample Output #00:

    3
    1 3
    1 2
    3 2

    Sample Input #01:
    6 4
    4 2 4 3 1 1
    1 1 1 1 1 1

    Sample Output #01:
    5
    3 1
    4 3
    4 1
    2 1
    3 1

    NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
    If you are using “Java”, the classname is “Solution”

  2. NnaSm:

    Я ее поковырял, решить ее можно, но по-моему не за 45 минут, которые требуются.

    Или я не вижу простого и очевидного алгоритма решения?

  3. NinAll:

    Обобщенная задача о Ханойских башнях?
    Есть несколько методов решения, я бы воспользовался А* поиском, как самым очевидным для меня решением. Тем более, что максимальная глубина решения указана.

  4. Akref:

    зашел написать поиск в ширину, А*

  5. NnaSm:

    :

    Что это за поиск?

  6. NnaSm:

    :

    А, вспомнил. Как это применимо к данной задаче?

  7. Akref:

    : есть начальное состояние, есть правила перехода, есть конечное состояние. Все это образует дерево. тебе нужно найти кратчайший путь до конечного состояния. Есть классические алгоритмы для этого – поиск в ширину и А*. В глубину искать нельзя тут. Можно сразу искать в ширину, но надо учитывать что для данной задачи(You can assume, there is always a solution with less than 7 moves) количество состояний в дереве будет порядка K*(K-1)^7, мб медленно будет.

  8. NnaSm:

    :

    Я думал есть какой-то целенаправленный алгоритм, а выходит полный перебор, как ни крути.

  9. NnaSm:

    Я уже нашел, сусанин:)

  10. Akref:

    : кто мешает правила перехода умными сделать?

  11. NnaSm:

    :

    Да в общем никто, кроме 45 минут на решение, плюс еще надо парсер инпута написать ко всему почему.

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

  12. NnaSm:

    Не, это частный случай, сусанин.

  13. NinAll:

    : Мне кажется, что рекурсивный вариант вполне себе обобщается.

  14. NnaSm:

    :

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

  15. NinAll:

    : ага, точно. Можно адаптировать, но полученное решение не будет оптимальным.

  16. Sueprado:

    : 45 минут – это даже много. задача – обычная с контестов, на которых на 5 часов дается 8-10 задач. второй аналог – 2-3 уровень топкодера, где на 3 задачи дается 40 минут.
    выделять отдельно парсер инпута – это вообще слишком, он пишется за пол-минуты с закрытыми глазами

  17. NnaSm:

    :

    Где можно посмотреть список задач для такого контеста?

  18. 0duaTa:

    : topcoder.com
    codeforces.ru

  19. Sueprado:

    : ну и про юву забывать не стоит, свои позиции она сдала, но архив задач огромнейший.

    Кроме самих архивов и всех проведенных там контестов, есть, например, задачи финалов АСМа

  20. NnaSm:

    :

    Надо посмотреть.

  21. OmiVelo:

    : Какой-такой парсер? Здесь вход – пачка целых, разделённых пробелами/переводами строк.
    В жабе, например, весь “парсер” сводится к input = new Scanner(…)/пачка foo = input.nextInt()

  22. NnaSm:

    :

    Я на пхп писал решение, с консольными приложениями на нем не доводилось иметь дел до сих, пришлось разбираться, что там да как.

  23. OmiVelo:

    : В PHP по идее для этого fscanf() должен подойти.

  24. NnaSm:

    :

    Там по-моему у них немного напущено туману в этом отношении, потому что загруз у них там осуществляется через пайп, скорее всего, а не из командной строки, из описания непонятно.

  25. OmiVelo:

    : По ссылке открытым текстом написано “Read inputs from STDIN and output to STDOUT”, никакой неоднозначности.
    fopen(‘php://stdin’, ‘r’) и – в бой.

  26. NnaSm:

    :

    Ну так пайп тоже со стдин читается.

  27. OmiVelo:

    : Так где тогда туман-то?

  28. NinAll:

    Подниму пост.
    “The case of 4 pegs is often called Reves’s problem – the problem being to determine the least number of moves to move all disks. The answer to Reve’s’s problem is currently unknown – that is, no-one knows the least number of moves to move n disks, using the same rules as the Tower of Hanoi, except there are 4 pegs instead of 3 (or if someone does know the answer, they’re not telling!)”. Отсюда.
    Так что А*.

Добавить комментарий