fork download
copy 
  1. using System;
  2. using System.Text;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5.  
  6. public class Test
  7. {
  8. 	        static int GetCountDP(int N, int x, int y, ref StringBuilder candidate, ref List<string> combinations)
  9.         {
  10.             Console.WriteLine("Trying: {0}", candidate.ToString());
  11.             if (N == 0) { candidate.Append(""); Console.WriteLine(candidate.ToString()); combinations.Add(candidate.ToString());  return 0; }
  12.             if (N == 1) { candidate.Append("()"); Console.WriteLine(candidate.ToString()); combinations.Add(candidate.ToString()); return 2; }
  13.             if (N == 2) { candidate.Append("())"); Console.WriteLine(candidate.ToString()); combinations.Add(candidate.ToString()); return 3; }
  14.             if (N == 3) { candidate.Append("()))"); Console.WriteLine(candidate.ToString()); combinations.Add(candidate.ToString()); return 4; }
  15.             if (x * y == N) { Console.WriteLine(candidate.ToString()); return x + y; }
  16.             if (x * y > N) return N * 2 + N; // max
  17.             var ret = new List<int>();
  18.             candidate.Insert(0,'(');
  19.             int count2 = GetCountDP(N - x-1, x, y + 1, ref candidate, ref combinations) + 1;
  20.             candidate.Remove(0, 1);
  21.             candidate.Insert(candidate.Length - 1, ')');
  22.             int count3 = GetCountDP(N - y-1, x + 1, y, ref candidate, ref combinations) + 1;
  23.             candidate.Remove(candidate.Length - 1, 1);
  24.  
  25.             if (N % 2 == 1 && x * y < N)
  26.             {
  27.                 candidate.Append("()");
  28.                 int count1 = GetCountDP(N - 1, x, y, ref candidate, ref combinations) + 2;
  29.                 candidate.Remove(candidate.Length - 2, 2);
  30.                 ret.Add(count1);
  31.             }
  32.             /*
  33.             for (int k = 1; k <= N / 2; k++)
  34.             {
  35.                 int count = GetCountDP(k, 1, 1, ref candidate,ref combinations) + GetCountDP(N - k, 1, 1, ref candidate, ref combinations);
  36.                 ret.Add(count);
  37.             }
  38.             */
  39.             ret.Add(count2);
  40.             ret.Add(count3);
  41.             // Console.WriteLine("{0}", NumConvert(ret));
  42.             return ret.Min();
  43.         }
  44. 	public static void Main()
  45. 	{
  46. 		    var candidate = new StringBuilder("()");
  47.             var combinations = new List<string>();
  48.             int number = GetCountDP(7,1,1, ref candidate, ref combinations);
  49.             var min = combinations.Min(x => x.Length);
  50.             Console.WriteLine("{0}", min);
  51.             Console.WriteLine("{0}", combinations.First(x => x.Length == min)); ;
  52.             Console.WriteLine();
  53. 	}
  54. }
Success #stdin #stdout 0s 131712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Trying: ()
Trying: (()
Trying: ((()
((()()))
Trying: (()())))
(()())))())
Trying: (()())))()()
Trying: ((()())))()()
((()())))()()())
Trying: (()())))()()()))
(()())))()()()))()
Trying: ()())))()()()))
Trying: (()())))()()()))
(()())))()()()))())
Trying: ()())))()()()))()))
()())))()()()))()))()))
Trying: ()())))()()()))()))())()
Trying: (()())))()()()))()))())()
(()())))()()()))()))())()()
Trying: ()())))()()()))()))())()())
()())))()()()))()))())()())())
Trying: ()())))()()()))()))())()()()
Trying: (()())))()()()))()))())()()()
Trying: ((()())))()()()))()))())()()()
((()())))()()()))()))())()()()())
Trying: (()())))()()()))()))())()()()()))
(()())))()()()))()))())()()()()))()
Trying: ()())))()()()))()))())()()()())))(
Trying: (()())))()()()))()))())()()()())))(
(()())))()()()))()))())()()()())))(()
Trying: ()())))()()()))()))())()()()())))(())
()())))()()()))()))())()()()())))(())())
8
((()()))
https://ideone.com/6CoOqH
language:
C# (gmcs 5.20.1)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!