Advertisement
Guest User

Untitled

a guest
Sep 6th, 2019
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace algorithms
  6. {
  7. class Program
  8. {
  9. private static int[] numbers;
  10. private static int totalHalf;
  11.  
  12. private static int[,] matrix;
  13. private static bool[,] usedMatrix;
  14.  
  15. public static void Main(string[] args)
  16. {
  17. numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
  18. int total = numbers.Sum();
  19. totalHalf = (int)Math.Floor((decimal)total / 2);
  20.  
  21. int rows = numbers.Length;
  22. int cols = totalHalf;
  23.  
  24. matrix = new int[rows + 1,cols + 1];
  25. usedMatrix = new bool[rows, cols];
  26.  
  27. for (int i = 1; i < rows + 1; i++)
  28. {
  29. for (int j = 1; j < cols + 1; j++)
  30. {
  31. int include = -1;
  32. if (numbers[i - 1] <= j)
  33. {
  34. include = numbers[i - 1] + matrix[i - 1,j - numbers[i - 1]];
  35. }
  36. int exclude = matrix[i - 1,j];
  37.  
  38. if (include > exclude)
  39. {
  40. //include the number
  41. matrix[i, j] = include;
  42. usedMatrix[i - 1, j - 1] = true;
  43. }
  44. else
  45. {
  46. //exclude the number
  47. matrix[i,j] = exclude;
  48. }
  49. }
  50. }
  51.  
  52. List<int> result = new List<int>();
  53.  
  54. int currentRow = rows - 1;
  55. int currentCol = cols - 1;
  56.  
  57. while (currentRow >= 0 && currentCol >= 0)
  58. {
  59. if (usedMatrix[currentRow, currentCol])
  60. {
  61. result.Add(numbers[currentRow]);
  62. currentCol -= numbers[currentRow];
  63. }
  64. currentRow--;
  65. }
  66.  
  67. int alanSum = result.Sum();
  68. int bobSum = Math.Abs(total - alanSum);
  69.  
  70. Console.WriteLine($"Difference: {Math.Abs(alanSum - bobSum)}");
  71. Console.WriteLine($"Alan:{alanSum} Bob:{bobSum}");
  72. Console.WriteLine($"Alan takes: {string.Join(" ",result)}");
  73. Console.WriteLine($"Bob takes the rest.");
  74. }
  75. }
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement