Composed Rhythms

Question

https://open.kattis.com/problems/composedrhythmsopen.kattis.com

Solution

Idea

This is a math problem. Since the question is asking for one of the solutions, it is not that hard. My method is to find as many 3s as possible, and after minusing all these 3s, we are left with the following three cases:

1. the remainder is 2, that means we can use one 2 to satisfy the requirement

2. the remainder is 1, that means we need to spare one 3 out and use two 2s to satisfy the requirement

3. the remainder is 0, that means our division with all 3s are successful!

Code

https://github.com/mendax1234/Coding-Problems/blob/main/kattis/composedrhythms/composedrhythms.c

#include <stdio.h>

int main()
{
  int n;
  scanf("%d", &n);

  int two = 0;
  int three = 0;
  if (n == 2)
  {
    two = 1;
    three = 0;
  }
  else if (n == 3)
  {
    two = 0;
    three = 1;
  }
  else if (n == 4)
  {
    two = 2;
    three = 0;
  }
  else
  {
    three = n / 3;
    if (n - three * 3 == 1)
    {
      three -= 1;
      two = 2;
    }
    else 
    {
      two = (n - three * 3) / 2;
    }
  }
  printf("%d\n", two + three);
  for (int i = 0; i < three; i += 1)
  {
    printf("3 ");
  }
  for (int i = 0; i < two; i += 1)
  {
    printf("2 ");
  }
  putchar('\n');
}