Новые сообщения · Правила  
  • Страница 1 из 1
  • 1
Модератор форума: Berestovskiy  
Паскаль. Задача о гирях.
Два игрока имеют гири на чашах весов. Гири первого игрока (N штук) стоят на первой чаше, а второго (M штук) - на второй.
Гири отличаются весом, для каждой гири задан свой вес. Двух гирь с одинаковым весом нет. В начальный момент суммарный вес гирь больше. Тот, кто ходит первый, убирает по одной гире со своей чаши, пока вес его гирь не станет меньше веса гирь противника. После этого ход переходит к противнику. Выигрывает тот, кто первым уберет все гири. Требуется определить, кто из них выиграет при оптимальной стратегии обоих игроковю

Входные данные: В первой строке входного файла содержатся два числа (через пробел) - N и M 0<N<=50000, 0<M<=50000. В последующих N+M строках расположены целые положительные числа а[i] (0<a[i]<=1000000, 1<=i<=N+M),веса гирь сначала первого, а затем второго игроков.

Выходные данные: в выходном файле должны отображаться последовательности убираемых гирь через пробел (каждая последовательность на новой строке), в последней строке номер выигравшего. (1 или 2).

Оптимальной стратегией будет "убирание гирь с минимальным весом". Как то так. Могу кинуть свой вариант решения, но как сказала учительница - оч долгий он у меня. Можно решить быстрее через подпрограмму процедуру.

Очень надо сделать!... Завтра сдавать...

1 | Автор: Lusy | 2010-11-10, 23:11   |  Репутация: [ + 0 ]
Я так понимаю если ваш вариант очень долгий, то в нём каждый шаг идёт поиск самой легкой гири и пересчитывается общая масса?

Отсортируйте массив с массами гирь для каждого игрока (тогда не прийдется искать) и храните общую массу в отдельной переменной, уменьшая ёё на вес убираемой гири.
В процедуре следует оформить действия для одного шага игры (т.е убирания гирь, до тех пор покаша весов не склониться в другую сторону).

massM, massN - суммы масс всех гирь на чашах весов для каждого игрока.
listM,listN - отсортированный массив гирь для каждого игрока.
submass - масса убира5емых за ход гирь
different - разница масс гирь на двух чашах весов.
i - глобальная переменная.
тогда:

Code

submass:=0;
different:=massM-massN;
while different>=submass do
   begin
     submass:=submass+listM[i];
     listM[i]:=0;
     inc(i);
   end;
massM:=massM-submass;

аналогично для второго игрока.

2 | Автор: Fireleo | 2010-11-11, 04:25   |  Репутация: [ + 30 ]
Quote (Lusy)
Очень надо сделать!... Завтра сдавать...

Не забывайте благодарить, того кто вам помог - повышайте ему репутации (зеленый плюсик)
3 | Автор: admin | 2010-11-11, 14:31   |  Репутация: [ + 22 ]
3 | Автор: admin | 2010-11-11, 14:31   |  Репутация: [ + 22 ]
Прошу прощения, изначально сориентировался на реализацию решения, а не на само решение.

При данной стратегии (убирая сначала самые легкие) выиграет тот у кого самая тяжелая гиря. Т.к. в любом случае перед самым последним ходом будет ситуация когда у обоих по одной гире, и тот у кого она тяжелей и сделает выигрышный ход.

4 | Автор: Fireleo | 2010-11-12, 02:18   |  Репутация: [ + 30 ]
  • Страница 1 из 1
  • 1
Поиск: