Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.10.2014, 23:45   #1
studentus1985
Пользователь
 
Регистрация: 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

Я думал что здесь нужно было вывести в файл номера кораблей в порядке возрастания времени ремонта и по быстрому набросал такое:

Код:
#include <fstream>
using namespace std;
int main(int argc, char** argv){
int N,index, max=10001;
ifstream input;
input.open("input.txt");
ofstream output;
output.open("output.txt");
input>>N;
int **p_mass=new int*[N];                          //sozdanie dinamicheskogo
for(int i=0; i<N; i++) p_mass[i]=new int[2]; //massiva
                                                               //
	for (int i=0; i<N; i++){                      //
		for (int j=0; j<2; j++){    	       //
		input>>p_mass[i][j];                   // iniciflizaciya
						             	//
		                  				//
		 			           	    	// dinamicheskogo
		}                           		        // massiva
	}                                   	                //
for (int j=0; j<N; j++){
	for (int i=0; i<N; i++){
		if ((p_mass[i][1]>0) && (p_mass[i][1]<=max)){
			max=p_mass[i][1];
			index=i;
		}	
	}
	output<<p_mass[index][0]<<" ";
	p_mass[index][1]=0;
	max=10001;
}
 output<<"\n";
 delete p_mass;
 input.close();
 output.close();
return 0;
}
Но увы эта программа не проходит ни одного теста, может кто подкинет идею, возможно мои соображения не верны.
PS. За код не ругать, это только проверка идеи)))

Последний раз редактировалось studentus1985; 29.10.2014 в 22:11.
studentus1985 вне форума Ответить с цитированием
Старый 29.10.2014, 02:16   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Вообще, идея похожа на правду. Обычно, первый тест такой же, как в условии. Попробуйте отправить программу, которая выводит "2 3 1" на стандартный поток вывода, чтобы, во-первых, убедиться в наличии теста из условия, во-вторых, возможности работать со стандартными потоками ввода/вывода.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 29.10.2014, 02:41   #3
studentus1985
Пользователь
 
Регистрация: 21.10.2014
Сообщений: 25
По умолчанию

Цитата:
Сообщение от BDA Посмотреть сообщение
Вообще, идея похожа на правду. Обычно, первый тест такой же, как в условии. Попробуйте отправить программу, которая выводит "2 3 1" на стандартный поток вывода, чтобы, во-первых, убедиться в наличии теста из условия, во-вторых, возможности работать со стандартными потоками ввода/вывода.
Попробую вот так:
Код:
#include <fstream>
using namespace std;
int main(int argc, char** argv){
ifstream input;
input.open("input.txt");
ofstream output;
output.open("output.txt");

 output<<2<<" "<<3<<" "<<1<<"\n";
 input.close();
 output.close();
return 0;
}
Но мне кажется что нету такого же теста как в условиях, так как с предыдущего задания у меня уже есть тесты, и там нет такого теста
studentus1985 вне форума Ответить с цитированием
Старый 29.10.2014, 10:07   #4
studentus1985
Пользователь
 
Регистрация: 21.10.2014
Сообщений: 25
Вопрос

Цитата:
Сообщение от BDA Посмотреть сообщение
Попробуйте отправить программу, которая выводит "2 3 1" на стандартный поток вывода, чтобы, во-первых, убедиться в наличии теста из условия, во-вторых, возможности работать со стандартными потоками ввода/вывода.
Попробовал, ничего не получилось:

Неполное решение

Всего тестов: 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 неверно и знак > нужно поменять на <, а это значит что сумма будет минимальной в том случае, когда элементы будут расположены в порядке возрастания.

Помогите пожалуйста, может я не правильно соображаю...
studentus1985 вне форума Ответить с цитированием
Старый 31.10.2014, 00:01   #5
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Не очень понял, что означает (N-1)*E(0). Что на что умножается? Идея же с сортировкой по возрастанию времени ремонта выглядит убедительно. Кстати, если сдача происходит на каком-то общедоступном сайте, то дайте ссылочку на него - желающие смогут потестировать свои решения.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 31.10.2014, 09:32   #6
studentus1985
Пользователь
 
Регистрация: 21.10.2014
Сообщений: 25
По умолчанию

Цитата:
Сообщение от BDA Посмотреть сообщение
Не очень понял, что означает (N-1)*E(0). Что на что умножается? Идея же с сортировкой по возрастанию времени ремонта выглядит убедительно. Кстати, если сдача происходит на каком-то общедоступном сайте, то дайте ссылочку на него - желающие смогут потестировать свои решения.
Попробую объяснить
В этой задаче нужно учитывать суммарное время ожыдания(простоя) всех кораблей. Например, если есть N кораблей, и первый корабль ремонтируется Е(0) часов, тогда все оставшиеся (N-1) кораблей должны ждать это время. Получается, что они суммарно простоят (N-1)*E(0) часов. Второй корабль ремонтируется Е(1) часов, тогда все оставшиеся (N-2) кораблей должны ждать это время - (N-2)*E(1), и т. д.
А на счет сайта могу дать ссылку, но нужна специфическая регистрация и мне кажется что информация из рег. формы проверяется, я думаю разберешься
Ссылочку кину в лс
studentus1985 вне форума Ответить с цитированием
Старый 31.10.2014, 21:33   #7
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Утром заполнил форму - пока данные для входа не прислали (наверное, не понравились данные ). И да, при такой формуле все равно нужно отсортировать время ремонта по возрастанию.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 31.10.2014, 21:42   #8
studentus1985
Пользователь
 
Регистрация: 21.10.2014
Сообщений: 25
По умолчанию

Цитата:
Сообщение от BDA Посмотреть сообщение
Утром заполнил форму - пока данные для входа не прислали (наверное, не понравились данные ). И да, при такой формуле все равно нужно отсортировать время ремонта по возрастанию.
Возможно нужно было регится до начала 1 тура, а уже второй
studentus1985 вне форума Ответить с цитированием
Старый 01.11.2014, 07:09   #9
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Задание не корректное. Пример из задания не правильный вообще.
Цитата:
при котором суммарное время ожидание кораблей, которые ожидают своей очереди было бы минимальным.
Что такое суммарное время? Как И КОГДА они предлагают его вычислять?

Цитата:
Пример.
input.txt
3
3 6
1 12
2 4

output.txt
2 3 1
Короче есть 3 корабля. Сейчас их суммарное время ожидания - 22. Надо запустить какой-то из них, так чтобы время ожидания оставшихся кораблей было минимальным.
Ну мне кажется логичным запустить первый корабль (у которого время равно 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.
rrrFer вне форума Ответить с цитированием
Старый 02.11.2014, 05:40   #10
studentus1985
Пользователь
 
Регистрация: 21.10.2014
Сообщений: 25
По умолчанию

Цитата:
Сообщение от rrrFer Посмотреть сообщение
Задание не корректное. Пример из задания не правильный вообще.


Что такое суммарное время? Как И КОГДА они предлагают его вычислять?
, нет задание и пример правильные, просто задание на украинском, и наверно из меня плохой переводчик. Но суть задачи я передал точно. А под суммарным временем ожидания предполагается время которое простаивает каждый корабль, вместо того чтобы заниматься чем то полезным. Почему определение суммарного времени такое - возможно и из-за того, что каждому матросу из любого корабля нужно платить, а матросы то штаны только протирают во время ожидания.
Пример.
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.
Вот и выходит что минимальное время будет как в примере.
studentus1985 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
В матрице поменять местами строки с 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