Форум на Исходниках.RU

Подкиньте алгоритмик... plz

S.Yu.Gubanov — Tue, 26 Nov 2002 08:50:04 +0000

S.Yu.Gubanov: Понятно, что "The friend printed first on the line is considered to be the winner of the game" - это чушь. Входной информации недостаточно, чтобы определить победителей. А также "It is guaranteed that for every test case there will be at least one possible scheduling of the games" тоже не очевидно, что есть всего один возможный граф...

Следующая прога для заданных начальных условий (2,4,1,5) выполняется на P4 1800Mhz не более чем за 0.016 сек (часто за 0.000 сек)

procedure TForm1.Button1Click(Sender: TObject);
type TVertex = Array[0..100] of integer; //Игроки
TConnection = record v1, v2: integer; end;
TConnections = Array[0..10000] of TConnection; //Партии

var Vertex: TVertex;
HighVertex: integer;
Connections: TConnections;
HighConnections: integer;
t,i,j: integer;
suc: boolean;
dt: cardinal;
begin
Randomize;
suc := False; //не удалось найти решение
ProgressBar1.Max := 1000; //максимальное количество попыток
ProgressBar1.Position := 0;
dt := GetTickCount; // засекаем время потраченное на поиск решения
//работаем до тех пор пока не найдется решение или пока не надоест искать
while (not suc) and (ProgressBar1.Position < ProgressBar1.Max) do
begin
ProgressBar1.Position := ProgressBar1.Position + 1;
// Вводим начальные данные
Vertex[0] := 2; // первый игрок играл 2 раза
Vertex[1] := 4; // второй игрок играл 4 раза
Vertex[2] := 1; // третий игрок играл 1 раз
Vertex[3] := 5; // четвертый игрок играл 5 раз
HighVertex := 3;
//сейчас будем искать кто с кем чем занимался...
HighConnections := -1;
//сделаем, например, 100000 попыток,
//макс число вариантов = 10000, так что 100000 попыток хватит на все
for t := 1 to 100000 do
begin
//Случайно выбираем пару игроков
i := Random(HighVertex + 1);
j := Random(HighVertex + 1);
if (i <> j) and (Vertex[i] > 0) and (Vertex[j] > 0) then
begin
inc(HighConnections);
Connections[HighConnections].v1 := i;
Connections[HighConnections].v2 := j;
//Эти игроки свою партию отыграли
dec(Vertex[i]);
dec(Vertex[j]);
end;
end;
//Проверяем замкнулся ли граф
suc := True;
for i:=0 to HighVertex do if Vertex[i] > 0 then suc := False;
end;
dt := GetTickCount - dt;
if not suc then
ShowMessage('Не удалось отыскать решение, попробуйте увеличить количество попыток.')
else
begin
Memo1.Clear;
Memo1.Lines.Add('Количество партий = '+IntToStr(HighConnections + 1));
for i:=0 to HighConnections do Memo1.Lines.Add(IntToStr(Connections[i].v1+1)
+' '+IntToStr(Connections[i].v2+1));
Memo1.Lines.Add('Время поиска '+FloatToStr(dt*0.001)+' сек');
end;
end;

P.S.
Забыл что в результирующем списке надо упорядочить так чтоб в последующей строке был победитель из предыдущей строки... Хм... возможно это и даст всего один возможный вариант...

Подкиньте алгоритмик... plz

R_Ally — Mon, 25 Nov 2002 16:05:48 +0000

R_Ally: Как я понял, это задача из какой-то олимпиады, причем явно не нашей
(судя по языку). Если есть линк на "сайт-исходник" - кинь на форум -
там могут быть дополнительные условия.
Например, непонятно, выбывает ли проигравший из турнира или нет,
на какой машине нужны эти 0.5 сек. и т.п.

Подкиньте алгоритмик... plz

PropellerMan — Mon, 25 Nov 2002 10:41:10 +0000

PropellerMan: Я тут внимательно посмотрел на пример выходного файла и мне кое-что пришло на ум: может быть стоит выбрать игрока, у которого больше всего сыгранных партий и составить пары с ним и другими игроками. Затем, если в какой-то момент после составления очередной пары у него стало меньше игр чем у кого либо, то проделать тоже самое с тем, у кого на данный момент больше всего игр. И т.д. до нулей.
P.S. Походу по входным данным можно составить уйму возможных пар (без учета последовательности игр).

Подкиньте алгоритмик... plz

Slava — Mon, 25 Nov 2002 08:07:52 +0000

Slava: Есть N друзей. 2<=N<=100. Сначала берётся один из них и играет с любым другим в шахматы. Победитель вновь выбирает себе любого из друзей и играет с ним и т. д.

Входной файл:
Первая строка - N
Вторая - a[1]-a[n], где a[i] - кол-во сыграных партий i'ым другом 1<=a[i]<=10000

Выходной файл:
Первая строка: Кол-во сыгранных партий всего. (M)
Следущие М строк в формате: победитель проигравший.

Вот оригинальный текст, если вдруг задачу я перевёл криво:

Time Limit: 0.5 sec

N friends gathered in order to play chess, according to the following rules. In the first game, two of the N friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the N friends played, find a schedule for the games, so that the above rules are obbeyed.

Input

The first line contains the number of friends N (2<=N<=100). The second line contains N integers, separated by blanks, representing the number of games each friend played. The first number represents the number of games played by the first friend, the second number represents the number of games played by the second friend and so on..

Output

The first line should contain the number of games played by all the friends (it will be an integer between 1 and 10 000, for every test case). Let's suppose this number is G. Then, G lines follow, each of them containing two integers, describing the games. The first line contains the numbers of the two friends who played the first game. The friend printed first is considered to be the winner. Each of the next G-1 lines contain the integers a and b, where a<>b and a or b is the winner of the previous game. The friend printed first on the line is considered to be the winner of the game.
It is guaranteed that for every test case there will be at least one possible scheduling of the games.

Sample Input

4
2 4 1 5

Sample Output

6
4 3
4 1
2 4
2 1
4 2
2 4

Люди, ещё кое-что. Я не хочу вас затруднять лишними проблемами, поэтому буду очень рад просто алгоритму, а не исходнику задачи. Хочется решить именно эту задачу, т.к. из всех, которых нам дали - она самая сложная, хотя могу взять и другую.

Единственное что сам раскопал: Нечётное кол-во партий у i-ого друга означает, что он хоть одну партию да проиграл, ну и само собой общее кол-во партий=сумме(a[i])/2, где 1<=i<=n.

Вроде всё. Заранее благодарен.