Member 14792370 Ответов: 3

След латинского квадрата

 Indicium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.

A Latin square is an N-by-N square matrix in which each cell contains one of N different values, such that no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the N values are the integers between 1 and N.

The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).

Given values N and K, produce any N-by-N "natural Latin square" with trace K, or say it is impossible. For example, here are two possible answers for N = 3, K = 6. In each case, the values that contribute to the trace are underlined.

2 1 3   3 1 2
3 2 1   1 2 3
1 3 2   2 3 1


Что я уже пробовал:

Я читал в Википедии, но она говорит, что может быть много значений следа латинского квадрата
Пожалуйста, предоставьте любую идею, как решить эту проблему.Как к нему подойти

3 Ответов

Рейтинг:
1

OriginalGriff

Попробуйте это на бумаге и посмотрите, сможете ли вы заставить его работать.
Когда вы можете, запишите английские правила, как это сделать, а затем протестируйте их - точно следуйте им и посмотрите, работает ли это. Если они этого не делают, то меняйте правила, пока они этого не сделают.

Когда правила работают, вы должны быть в состоянии преобразовать их в псевдокод, и из этого дизайна и кода программа сделает это за вас.

Но просто разместите здесь свою домашнюю работу и ничего не пытайтесь сделать ... это не приведет вас очень далеко.

Member 14792370

нет, на самом деле я даже не знаю, как строится латинский квадрат, имеющий след k.Я не знаю точного процесса, я написал какой-то код, но он не сработал.....вот мой код

#Highest number in square
order_of_sq = int(input("Enter order of sq: "))

#Number you want to start the square with
top_left = int(input("Enter top left number: "))

#Sets a placeholder for a variable called top_left_init
top_left_init=0

#Sets the initial value of top_left to a new variable because the code will change the value of top left later on 
top_left_init += top_left

#Initialize the value of count
count = 0

#Add 1 to the highest value in latin square to account for the range function (the ending number is always one less than the number you enter into the range function)
for values in range (1,order_of_sq+1):

    #Prevents the program from adding too many characters to the line
    while count != order_of_sq:

        #Prints numbers with spaces after them in a horizontal manner
        print(top_left,sep=' ',end=' ')

        #Adds 1 to the top_left
        top_left += 1

        #Count is used to keep track of how many characters are in your line
        count+=1

        #Restarts the numbers in your line when you reach the highest number
        if top_left == order_of_sq+1:
            top_left = 1

    #Creates a new row
    print()
    count = 0

    #Calls the initial value of top_left and adds 1 to it before beginning the next row
    top_left_init += 1

    #Resets top_left_init to 1 if it reaches the highest number in the square
    if top_left_init == order_of_sq + 1:
        top_left_init = 1
        top_left = top_left_init
    else:
        top_left = top_left_init

Patrice T

Воспользуйся Улучшить вопрос чтобы обновить ваш вопрос.
Чтобы каждый мог обратить внимание на эту информацию.
Также добавьте пример вывода.

Рейтинг:
0

Member 14792546

Это из Google Code Jam, не обманывайте :)

Patrice T

Хороший улов !

Рейтинг:
0

Patrice T

Цитата:
Это из Google Code Jam

Действительно: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0[^]
Спасибо, что указали на это.
Цитата:
Я написал какой-то код, но он не сработал.....вот мой код

Первая проблема заключается в том, что вы не скопировали полное требование, поэтому мы этого не видим вы не уважаете формат ввода и насколько я могу судить, вы не уважаете ведение невозможных дел любой.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing two integers N and K: the desired size of the matrix and the desired trace.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no answer for the given parameters or POSSIBLE otherwise. In the latter case, output N more lines of N integers each, representing a valid "natural Latin square" with a trace of K, as described above.