結果

問題 No.115 遠足のおやつ
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:30:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 41 ms / 5,000 ms
コード長 1,929 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 54,040 KB
最終ジャッジ日時 2025-03-20 20:31:38
合計ジャッジ時間 3,454 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find_snack_combination():
    import sys
    N, D, K = map(int, sys.stdin.readline().split())
    
    def dfs(path, start, remaining, current_sum):
        if remaining == 0:
            if current_sum == D:
                return path
            else:
                return None
        
        for i in range(start, N + 1):
            new_sum = current_sum + i
            if new_sum > D:
                break  # Prune if sum exceeds D
            
            next_remaining = remaining - 1
            if next_remaining == 0:
                if new_sum == D:
                    return path + [i]
                else:
                    continue  # Skip if last element doesn't reach D
            
            required = D - new_sum
            m = next_remaining
            
            # Calculate minimum possible sum with next m elements starting from i+1
            a = i + 1
            if a + m - 1 > N:
                min_sum = (m * (a + (a + m - 1))) // 2
                if a > N:
                    min_sum = 0  # Invalid if there are not enough elements
            else:
                min_sum = (m * (2 * a + m - 1)) // 2
            
            # Calculate maximum possible sum with the largest m elements
            max_elem = N
            if max_elem < m:
                max_sum = 0  # Not enough elements
            else:
                max_sum = (m * (max_elem + (max_elem - m + 1))) // 2
            
            if min_sum > required or max_sum < required:
                continue  # Prune if sum cannot be achieved
            
            # Continue DFS
            result = dfs(path + [i], i + 1, next_remaining, new_sum)
            if result is not None:
                return result
        
        return None
    
    combination = dfs([], 1, K, 0)
    if combination:
        print(' '.join(map(str, combination)))
    else:
        print(-1)

find_snack_combination()
0