Asya loves confetti. One day she decided to create exactly N small pieces of sheets with paper size A10.

A10 is a standard for paper sizes. A9 is another standard that is twice as bigger as A10, so A9 can be cut into 2 pieces of size A10. A8 is twice as bigger as A9 and so on. A0 is twice as bigger as A1. See the picture on the left.

Asya has only one sheet of each type (totally 11 sheets). She wants to have exactly N pieces of size A10 by cutting as few sheets as possible.

Asya should not have any wasted sheets.

Write a program for her.

For example if we want to cut sheets into 9 pieces with the size of A10, we will use the only A7 sheet (cut into 8 pieces of size A10) and the only sheet with size A10. Then we will use 2 sheets. All other 9 sheets will not be used.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Sheets { static void Main() { int N = int.Parse(Console.ReadLine()); int sum = 0; List<int> listA = new List<int> { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 }; List<string> listS = new List<string> { "A10", "A9", "A8", "A7", "A6", "A5", "A4", "A3", "A2", "A1", "A0" }; for (int i = 0; i <= 10; i++) { if (sum + listA[10 - i] <= N) { sum += listA[10 - i]; listS.Remove(listS[10 - i]); } } foreach (var item in listS) { Console.WriteLine(item); } } } |