Advertisement
sashomaga

Dynamic optimization

Jan 31st, 2013
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.89 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. class Program
  5. {
  6.     static void Main()
  7.     {
  8.         string[] strData = Console.ReadLine().Split(new string[]{","},StringSplitOptions.RemoveEmptyEntries);
  9.         int[] data = new int[strData.Length];
  10.         for (int i = 0; i < strData.Length; i++)
  11.         {
  12.             data[i] = int.Parse(strData[i]);
  13.         }
  14.         int start = int.Parse(Console.ReadLine());
  15.         int max = int.Parse(Console.ReadLine());
  16.         int[,] matrix = new int[data.Length+1, max + 1];
  17.         matrix[0, start] = 1;
  18.         for (int x = 0; x < matrix.GetLength(0)-1; x++)
  19.         {
  20.             for (int y = 0; y < matrix.GetLength(1); y++)
  21.             {
  22.                 if (matrix[x,y] == 1)
  23.                 {
  24.                     if (y + data[x] < matrix.GetLength(1))
  25.                     {
  26.                         matrix[x + 1, y + data[x]] = 1;
  27.                     }
  28.                     if (y - data[x] >= 0)
  29.                     {
  30.                         matrix[x + 1, y - data[x]] = 1;
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.         int result = 0;
  36.         for (int y = matrix.GetLength(1)-1; y >= 0 ; y--)
  37.         {
  38.             if (matrix[data.Length,y] == 1)
  39.             {
  40.                 result = y;
  41.                 break;
  42.             }
  43.         }
  44.         if (result > 0)
  45.         {
  46.             Console.WriteLine(result);
  47.         }
  48.         else if (data.Length == 0)
  49.         {
  50.             Console.WriteLine(start);
  51.         }
  52.         else
  53.         {
  54.             Console.WriteLine(-1);
  55.         }
  56.     }
  57.  
  58.     private static void PrintMatrix(int[,] matrix)
  59.     {
  60.         for (int x = 0; x < matrix.GetLength(0); x++)
  61.         {
  62.             for (int y = 0; y < matrix.GetLength(1); y++)
  63.             {
  64.                 Console.Write(matrix[x,y]);
  65.             }
  66.             Console.WriteLine();
  67.         }
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement