Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 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
15-1345146034
AntiUser
2012-08-16 23:40
2013.03.22
Есть знатоки SVG?


15-1354292775
Очень Злой
2012-11-30 20:26
2013.03.22
Оптимизировать код


15-1351629002
Юрий
2012-10-31 00:30
2013.03.22
С днем рождения ! 31 октября 2012 среда


1-1301162465
Вячеслав
2011-03-26 21:01
2013.03.22
Интеграция апплета в подкатегории панели управления Windows 7


15-1343292116
Petr V. Abramov
2012-07-26 12:41
2013.03.22
В этом году ж, оказывается, круглая дата!





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский