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

[Poma][a]

День Добрый!
Вот и прошла дистанционная командная(была и личная, но я участвовал в командной) олимпиада.

Задания были подразделены на теорию (5 заданий) и практику (3 задания).
я, конечно, понимаю что возможно, пишу не в тот раздел, но т.к. люди ответы, которых я очень надеюсь увидеть в данной теме, так же посещают и раздел "Паскаль", я набравшись смелости, дерзнул создать тему здесь

Хочется разобрать полеты. Найти ошибки. Увидеть более эффективные и красивые решения.
И так, наверное лучше пойти по порядку..

И так :
Теория
Задание №1

1. Конверты

По краю очень большого круглого стола с равными интервалами разложены небольшие конверты, в каждом из которых лежат деньги. Известны суммы, лежащие в каждом конверте. Опишите алгоритм, позволяющий провести прямую через центр стола, разделяющую конверты на два множества с одинаковой суммой денег. Прямая не должна проходить по конвертам. Если такой прямой нет – сообщите об этом.
___________________________
Задание решал не я.
Но я пытался на наших "сходках" найти что-то более изящное, красивое...
Увы, мои попытки остались тщетны...
P.S. Что-то мне подсказывает что мы не правильно поняли суть задания

[eoln]

Ну если не в лоб, то предложу такой вариант

  gr[0] := 0;//массив углов, первый элемент нулевой
  for i := 0 to length(mas) - 1 do begin
    mas[i] := массив mas заполняем суммами из конвертов
    sum := sum + mas[i];//общая сумма в конвертах
  end;

  k := 0;
  for i := 0 to length(mas) - 1 do begin
    k := k + mas[i];
    gr[i+1] := 360*k/sum;//угол под которым как-бы расположен конверт на круглом столе
  end;
  
перебором массива gr ищем те углы, которые отличаются на 180 градусов, если таковые есть, то проверяем лежат ли конверты напротив друг друга на самом деле.
можно не простым перебором, а с доп условиями, чтобы ускорить поиск

При проверке углов надо учесть, что угол 180 градусов может быть неточен (179,999999999999 или 180,000000000000001).
Как избавиться? Можно ввести эпсилон и если надо, то дополнительным циклом проверить суммы в найденных полуокружностях (на всякий пожарный). Можно предположить, что в круге не 360 градусов, а SUM градусов (чисто гипотетически) - это избавит нас от деления, т.е. в массив градусов попадут только целые числа. В этом случае надо смотреть, чтобы углы отличались на SUM div 2 градусов.

[Poma][a]

eoln, огромное спасибо спасибо! Мы-то жестко тупанули, думая что задача супер-легкая, а оказалась она на геометрию... Жаль..

Ладно с 1 более-менее разобрались, так что продолжим :
Теория
Задача № 2
Что-то я тупанул, и сразу не выложил ссыль, исправляю свою ошибку (тыц)
Задача 2 - рекурсия, просто вбить, получить ответ, дальше чуть-чуть оформить и всё.

Так что давайте сразу перейдем к задаче №3.
Вот её решал я. И много нервишек она мне подпортила.
И так : Теория
Задача № 3
3. Преобразования числа

С написанным на доске числом производят следующее действие. Каждую его цифру возводят в квадрат, все результаты суммируют и результат выписывают на доску вместо исходного числа. Так продолжается сколько угодно раз. Опишите алгоритм, определяющий, можно ли таким образом получить из начального натурального числа N заданное натуральное число M? Обоснуйте конечность разработанного алгоритма.

Расскажу как всё было :
Что бы понять в чем загвоздка я написал программку решающую данную задачку. Чтож программка работала, но иногда долго не выводила ответ. Чтож отладка в помощь, и тут я увидел бесконечный цикл [145, 42, 20, 4, 16, 37, 89]. Что ж хорошо, осталось найти когда, как и почему он возникает. Как это сделать? Да давайте погоняем программку на других исходных данных при этом увеличив число, которое мы должны получить. Оказывается любое число попадает в этот цикл. Но ведь не я 1 нашел эти числа, давайте вобьем их в интернете
Вот ссылочки найденные на тот момент времени :
тыц
тыц

Чтож там найдем подтверждение моим догадкам, и увидим еще 1 цикл (единственное значение которого - 1).

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

При выполнении алгоритма уже в бесконечном цикле мы понимаем
что все значения повторяются. Они равны [145, 42, 20, 4, 16,
37, 89].

Мы находим еще один есконечный цикл. И его единственное значение равно 1.

При любом значении n (число к которому будет применен алгоритм)
мы, попадем в один из бесконечных циклов (разумеется если мы
раньше не достигнем значения m). И в случае если мы оказались
в бесконечном цикле (сумма квадратов числа n стала равна [145, 42, 20, 4, 16,
37, 89, 1]), то тогда мы должны вывести ответ "НЕТ" и прекратить
выполнение алгоритма.

Так же при трассировке стало понятно, что любое число(сумма которого не равно 1)
может достигнуть значение [145, 42, 20, 4, 16, 37, 89]. Следственно, если m равно
[145, 42, 20, 4, 16, 37, 89], то надо вывести ответ "ДА" и прекратить выполнение
алгоритма.

Если m равно 1 и изначальная сумма корней числа n равна 1, тогда надо вывести ответ
"ДА" и закончить выполение алгоритма.
Если же m равно 1, а изначальная сумма корней числа n не равна 1, тогда надо
вывести ответ "НЕТ" и закончить выполнение алгоритма.

Если sum = 1 или sum = 0 тогда вывести ответ "НЕт" и прекратить выполнение алгоритма.
Обобщив знания полученные в ходе решения задачи, можно составить следующий алгоритм
для более наглядного представления запишем его в псевдокоде :

констата
	Беск[145, 42, 20, 4, 16, 37, 89]

НАЧАЛО
	Прочитаем значение n;
	Прочитаем значение m;
	sum = сумма квадратов цифр числа n;
	
	Если sum равно m тогда начало
		Вывести "ДА";
		Прекратить выполнение алгоритма;
	все;
	Если (sum = 1) или (sum = 0) тогда начало
		Вывести "НЕТ";
		Прекратить выполнение алгоритма;
	все;
	
	Если m в Беск тогда начало
		Вывести "ДА";
		Прекратить выполнение алгоритма;
	все;
	
	
	пока sum <> m выполнять начало
		Если (sum в Беск) или (sum = 1) тогда начало
			Вывести "НЕТ";
			Прекратить выполнение алгоритма:
		все;
		
		sum := сумма всех цифр числа n в квадрате;

	все;
	
	Если m = sum тогда 
		Вывести "ДА"
	иначе
		Вывести "НЕТ"
КОНЕЦ.

Алгоритм будет являться конечным. Т.к. все "бесконечные циклы" были учтены и число n гарантированно окажется в
в бесконечном цикле(но может быть это не произойдет, т.к. мы найдем число m раньше). Следственно, рано или поздно число окажется или равно m
и алгоритм остановится или в бесконечном цикле и алгоритм прекратится.


Но есть 1 проблемка, мы не доказали что любое число гарантированно попадет в бесконечный цикл.
Вот тут я и повис...

[Аватар]

При разрядности числа больше 3 сумма квадратов его цифр всегда меньше исходного числа. Мало того, у этой суммы и разрядность меньше разрядности исходного числа. Нужно просто доказать, что 10^(n-1)>81n для n>3 И вычисляем спокойно, пока разрядность не станет меньше 4. А дальше что бы не зациклиться можно и не ориентироваться на магические цифры, а просто запоминать в массив полученные результаты и проверять на предмет совпадения.

[Poma][a]

При разрядности числа больше 3 сумма квадратов его цифр всегда меньше исходного числа. Мало того, у этой суммы и разрядность меньше разрядности исходного числа. Нужно просто доказать, что 10^(n-1)>81n для n>3

Гениально! Просто супер!

А дальше что бы не зациклиться можно и не ориентироваться на магические цифры, а просто запоминать в массив полученные результаты и проверять на предмет совпадения.

А вот тут наверное не соглашусь.
Ведь в бесконечный цикл мы точно попадем, и можем попасть раньше чем найдем нужное нам число. Всё-таки магические цифры нам нужны.. Или я что-то не так понял?

[Аватар]

Гениально! Просто супер!

Перебор

Получили очередное число, проверили нет ли такого в массиве. Если есть, то это начало бесконечного цикла. Если нет - добавили в массив и дальше

[Poma][a]

Получили очередное число, проверили нет ли такого в массиве. Если есть, то это начало бесконечного цикла. Если нет - добавили в массив и дальше

Хитро! Даже очень. Что-то я до такого не додумался...

Хотя наверное проиграет решение по быстродействию варианту с циклом Штайнхауса. Зато выдержит критику, которая в легкую сломит "магию"

[Татьяна Гном]

Если не слажно выложи пожалуйста решение второго задания теоретической и третью практическую если есть

[Poma][a]

Татьяна, задачу 2(по теории) решал не я. Но насколько помню ответом будут являться цифры 2 и 4. А 3 задачу (по практике), увы мы не решили...

[Татьяна Гном]

все равно спасибо))