케이크 분배

시간 제한1초메모리 제한512 MB

요약
A, B, C명이 올 때 각각 똑같이 나눌 수 있도록 5000개 이하의 양의 정수 조각으로 케이크를 자르고, 각 조각마다 세 경우의 받는 사람 번호를 정한다.
난이도

어려움10점 중 8점

유형
수학, 정수론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

곧 생일이라 무게가 1그램 이상 101810^{18}그램 이하인 생일 케이크를 준비하려고 한다. 파티에 오는 손님이 A명, B명 또는 C명이라는 것만 알고 있다. 이 케이크를 다음과 같이 잘라야 한다.

  • 각 조각의 무게는 양의 정수 그램이다.
  • 몇 명의 손님이 오든, 조각을 손님에게 나눠 각 손님이 같은 양의 케이크를 받도록 할 수 있다. 한 손님이 조각을 두 개 이상 받아도 된다.

케이크를 자르는 데 시간을 너무 쓰고 싶지 않으므로 조각의 개수를 최대 5,000개로 하려고 한다. 해 보자!

입력

입력은 한 줄이며, 3개의 수 A, B, C가 주어진다. 모두 1000 이하인 양의 정수이다.

출력

첫째 줄에 조각의 개수 K를 출력한다. 다음 K개의 줄에는 조각 하나의 정보를 나타내는 4개의 수 wi, ai, bi, ci를 출력한다. wi는 조각의 무게(그램)이고, ai, bi, ci는 각각 A명, B명, C명의 손님이 왔을 때 이 조각을 받을 손님의 번호이다. 번호는 1 ≤ ai ≤ A, 1 ≤ bi ≤ B, 1 ≤ ci ≤ C를 만족해야 한다. 모든 wi의 합은 101810^{18} 이하여야 한다.

예제1

  1. 예제 1

    입력
    1 2 3
    예상 출력
    4
2 1 1 1
1 1 1 2
1 1 2 2
2 1 2 3