🛒[プログラマー]多段歯ブラシ販売


問題の説明
民浩は多段階組織を利用して歯ブラシを販売している.販売員が歯ブラシを販売すると、その利益はピラミッドを通じて少しずつ分配される形の販売ネットワークになる.販売がある程度に達した後、民浩は組織を経営しており、組織の中で誰がどれだけの利益を得たのか知りたいと思っている.例えば、民浩が運営する多段歯ブラシ販売組織を下図に示す.

ミンホはセンターで、青いボックスは8人の店員がいることを示しています.誰もが自分を組織に参加させる推薦者に接続し、ピラミッド式の構造を形成している.組織の収益配分ルールは簡単です.すべての販売員は歯ブラシ販売による利益から10%を計算し、参加組織の推薦者に自分を割り当て、残りは自分が所有する.各販売員は、歯ブラシの販売によって生じた利益と、組織に参加することを推奨した販売員の10%の利益から利益を得ることができます.あなたの身に起こった利益も同じルールで推薦者に割り当てられます.ただし、10%を計算すると、1元単位で計算され、10%の金額が1元未満を計算すると、すべての収益が得られます.
たとえば、次の営業記録があるとします.歯ブラシの販売利益は1本100元になる.
販売員販売数量利益金young 121200元john 4400元tod 2200元emily 5500元mary 101000元
販売員youngは1200元の利益を得た.youngはその中の10%に相当する120元を、自分が組織に参加させる推薦者edwardに割り当て、残りの1080元を自分で持っていく.エドワードはyoungからもらった120元のうち、10%の12元をmaryに割り当て、自分で残りの108元を取った.メアリーはエドワードから12元をもらい、10%の1元をセンター(民浩)に割り当て、自分で残りの11元を取った.この状態を下図に示します.

その後、販売員johnは400元の利益を得た.johnは10%の40元を中心に割り当て、自分で残りの360元を取った.この状態を下図に示します.

その後、販売員todは200元、tod自身は180元、推薦人jamieはそのうち10%の20元、jamieの推薦人maryは18元、jamieの推薦人maryは2元を獲得するが、この10%は1単位で購入すると配分された金額がないため、maryは2元を全部持っていく.この状態を下図に示します.

次に、エミリーが歯ブラシを販売することで得た500元の利益は、同じルールでエミリー450元、mary 45元、センター5元に分配された.この状態を下図に示します.

最後に、販売員maryは1000元の利益を得て、そのうち10%の100元をセンターに分配した後、残りの900元は自分で取ります.この状態を下図に示します.

以下に示すように、すべての組織メンバーの利益実現状況統計が完了しました.次の図に示すように、すべての収益を統合します.

これが民浩が知りたい利益分配の状況だ.
各販売者名単位の並び登録、各販売者が多段階組織に参加する他の販売者名単位の並び推薦、販売統計データ単位で販売者名を並べた並び売り、販売統計データ単位で販売数を並べた並び数をパラメータとする.各営業担当者が得た利益のリストを返すソルバを完了してください.営業担当者に割り当てられた利益総額(整数)を計算し、入力した形式で所定の登録に名前が含まれている順序でリストすればよい.
せいげんじょうけん
  • 登録長さは1万を超えない.
  • に民浩の名前が登録されていません.したがって,登録長は民浩を除く組織メンバーの総数である.
  • で推奨される長さは、登録されている長さと同じです.
  • 転診において、iの1番目の名称は、配列登録においてiの1番目の販売者を組織に参加させる者の名称である.
  • 誰にも推薦されずに組織に参加した人の場合、推薦案には推薦者の名前が記入されず、「-」が記入されます.上記の例ではjohnとmaryがこのような例です.
  • に登録された名前は、参加組織の順に並べられています.
  • すなわち、ある販売者の名前が登録されたi番に表示された場合、その販売者を組織に加入させた人の名前、すなわち推奨されるi番要素が登録されたj番に表示されたことを保証する(j
  • 売り手の長さは1以上100000以下である.
  • 売り手のi番目の名称は、i番目の販売統計データがどの販売員によって提供されたかを示す.
  • 売り手は重複する名前を持つ可能性があります.
  • 金額の長さは売り手の長さと同じです.
  • の数のうち、i番目の数字は、i番目の販売統計データの販売量を表す.
  • 販売量の範囲、すなわち数量要素の範囲は1以上100以下の自然数である.
  • 歯ブラシを販売する利益は100元に設定されています.
  • すべての組織メンバーの名前は、10文字以内の英字小文字で構成されています.
  • I/O例
    enrollreferralselleramountresult["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]["young", "john", "tod", "emily", "mary"][12, 4, 2, 5, 10][360, 958, 108, 0, 450, 18, 180, 1080]["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]["sam", "emily", "jaimie", "edward"][2, 3, 5, 4][0, 110, 378, 180, 270, 450, 0, 0]
    I/O例説明
    I/O例#1
    問題の例.
    I/O例#2
    これは、問題の例と同じ組織構成に少し異なる販売量統計を適用したものです.収益を割り当てるルールは同じなので、簡単な計算で表に表示される結果を得ることができます.
    ※公告-2012年5月21日にテストケースを追加しました.

    私の答え

    function solution(enroll, referral, seller, amount) {
        // 추천 받은 사람을 key, 해준 사람을 value 에 담은 객체 생성
        const line = {}
        // 결과를 담을 array
        const result = Array.from({length:enroll.length}, () => 0)
        enroll.forEach((en,eIdx) => {
            if(referral[eIdx] !== '-') {
                line[en] = referral[eIdx]
            } else {
                line[en] = ''
            }
        })
        // 판매 한 사람을 모두 순회
        seller.forEach((sel,sIdx) => {
            dfs(sel,amount[sIdx]*100)
        })
        // DFS
        function dfs(sel,cost) {
            // 전달할 돈
            const val = Math.floor(cost*0.1)
            // 전달 하려는 값이 1보다 낮은 경우 전달할 필요 없이 불필요한 호출스택이 쌓이므로 조건을 걸어주지 않는다면 효율성 테스트에서 통과하지 못함
            if(line[sel] && val > 0) {
                dfs(line[sel], val)
            }
            // 정답 배열에 전달한 금액을 제외한 수익을 더함
            result[enroll.indexOf(sel)]+=cost-val
        }
        return result
    }