Created
November 21, 2016 05:56
-
-
Save jianminchen/82ea02204871beb8463cc818a163b291 to your computer and use it in GitHub Desktop.
stone division - HackerRank - woman codesprint #2 - with more bugs to fix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace stoneDivision | |
{ | |
class Program | |
{ | |
/* | |
* stone division | |
* | |
* 1 | |
* 12 3 | |
* 2 3 4 | |
* | |
* answer: 4 | |
* | |
* start coding at 7:18pm | |
* 1<=m <= 10 30% of maximum score | |
*/ | |
static void Main(string[] args) | |
{ | |
process(); | |
// testcase1(); | |
} | |
private static void testcase1() | |
{ | |
int n = 12; | |
int m = 3; | |
int[] setS = new int[3]{2,3,4}; | |
Console.WriteLine(maximumMove(n, m, setS)); | |
} | |
private static void process() | |
{ | |
int q = int.Parse(Console.ReadLine()); | |
for (int i = 0; i < q; i++) | |
{ | |
string[] arr = Console.ReadLine().Split(' '); | |
int n = int.Parse(arr[0]); | |
int m = int.Parse(arr[1]); | |
string[] arr2 = Console.ReadLine().Split(' '); | |
int[] setS = Array.ConvertAll(arr2, int.Parse); | |
Console.WriteLine(maximumMove(n, m, setS)); | |
} | |
} | |
/* | |
* review at 8:22pm | |
* | |
*/ | |
private static int maximumMove(int n, int m, int[] setS) | |
{ | |
bool[,] isDivisable = new bool[m+1, m+1]; | |
IList<int> list = new List<int>(setS); | |
list.Add(n); | |
int[] newArr = list.ToArray(); | |
Array.Sort(newArr); | |
for(int i=0; i< m +1; i++) | |
for(int j=i; j< m+1; j++) | |
{ | |
int divisor = newArr[i]; | |
int runner = newArr[j]; | |
isDivisable[i, j] = (runner % divisor == 0) ? true : false; | |
} | |
IList<string> chains = new List<string>(); | |
StringBuilder sb = new StringBuilder(); | |
int index = m; | |
string val = m.ToString(); | |
getAllChains(chains, sb, isDivisable, newArr, n, m,val+"="+val); | |
// get maximum one here ... | |
int maximumMov = int.MinValue; | |
foreach(string s in chains) | |
{ | |
string[] steps = s.Split(' '); | |
int[] sequence = Array.ConvertAll(steps, int.Parse); | |
int count = 0; | |
int len = sequence.Length; | |
if (len == 1) | |
count = 0; | |
int prev = sequence[0]; | |
int prevCount = 0; | |
int groupCount = 1; | |
for(int i = 1; i< len; i++) | |
{ | |
int cur = sequence[i]; | |
int setCount = prev / cur; | |
if (i == 1) | |
count++; | |
else | |
{ | |
groupCount *= prevCount; | |
count += groupCount; | |
} | |
prev = cur; | |
prevCount = setCount; | |
} | |
maximumMov = (count > maximumMov) ? count : maximumMov; | |
} | |
return maximumMov; | |
} | |
/* | |
* 7:37pm | |
*/ | |
private static void getAllChains( | |
IList<string> chains, | |
StringBuilder sb, | |
bool[,] isDivisable, | |
int[] newArr, | |
int n, | |
int m, | |
string keyword | |
) | |
{ | |
string[] rowCol = keyword.Split('='); | |
int lastRow = Convert.ToInt32(rowCol[0]); | |
int lastCol = Convert.ToInt32(rowCol[1]); | |
if (isTheEnd(isDivisable, m, lastRow, lastCol)) | |
{ | |
chains.Add(sb.ToString()); | |
//sb.Clear(); | |
return; | |
} | |
for (int i = 0; i <= lastRow; i++) | |
{ | |
if (isDivisable[i, lastCol] == true) | |
{ | |
int len = sb.ToString().Length; | |
string next = sb.ToString().Length > 0 ? (" " + newArr[lastCol]) : newArr[lastCol].ToString(); | |
sb.Append(next); | |
bool nextOneFound = false; | |
string newKey = ""; | |
for (int col = lastCol - 1; col >= 0; col--) | |
{ | |
if (isDivisable[i, col]) | |
{ | |
newKey = i.ToString()+"="+col.ToString(); | |
nextOneFound = true; | |
break; | |
} | |
} | |
if (!nextOneFound) | |
{ | |
chains.Add(sb.ToString()); | |
//sb.Clear(); | |
return; | |
} | |
getAllChains(chains, sb, isDivisable, newArr, n, m, newKey); | |
int newLen = sb.ToString().Length; | |
sb.Remove(len, newLen - len); | |
} | |
} | |
} | |
private static bool isTheEnd(bool[,] array, int m, int lastRow, int lastCol) | |
{ | |
if (lastRow < 0 || lastCol < 0) | |
return true; | |
for (int i = 0; i <= lastRow; i++) | |
{ | |
if (array[i, lastCol] == true) | |
return false; | |
} | |
return true; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment