Олимпиадные задачи

[ViktorR]

Задача о конвертах.
Что-то я засомневался в алгоритме, который предложен eoln.
Требуется ведь разбить множество конвертов на две группы с равными суммами, если таковые будут обнаружены.
Суммы, как понимаю, разложены хаотически.
Если пронумеровать конверты от 1 до N, то следует указать номера конвертов, между которыми пройдет прямая.
Условие о прохождении прямой через центр и условие о равномерности разложенных конвертов говорят о том, что число конвертов справа от разделительной прямой и слева - одинаково.
Предлагаю такой алгоритм.
1. Заполняем массив суммами в конвертах.
2. Определяем номер первого конверта второго полукруга - k;
3. Находим две суммы: конверты от первого до k -1 и от k до N.
4. Проверяем равенство полученных сумм.
5. Если суммы равны, то завершаем работу программы указывая номера конвертов между которыми проходит прямая (N,1 и k-1, k).
6. Определим указатель на начало полукруга - i = 1;
7. Если суммы неравны, то из первой суммы вычитаем сумму i-го конверта и добавляем сумму k + i -го конверта, а ко второй сумме прибавляем сумму i-го конверта и вычитаем сумму k+i -го конверта.
8. Проверяем суммы. Если они неравны, то продолжаем с п.6 изменив
указатель на начало полукруга на единицу.
9. Продолжаем до тех пор, пока указатель не достигнет положения, при котором полукруги поменяются местами.

Во вложении поместил вариант решения без выдачи точного сообщения. Думаю, что доделать можно без труда.


Вроде так ...

[eoln]

ViktorR, сомнения рождают истину
Там как раз и алгоритм разделения суммы пополам. Допустим, есть конверты с суммами 7 4 5 6. Всего 22 рубля. На круге рисуем сектора из расчёта 1 рубль - 16,36 градусов. (Если предположить, что полный круг не 360 градусов, а 22 градуса, то будут только целые значения)
старт - 0 градусов
7 руб - 16,36*7=144 градуса
4 руб - 144+16,36*4 = 180 градусов
5 руб - 180+5*16,36 и т.д.
6 руб - ...

Видим, что есть углы, отличающиеся на 180 градусов, значит все конверты между ними образуют половину суммы. Осталось проверить, лежат ли конверты против друг друга (их кол-во = общее колво/2, т.к. расстояние между конвертами одинаковое). Если конвертов нечётное кол-во, то суть практически не меняется.

[ViktorR]

eoln, спасибо за пояснение. Как-то не сразу въехал.

[ViktorR]

eoln
обдумал Ваш алгоритм и пришел к выводу, что он не верен.
И вот почему:
Для понимания алгоритма достаточно представить суммы в конвертах грузиками (вес каждого - сумма в граммах), которые расположены равномерно на невесомой палке.
Ваш алгоритм вычисляет относительный вес суммы грузиков, начиная от начала такой палки. В том случае, когда этот вес будет равен 0.5 мы найдем точку равновесия этой системы грузиков.

Но! По условию задачи грузики расположены на кольце, т.е. в системе есть две точки, на которые надо опереть кольцо для равновесия.
Мы не знаем, с какого грузика (конверта) надо начинать проворачивать кольцо.
В Вашем алгоритме предполагается, что цент равновесия находится между первым конвертом и далее ...
См. пример, приведенный Вами - центр равновесия находится между двумя грузиками (по центру палки). Усложните задачу. Посмотрите предложенные мной варианты расположения сумм.

К тому же, ошибка, накапливаемая в предложенного Вами алгоритме может быть существенной, если разброс сумм большой. В этом случае отличие на 1 руб или 1 коп суммы конверта может дать вообще неверное решение.

[eoln]

К тому же, ошибка, накапливаемая в предложенного Вами алгоритме может быть существенной, если разброс сумм большой. В этом случае отличие на 1 руб или 1 коп суммы конверта может дать вообще неверное решение.

Я написал, что в круге может быть не 360 градусов, а например 22 псевдоградуса (или миллион - зависит от суммы) чтобы небыло ошибок округления при делении. Если в конвертах есть копейки, то всё надо выразить в копейках. Так что всё целочисленно!

Допустим, есть конверты с суммами 6 7 4 5. Всего 22 рубля.
старт - 0 псевдоградусов
6 руб - 98,2 градусов или 6 псевдоградусов
7 руб - 212,7 градусов или 13 псевдоградусов
4 руб - 278,2 градусов или 17 псевдоградусов
5 руб - 360 градусов или 22 псевдоградусов

Ищем отличие на 180 градусов (или на 11 псевдоградусов). Т.е конверты с 7 и 4 рублями образуют угол 180 градусов (или 11 псевдоградусов).

Те самые две точки опоры на весах - это 98,2 и 278,2 градусов на круге

Чуть более сложный пример: 4 4 5 3 1 4 5 9 1
Сумма: 36 руб
Пусть в окружности: 36 псевдоуглов
Образуют псевдоугды: 0 4 8 13 16 17 21 26 35 36
Половина окружности: 18 псевдоградусов
"Умным" циклом находим пары чисел - это (8 и 26) (17 и 35)
Это конверты с суммами:
а) (5 3 1 4 5) и (9 1 4) + (4) // кол-во конвертов отличается не более чем на 1 шт., значит линию можно провести
б) (4 5 9) и (1) + ( 4 4 5 3 1) // кол-во конвертов отличается более чем на 1 шт., значит линию нельзя провести
Так что начало отсчёта можно брать произвольное

P.S. Сразу скажу, что алгоритм можно упростить (если сумма выраженная минимальной единицей измерения нечётна, то разделить нельзя и т.п.).

[ViktorR]

Большое спасибо за дополнительное пояснение.
Как-то медленно, но наконец то въехал во фразу

перебором массива gr ищем те углы, которые отличаются на 180 градусов

Т.е. предложенный Вами код надо дополнить перебором массива gr для поиска элементов, между которыми разница составит 180 град.
Замечательно! Теперь у меня есть два решения.

[eoln]

Сообщение от ViktorR

Т.е. предложенный Вами код надо дополнить перебором массива gr для поиска элементов, между которыми разница составит 180 град.

Ага, именно так, впрочем в первоначальном варианте цикл тоже был, правда я для него код не писал. Только всё-таки в псевдоградусах лучше (ИМХО, конечно).

[Demius]

4. Найдите карточку

На столе в виде прямоугольника N×M лежат карточки, на которых написаны числа. Карточки лежат числами вниз. Известно, что в каждой строке числа упорядочены по возрастанию слева направо и в каждом столбце числа упорядочены по возрастанию сверху вниз. Задаётся число X. За возможно меньшее количество переворачиваний карточек требуется найти карточку с числом X или заявить, что такой карточки на столе нет.

Решение такое:
Наиболее эффективным алгоритмом поиска элемента в массиве является бинарный поиск (или метод дихотомии). Но при решении данной задачи необходимо учесть то, что данного числа может и не быть. Поэтому требуется всё время учитывать этот факт. Сам алгоритм решения можно представить следующим способом:

начало
Переворачиваем карточку (1, 1) и (n, m)
Если искомое число меньше числа на карточке (1, 1) или больше числа на 
  карточке (n, m) 
	  то говорим что этого числа нет
	  иначе 
		Переворачиваем карточку с номером (1, m) 
		l = 1
		r = m
		Пока не найдём нужную строку 
		Повторяем
			med = округлённое ((l + r) / 2)
			Переворачиваем карточку (med, m)
			Если искомое число меньше чем число на карточке (med, m) 
			  то r = med
			  иначе l = med + 1
		кц
		ls = 1
		rs = n
		Пока не найдём нужное число или не покажем, что его нет	
		Повторяем
			med = округлённое ((ls + rs) / 2)
			Переворачиваем карточку (med, l)
			Если искомое число меньше чем число на карточке (med, l) 
			  то rs = med
			  иначе ls = med + 1
		кц
		Если среди перевёрнутых карточек найдётся  две таких,  для которых
  выполняется условие: (число на первой больше числа на второй) и (искомое
  число  больше первого числа, но меньше второго)
то выходим из цикла и говорим, что этого числа нет
конец.

[Poma][a]

Господа, постом выше представлен наш вариант решения задачи № 4.

Единственное человек, выкладывающий задание, по-своему незнанию правил форума, не выделил псевдокод соответствующим тегом..

[Poma][a]

Ладно, т.к. замечаний\предложений\etc не поступала, то вылажу-ка я задачу №5.

Теория
Задача №5

Само задание :
5. Двоичные числа по кругу

Заданы натуральные N и K. Требуется расположить по кругу все N-разрядные двоичные числа, в записи которых содержится ровно K единиц, чтобы соседние числа различались только в двух разрядах. Ведущие разряды двоичного числа могут быть нулевыми.
Например при N=4 и K=2 числа можно расположить так:
1100
1010
1001
0101
0011
0110
Опишите алгоритм, как это можно сделать при произвольных N и K.

Решение : При рассмотрении примера можно сделать вывод, что сначала мы должны поставить все единицы в начало, затем
постепенно двигать каждую единицу, начиная с последней единицы (чтобы найти её будем рассматривать все цифры в
записи двоичного числа последовательно, начиная с самой левой цифры, и как только i-тая цифра станет равна не
1, то i-1 цифра будет называться последней). То есть, любое число, данное нам, мы можем представить так :
k единиц, n-k нулей. Тогда 2 число, полученное при выполнении алгорита, можно представить так :
k-1 единиц, 0, 1, n-k-1 нулей. Далее мы будем продолжать сдвигать единицу до тех пор, пока она не окажится n-ой
цифрой в записи числа.

После этого мы снова найдем последнюю единицу и снова будем сдвигать её.

Так будем продолжать до тех пор, пока мы не сможем найти последнюю единицу.

Но мы понимаем, что числа, которые мы получим в ходе выполнения алгоритма, не будут являться правильным ответом.

Тогда мы найдем последнюю единицу' (чтобы найти её будем рассматривать все цифры в записи двоичного числа
последовательно, начиная с самой правой цифры, и как только i-тая цифра станет равна 1, то эта i-тая цифра
будет называться последней единицей') И будем выполнять такие действия : на месте последней единицы' запишем
0, а на p-том месте (где p = позиция последней единицы' + k) поставим единицу.

Будем продолжать искать последнюю единицу' и выполнять алгоритм для неё до тех пор, пока p не станет равна
n-1.


Тогда мы получим ту же самую задачу, но кол-во нулей будет на 1 меньше (без учета ведущих нулей). Тоесть
можно представить получившееся число в виде k единиц, n-k-1 нулей. Теперь будем продолжать выполнять алгоритм,
до тех пор пока кол-во нулей (без учета ведущих) не станет = 0.

После этого все двоичные числа, состоящие только из n разрядов и k единиц,
будут выведены на экран.