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

← →
Думкин © (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 - простое число)
Все, он победил на первом ходу.

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

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

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

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

> Думкин

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

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

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

И ещё смотри

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

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

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

2^15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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