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




Скачати 62.91 Kb.
НазваКількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до
Дата конвертації15.06.2013
Розмір62.91 Kb.
ТипДокументы
uchni.com.ua > Інформатика > Документы
1. Шаховий клуб

Нехай M — кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця – число від 1 до M, і жодна пара гравців не має однакового рівня гри. Впорядкуємо всіх шахістів за рівнем гри. Розглянемо події у порядку над­ход­ження. В кожний момент часу розглянемо послідовність X1, X2, ... , XM величин віку гравців з рівнем гри 1, 2, ... , M з тим зауваженням, що вік певного гравця вважатимемо нульовим, якщо він ще не прийшов до клубу на момент події. Таке припущення еквівалентне відсутності гравця: його ніколи не виберуть як супротив­ника. На початку розгляду послідовність X1, X2, ... , XM містить лише нулі, а подія першого типу полягає у зміні величини деякого числа Xi послідовності з 0 на певне натуральне число.

Нехай k та Xk — рівень гри та “поточний вік” гравця з деякої події другого типу. Тоді його суперником буде гравець з силою гри s(k) = min {j | j > kXj Xk}, якщо ця множина не порожня.

Побудуємо дерево відрізків (інтервалів) над послідовністю X1, X2, ... , XM, у якій кожна вершина зберігає максимальне значення Xj на відповідному відрізку індексів:

  • кореню дерева відповідає відрізок індексів [1.. M], тобто вся послідов­ність;

  • кожній вершині, якій відповідає відрізок довжини, більшої за 1, має дві дочірніх вершини, що є коренями піддерева відрізків на лівій і правій половині (рекурсивно).

Дерево відрізків дозволяє швидко змінювати значення Xi з підтриманням властивості, виділеної у тексті підкресленням, за O(log2 M) операцій таким чином:

  1. Змінимо значення максимуму у відповідному листі;

  2. Для кожної вершини на шляху від листа до кореня дерева змінимо значення максимуму на більше з двох дочірніх вершин.

Також дерево відрізків дозволяє знайти найменше t, при якому Xt > z при даному z (якщо воно існує), за допомогою наступного алгоритму.

  1. Починаємо з повного дерева (всього відрізку);

  2. Якщо поточне піддерево — лист, ми знайшли відповідь і припиня­ємо виконання алгоритму;

  3. Якщо максимум в лівій половині відрізку більше ніж z, оголошуємо ліве піддерево поточним, інакше оголошуємо праве піддерево поточним

  4. Переходимо до кроку 2.

Глибина дерева відрізків є O(log2 M), тому обидва алгоритми мають складність O(log2 M).

Складніше реалізувати запит на пошук s(k). Розглянемо такий алгоритм:

  1. Починаємо розгляд з кореня дерева.

  2. Повторюємо для поточного піддерева:

  • якщо k не належить до поточного піддерева, то жодна з його вершин не може бути відповіддю;

  • якщо k належить до правого піддерева поточного піддерева, оголошуємо праве піддерево поточним (у цьому випадку жодна з вершин лівого піддерева не може бути відповіддю);

  • інакше, тобто якщо максимум Xj в лівому піддереву більший за Xk, рекурсивно знаходимо s(k) для лівого піддерева. Якщо відповідь не існує в лівому піддереві, то повертаємо найменше t з правого піддерева, при якому Xt > Xk.

Кількість рекурсивних викликів алгоритму пошуку s(k) є O(log2 M). Ключовим спостереженням є те, що пошук найменшого допустимого t правого піддерева може відбутися не більше одного разу, тому також потребує O(log2 M) часу. Тому загальна складність дорівнює O(log2 M).

Зведемо початкову задачу до щойно розв'язаної.

  1. Впорядкуємо гравців за зростанням рівня гри, а при рівності — за зростанням віку (наприклад, швидким методом Хоара);

  2. Замінимо рівень гри кожного гравця на його позицію у впорядкованій таким чином послідовності.

Вперше на Київських міських учнівських олімпіадах з інформатики викорис­тан­ня дерева відрізків передбачалося у 2007 році (ІІ тур, задача 5 «Комарі»).

2. Факторіали


Подамо N! добутком 2m∙5nN0, де N0 не кратне ні двом, ні п’ятьом,

m = [N/2] + [N/22] + [N/23] + ...
n = [N/5] + [N/52] + [N/53] + ...

де [x] — ціла частина числа x. Легко бачити, що nm.

Міркування щодо m такі. У добутку N!=1∙2∙…∙N кожне друге число кратне 2, кожне четверте — кратне числу 4 = 22, кожне восьме — кратне числу 8 = 23 і т.і. Серед чисел 1, 2, … , N саме [N/2] кратні 2. Поділивши кожне парне число на 2, отримаємо у добутку [N/22] парних чисел (тих, що спочатку були кратні 4). Поділивши й ці парні числа на 2, то отримаємо [N/23] парних чисел (тих, що спочатку були кратні 8)… Міркування щодо n аналогічні.

Шуканим кодом буде (N0 ∙ 2m n) mod 1000 (лишок при діленні на 1000).

Розглянемо таку допоміжну задачу: підрахувати (N!/pmax) mod pk , де p — просте число, а (N!/pmax) — це N!, поділене на p максимальну можливу кількість разів, так щоб результат все ще був цілим, k — довільне натуральне число. Спочатку маємо:



В кожній великій дужці p множників, окрім, можливо, останньої, де множників може бути менше (якщо N не кратне p). Надалі вважатимемо, що N не кратне p: це не суттєво для подальших міркувань. Перші p – 1 множник у дужці не ділиться на p, але p-ий ділиться. Запишемо такі p-ті множники окремо наприкінці виразу:

. (1)

З рівності: виплаває: . Тут степінь max у знаменнику кожного дробу свій і є найбільшим невід’ємним цілим числом, при якому відповідне відношення є натуральним числом.

Нас цікавить не N!/pmax, а (N!/pmax) mod pk, тому усі множники більші за pk можна замінити на їхню остачу від ділення на pk: apk + b = b (mod pk). Першу частину подання (1) перетворимо на добуток багатьох однакових множників:

.

Якщо N кратне pk, то друга група множників, виділена дужками, відсутня. Позначимо:

  • Bp,k = (1∙2 ∙∙∙ (p – 1) (p + 1) ∙∙∙ (2p – 1) (2p + 1) ∙∙∙ (pk1)) mod pk ;

  • SM,p,k = (1∙2 ∙∙∙ (p – 1) (p + 1) ∙∙∙ M) mod pk .

Тоді: .

Bp,k обчислимо так:

Bp,k = 1
для всіх i від 1 до pk при i не кратному p:
Bp,k = (Bp,k * i) mod pk

SM,p,k обчислимо так:

SM,p,k = 1
для всіх i від 1 до M при i не кратному p:
SM,p,k = (SM,p,k * i) mod pk

Тоді (N!/max) mod pk можна обчислити таким чином:

calcMod(N, p, k)
якщо N = 0, то
повернути 1

повернути (
Bp,k в степені (N div pk) за модулем pk *
SN mod pk,p,k *
calcMod(N div p, p, k)
) mod pk

В даному випадку треба використовувати алгоритм швидкого підняття до степеня за модулем:



Використовуючи цю рекурентну формулу можна порахувати xn mod m за O(log n).

Тепер відомо, як обчислити A = (N!/2max) mod 23 і = (N!/5max) mod 53. Звернемо увагу, що N!/2max = N0∙5n і N!/5max = N0∙2m.

Постає логічне питання: чи можна, знаючи (N0∙5n) mod 23 і величину n, знайти N0 mod 23? На щастя, в нашому випадку відповідь: «так».

Число 5n — непарне, а тому — взаємно просте з 23:

НСД(5n, 23) = 1 = 5na + 23b (2)

при певних цілих a, b. Теорему про подання найбільшого спільного дільника (НСД) такою сумою доводять при логічно послідовному викладі теорії цілих чисел і многочленів у курсі вищої алгебри для студентів вищих навчальних закладів. Для учнів загально освітніх шкіл такий матеріал подано, наприклад, у таких виданнях:

  • Вибрані питання елементарної математики/ За ред. чл.-кор. АН УРСР А.В.Скорохода. — Київ: Вища школа, 1982. — 455 с.;

  • О.Б.Рудик. Початки алгебри, аналізу, аналі­тич­­ної геометрії і теорії ймовір­нос­тей. Тернопіль: Навчальна книга – Богдан, 2005, 416 с.

Помноживши усі частини рівностей (2) на ^ А, отримаємо таке твердження: існує єдиний з точністю до кратного 23 розв’язок N0 рівняння: N0∙5n = A (mod 23).

Число N0 — непарне, тому лишок його при діленні на 8 належить до мно­жини {1, 3, 5, 7}. Ми можемо перебрати усі 4 варіанти значень і пере­вірити, при якому значенні справджується рівність (2). Таким чином ми можемо визна­чи­ти A0 — лишок від ділення N0 на 23 . Аналогічно ми можемо визначити B0 — лишок від ділення N0 на 53, перебравши 100 лишків при діленні на 125, що не кратні 5.

Знаючи лишки від ділення ^ N0 на 23 і на 53, можна обчислити лишок від ділення N0 на 23∙53 = 1000. Для цього достатньо перебрати 1000 можливих лишків від 0 до 999 і перевірити, чи при діленні на 23 лишок буде A0 , а при діленні на 53 лишок буде B0. Iснування розв’язку випливає з китайської теореми про лишки. Учням, не знайомим з цією теоремою, можна запропонувати такі міркування:

  • 5∙0 = 0, 5∙1 = 5, 5∙2 2, 5∙3 7, 5∙4 4, 5∙5 1, 5∙6 6, 5∙7 3;

  • розв’язати рівняння: B0 + 125b = A0 + 8a відносно цілих a,b можна перебором 8 лишків b при діленні на 8 до досягнення кратності 8 таких виразів:

B0 + 125b A0 B0 + 5b A0 .

Як уже зазначено, остаточна відповідь має вигляд: (N∙ 2mn) mod 1000.






Схожі:

Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconПлан правила поведінки; Технічних фол гравця; Бійка; П'ять/шість фолів Гравця; Фоли команди
Належний плин гри вимагає повного І лояльного співробітництва із Суддями І помічниками суддів членів обох команд, включаючи Тренерів,...
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconТема: число гравців, заміни, покарання в футболі
Мета: ознайомити студентів з кількість гравців, порядком заміни гравців та порушеннями на футбольному полі
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconA означає відстань на числовій прямій від початку відліку до точки, що відповідає числу a
Це пов'язано з тим, що не має чітко сформульованих правил для їх розв'язання. Тому розглянемо необхідний план дій на випадок, коли...
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconКількість речовини. Моль — одиниця кількості речовини. Число Авогадро
Але для хіміка поряд з цим важливо ще знати число структурних частинок (атомів, молекул або йонів), які містяться в цій порції речовини,...
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconВ акваріум, довжина якого 7 дм, ширина 4 дм І висота 35 см, налили...
Число а складає 75% від числа b І 40% від числа с. Число с на 42 більше за число b. Знайдіть числа а І b
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconТема. Послідовності
В усіх завданнях передбачається, що вихідний набір даних містить ненульову кількість елементів (зокрема, число n завжди більше нуля)....
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconРозв’язати методом потенціалів транспортну задачу
Так як 70+40+30+60+50=20+90+80+60, то маємо закриту т-задачу, отже фіктивних пунктів вводити не треба
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconВася написав на дошці натуральне число. Петя помножив його на 3 І...
Число із сумою цифр 2014 не ділиться на 3, а число яке отримав Петя має вид, тому ділиться на 3
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconА б в г д 37 73 75
У саду в окремі ящики зібрали груші та яблука. Кількість ящиків з яблуками відноситься до кількості ящиків з грушами, як 7 Серед...
Кількість гравців в клубі. Розглянемо простішу задачу, в якій рівень гри кожного гравця число від 1 до iconВказівки щодо розв'язання завдання №29 відбірково-тренувальних зборів команди міста Києва
Вважаємо, що шукані числа X мають таку саму кількість цифр L, як І число N. Якщо це не так, доповнимо початок десяткового запису...
Додайте кнопку на своєму сайті:
Школьные материалы


База даних захищена авторським правом © 2014
звернутися до адміністрації
uchni.com.ua
Головна сторінка