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

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

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 30.04.2015, 15:49   #1
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию Простая (или не очень) задача про окраску канареек

Доброе время суток, уважаемые форумчане! Хотелось бы прочитать ваши соображения по поводу следующей задачки:
Цитата:
На столе стоят N (1 <= N <= 10000) занумерованных фарфоровых канареек. Каждая канарейка покрашена в какой-то цвет, зашифрованный с помощью чисел (всего цветов не более 1000). Роботу даётся несколько запросов в виде двух целых чисел: A (1 <= A <= 10000) и B (1 <= B <= 1000). Робот окрашивает всех канареек с порядковым номером кратным A в цвет B. В случае если A=1 робот окрашивает канареек, с номером являющимся простым числом или 1. Робот красит канареек вне зависимости от их первоначального цвета. Вам необходимо за наименьшее число запросов и наименьшее число окрашиваний добиться того, что все канарейки покрашены в один цвет. В качестве ответа на задачу выведите в любом порядке последовательность команд.
UPD: Внесено уточнение. Не сразу заметил, что первая канарейка никогда не перекрашивается

Последний раз редактировалось Demius; 30.04.2015 в 16:53. Причина: Уточнение формулировки
Demius вне форума Ответить с цитированием
Старый 30.04.2015, 16:43   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

А на мой взгляд, совсем не простая задача!

тут же надо анализировать исходную окраску элементов и, исходя из неё, строить оптимальную стратегию по закраске в нужный (единый цвет).
Serge_Bliznykov вне форума Ответить с цитированием
Старый 30.04.2015, 16:50   #3
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
А на мой взгляд, совсем не простая задача!

тут же надо анализировать исходную окраску элементов и, исходя из неё, строить оптимальную стратегию по закраске в нужный (единый цвет).
Мы же можем при чтении цвета канареек выбрать тот цвет, который встречается чаще всего и в него всех остальных перекрашивать, или я не прав?
Demius вне форума Ответить с цитированием
Старый 30.04.2015, 17:09   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

нет, это неверный алгоритм.
допустим, 1,3,5 и 7-я канарейки окрашены в зелёный цвет, 2-я в красный, а 4-я и 6-я - в фиолетовый.
Тогда ОДНОЙ командой "Красить" A=1 B=фиолетовый мы всех окрасим в фиолетовый цвет.

хотя преобладающий цвет явно зелёный...
Serge_Bliznykov вне форума Ответить с цитированием
Старый 30.04.2015, 17:14   #5
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
нет, это неверный алгоритм.
допустим, 1,3,5 и 7-я канарейки окрашены в зелёный цвет, 2-я в красный, а 4-я и 6-я - в фиолетовый.
Тогда ОДНОЙ командой "Красить" A=1 B=фиолетовый мы всех окрасим в фиолетовый цвет.

хотя преобладающий цвет явно зелёный...
В данном случае выгоднее окрасить канареек командой A=2 B=зелёный.

командой "Красить" A=1 B=фиолетовый мы всех окрасим в фиолетовый цвет за пять перекрашиваний (1,2,3,5,7), в то время как команда A=2 B=зелёный даст нам всего 3 перекрашивания (2,4,6).
Demius вне форума Ответить с цитированием
Старый 30.04.2015, 17:31   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

в данном случае согласен с Вами.

но я хотел проиллюстрировать другое.

ладно
Пусть 1-я, 2 и 3-я выкрашены в красный цвет
4-я - в фиолетовый
5-я - в зелёный
6-я - в фиолетовый

в какой цвет и как будем красить?

кстати,
Цитата:
Вам необходимо за наименьшее число запросов и наименьшее число окрашиваний
а что имеет более высокий приоритет?
Нвапример, что будет иметь "наименьшее число":
покрасить за 1 запрос 4 канарейки,
или покрасить за 3 запроса 3 канарейки?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 30.04.2015, 17:40   #7
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
в данном случае согласен с Вами.

но я хотел проиллюстрировать другое.

ладно
Пусть 1-я, 2 и 3-я выкрашены в красный цвет
4-я - в фиолетовый
5-я - в зелёный
6-я - в фиолетовый

в какой цвет и как будем красить?

кстати,
а что имеет более высокий приоритет?
Нвапример, что будет иметь "наименьшее число":
покрасить за 1 запрос 4 канарейки,
или покрасить за 3 запроса 3 канарейки?
1) Приоритет: минимум перекрашиваний, минимум запросов
2) Рассмотрим два случая:
  • красим в красный цвет. Команды A=2 B="красный" и A=5 B="красный". Итого 4 перекрашивания за 2 команды
  • красим в фиолетовый цвет. Команда A=1 B="фиолетовый". Итого 4 перекрашивания за 1 команду
Из п. 1 делаем вывод, что красить выгоднее в фиолетовый цвет.

Согласен, брать макс цвет не всегда выгодно.
Demius вне форума Ответить с цитированием
Старый 30.04.2015, 20:39   #8
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Внимание! Написано в больном бреде. Кто поверит, тот сам виноват

Теперь по делу :
Рассмотрим работу алгоритма на неком k-ом шаге :
Всего у нас было k-1 канареек и p - кол-во различных цветов, в которых изначального были выкрашены первые k-1 канареек
Теперь мы бахаем перебор : мы можем выкрасить оставшуюся канарейку в цвета 1..p. Как это делать : у нас будет матрица (k-1)*p. На пересечении i-ой строки и j-ого столбца будет находиться массив изменений, которыми мы производили для этих параметров. Тогда нам остается перебрать все решения для k-1 и clr = 1..p. И смотреть в массив, который находится в в матрице[k-1][clr].
Вот из него мы берем все ходы и смотрим кратно ли k ходу (ну или есть 1 - является ли k простым)
Если нашли такой - матрица[k][clr] = матрица[k-1][clr], если нет - матрица[k][clr] = матрица[k-1][clr]+1 (потом напишу какой элемент добавить)

Ответом же будет являться минимум из последней строки

Но тут такой еще момент : когда на k-Ом шаге получается p+1. Тогда нужно решать туже проблему, но для одного цвета(эт несильно мудрено)

Теперь про то, какой элемент добавить : я бы делал так : если красим все элементы кратные m, то ничего хорошего в голову не лезет, кроме как смотреть по всем делителям и определять сколько элементов перекрасим. Другой вариант - просто добавлять токующий элемент, но потом при добавлении следующего смотреть, можно ли объединить некий элемент предыдущего решения и нынешней позиции


Вот. За сим откланиваюсь
Poma][a вне форума Ответить с цитированием
Старый 01.05.2015, 00:29   #9
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

Просто отвлечённые рассуждения.
1. Есть массив (канареек), заполненный числами (окрашенных цветами).
2. Пока предположим, что цвета абсолютно все разные.
3. Чтобы покрасить все в один цвет х (нам на данном этапе пояснений безразличен цвет) нужно дать серию команд
Код:
N A B
1 1 x
2 2 x
3 3 x
4 5 x
5 7 x
....
где N - порядковый номер запроса, A и B - смысл как в условии задачи.
На словах, какие команды подаются: покрасить простые, кратные простым (в том числе чётные). Последние, чтобы учесть случаи, когда индекс элемента (номер канарейки) - степень простого числа (например, 7*7*7*7).
Теперь нужно решать задачу о минимальном покрытии.
Для минимизации нужно учесть, что какие-то группы могут быть полностью одного цвета, а также наличие "особых" индексов (равных степеням одного простого числа), гарантированно добавляющих группу (тут можно минимизировать количество покрасок разложением степени на множетели).
В общем, что-то напоминающее импликанты из Квайна-МакКласки.
FPaul вне форума Ответить с цитированием
Старый 02.05.2015, 17:58   #10
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Попробовал свой вариант (только решил отказаться от матрицы и считать по строкам)
Код:
{
 Ибо  не совсем понятен момент с единицей (что за "или" в условии?),
 буду решать задачу так : чтобы перекрасить все числа кратные K,
 нужно указать K. Чтобы перекрасить все простые числа, нужно скормить 0.
 Чтобы перекрасить одну лишь единичку, нужно ввести 1
}

type
	TArr = array [1..100] of Byte;

var
	Dont : set of Byte;

function GCD(a, b : Byte) : Byte;
begin
	if (a = 0) or (b = 0) then begin
		GCD := 1;
		Exit
	end;

	while (a <> 0) and (b <> 0) do begin
		if a > b then
			a := a mod b
		else
			b := b mod a
	end;

	GCD := a+b
end;

procedure AddToAns(var a : TArr; var n : Byte; k : Byte);
var
	i : Byte;
begin
	for i := 1 to n do
		if GCD(a[i], k) <> 1 then begin
			a[i] := GCD(a[i], k); Dont := Dont + [k, a[i]]; Exit
		end;

	Inc(n);
	a[n] := k
end;

function IsPrime(n : Byte) : Boolean;
var
	i : Byte;
begin
	if n = 1 then begin
		IsPrime := FALSE;
		Exit
	end;

	for i := 2 to Trunc(Sqrt(n)) do
		if n mod i = 0 then begin
			IsPrime := FALSE;
			Exit
		end;

	IsPrime := TRUE
end;

procedure DeletePrime(var a : TArr; var n, k : Byte);
var
	b : TArr;
	m, i : Byte;
begin
	m := 0;
	for i := 1 to n do
		if (not IsPrime(a[i])) or (IsPrime(a[i]) and (a[i] in Dont)) then begin
			Inc(m);
			b[m] := a[i]
		end;

	if m <> n then begin
		Inc(m);
		b[m] := 0
	end;

	a := b;
	n := m
end;

procedure PrintAns(const a : TArr; n, k : Integer);
var
	i : Byte;
begin
	for i := 1 to n do
		WriteLn('  ', a[i], ' ', k)
end;

function MoreThanOne(const a : TArr; n : Byte) : Boolean;
var
	i, cnt : Byte;
begin
	cnt := 0;
	for i := 1 to n do
		if IsPrime(a[i]) and (not(a[i] in Dont)) then
			Inc(cnt);

	MoreThanOne := cnt > 1

end;

procedure Find(k, n : Byte; a : TArr);
var
	i, m : Byte;
	ans : TArr;
begin

	Dont := [];

	m := 0;
	for i := 1 to n do
		if a[i] <> k then
			AddToAns(ans, m, i);

	if MoreThanOne(ans, m) then
		DeletePrime(ans, m, k);

	PrintAns(ans, m, k)
end;

var
	n, i : Byte;
	a : TArr;
	use : set of Byte;

begin
	ReadLn(n);

	for i := 1 to n do
		Read(a[i]);

	use := [];
	for i := 1 to n do
		if not (a[i] in use) then begin
			use := use + [a[i]];
			WriteLn('Color ', a[i], ' :');
			Find(a[i], n, a);
			WriteLn()
		end
end.
Надеюсь, что никто не видел

Последний раз редактировалось Poma][a; 02.05.2015 в 21:14.
Poma][a вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Очень сложная задача про векторы logikal Помощь студентам 4 29.04.2014 22:29
Delphi - Очень простая задача! honest Помощь студентам 1 11.06.2009 14:10
Не простая, но очень интересная задача (Pascal)! Juliya_U Паскаль, Turbo Pascal, PascalABC.NET 29 17.04.2009 19:33