Проблем със задача Problem 2 – Greedy Dwarf


0
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Numerics; namespace ConsoleApplication11 { class Program { static void Main(string[] args) { string input = Console.ReadLine(); //string input = "1, 3, -6, 7, 4, 1, 12"; string[] valley = input.Split(new char[] { ' ', ',' }, StringSplitOptions.RemoveEmptyEntries); string[] valleyClone = new string[valley.Length]; valleyClone = valley.ToArray(); byte m = byte.Parse(Console.ReadLine()); BigInteger sum = 0; BigInteger bestSum = 0; for (int i = 0; i < m; i++) { if (sum > bestSum) { bestSum = sum; } long stepCounter = 0; sum = 0; valley = valleyClone.ToArray(); string[] patterns = Console.ReadLine().Split(new char[] { ' ', ',' }, StringSplitOptions.RemoveEmptyEntries); //sum += Convert.ToInt64(valley[0]); while (true) { foreach (var step in patterns) { if (valley[stepCounter] == null) { break; } //stepCounter += Convert.ToInt64(step); //stepCounter += Convert.ToInt32(step); long coin = Convert.ToInt64(valley[stepCounter]); sum += coin; valley[stepCounter] = null; stepCounter += Convert.ToInt64(step); } if (valley[stepCounter] != null) { continue; } else { break; } } } Console.WriteLine(bestSum); } } }

Здравейте,

дайте мнение има ли бъдеще това решение и къде греша :)

Благодаря!




Отговори



0

Това е условието:

The dwarfs escape the valley when they step on already visited position in the valley, or when they go out the valley (i.e. their current position + the number in the pattern is leading outside of the valley).

Ти никъде не проверяваш дали джуджето е излязло от масива. Трябва да имаш нещо подобно в кода си:

if (stepCounter < 0 || valley.Length <= stepCounter) { break; }

Остава да помислиш къде да сложиш тази проверка. Аз бих я сложил в самото начало на while цикъла :)


от wnvko (3123 точки)


0

Реших да започна отначало, но стана по-зле :D

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Numerics; namespace ConsoleApplication11 { class Program { static void Main(string[] args) { string[] inputValley = Console.ReadLine().Split(new char[] { ',', ' ' }, StringSplitOptions.RemoveEmptyEntries); long[] valley = new long[inputValley.Length]; for (int i = 0; i < valley.Length; i++) { valley[i] = int.Parse(inputValley[i]); } int numberOfPatterns = int.Parse(Console.ReadLine()); long sum = 0; long bestSum = 0; for (int i = 0; i < numberOfPatterns; i++) { string[] inputPatterns = Console.ReadLine().Split(new char[] { ',', ' ' }, StringSplitOptions.RemoveEmptyEntries); long[] patterns = new long[inputPatterns.Length]; for (int patternsParse = 0; patternsParse < patterns.Length; patternsParse++) { patterns[patternsParse] = int.Parse(inputPatterns[patternsParse]); } sum = 0; sum += valley[0]; bool[] visited = new bool[valley.Length]; visited[0] = true; long possition = 0; bool broken = false; while (!broken) { foreach (var number in patterns) { long nextPossition = possition + number; if (nextPossition > 0 && nextPossition < valley.Length && visited[nextPossition] != true) { sum += valley[nextPossition]; visited[nextPossition] = true; possition = nextPossition; if (sum > bestSum) { bestSum = sum; } } else { broken = true; break; } } } } Console.WriteLine(bestSum); } } }


от tomhafner (75 точки)

0

Това, което изтърваш във новото си решение е, че шаблоните се "въртят". Например, ако имаш такава долина:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

и такъв шаблон за обхождане:

1, 3, -2

обхождането ще е следното:

- първа цифра от шаблона 1 -> отиваш на позиция едно -> долината става х, 2, 3, 4, 5, 6, 7, 8, 9, 10

- втор цифра от шаблона 3 -> отиваш на позиция четири -> долината става х, 2, 3, х, 5, 6, 7, 8, 9, 10

- трета цифра от шаблона -2 -> отиваш на позиция две -> долината става х, х, 3, х, 5, 6, 7, 8, 9, 10

Тук шаблона ти свършва и трябва да почнеш отново от първата му цифра:

- първа цифра от шаблона 1 -> отиваш на позиция три -> долината става х, х, х, х, 5, 6, 7, 8, 9, 10

- втор цифра от шаблона 3 -> отиваш на позиция шест -> долината става х, х, х, х, 5, х, 7, 8, 9, 10

- трета цифра от шаблона -2 -> отиваш на позиция четири -> позицията е посетена значи приключваш.

Успех и един съвет - чети мнооооого внимателно условията. Това може да ти спести много главоболия :)


от wnvko (3123 точки)