Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
ВнизЗадчка с олимпиады недавней Найти похожие ветки
← →
Думкин © (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 уже не лежат ни в одной последовательности нужного типа.
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.078 c