Witam.
Musze napisac algorytm zadania znajdujacego sie ponizej. Wydaje mi sie ze trzeba tu uzyc algorytmu zachlannego ale nie jestem pewien poniewaz dla niektorych danych wejsciowych nie bedzie on chyba optymalny. Bede wdzieczny za jakas pomoc. Nie chodzi mi o to aby ktos napisal mi caly algorytm, tylko abyscie mnie prawidlowo naprowadzili bo szczerze mowiac to nie wiem nawet od czego zaczac :(
Wklejam tresc zadania:
Studenci II roku informatyki zaliczyli pomyślnie sesję zimową i wybierają się na wycieczkę po Europie. Co prawda lotem bliżej, ale na pewno nie taniej, więc jako środek transportu uwzględniają wyłącznie autokar. Spędzą w drodze wiele dni, zatem opłaty za noclegi stanowią poważną część kosztów podróży. Ze względu na bezpieczeństwo podróży każdy autokar jedzie tylko w ciągu dnia i nie może przejechać więcej niż 800 km. Noc na trasie (poza początkiem i końcem) studenci i kierowcy spędzają w hotelach. Oczywiście trzeba podróż zaplanować optymalnie, czyli tak, aby koszt noclegów w ciągu całej wycieczki był jak najmniejsza. Przedsiębiorstwo przewozowe znając potrzebę obniżenia kosztów wycieczki, postanowiło zbadać, czy opłaci się układanie planów podróży tak, aby suma opłat za noclegi była możliwie najniższa, nawet wtedy gdyby to miało przedłużyć podróż. W każdej ofercie jest podana odległość hotelu od początku trasy i cena jednostkowa noclegu. Studenci podróżują tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża tylko raz. Nie ma dwóch hoteli w jednym punkcie, więc każdy hotel może być zidentyfikowany przez jego odległość od początku trasy. Nie planuje się noclegu ani na początku ani na końcu trasy. Liczba osób w autobusie nie zmienia się i wszyscy razem z kierowcą płacą taką samą cenę jednostkową za nocleg w tym samym hotelu. Pojemność hoteli jest na tyle dużą, że wszyscy mogą w nim zanocować. Na każdym odcinku trasy o długości 800 km jest przynajmniej jeden hotel. Zakładamy, że długość trasy jest liczbą całkowitą d<=16000, a liczba hoteli h<=1000.
Pomóż przedsiębiorstwu, pisząc program, który po wczytaniu długości trasy, liczby hoteli oraz oferty hoteli (cena jednego noclegu za jedną osobę) znajduje plan najtańszej podróży, tzn. takiej, której suma opłat za hotele była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą liczbą noclegów.