|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
28.10.2014, 23:45 | #1 |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
Имя файла для ввода: input.txt
Имя файла для вывода: output.txt Лимит времени: 1с. На кораблеремонтный завод для ремонта одновременно пришло N кораблей. В док на ремонт может зайти только один корабль. Время ремонта в доке для каждого корабля разное. После ремонта корабль сразу уходит в рейс. Составить программу, которая определяла бы порядок поступления кораблей в док, при котором суммарное время ожидание кораблей, которые ожидают своей очереди было бы минимальным. Входные данные. У первой строке файла содержится число N – количество кораблей, которые пришли на ремонт (1≤N≤10000). В следующих N строках – пары чисел – номер корабля и через пробел – время ремонта (натуральные числа, не больше 10000). Выходные данные. Файл должен содержать последовательность чисел – номера кораблей, в том порядке, в котором они заходят в док. Пример. input.txt 3 3 6 1 12 2 4 output.txt 2 3 1 Я думал что здесь нужно было вывести в файл номера кораблей в порядке возрастания времени ремонта и по быстрому набросал такое: Код:
PS. За код не ругать, это только проверка идеи))) Последний раз редактировалось studentus1985; 29.10.2014 в 22:11. |
29.10.2014, 02:16 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,285
|
Вообще, идея похожа на правду. Обычно, первый тест такой же, как в условии. Попробуйте отправить программу, которая выводит "2 3 1" на стандартный поток вывода, чтобы, во-первых, убедиться в наличии теста из условия, во-вторых, возможности работать со стандартными потоками ввода/вывода.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
29.10.2014, 02:41 | #3 | |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
Цитата:
Код:
|
|
29.10.2014, 10:07 | #4 | |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
Цитата:
Неполное решение Всего тестов: 10, пройдено: 0, не пройдено: 10. Получено баллов: 0 (из 20). N Результат Время (с) Баллы 1 Неправильный ответ 0.000 0 (2) 2 Неправильный ответ 0.000 0 (2) 3 Неправильный ответ 0.000 0 (2) 4 Неправильный ответ 0.000 0 (2) 5 Неправильный ответ 0.000 0 (2) 6 Неправильный ответ 0.000 0 (2) 7 Неправильный ответ 0.000 0 (2) 8 Неправильный ответ 0.000 0 (2) 9 Неправильный ответ 0.000 0 (2) 10 Неправильный ответ 0.000 0 (2) Может изначально идея не верна и суммарное время ожидания не будет минимальным в случае ремонта кораблей в порядке увеличения времени ремонта? Логика подсказывает что среди всех кораблей не должно быть двух с одинаковым временем ремонта ибо результат будет неоднозначным. А если так, то корабли можно отсортировать в возрастающую последовательность с номерами (припустим) от 0 до N-1. В этом случае, как мне кажется, суммарное время можно рассчитать как (N-1)*E(0)+(N-2)*E(1)+..+2*E(N-3)+1*E(N-2); ну а если все это переписать как код то что то в этом роде: (N-1)*p_mass[0][2]+(N-2)*p_mass[1][2]+(N-3)*p_mass[2][2]+...+1*p_mass[N-2][2]. Но также мне кажется что эта сумма будет минимальной если все N элементов будут размещены в порядке возрастания. Допустим что мы отсортировали элементы, тогда, например: (1 неравенство) E(0)<E(1). Но если мои предположения не верны, то при некоторых значениях элементов E(0) и E(1) можно записать: (2 неравенство) (N-1)*E(0)+(N-2)*E(1)+..+2*E(N-3)+1*E(N-2)>(N-1)*E(1)+(N-2)*E(0)+..+2*E(N-3)+1*E(N-2); тогда сократив слева и справа одинаковые слагаемые, получим: (N-1)*E(0)+(N-2)*E(1)>(N-1)*E(1)+(N-2)*E(0); Сгруппируем неравенство по элементах: (N-1)*E(0)-(N-2)*E(0)>(N-1)*E(1)-(N-2)*E(1); Очевидно что это неравенство превращается в E(0)>E(1), а это противоречит первому неравенству. Вывод: неравенство 2 неверно и знак > нужно поменять на <, а это значит что сумма будет минимальной в том случае, когда элементы будут расположены в порядке возрастания. Помогите пожалуйста, может я не правильно соображаю... |
|
31.10.2014, 00:01 | #5 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,285
|
Не очень понял, что означает (N-1)*E(0). Что на что умножается? Идея же с сортировкой по возрастанию времени ремонта выглядит убедительно. Кстати, если сдача происходит на каком-то общедоступном сайте, то дайте ссылочку на него - желающие смогут потестировать свои решения.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
31.10.2014, 09:32 | #6 | |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
Цитата:
В этой задаче нужно учитывать суммарное время ожыдания(простоя) всех кораблей. Например, если есть N кораблей, и первый корабль ремонтируется Е(0) часов, тогда все оставшиеся (N-1) кораблей должны ждать это время. Получается, что они суммарно простоят (N-1)*E(0) часов. Второй корабль ремонтируется Е(1) часов, тогда все оставшиеся (N-2) кораблей должны ждать это время - (N-2)*E(1), и т. д. А на счет сайта могу дать ссылку, но нужна специфическая регистрация и мне кажется что информация из рег. формы проверяется, я думаю разберешься Ссылочку кину в лс |
|
31.10.2014, 21:33 | #7 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,285
|
Утром заполнил форму - пока данные для входа не прислали (наверное, не понравились данные ). И да, при такой формуле все равно нужно отсортировать время ремонта по возрастанию.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
31.10.2014, 21:42 | #8 |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
|
01.11.2014, 07:09 | #9 | ||
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,618
|
Задание не корректное. Пример из задания не правильный вообще.
Цитата:
Цитата:
Ну мне кажется логичным запустить первый корабль (у которого время равно 12) - у оставшихся суммарное время - 10. А они предлагают запустить второй корабль - у него время 4, но тогда у кораблей в очереди суммарное время будет 18. Что я делаю не так? Даже если предположить что суммарное время вычисляется на каждом шаге ремонта (ну типа корабль со временем ремонта 12 ремонтируется 12 тактов) - то: 1) это не оговорено в задании (я щас сам напридумывал, ну потому что иначе объяснить пример не могу, а так... я хотя бы попытался) 2) все равно выгоднее запустить первый корабль. 12 * (6+4) + 6 * 4 + 4 = 148 (мы запускаем всегда самый долгий в ремонте корабль) 4 * (12+6) + 6 * 12 + 12 = 72 + 72 + 12 = 156. Ну ясно что первый вариант лучше. Короче, я не осилил пример. Задача в любом случае не дописана (я написал выше что именно) - можешь переслать ссылку на этот пост организаторам - пусть объяснят свою задачу. Последний раз редактировалось rrrFer; 01.11.2014 в 07:46. |
||
02.11.2014, 05:40 | #10 | |
Пользователь
Регистрация: 21.10.2014
Сообщений: 25
|
Цитата:
Пример. input.txt 3 3 6 1 12 2 4 output.txt 2 3 1 Если на ремонт заходит 2 корабль, то первый и третий должны ждать когда ремонт закончится, прежде чем какой нибудь из них сам зайдет в док. Далее в примере запускают 3 корабль, ну а второй должен ждать и это время. Ну а дальше заходит 1 корабль, его то никто не ждет так как он последний. Получается: (4+4)+6=12; Если же сначала запускать корабль с наибольшим временем ремонта, то оставшиеся два должны его ждать12+12)+6=30. Вот и выходит что минимальное время будет как в примере. |
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
В матрице поменять местами строки с max элементом и min элементом: объясните код, где какие действия выполняются (Паскаль). | КонстантинКонстант | Помощь студентам | 0 | 08.01.2014 13:38 |
DirectX. Где я ошибаюсь? | _-Re@l-_ | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 2 | 16.08.2010 20:59 |
где-то ошибаюсь, а где не пойму!укажите ошибку | <<Katushka>> | Общие вопросы C/C++ | 2 | 15.05.2010 11:41 |
Простая вещь, кажется сложной, или я ошибаюсь? | mimimi | PHP | 8 | 13.03.2009 22:10 |
Объясните пожалуйста, где и как ошибся | Manchester | Паскаль, Turbo Pascal, PascalABC.NET | 10 | 09.02.2009 20:51 |