ez_code   1년 전

문제

1999년 체코 기술 대학교에서는 세 개의 서로 다른 대회가 있었습니다: 학부생 대회 (FEL++), 체코 기술 대학교 대회, 중부 유럽 지역 대회입니다. 당연하게도 그동안 "선구자"의 열정도 약간 식었습니다. 5년 동안 매년 2~3개의 대회를 기획해야 했죠. 처음에는 재미있었던 일이 어느새 힘든 업무가 되어버렸습니다. 다행히 대회 참가자였던 사람이 새로운 주최자가 되는 경우가 많아지고 하나의 전통으로 자리 잡았습니다.

1999년 대회 거의 직전에 추가된 광맥 문제는 쉬운 문제로 의도하고 출제된 문제였습니다. 문제가 쉬운지 어려운지는 직접 판단해봅시다.

줄리엣이 흥미로운 SF 책을 읽고 있습니다. 한 부분에서, 주인공은 화물 우주선의 효용을 극대화하는 문제를 해결해야 했습니다. 우주선은 각 차원마다 3개의 정점으로 이루어진 D-차원 그물 모양의 값진 물품을 운송합니다. 정점은 동일한 무게의 공입니다. 공을 연결한 부분은 너무 가벼워 공의 무게를 고려했을 때 무시해도 상관 없습니다. 이는 곧 물품의 무게가 정점의 수로만 결정됨을 의미합니다. 하지만 물품의 가치는 정점의 수와 연결 부분의 수의 합으로 결정됩니다.

(그림 참조)

각 우주선에는 실을 수 있는 최대 무게가 정해져 있는데, 당신의 목표는 최대 무게를 넘기지 않고 우주선에 저장할 수 있는 물품의 가치를 최대로 만드는 것입니다. 모든 차원의 물품이 무한대로 있다고 할 때, 당신은 총 가치를 최대로 만들기 위해 어떤 차원의 어떤 물품을 실어야 하는지 결정해야 합니다. 

입력

첫 줄에 테스트 케이스의 수 N이 주어집니다. 각 테스트 케이스에는 우주선에 실을 수 있는 최대 무게를 나타내는 하나의 양의 정수 K < 10000000가 한 줄에 주어집니다. 

출력

각 테스트 케이스에 대해, 한 줄에 공백으로 구분된 음이 아닌 정수 Xm Xm-1 ... X1 X0를 출력하는데, 이 때 Xm > 0이며 Xi는 총 가치를 최대로 만들기 위해 저장해야 하는 i번째 차원의 물품의 수입니다. 

댓글을 작성하려면 로그인해야 합니다.