Отправлено: 07.05.17 20:50. Заголовок: 27 из нестандартного варианта Д.В. Богданова

Здравствуйте, уважаемый Константин Юрьевич. Вопрос насчёт эффективности решения этой задачи. Чтобы исключить пары с равными элементами, я создал список уникальных элементов, кратных 6. Однако будет ли такое решение эффективным по памяти? Ведь можно предположить, что все введённые элементы будут делиться на 6 и, соответственно, размер списка будет зависеть от N. С решением автора ознакомился, но сам до такой модели, думаю, не дошёл бы на экзамене. Буду очень благодарен за ответ. Решение

 Отправлено: 07.05.17 21:19. Заголовок: Добрый вечер! Привед..

Добрый вечер!
Приведённое решение не будет эффективным. Действительно, заранее неизвестно, сколько элементов кратно 6.
Хочу обратить внимание на "геометрические" 27-ые задания СтатГрада прошлого года. В их решении комбинаторика также играла важную роль. Поэтому лучше "подтягивать" комбинаторику, она пригодится не только в 10 и 27 задании, но и в 23 и в некоторых других.
Если получится разобраться с решением этого 27-го номера, то можно усложнить условие: "Найти количество пар, произведение которых кратно 6 ИЛИ КРАТНО 5". Но решение будет гораздо сложнее.
С уважением,
Дмитрий Богданов

 Отправлено: 07.05.17 21:35. Заголовок: Спасибо большое за о..

Спасибо большое за ответ, Дмитрий Валериевич! Можете посоветовать какие-либо материалы в этом направлении?

 Отправлено: 07.05.17 22:08. Заголовок: Пожалуйста. Именно в..

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

 Отправлено: 08.05.17 03:50. Заголовок: Что за геометрически..

Что за геометрические задания 27-го?

 Отправлено: 08.05.17 12:01. Заголовок: Victor1010, например..

Victor1010, например, такое задание: https://inf-ege.sdamgia.ru/test?pid=11283
В прошлом учебном году почти все задания от СтатГрад были подобного типа.

 Отправлено: 10.05.17 10:08. Заголовок: Можно более простую ..

Можно более простую формулу использовать для получения ответа.
par = (M2 * M3) + ((N - 1) + (N - M6)) / 2 * M6

Это формула арифместической прогрессии (сумма пар с элементом кратным 6)
((N - 1) + (N - M6)) / 2 * M6

 Отправлено: 10.05.17 10:25. Заголовок: nikson, если код на ..

nikson, если код на C/С++, то может возникнуть ошибка. Когда ((N - 1) + (N - M6)) - нечётное число, например, 5, то 5 / 2 = 2 и дальнейшее умножение на чётное M6 ситуацию не исправит. Надо либо делить на 2.0, переходя к вещественным числам, либо умножение выполнять перед делением.
Потому я и не стал выносить за скобки m6, так как в выражении m6 * (m6 + 1) / 2 очень наглядно, что либо m6 + 1, либо само m6 является чётным, поэтому вся дробь корректно сократится на 2.
Если программа на Бейсике, то при делении на 2 тоже возможен переход к вещественному типу. В рассматриваемом случае ошибки не будет, но кое-где это делать не желательно.

 Отправлено: 14.05.17 23:33. Заголовок: Только сейчас понял,..

Только сейчас понял, что неправильно интерпретировал условие задачи. Ибо 1 ≤ 𝑖 < 𝑗 ≤ N означает, что у элементов должны быть разные индексы, а не значения.

 Отправлено: 15.05.17 01:14. Заголовок: novelldd, да, именно..

novelldd, да, именно индексы. Первый индекс меньше второго.
Если изменить задачу, полагая, что порядок следования элементов не важен, то есть учитывать обе пары (a_i, a_j) и (a_j, a_i), то задача даже немного усложнится. Просто умножить на 2 количество пар будет нельзя - ведь могут встречаться пары, в которых a_i = a_j и их нужно добавлять к общему количеству пар лишь однократно.
У меня есть идея сделать для некоторых 27 заданий не два уровня "А" и "Б", а ещё больше. Например, для этой задачи уровень Б2 - это или количество неупорядоченных пар или количество упорядоченных троек. Уровень Б3 - количество упорядоченных и неупорядоченных m-ок (т. е. наборов из m элементов, m задаётся из ввода). Разумеется, в подобных Б3 скорее всего уже потребуются динамические массивы. В этом случае задания из ЕГЭ будут плавно перетекать в олимпиадные задания. ))