사탕 항아리
시간 제한2초메모리 제한128 MB
K부터 시작하는 연속된 개수의 사탕이 든 N개의 병을, 부분집합에서 같은 수를 빼는 연산을 최소 횟수로 사용해 모두 비우고 그 연산들을 출력하는 문제입니다.
문제
N개의 항아리에 사탕이 들어 있다. 1번 항아리에는 K개, 2번 항아리에는 K+1개가 들어 있고, 번호가 하나 커질 때마다 사탕도 하나씩 늘어난다. 따라서 N번 항아리에는 K+N-1개의 사탕이 들어 있다.
한 번의 작업에서는 항아리 몇 개를 골라, 고른 모든 항아리에서 같은 개수의 사탕을 꺼낸다. 꺼내는 개수는 선택한 항아리들에 남아 있는 사탕 수보다 많을 수 없다.
모든 사탕을 꺼내기 위해 필요한 작업 횟수를 최소화하고, 그 작업들을 구하라.
입력
첫째 줄에 항아리의 개수 N과 1번 항아리에 들어 있는 사탕의 개수 K가 공백으로 구분되어 주어진다.
- 1 <= N <= 100,000
- 1 <= K <= 500,000
항아리는 왼쪽부터 1번부터 N번까지 번호가 매겨져 있다.
출력
첫째 줄에 최소 작업 횟수 M을 출력한다.
이후 각 작업을 두 줄로 출력한다. 첫 줄에는 선택한 항아리의 개수와 각 항아리에서 꺼낼 사탕 개수를 출력한다. 다음 줄에는 선택한 항아리 번호를 공백으로 구분해 출력한다.
모든 작업을 순서대로 수행했을 때 모든 항아리의 사탕 수가 정확히 0이 되어야 한다. 최소 횟수를 만족하는 방법이 여러 가지라면 그중 아무 방법이나 출력해도 된다.