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

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

Есть два игрока. Есть мешок с бочонками. На бочонках выставлены произвольные натуральные числа больше 2. Все числа разные. Игроки берут бочонки по очереди. При этом, они знают какой именно бочонок и с каким номером возьмут – игра в открытую.
Все выставляемые номера должны быть членами некоторой арифметической прогрессии. При этом шаг прогрессии больше либо равен 2. Игра заканчивается, когда нельзя сделать ход. Если в мешке что-то осталось, то выиграл тот, кто ходил последним. Если нет – ничья.

По заданному набору бочонков, необходимо сказать – выиграет ли первый игрок или проиграет. Второй игрок играет без ошибок.

Ограничения для счета - 15 бочонков. Числа на них от 2 до 100 000.

← →
Думкин © (2012-02-14 10:03) [1]

Первый игрок - делает ход первым.

← →
Омлет © (2012-02-14 10:17) [2]

Если первый игрок возьмет бочонок с максимальным номером, то он же в любом случае выиграет? Или в прогрессию можно и в обратную сторону строить?

← →
Anatoly Podgoretsky © (2012-02-14 10:19) [3]

> Думкин (14.02.2012 09:57:00) [0]

Несправедливо, второй играет без ошибок, игрок 1 обречен.

← →
Думкин © (2012-02-14 10:23) [4]

> Омлет © (14.02.12 10:17) [2]

Все выбранные элементы - члены какой-либо прогрессии. Порядок не важен.

← →
Inovet © (2012-02-14 10:24) [5]

Если есть бочонок с числом меньшим 100000 - 1 то проиграет, иначе выиграет.

← →
Думкин © (2012-02-14 10:27) [6]

> Inovet © (14.02.12 10:24) [5]

Не. Задача со школьной олимпиады по информатике для 11-х классов. Т.е. есть некоторый алгоритм как можно узнать - и не в две строки.

← →
Inovet © (2012-02-14 10:27) [7]

> [5] Inovet © (14.02.12 10:24)
> Если есть бочонок с числом меньшим 100000 - 1

т.е. наоборот условие - если нет с числом 99999.

А что там, если первый с ошибкой сделает ход? Надо подумать.

← →
Inovet © (2012-02-14 10:28) [8]

> [6] Думкин © (14.02.12 10:27)
> Т.е. есть некоторый алгоритм как можно узнать - и не в две
> строки.

Как раз на ишибки первого.

← →
Думкин © (2012-02-14 10:30) [9]

> А что там, если первый с ошибкой сделает ход?

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

Ну, с ничьей все понятно - как.

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

> [9] Думкин © (14.02.12 10:30)

Ну тогда при наличии числа 99999 первый его ставит и выигрывает, если такого нет, то он ставит любое меньше 99999, второй ставит 100000 и выигрывает.

← →
Думкин © (2012-02-14 10:37) [11]

> Inovet © (14.02.12 10:34) [10]

Я не понял. Вот у тебя 4 бочонка с числами 2,3,5,7. Где тут 999999? Может все-таки, перед тем как бросаться на мельницу внимательно прочитать условие?

← →
Омлет © (2012-02-14 10:53) [12]

1. Сначала считаем разницу каждого с каждым - получаем матрица 15х15. Затем считаем количество одинаковых ячеек матрицы.
2. Если все ячейки с одни числом - ничья.
3. Если есть нечетное количество одинаковых ячеек - первый может выиграть. Иначе - выиграть не сможет.

← →
Думкин © (2012-02-14 10:57) [13]

> Омлет © (14.02.12 10:53) [12]

2,4,10, 48, 100. Ничья. Хотя ячеек с одинаковым - ни одной.

← →
Омлет © (2012-02-14 11:01) [14]

> Думкин © (14.02.12 10:57) [13]

Да, что-то я туплю.

← →
Inovet © (2012-02-14 11:04) [15]

> [11] Думкин © (14.02.12 10:37)
> Может все-таки, перед тем как бросаться на мельницу внимательно
> прочитать условие?

Членами последовательности, порядок не оговаривается. Понятно.

← →
Думкин © (2012-02-14 11:06) [16]

> Inovet © (14.02.12 11:04) [15]

да, входя в некоторую последовательность, а не сами образуют.

← →
oldman © (2012-02-14 11:06) [17]

> Если в мешке что-то осталось, то выиграл тот, кто ходил
> последним.

Чтобы в мешке ничего не осталось, значит либо ВСЕ числа есть прогрессия (1), либо игрок может брать бочонок, не выставляя его (2).
Если (1), легко просчитать количество бочонков и шаг прогрессии,
Если (2), сложнее...

← →
Думкин © (2012-02-14 11:10) [18]

> oldman © (14.02.12 11:06) [17]

Я выше и написал:

> Ну, с ничьей все понятно - как.

← →
Inovet © (2012-02-14 11:17) [19]

Посчитать количество членов вех возможных последовательностей. Найти такой член, который принадлежит только с нечётным количеством.

← →
Омлет © (2012-02-14 11:17) [20]

Перебор не катит? )

← →
Думкин © (2012-02-14 11:18) [21]

> Inovet © (14.02.12 11:17) [19]

ага

← →
Думкин © (2012-02-14 11:21) [22]

> Омлет © (14.02.12 11:17) [20]
>
> Перебор не катит? )

Смотря какой. Но Inovet уже фактически решил.

← →
Думкин © (2012-02-14 11:59) [23]

> о Inovet уже фактически решил.

Но не решил все-таки. Расслабляться рано.

← →
Омлет © (2012-02-14 12:15) [24]

> Но не решил все-таки. Расслабляться рано.

Я что, код надо?

← →
Думкин © (2012-02-14 12:16) [25]

> Омлет © (14.02.12 12:15) [24]

Ну, вот он пишет, что все возможные последовательности. А это не так. Да и много их таких может быть.

← →
oldman © (2012-02-14 13:12) [26]

Задача первого игрока после первого хода второго свести все к последовательности с известным шагом (2, 3, 5, 7, 9, 11 и т.д.).
Тогда подсчетом чисел выясняется победитель.

← →
Inovet © (2012-02-14 13:22) [27]

> [26] oldman © (14.02.12 13:12)
> Задача первого игрока после первого хода второго свести
> все к последовательности с известным шагом

Это ему неизбежно придётся делать. Надо первый ход сделать правильно. Для этого отсортировать бочонки по возрастанию и перебирать все возможные последовательносьти от позиций 1, 2 затем 1, 3 и т.д. до 1, N. Запоминать количество елементов в каждой. Найти, принадлежащие только последовательностям с нечётным количеством.

← →
oldman © (2012-02-14 13:29) [28]

Задача второго - первым же ходом выставить максимальное число с максимальным шагом.
Например 1, 2594 (2593 - простое число)
Все, он победил на первом ходу.

Вывод: если данный вариант возможен, первый игрок обречен.

← →
Inovet © (2012-02-14 13:39) [29]

> [28] oldman © (14.02.12 13:29)
> Вывод: если данный вариант возможен, первый игрок обречен.

Если у первого нет других вариантов.

← →
? (2012-02-14 13:42) [30]

> Думкин

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

← →
Sha © (2012-02-14 13:43) [31]

построить дерево игры перебором сочетаний

← →
Inovet © (2012-02-14 13:43) [32]

> [28] oldman © (14.02.12 13:29)
> Вывод: если данный вариант возможен, первый игрок обречен.

И ещё смотри

> [15] Inovet © (14.02.12 11:04)

> [16] Думкин © (14.02.12 11:06)

← →
Inovet © (2012-02-14 13:45) [33]

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

Большое оно может быть.

← →
Sha © (2012-02-14 13:47) [34]

> Большое оно может быть.

2^15

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

> Вот у тебя 4 бочонка с числами 2,3,5,7.

Противоречит условию

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

Но 2 не больше 2

← →
oldman © (2012-02-14 14:59) [36]

Для каждого бочонка можно составить N прогрессий, в которые он входит.
Для каждой прогрессии определить количество входящих в него бочонков М.

Если существует бочонок, где для всех N М-нечетное число, ходить надо с него.
Тогда выиграет первый.
Иначе выиграет второй.

Шагов "прогрессий" всего 107 для 15 бочонков. Для одного их соответственно, максимум 14. Сокращая кратные, получим гораздо меньше N для каждого бочонка.

← →
oldman © (2012-02-14 15:04) [37]

> По заданному набору бочонков, необходимо сказать – выиграет
> ли первый игрок или проиграет. Второй игрок играет без ошибок.

И еще - неверная постановка задачи.
Это нельзя сказать по набору бочонков.
Это можно сказать по ходам первого.

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

← →
oldman © (2012-02-14 15:18) [38]

[36] - плохо читал ветку...

← →
Mystic © (2012-02-14 15:41) [39]

Имеет смысл рассматривать только простой шаг

← →
Думкин_ (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)
> простых чисел

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

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

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

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

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

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

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

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

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

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

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

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

та же самая.
В твоем примере 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)

> [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 элемента.

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

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

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

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

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

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

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

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

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

> [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...

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

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