Задчка с олимпиады недавней

← →
Думкин_ (2012-02-14 16:30) [40]

> Извиняюсь.Я что то недопонял условие задачи.Как понять числа
> от 2 до 100.000(это какие числа на бочонках)и шаг прогрессии
> равен или больше двух?Можно хоть пару ходов описать для
> примера?А то вообще не пойму какие возможные ходы может
> сделать первый игрок,а потом и второй.Хотелось бы тоже попробовать
> порешать.

1. Числа на бочонках в таких пределах. Задача олимпиадная, надо код давать, проверяли потом на время - там поэтому оговорено.
2. Шаг прогресии - натуральное число от 2 и выше.

Ход - взятие бочонка. Вот 2, 3,5,7.

Первый берет 5, второй может взять 3, Первый тогда может взять только 7. Второму остается ничто. Он проиграл. Взять 2 он не может, т.к 2,3 уже не лежат ни в одной последовательности нужного типа.

← →
Думкин_ (2012-02-14 16:34) [41]

> Mystic © (14.02.12 14:06) [35]
>
> > Вот у тебя 4 бочонка с числами 2,3,5,7.
>
>
> Противоречит условию

Где?

> > На бочонках выставлены произвольные натуральные числа
> больше 2
>
>
> Но 2 не больше 2

А, ну это не принципиально. Больше или равно. На решение не влияет.

> Sha © (14.02.12 13:43) [31]
> построить дерево игры перебором сочетаний

А если 50?

← →
Думкин_ (2012-02-14 16:40) [42]

> oldman © (14.02.12 15:04) [37]
>
> > По заданному набору бочонков, необходимо сказать – выиграет
>
> > ли первый игрок или проиграет. Второй игрок играет без
> ошибок.
>
>
> И еще - неверная постановка задачи.
> Это нельзя сказать по набору бочонков.
> Это можно сказать по ходам первого.
>
> Правильно ставить задачу: "может ли выиграть первый игрок"!
>

Обидно пишешь, да. Можно сказать.

← →
Думкин_ (2012-02-14 16:44) [43]

> > Правильно ставить задачу: "может ли выиграть первый игрок"!

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

← →
Mystic © (2012-02-14 16:50) [44]

Цикл по простым числам (n) Обнулить C Цикл i = 1..N ++C[Data[i] mod n] Цикл i = 0..n-1 Если C[i] четно, то отмечаем все элементы из Data[i] сравнимые с i по модулю n как проигрывающие Все элементы проигрывают???

← →
Думкин_ (2012-02-14 16:56) [45]

> Mystic © (14.02.12 16:50) [44]

Ну, тут бы прокомментировать, я думаю. Мало того, что богомерзкое ++, так еще кто за что отвечает понять бы. :)

← →
Mystic © (2012-02-14 17:06) [46]

В реализации хороши будут битовые маски для C, и инструкция POPCNT для подсчета количества бит. Тогда

LoseN = 0 Цикл по простым числам (n) Обнулить C Цикл i = 1..N C[Data[i] mod n] |= 1 << i Цикл i = 0..n-1 Если POPCNT(C[i]) & 1 == 0 То LoseN |= C[i] i = BSF(~LoseN) Если i < N, То брать надо боченок i, Иначе брать бочонок бесполезно

← →
Думкин_ (2012-02-14 17:07) [47]

> Mystic © (14.02.12 16:50) [44]

Начало прогресии может быть другим простым числом.

← →
Думкин_ (2012-02-14 17:14) [48]

> Mystic © (14.02.12 16:50) [44]

Да. Похоже на правду. Ограничение по простым задано в условии. С другим подходом шел. Но так быстрее.

← →
Mystic © (2012-02-14 17:24) [49]

Комментировать...

LoseN = 0 Цикл по простым числам (n) Обнулить C Цикл i = 1..N C[Data[i] mod n] |= 1 << i // В C[i] у нас битовая маска индексов элементов, сравнимых с i по модулю n Цикл i = 0..n-1 // Если установлено четное число бит, то второй участник при выборе любого бочонка из этой группы также выбрать бочонок из этой группы и победить Если POPCNT(C[i]) & 1 == 0 То // Отмечает эти альтернативы как проигрывающие LoseN |= C[i] // Смотрим индекс первого нуля i = BSF(~LoseN) Если i <= N, То брать надо боченок i, Иначе брать бочонок бесполезно

← →
Думкин_ (2012-02-14 17:26) [50]

Я исходил из следующего:

Любая пара чисел задет полность все возможные последовательности. Они просчитавются через разложение на простые множители разности между ними.
То есть паре сопоставлем элементы в ее последовательности. Две такие пары эквиваленты если оба элемента пары встречются в последовательности другой. В итоге все множество дают максимум n(n-1)/2 множеcтв разных последовательностей.

теперь остается проверить, существует ли элемент, который присутствует в нечетных и отсутствует в четных. Есть - выигрывает, нет - увы.

Если все элементы являются участниками хотя бы одной пары с четным число элементов - дело табак.

Это теория. Реализацию дал Mystic.

← →
Думкин © (2012-02-15 08:15) [51]

Единственно, я реализацию по другому вижу. Все-таки по теории - через разбиение на классы эквивалентности. И потом как предложил Inovet. Но не все последовательности, а т.н. максимальные, каждая соответствует своему классу.

← →
Inovet © (2012-02-15 09:52) [52]

> [51] Думкин © (15.02.12 08:15)
> через разбиение на классы эквивалентности

Я предлагал найти все возможные приращения, Не указал там не все, ты уже поправил потом. Надо найти начало и приращение каждой:
(1, 2), (1, 3), (1, N)
(2, 3), (2, 4), (2, N)
(N - 1, N)

А что есть классы эквивалентности?

← →
Думкин © (2012-02-15 09:57) [53]

> Inovet © (15.02.12 09:52) [52]

Да не, не пойдет с ними. Поспешил.

Допустим 6, 12 выставили, а потом есть 8 и 9. Выбор любого возможен, но исключает выбор второго. Все-таки на уровне простых чисел только. Но как-то некузяво по всем цикл устраивать.

← →
Inovet © (2012-02-15 10:14) [54]

> [53] Думкин © (15.02.12 09:57)
> простых чисел

В условии натуральные числа. Или ты образно?

Можно сразу искать и всю последавательность и записывать в таблицу:

Приращение, Индекс первого, Индекс последнего, количество

Если пара уже была в последовательности с таким приращением, то её не учитываем. Ну и, для задачи достаточно найти первую с нечётным количеством.

← →
Думкин © (2012-02-15 10:19) [55]

> Inovet © (15.02.12 10:14) [54]

Не образно. Интересны только шаги с простыми числами ведь.

> Ну и, для задачи достаточно найти первую с нечётным количеством.

Почему? Этого мало.

← →
Думкин © (2012-02-15 10:34) [56]

> Inovet © (15.02.12 10:14) [54]

Максимальная последовательность - это последовательность, которая уже не может быть дополнена никаким элементом. Я подумал, что их можно любыми двумя их них определить, но это не так. Но минимальным в ней и простым числом (одним из разложения шага) получается. Это и дает решение.

← →
Inovet © (2012-02-15 10:40) [57]

> [56] Думкин © (15.02.12 10:34)
> Но минимальным в ней и простым числом (одним из разложения шага) получается.

2, 6, 10
минимальное 2, шаг 4, разложение 2^2
2, 4, 6, 8, 10
уже другая

← →
Inovet © (2012-02-15 10:42) [58]

> [57] Inovet © (15.02.12 10:40)
> уже другая

Что я не понял?

← →
Думкин © (2012-02-15 10:44) [59]

та же самая.
В твоем примере 2,6,10 - не максимальная для предложеного набора. Ее можно дополнить 4,8.

Кодируется как (2,2) - 2 начало, 2 - простое в шаге.

2,8,14 если максимальная то кодируется (2,2) или (2,3) Берем (2,2)

2,8,14,5 - (2,3)

2,8,14,6 - (2,2)

← →
Inovet © (2012-02-15 10:59) [60]

> [59] Думкин © (15.02.12 10:44)
> 2,6,10 - не максимальная для предложеного набора. Ее можно
> дополнить 4,8

Так. И что это для задачи даёт, если нет бочонков с числами 4, 8? Но зато есть дальше 12, 14, 16.
Получится две разных
2, 6, 10
и
10, 12, 14, 16
в одной 3, в другой 4 элемента.

← →
Думкин © (2012-02-15 11:01) [61]

Но, в общем-то при таком подходе можно избежать работы с простыми числами. Достаточно НОД разностей. Затраты в том и другом случае, наверное, можно сравнить.

← →
Inovet © (2012-02-15 11:01) [62]

> [60] Inovet © (15.02.12 10:59)
> Получится две разных
> 2, 6, 10
> и
> 10, 12, 14, 16
> в одной 3, в другой 4 элемента.

2, 6, 10, 14
и
10, 12, 14, 16
Хм

← →
Думкин © (2012-02-15 11:05) [63]

> 2, 6, 10
> и
> 10, 12, 14, 16
> в одной 3, в другой 4 элемента.

Если у тебя, 2,6,10,12,14,16

То тут получается не две, а одна максимальная последовательность.

2,6,10 - не максимальная, т.к ее можно дополнить. У нее изменится шаг с 4 на 2, но быть арифметической последовательностью она от этого не перестанет же.

← →
Inovet © (2012-02-15 11:27) [64]

Я понял. Не обязательно ей быть со всеми элементами.
Из набора 2,6,10,12,14,16
при ходах 10, 12, можно ставить все оставшиеся бочки
при ходах 2, 6, только 10, 14.
Так?

← →
Думкин © (2012-02-15 11:36) [65]

Нет. При ходах 2,6 можно поставить и 16 тоже.

← →
Inovet © (2012-02-15 11:46) [66]

> [65] Думкин © (15.02.12 11:36)
> Нет. При ходах 2,6 можно поставить и 16 тоже.

И 12? т.е. тоже все? Надо посмотреть, что такое арифметическая прогрессия.

> Inovet © (15.02.12 11:46) [66]

там элементы можно и так выбирать - 14, 6, 12 и т.п

Главное, чтобы бочонки стоящие на столе были элементами некоторой арифметической прогрессии. Были элементами, а не сами, в жестком порядке ее образовывали.

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

> [68] Думкин © (15.02.12 11:59)

В Вики определение неверное?
http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F

> [70] Думкин © (15.02.12 12:17)
> Верная, а что?

Ну всё, тогда понял. Проверяем не на сам интервал а на его разложение на простые. Или, если тупо, вообще все элементы со всеми простыми с 2 до ближайшего меньшего 100000.

> Inovet © (15.02.12 13:08) [71]

Ну. я писал выше - простые числа могут и не понадобиться. Что затратнее - вопрос открытый.

С простыми числами сложность выше. Факторизация - задача очень сложная. На ней держутся многие криптоалгоритмы. С НОДом на диких вариантах веселее будет.

> Но как-то некузяво по всем цикл устраивать.

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

> С простыми числами сложность выше. Факторизация - задача
> очень сложная.

Вряд ли натуральные числа будут настолько большими. Опять же, если мы получили НОД, то потом его надо все равно надо разбить на простые множители. Потому как если НОД = 6, то арифметическая прогрессия будет подпоследовательностью для НОД = 3 и НОД = 2. И на этом игра не закончится.

Из условия:

> Числа на них от 2 до 100 000.

sqrt(100000) = 316.23...

> Mystic © (15.02.12 14:28) [75]

А зачем раскладывать на простые? В моем варианте разложение не требуется. Каждая максимальная последовательность характеризуется минимальным членом в последовательности и минимальным полученым НОДом.

> Не обязательно по всем. Можно каждое число разложить на
> простые множители, и искать только в полученном множестве.

Разности?

> sqrt(100000) = 316.23...

Это да. Я думаю, что даже самый неоптимальный алгоритм на таких данных будет летать.

Задчка с олимпиады недавней Найти похожие ветки