Решал я одну задачку: 353B - Two Heaps. В принципе, она не сложная, но один момент я в ней не понял.
Мое решение (4988446) заключалось в следующем: отсортируем все кубики по числам, которые на них написаны. Четные кубики положим в первую кучку, нечетные — во вторую кучку. WA6
Не поняв, почему решение могло быть неправильным, решил посмотреть разбор. Суть решения была та же, однако при распределении кубиков по кучкам в разборе сначала брались кубики, которые встречаются >1 раза, раскидывались в кучки по одному, затем те, которые встречаются по 1 разу и уже произвольным образом кидались в кучки. Вроде как все успешные попытки в этом и заключались.
После нескольких поправок, задача зашла (4992055), но то, почему надо было делать именно так, осталось для меня непонятным. Ведь в моем решении вроде как одинаковые числа тоже кидались в кучки по одному. Объясните, пожалуйста, почему важно было разделить эти процессы?
Сначала нужно разбросать все кубики, количество которых >1, т.к если они соберутся в одно кучке, то количество различных четырёхзначных чисел не будет максимальным.Ещё нужно учесть, что кучки должны быть равны по размерам.
Ну у меня итак после сортировки это и происходит, или я что-то недопонимаю?
Тест такой: 1 1 1 3 5 5 5 7.
Ответ твоего первого решения будет такой:
первое множество 1 1 5 5
второе множество 1 3 5 7
общее количество чисел 8.
Верный ответ такой:
первое множество 1 3 5
второе множество 1 1 5 5 7
общее количество будет 9.
Из условия задачи"У Валеры имеется 2·n кубиков, на каждом из которых записано целое число от 10 до 99. Он произвольным образом выбирает n кубиков и откладывает в первую кучку. Оставшиеся кубики образуют вторую кучку."То есть в первой кучке и во второй должно быть равное количество кубиков и оно должно равняться n.У вас же в первой кучке 3, а во второй 5.
Не дочитал условие, извините.
Верный ответ такой:
первое множество 1 3 5 5
второе множество 1 1 5 7
общее количество будет 9.
PS. Хотя если посмотреть на тест 8 этой задачи, то можно заметить, что авторское решение этого не соблюдает. Видимо, это не было необходимым условием.
Случай когда кучки неравных размеров учитывается в 6-ом тесте.
Агрх.
Он получил ВА6 так как его ответ был не оптимален.
Закончим спор.
Странно, в одной из посылок я допустил багу, что могут кучки оказаться неравными по размеру. Получил WA
UPD. WA11, wrong answer The number of cubics in first heap must be equal to 91, but it equals 92
В первом решении у тебя на 6-й тест выдало WA из-за того, что количество кубиков в первой кучке у тебя 31, а во второй 19.
Нет, я посчитал, там одинаковое количество единиц и
нулейдвоек. Ответ был на 1 меньше оптимальногоНу это я заметил.