20 / 13 / 1
Регистрация: 17.12.2010
Сообщений: 34
|
||||||
1 | ||||||
Оптимальное заполнение или "Халява"25.01.2012, 22:16. Показов 3585. Ответов 22
Метки нет (Все метки)
Наткнулся на задачку с acmp.ru.
Текст задачи
Гриша очень любит газировку PupsiCola. Однажды он узнал, что, собрав несколько крышек со звездочками, можно получить футболку. Гриша нашел A крышек с одной звездочкой, B крышек с двумя звездочками и C крышек с тремя звездочками. На футболку можно обменять набор крышек, общее количество звездочек на которых не меньше K.
Помогите Грише узнать, сколько футболок он может получить. Входные данные Входной файл INPUT.TXT содержит целые числа A, B, C и K (0 ≤ A, B, C ≤ 100, 1 ≤ K ≤ 1000). Выходные данные В выходной файл OUTPUT.TXT выведите максимальное количество футболок, которые может получить Гриша. Вроде не сложно. Я начал решать задачу думая мол так : чем оптимальней заполнять k тем больше футболок получу на выходе. Как мне кажется, оптимальным будет начинать с трехзвездочных крышек, продолжая двухзвездочными и заканчивая однозвездочными, отдавая так, чтобы их сумма как можно реже превышала k. Вроде бы все замечательно, я проверил с кучей вариантов из головы свой код, с ними все работает должным образом. Но тем не менее не прохожу проверку "Тест 3" на сайте.
2
|
25.01.2012, 22:16 | |
Ответы с готовыми решениями:
22
OTEC или халява из тепла океана Оптимальное заполнение объема оптимальное заполнение пространства Оптимальное заполнение двумерного массива другими 2-мерными массивами |
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
27.01.2012, 09:00 | 2 |
2
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
20.05.2012, 09:45 | 3 |
Кто-нибудь может подсказать, как решается эта задача? Ее тема "Динамическое прогарммирование", но лично я вообще не вижу от чего к чему можно переходить! Разве что какой-то бинпоиск...
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
20.05.2012, 12:06 | 4 | |||||
Могу описать алгоритм, который сам использовал для решения этой задачи:
Для решения нужны два трехмерных массива: t1[][][] размером (a+1)*(b+1)*(c+1) и t2[][][] такого же размера. Изначально значения массивов равны 0. t1[][][] - нужен для количества звездочек, которые не хватает на очередную футболку. Т.е. любое значение t1[i][j][y] (i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами) может быть в диапазоне от 0 до K-1. Как только это значение достигает или превышает K , то мы значение t1[i][j][y] обнуляем, но увеличим на 1 значение t2[i][j][y]. t2[i][j][y] - будет иметь значение максимального числа футболок когда: i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами. Теперь сам проход: три цикла:
Пробуем сначало оттолкнуться от значения t1[i-1][j][y] (количество неиспользуемых звезд) и t2[i-1][j][y] (количество имеющихся футболок). t1[i][j][y] будет равно t1[i-1][j][y]+1, а t2[i][j][y] будет равно t2[i-1][j][y]. Но если t1[i][j][y] стало равным или более K, то запишем t1[i][j][y]=0; t2[i][j][y]++; Потом пробуем оттолкнуться от значения t1[i][j-1][y] и t2[i][j-1][y]. Здесь нужно учитывать, что значения в t1[i][j][y] и t2[i][j][y] уже есть, но если количество футболок получаем из варианта [i][j-1][y] превысит записанное значение в t2[i][j][y] или количество футболок останется прежним, но увеличится количество неиспользованных звезд, то значения t1[i][j][y] и t2[i][j][y] будут расчитываться от значений t1[i][j-1][y] и t2[i][j-1][y]. Так же в этой же итерации проверяется возможность получения максимального значения t1[i][j][y] и t2[i][j][y] из варианта t1[i][j][y-1] и t2[i][j][y-1]
1
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
20.05.2012, 15:44 | 5 |
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
0
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
20.05.2012, 16:21 | 6 |
Спасибо за обьяснение, сейчас попробую сдать. Вообще странно, что 10^8 операций заходят.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 16:23 | 7 |
В смысле сделать так:
(A*1 + B*2 + C*3 ) / K это число и подать в ответ? Если это имели ввиду, то могу привести несколько контрпримеров, когда нельзя. Один прямо сейчас: 0 0 1 1 правильный ответ 1. А если перемножить, сложить и разделить то получится 3.
1
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
20.05.2012, 16:23 | 8 |
Вот Вам пример:
100 0 0 100 2 По вашему решению, ответ это 100*3 / 2 , а на самом деле не так, потому что всегда 1 звезда будет лишней и мы ее будем "терять".
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 16:24 | 9 |
1
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
20.05.2012, 16:46 | 10 |
Memory limit. o-O
А Вы ее пытались сдавать? Добавлено через 44 секунды Эх, придется извращаться и запоминать лишь предыдущие значения.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 16:54 | 11 |
1
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
20.05.2012, 16:56 | 12 |
Сдал, спасибо большое . Только в цикле нужно от нулей начинать, кстати!
Добавлено через 37 секунд На счет лимита памяти - был тип long long , сделал int . Думал ответы будут большие иногда, оказалось - нет.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 17:02 | 13 |
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
||||||
20.05.2012, 18:14 | 14 | |||||
Попробовал сделать без циклов и массивов, вроде работает:
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 19:54 | 15 |
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
||||||
20.05.2012, 20:06 | 16 | |||||
Да я заметил, поспешил, не доделал. Сейчас по Вашему варианту выдает правильный ответ, а вот если вбить 0 4 2 7 то уже нет
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
20.05.2012, 20:10 | 17 |
0
|
7 / 7 / 0
Регистрация: 16.05.2012
Сообщений: 31
|
|
20.05.2012, 21:50 | 18 |
if ((A*1 + B*2 + C*3 ) == K )then..
+три цикла +запись в масив из которого потом найти оптимальный Добавлено через 1 минуту простинкий перебор
0
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
|
||||||
24.11.2013, 22:03 | 19 | |||||
Не знаю, принято ли тут создавать новые темы, или "поднимать" старые, так что на всякий случай напишу тут.
Тоже занялся этой задачкой. После "облома" с "оптимальным" набором крышек для каждой футболки (тест 0 12 3 11) сам пришёл к такому алгоритму, реализовал. Выдаёт правильные ответы, но: 1) Массив размером [100][100][100] создать не удается, по крайней мере Visual Studio ругается. Что предпринять? 2) Возможно, я где-то туплю, но решение не проходит по времени. При этом, решения многих на acmp.ru работают быстро и используют ~56 Кб памяти, вроде 2-мя трехмерными массивами не пахнет. Куда копать? Уже все мозги измучал, ЧСВ ниже плинтуса упало. Код решения:
0
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
|
|
26.11.2013, 18:55 | 20 |
Немного оптимизировал, вроде нет ошибки по времени, но все равно массив [100][100][100] не создать, а, похоже, один из тестов 100 100 100 как раз.
0
|
26.11.2013, 18:55 | |
26.11.2013, 18:55 | |
Помогаю со студенческими работами здесь
20
Заменил вентилятор, как понять оптимальное количество оборотов или температуру бп? Оптимальное количество заданий и оптимальное количество игр при обучении с использованием ИИ Халява Сэр Определить оптимальное количество шагов, при котором max траекторий возвращается ИЛИ пересекает 0 Халява для студентов Очередная халява от NXP Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |