[Advanced C# Exercises] Stacks and Queues - 06. Truck Tour
Здравейте Колеги, някакви препоръки можете ли да дадете за тази задачка. Много дълго време я мъча, но повече от 20 точки не взимам.
Best Answer
Здравей,
Проблема в тази задача като цяло е неправилното увеличаване на индекса. Идеята е, че ако на една станция си и добавил някакво гориво и не не можеш да отидеш в следващата, то и ако тя ни е стартова точка(без да сме ѝ добавили нищо) пак няма да можеш. Следователно, ако не можеш да минем целия път, станциите през, които си минал не те интересуват и следващата стартова точка трябва да е тази на която си прекъснал. На практика станциите се roll-ват, просто индекса не се увеличава.
Пример:
11, 2 –> 5, 10 –> 1, 100 –> 400, 6. От първата станция можем да стигнем до предпоследната. И тук трябва да почнем от последния индекс, който е 3 и от него можем да минем всички станции. Но ако не сме го увеличили докато сме обхождали ще изпише грешен резултат - 1.
Ето и код на Java.
Здравей,
Дай да видим решението ти?
Здравей,
Пускамв и кода, който 10 пъти пренаписах по различен начин, но въпросът ми е по -скоро по условието. Може би аз не го разбирам като хората. http://pastebin.com/q5UqAJ9S
В задачата имаш N на брой станции наредени в кръг ( след последната следва първата ), всяка от тях ти дава определено количество гориво и знае колко километра има до следващата станция. Иска се да намериш първата станция, която ти позволява да направиш пълен кръг ( да се върнеш до нея ) без да ти свърши горивото по пътя.
Да разгледаме първия пример. Тук имаш 3 станции - A: 1-5, B: 10-3, C: 3-4. Още от тук става ясно че няма как да тръгнеш от станция А защото горивото, което ти дава няма да ти стигне до следващата станция ( 1-5 < 0 ). Пробваме B: тук ни дават 10 литра и имаме да минем път за 3 => възможно е да стигнем до следващата станция ( 10-3 >=0 ) => възможно е това да е отговор на задачата. Щом сме намерили станция Х, която ни позволява да стигнем до следващата се опитваме да обиколим всички станции и да стигнем пак до Х. Горивото, което ни е останало от пътя B -> C е 7 литра. Когато сме на станция C зареждаме 3 (7+3 = 10) и имаме да минем път до A за 4 ( 10 - 4 = 6 >= 0 ). Отиваме до А, зареждаме 1 литър ( 6 + 1 = 7) и имаме да минем 5 до B (7 - 5 >=0 ) Стъпим ли на B значи вече сме направили пълен кръг и изкарваме на конзолата B.
Много ти благодаря за помощта. Принципно и моята логика е същата. Този код, който пуснах е един от послените. Принципно в началото го правех с две опашки като завъртах последние и първия елемент и правих нова опашка. Пак ще го мъча. Мерси отново
https://github.com/DenisAngelov/SoftUni-Advanced-CSharp/blob/master/01.BasicStackOperations/06.TruckTour/TruckTour.cs
Ето го моето решение. Надявам се да помогне.
Колеги,
дайте коз къде бъркам?
https://github.com/iozzilina/CSharpAdvanced/blob/master/TruckTour.cs
минавам си през кръгчето с опашка, и ако намеря възможна стартова точка, копирам си опашката в един Лист, и си проверявам вътрешно в него. Ако не става, обратно през опашката.
какво пропускам?
благодаря предварително.
Ето го и моя код: http://pastebin.com/mnwvg2uf. Работи ама не съвсем. Изкарвам 80 точки и не мога да разбера къде бъркам. Ако някой има идея,че се побърках нещо вече.
Там където проверяваш дали горивото е свършило трябва да е fuel < 0, а не fule <= 0. Ако горивото ти падне под 0, тогава не можеш да минеш пътя, но ако е 0, ти е стигнало точно.
В повечето случаи когато имаш 70/80 точки, алгоритъма ти е верен, и тестовете не излизат за някакви гранични случаи.
Благодаря на всички. Отдавна намерих работещо решение. Явно е имало проблем с тестовете, защото още преди седмица мина 100/100
Здравейте!
Написах(преписах) кода(Solution for problem 06. Truck Tour) от видеото:
(https://youtu.be/XwfhSV7K2aI),
въпреки че го няма целия код никъде в окончателния му вид(това, което се копира от преподавателя и "субмитва" в Judge-a) и получих 0 точки.
Solution #1074761 by valenteeeen for problem 06. Truck Tour
Test #1 (Time limit)
Time used: 0.453 s
Memory used: 8.34 MB
Test #2 (Incorrect answer)
Time used: 0.015 s
Memory used: 9.11 MB
Test #3 (Incorrect answer)
Time used: 0.015 s
Memory used: 0.07 MB
Test #4 (Time limit)
Time used: 0.453 s
Memory used: 8.37 MB
Test #5 (Time limit)
Time used: 0.453 s
Memory used: 8.34 MB
Вижте видеото:
https://youtu.be/XwfhSV7K2aI
след 52 - та минута(решаването на задачата започва от 53:05 -та минута)
Къде сгреших? Къде е разликата - грешката ми(Къде са разликите - грешките ми)?
Преподавателят "субмитва" в Judge-a кода, който аз преписах и получи 100 точки?
Ето моя преписан от видеото код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Pump
{
class TruckTour
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
Queue<GasPump> pumps = new Queue<GasPump>();
for (int i = 0; i < n; i++)
{
string[] pumpInfo = Console.ReadLine().Split();
int distanceToNext = int.Parse(pumpInfo[1]);
int amountOfGas = int.Parse(pumpInfo[0]);
GasPump pump = new GasPump(distanceToNext, amountOfGas, i);
pumps.Enqueue(pump);
}
GasPump starterPump = null;
bool completeJourney = false;
while (true)
{
GasPump currentPump = pumps.Dequeue();
pumps.Enqueue(currentPump);
starterPump = currentPump;
int gasInTank = currentPump.amountOfGas;
while (gasInTank >= currentPump.distanceToNext)
{
currentPump = pumps.Dequeue();
pumps.Enqueue(currentPump);
if (currentPump == starterPump)
{
completeJourney = true;
break;
}
}
gasInTank += currentPump.amountOfGas;
if (completeJourney)
{
Console.WriteLine(currentPump indexOfPomp);
break;
}
}
}
}
public class GasPump
{
public int distanceToNext;
public int amountOfGas;
public int indexOfPomp;
public GasPump(int distanceToNext, int amountOfGas, int indexOfPomp)
{
this.distanceToNext = distanceToNext;
this.amountOfGas = amountOfGas;
this.indexOfPomp = indexOfPomp;
}
}
}
Класове не са ми преподавани до момента в СофтУни, не са изучавани от мен и не зная защо на упражненията не ни решиха тази задача използвайки преподаденото до момента ... !
След като около три дни се занимавах с тази задача, успях да напиша работещ код използвайки само неща от вече изучените уроци и в Judge-a с този код получих 100 точки !
Споделям ви и кода:
using System;
using System.Collections.Generic;
using System.Linq;
class _06_02_TruckTour
{
static void Main()
{
int n = int.Parse(Console.ReadLine()),k=0,sum=0,m=0;
int[] pumpsInfo = new int[2*n];
for (int i = 0; i < n; i++)
{
int[] pumpInfo = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
pumpsInfo[i] = pumpInfo[0];
pumpsInfo[i+n] = pumpInfo[1];
}
Queue<int> pumps = new Queue<int>();
pumps.Enqueue(0);m++;
int amountOfGas = pumpsInfo[0];
int distanceToNext = pumpsInfo[n];
sum = amountOfGas - distanceToNext;
for (int i = 1; i <= n+k; i++)
{
if (sum<0)
{
pumps.Clear();k+=m;m = 0;
pumps.Enqueue(i);
amountOfGas = pumpsInfo[i%n];distanceToNext = pumpsInfo[i%n+n];
sum = amountOfGas - distanceToNext;
}
else
{
m++;
pumps.Enqueue(i);
amountOfGas = pumpsInfo[i % n]; distanceToNext = pumpsInfo[i % n + n];
sum += amountOfGas - distanceToNext;
}
}
Console.WriteLine(pumps.Peek());
}
}
Ето и моето решение. С Queue<Tuple<int, int, int>> я направих.
https://github.com/SoftuniAdvancedCSharp/Stacks-and-Queues/blob/master/06.TruckTour/TruckTour.cs
Ето и моето решение (доста късно, но все пак). Използването на опашка, просто усложнява решението според мен.
http://pastebin.com/eC4xuDmY
Аз също зациклих на 20 процента. Ако може малко помощ, това е кодът https://pastebin.com/9ES6Gg8m
На пръв поглед забелязвам един проблем.
На 40-ти ред добавяш горивото от текущата точка към текущото гориво, а на 42-ри ред записваш модифицираното гориво обратно в опашката, което променя данните и съответно ще ти счупи резултатите в повечето сценарии. За да го избегнеш, трябва да прочетеш горивото от текущата точка във временна променлива (както правиш с разстоянието на 41-ви ред), която да добавиш към текущото гориво и да добавиш обратно в опашката.
Оправен код:
long current_petrol = tours.Dequeue();
petrol += current_petrol;
long dist = tours.Dequeue();
tours.Enqueue(current_petrol);
tours.Enqueue(dist);
Между другото, има и по-оптимално решение на проблема в тази задача.
Успех!
Благодаря за помощта, но дори след корекцията пак не ми дава повече от 20 точки.
using System;
using System.Linq;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
Queue<int[]> truckTour = new Queue<int[]>();
for(int i =0; i<n; i++)
{
int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
int petrol = input[0];
int distance = input[1];
truckTour.Enqueue(input);
}
int startIndex = 0;
while(true)
{
int currentPetrol = 0;
foreach(var info in truckTour)
{
int truckPetrol = info[0];
int truckDistance = info[1];
currentPetrol += truckPetrol;
currentPetrol -= truckDistance;
if (currentPetrol < 0)
{
int[] element = truckTour.Dequeue();
truckTour.Enqueue(element);
startIndex++;
break;
}
}
if (currentPetrol >= 0)
{
Console.WriteLine(startIndex);
break;
}
}
}
}
}
Това е решението от видеото с упражненията.