Дистанционная подготовка: Проблема с решением на Haskell (решение на C++ прошло все тесты)
Проблема с решением на Haskell (решение на C++ прошло все тесты)
от Дмитрий Гершвин - Четверг 26 Февраль 2015, 02:13
111507. Диадема Клеопатры
 

В качестве тренировки программирования на языке Haskell я решаю задачу 111507 (диадема клеопатры). Моё решение на C++ прошло все тесты с первой попытки, аналогичный алгоритм реализованный на haskell не прошел два теста (10 и 18).

Методом пробы было выяснено, что это тесты, на которые предполагается существующее решение, а не "Impossible" или "Fail", то есть либо программа находит неправильный список камней, которые могут быть настоящие, либо отвечает "Fail" или "Impossible" вместо того, чтобы выдать правильное решение.

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

Я составил много всевозможных тестов, но не нашел ни одного, где бы вывод двух моих программ был разным. Зато нашел тесты, которые не проверяются на сайте, и которые мои программы проваливают — например, когда было было проведено всего два взвешивания по одному камню, и оба камня весили, как настоящий камень. Такое не может быть, потому что настоящий камень только один. Мои программы отвечают на это "Fail", а должны "Impossible".

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

main = do firstLine <- getLine
          let a = read $ (words firstLine) !! 1
          let b = read $ (words firstLine) !! 2
          let k = read $ (words firstLine) !! 3
          entries <- sequence $ replicate k getLine
          let parsedEntries = map ((map read) . words) entries
          putStrLn $ formatOutput $ solve a b (map (\(x:y:xs) -> (x,xs)) parsedEntries)

При этом формат функции решения:

solve :: Int -> Int -> [(Int, [Int])] -> Maybe [Int]

первое число A, второе B, затем список взвешиваний, где каждый элемент это пара (суммарный вес, [список элементов для взвешивания]).

Правильно ли я читаю входные данные? Отличаются ли тесты 10 и 18 от остальных по форматированию?

Спасибо, Дмитрий

Re: Проблема с решением на Haskell (решение на C++ прошло все тесты)
от Дмитрий Гершвин - Понедельник 2 Март 2015, 12:23
  Разобрался со случаями, которые не учитывал, оказалось, что по ошибке запускал одну и ту же программу, думая, что сравниваю со своей на си. Эх.