じゅうたん

プログラマー-カーペット

問題の説明

Leoはじゅうたんを買いに行きました.格子じゅうたんの列が見えました.真ん中は黄色で、一列は茶色で、下図のように見えます.

Leoは家に帰ってから、さっき見たじゅうたんの黄色と茶色の格子数を覚えたが、じゅうたん全体の大きさは覚えていない.
Leoがこのカーペットに茶色の格子の数茶色、黄色の格子の数黄色をパラメータとして与えた場合、カーペットの横方向と縦方向の寸法を順番に並べて返します.

せいげんじょうけん

茶色の格子の水茶色は8以上5000以下の自然水です.

黄色のメッシュの数は、1以上200000以下の自然数です.

カーペットの横方向の長さは、縦方向の長さ以上である.

I/O例

brownyellowreturn102[4, 3]81[3, 3]2424[8, 6]

に答える

from math import sqrt


def get_one_row_include_yellow(num_of_row_yellow):
    return num_of_row_yellow + 2


def get_row_include_yellow(yellow, div):
    return get_one_row_include_yellow(yellow // div) * div


def get_total_grid(yellow, div):
    row_include_yellow = get_row_include_yellow(yellow, div)
    return row_include_yellow + (get_one_row_include_yellow(yellow // div) * 2)


def is_saw_carpet(yellow, div, brown):
    if get_total_grid(yellow, div) - yellow != brown:
        return False

    return True


def get_carpet_row_col(yellow, div):
    row = get_one_row_include_yellow(yellow // div)
    col = div + 2
    return [row, col]


def solution(brown, yellow):
    if is_saw_carpet(yellow, 1, brown):
        return get_carpet_row_col(yellow, 1)

    for div in range(2, int(sqrt(yellow)) + 1):
        if not (yellow % div) and (yellow // div) >= div:
            if is_saw_carpet(yellow, div, brown):
                return get_carpet_row_col(yellow, div)

            if (yellow // div) != div and div >= (yellow // div):
                if is_saw_carpet(yellow, (yellow // div)):
                    return get_carpet_row_col(yellow, (yellow // div))

ソリューション

黄色の水平グリッド数を含む行を求めます

タイルメッシュ全体の個数を要求します.また,黄色の横線が全部で何行あるかを知るためには,まず黄色を含む横線がどれだけのメッシュを必要とするかを求めることにする.

def get_one_row_include_yellow(num_of_row_yellow):
    return num_of_row_yellow + 2

黄色を含む横線は(1行の黄色いタイル数)+2です.両端の黄色が茶色に遮られているからです.

黄色の水平線のメッシュの数を求めます

def get_row_include_yellow(yellow, div):
    return get_one_row_include_yellow(yellow // div) * div

この場合,上記で求めたメッシュ個数と黄色の連続した縦数行を知れば得られる.この関数では、divは黄色のメッシュの縦方向の連続する数行を表す.

総グリッド数を求める

def get_total_grid(yellow, div):
    row_include_yellow = get_row_include_yellow(yellow, div)
    return row_include_yellow + (get_one_row_include_yellow(yellow // div) * 2)

グリッド全体の数は、式(黄色の横線グリッド数を含む)+(黄色の横線グリッド数*2を含む)を使用します.
黄色を含まない横線は茶色のメッシュで構成されているため、最初の行と最後の行にのみ表示されます.それらは何列かの横に並んだ格子から構成されています.

問題の要求に合致するタイルですか?

def is_saw_carpet(yellow, div, brown):
    if get_total_grid(yellow, div) - yellow != brown:
        return False

    return True

黄色のメッシュの個数でメッシュ全体を求めたので、タイル上の茶色のメッシュの数が問題で要求されたメッシュの数と同じかどうかを比較し、同じであればTrueを返します.

横と縦の長さを求めて戻る

def get_carpet_row_col(yellow, div):
    row = get_one_row_include_yellow(yellow // div)
    col = div + 2
    return [row, col]

問題で要求されるカーペットが正しい場合、カーペットの横方向の長さと縦方向の長さを求めることによって戻る.

solution

def solution(brown, yellow):
    if is_saw_carpet(yellow, 1, brown):
        return get_carpet_row_col(yellow, 1)

    for div in range(2, int(sqrt(yellow)) + 1):
        if not (yellow % div) and (yellow // div) >= div:
            if is_saw_carpet(yellow, div, brown):
                return get_carpet_row_col(yellow, div)

            if (yellow // div) != div and div >= (yellow // div):
                if is_saw_carpet(yellow, (yellow // div)):
                    return get_carpet_row_col(yellow, (yellow // div))

茶色と黄色の数が任意に与えられた場合、すべての黄色が1列に並んでいれば、問題として要求されるカーペットの条件は満たされる.だからまずこのような状況を実行します.
黄色を一列に並べた場合でなければ、薬水の関係も考えられます.最終的には、黄色は長方形の形で中央に位置する必要があります.
1行ではなく複数の行をリストする必要がある場合は、1とそれ自体(横方向の長さ>=縦方向の長さの条件のため)を約数の組み合わせに組み合わせることができます.
ただし、約数の場合でも가로 길이 >= 세로 길이の条件を満たす必要があり、黄色/divの値がdivより小さい場合は、その条件を満たすことができない.したがって、条件文に対応する条件が追加され、不要な関数呼び出しがブロックされます.
薬液は黄色の平方根を繰り返し検査し,黄色をこの数で割った値をもう一度検査した(この場合は2×4と4×2と考えられる).ただし、この場合、2×2のように反転しても同様、または가로 길이 >= 세로 길이の条件を満たさない場合、関数呼び出しは不要であるため、実行されない.

他人の解答

def solution(brown, yellow):
  x = (brown + 4 + ((brown + 4) ** 2) - 16 * (brown + yellow)) ** 0.5 / 4
  y = (brown + yellow) // x
  return [max(x, y), min(x, y)]

コードソース:[プログラマー]Pythonのカーペット-超いい
グリッド全体の数はbrown + yellowで得ることができます(私はどうしてそれを思わなかったのですか?)また(x - 2) * (y - 2) = yellowです.
この2つの方程式を連立して解くと,得られた式をルートの式に解くとx,yを求めることができる.가로 길이 >= 세로 길이の条件に従って、両者のうちの大きい値の横方向、小さい値の縦方向のリストを返すと問題が解決される.