Paste Search Dynamic
Recent pastes
PompomBunny sorted
  1. using system;
  2. using system.Collections.Generic;
  3. using system.Linq;
  4.  
  5. namespace PompomBunny
  6. {
  7.     public class MainProgram
  8.     {
  9.         public static string  getInputLine()
  10.         {
  11.                 string line;
  12.                 line = Console.ReadLine();
  13.             while (line == null)
  14.             {
  15.                 line = Console.ReadLine();
  16.             }
  17.             return line;
  18.         }
  19.         static int  getNumberOfTestCases()
  20.         {
  21.                 string firstLine = getInputLine();
  22.             int testNum = Int32.Parse(firstLine);
  23.             return testNum;
  24.         }
  25.         static int[] getAllAndBreakEggsNumbers()
  26.         {
  27.                 string nextLine = getInputLine();
  28.                 string[] N_K_str = nextLine.Split(' ');
  29.                 int[] allEggs_breakEggs = Array.ConvertAll<string, int>(N_K_str, Int32.Parse);
  30.             return allEggs_breakEggs;
  31.         }
  32.         public static List<int> BubbleSort(List<int> unsorted)
  33.         {
  34.             for (int i = 0; i < unsorted.Count; i++)
  35.             {
  36.                 for (int a = 0; a < unsorted.Count-1; a++)
  37.                 {
  38.                     if (unsorted[a] < unsorted[a + 1])
  39.                     {
  40.                         int temp = unsorted[a + 1];
  41.                         unsorted[a + 1] = unsorted[a];
  42.                         unsorted[a] = temp;
  43.                     }
  44.                 }
  45.                
  46.             }
  47.             return unsorted;
  48.         }
  49.         static List<int> getEggsSortedTapValues()
  50.         {
  51.                 string nextLine = getInputLine();
  52.                 string[] tapValuesStr = nextLine.Split(' ');
  53.                 int[] tapValuesArr = Array.ConvertAll<string, int>(tapValuesStr, Int32.Parse);
  54.                 List<int> tapValues = tapValuesArr.ToList<int>();
  55.                 List<int> sortedTapValues = BubbleSort(tapValues);
  56.             return sortedTapValues;
  57.         }
  58.         // ------------------------------------------------------------------------------------
  59.                 public static List<int> CopyList(List<int> listToCopy)
  60.         {
  61.             List<int> copiedList = new List<int>();
  62.             for (int i = 0; i < listToCopy.Count; i++)
  63.             {
  64.                 copiedList.Add(listToCopy[i]);
  65.             }
  66.             return copiedList;
  67.         }
  68.         public static List<int> SumTapsFromFirstToEach(List<int> tempList)
  69.         {
  70.             List<int> temp = tempList;
  71.             for (int i = 0; i < temp.Count; i++)
  72.             {
  73.                 temp[i] = temp[i] * (i + 1);
  74.             }
  75.             return temp;
  76.         }
  77.         public static int FindIndexOfSmallestTapsNum(List<int> summedTaps)
  78.         {
  79.             int leastTaps = summedTaps[0];
  80.             int leastTapEggPosition = 0;
  81.             for (int i = 0; i < summedTaps.Count; i++)
  82.             {
  83.                 if (summedTaps[i]< leastTaps)
  84.                 {
  85.                     leastTaps = summedTaps[i];
  86.                     leastTapEggPosition = i;
  87.                 }
  88.             }
  89.             return leastTapEggPosition;
  90.         }
  91.         public static List<int> AddEggsStartingFromIndex(int eggsNeeded, int startIndex, List<int> tempList)
  92.         {
  93.             int eggsAdded = 0;
  94.             int sumOfTaps = 0;
  95.             if (eggsNeeded > 0)
  96.             {
  97.                 sumOfTaps += tempList[startIndex] * (startIndex + 1);
  98.                 eggsAdded += 1;
  99.                 startIndex += 1;
  100.             }
  101.             while (eggsNeeded>eggsAdded)
  102.             {
  103.                 if(startIndex <= tempList.Count - 1)
  104.                 {
  105.                     sumOfTaps += tempList[startIndex];//only the first one is from summed the other is from tempList
  106.                     eggsAdded += 1;
  107.                     startIndex += 1;
  108.                 }
  109.                 else
  110.                 {
  111.                     break;
  112.                 }
  113.             }
  114.             eggsNeeded -= eggsAdded;
  115.             List<int> output = new List<int> { eggsNeeded, sumOfTaps };
  116.             return output;
  117.         }
  118.         public static List<int> RemoveBrokenAndApplyTaps(int startIndex, List<int>templist)
  119.         {
  120.             List<int> temp = templist;
  121.             for (int i = 0; i < startIndex; i++)
  122.             {
  123.                 temp[i] -= temp[startIndex];
  124.             }
  125.             temp.RemoveRange(startIndex, (temp.Count - startIndex));
  126.            
  127.             return temp;
  128.         }
  129.         public static uint  FindMinTaps (List<int> sortedEggs, int eggsNeeded)
  130.         {
  131.             uint minTaps = 0;
  132.             List<int> tempList = CopyList(sortedEggs);
  133.             while (eggsNeeded > 0)
  134.             {
  135.                 List<int>summedList = SumTapsFromFirstToEach(CopyList(tempList));
  136.                 int leastTapsEggPosition = FindIndexOfSmallestTapsNum(CopyList(summedList));
  137.                 List<int> numOfEggsStillNeeded_TapsAdded = AddEggsStartingFromIndex(eggsNeeded, leastTapsEggPosition, CopyList(tempList));
  138.                 eggsNeeded = numOfEggsStillNeeded_TapsAdded[0];
  139.                 minTaps += (uint)numOfEggsStillNeeded_TapsAdded[1];
  140.                 tempList = RemoveBrokenAndApplyTaps(leastTapsEggPosition, CopyList(tempList));
  141.             }
  142.             return minTaps;
  143.         }
  144.         //-----------------------------------------------------------------------------------
  145.  
  146.         public static void Main()
  147.         {
  148.             int testNum = getNumberOfTestCases();
  149.             for (int test = 0; test < testNum; test++)
  150.             {
  151.                 int[] allEggs_breakEggs = getAllAndBreakEggsNumbers();
  152.                 int N = allEggs_breakEggs[0];
  153.                 int K = allEggs_breakEggs[1];
  154.                 List<int> tapValues = getEggsSortedTapValues();
  155.                 string taps = string.Join(",", tapValues.Select(x => x.ToString()).ToArray());
  156.                 string status = string.Format("Test #{0}: break {1} of {2} eggs using taps {3}", test, K, N, taps);
  157.                 // Console.WriteLine(status);
  158.                 uint worstCaseMinTaps = FindMinTaps(tapValues, K);
  159.                 // Console.WriteLine(String.Format("Test #{0}: break {1} eggs needs {2} taps in worst case", test, K, worstCaseMinTaps));
  160.                 Console.WriteLine(worstCaseMinTaps);
  161.             }
  162.         }
  163.     }
  164. }
Parsed in 0.024 seconds