25 Feb
2010
25 Feb
'10
7:15 a.m.
Sziasztok,
Balázs küldte az alábbi feladatot péntekre:
--------------------------------------------
Problem Statement
A contest is held between two teams of fighters. The first team is comprised
of N persons and the second is comprised of M persons. In the course of the
contest, each fighter of the first team will confront each fighter of the
second team once. To make the contest more entertaining and less protracted,
the organizers divided it into several rounds. In each of the rounds,
several fights occur simultaneously. Therefore, a fighter may only
participate in one fight per round. The contest must be divided into the
least number of rounds. One can easily see that this number is the maximum
between N and M. Now the exact schedule of fights must be determined. Return
a String[] containing exactly N elements. Each element of the return must
contain exactly M characters from the set {'1'-'9',
'A'-'Z', 'a'-'o'}.
Letters 'A'-'Z' stand for numbers 10-35 and 'a'-'o' stand
for numbers 36-50.
The j-th character of element i corresponds to the number of the round in
which fighter i of the first team encounters fighter j of the second team.
If there are several possible schedules, return the one with the
lexicographically least first element. If there still are multiple choices,
choose the schedule with the lexicographically least second element, and so
on.
Definition
Notes
-
A string A is lexicographically less than another string B of the same
length if there exists a position i such that each character of A before the
i-th position is equal to the character at the corresponding position in B,
and A[i] is less than B[i]. When comparing the characters, refer to the
following list of characters in ascending order: '1', '2', ...,
'9', 'A',
'B', ..., 'Z', 'a', 'b', ..., 'o'.
Constraints
-
N will be between 1 and 50, inclusive.
-
M will be between 1 and 50, inclusive.
Examples
0)
3
3
Returns: {"123", "231", "312" }
There are three persons on each team, so the whole contest is divided into
three rounds. If we denote the i-th person of the first team as Ai and the
j-th person of the second team as Bj, the fights schedule for each of the
rounds is: Round 1: A1-B1, A2-B3, A3-B2 Round 2: A1-B2, A2-B1, A3-B3 Round
3: A1-B3, A2-B2, A3-B1
1)
4
4
Returns: {"1234", "2143", "3412", "4321" }
This time, both teams comprise of four persons, so the contest takes 4
rounds to finish. Round 1: A1-B1, A2-B2, A3-B3, A4-B4 Round 2: A1-B2, A2-B1,
A3-B4, A4-B3 Round 3: A1-B3, A2-B4, A3-B1, A4-B2 Round 4: A1-B4, A2-B3,
A3-B2, A4-B1
2)
4
6
Returns: {"123456", "214365", "345612", "436521"
}
The competition now is held in 6 rounds. Note that since the teams are of
unequal size, two of the second team's fighters are taking rest in each of
the rounds. Round 1: A1-B1, A2-B2, A3-B5, A4-B6 Round 2: A1-B2, A2-B1,
A3-B6, A4-B5 Round 3: A1-B3, A2-B4, A3-B1, A4-B2 Round 4: A1-B4, A2-B3,
A3-B2, A4-B1 Round 5: A1-B5, A2-B6, A3-B3, A4-B4 Round 6: A1-B6, A2-B5,
A3-B4, A4-B3
3)
5
3
Returns: {"123", "214", "345", "451",
"532" }
4)
28
40
Returns:
{"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcde",
"21436587A9CBEDGFIHKJMLONQPSRUTWVYXaZcbed",
"34127856BC9AFGDEJKHINOLMRSPQVWTUZaXYdebc",
"43218765CBA9GFEDKJIHONMLSRQPWVUTaZYXedcb",
"56781234DEFG9ABCLMNOHIJKTUVWPQRSbcdeXYZa",
"65872143EDGFA9CBMLONIHKJUTWVQPSRcbedYXaZ",
"78563412FGDEBC9ANOLMJKHIVWTURSPQdebcZaXY",
"87654321GFEDCBA9ONMLKJIHWVUTSRQPedcbaZYX",
"9ABCDEFG12345678PQRSTUVWXYZabcdeHIJKLMNO",
"A9CBEDGF21436587QPSRUTWVYXaZcbedIHKJMLON",
"BC9AFGDE34127856RSPQVWTUZaXYdebcJKHINOLM",
"CBA9GFED43218765SRQPWVUTaZYXedcbKJIHONML",
"DEFG9ABC56781234TUVWPQRSbcdeXYZaLMNOHIJK",
"EDGFA9CB65872143UTWVQPSRcbedYXaZMLONIHKJ",
"FGDEBC9A78563412VWTURSPQdebcZaXYNOLMJKHI",
"GFEDCBA987654321WVUTSRQPedcbaZYXONMLKJIH",
"HIJKLMNOPQRSTUVWXYZabcde123456789ABCDEFG",
"IHKJMLONQPSRUTWVYXaZcbed21436587A9CBEDGF",
"JKHINOLMRSPQVWTUZaXYdebc34127856BC9AFGDE",
"KJIHONMLSRQPWVUTaZYXedcb43218765CBA9GFED",
"LMNOHIJKTUVWPQRSbcdeXYZa56781234DEFG9ABC",
"MLONIHKJUTWVQPSRcbedYXaZ65872143EDGFA9CB",
"NOLMJKHIVWTURSPQdebcZaXY78563412FGDEBC9A",
"ONMLKJIHWVUTSRQPedcbaZYX87654321GFEDCBA9",
"PQRSTUVWXYZabcde9ABCDEFGHIJKLMNO12345678",
"QPSRUTWVYXaZcbedA9CBEDGFIHKJMLON21436587",
"RSPQVWTUZaXYdebcBC9AFGDEJKHINOLM34127856",
"SRQPWVUTaZYXedcbCBA9GFEDKJIHONML43218765" }
---
Üdv,
Balázs