Hallo,
ich möchte am Bundeswettbewerb Informatik teilnehemen.
Die meisten Aufgaben sind ja sehr leicht und lassen sich schnell lösen.
Die einzige Aufgabe, die ich noch nicht gelöst habe ist Aufgabe 4.
Ich glaube das ist mit Abstand die schwierigste Aufgabe.
Mein Ansatz ist einfach alle verschiedene Möglichkeiten, die der Mann da
gehen kann durchzugehen. Das würde sich dann Brute Force nennen.
Aber das kann es ja wohl nicht sein, dass dauert wahrscheinlich auch
viel zu lange, wenn es mal 100 Teekücken geben würde...
Marvin
Hier die Aufgabe:
Aufgabe 4: Kreisrund
Hugo Langbein ist stolzer Vater zweier M¨adchen, die den
Betriebskindergarten seiner Firma
besuchen. F¨ur den Tagesausflug des Kindergartens hat er sich bereit
erkl¨art, bei den Kollegen
die Elternbeitr¨age einzusammeln. Aber, oh weh, er hat es vergessen!
Jetzt ist nur noch wenig
Zeit.
Man sollte meinen, Hugo k¨onnte nun schnell bei seinen Kollegen
vorbeischauen und das Vers¨aumte
nachholen. Doch das ist nicht so einfach: Hugo arbeitet bei der
Kreisrund AG, deren Mitarbeiter
extrem arbeitsw¨utig sind. Sie wollen auf keinen Fall w¨ahrend der
Arbeitszeit gest¨ort
werden.
Zum Gl¨uck f ¨ur Hugo sind seine Kollegen aber auch sehr durstig: Jeder
Mitarbeiter hat eine
pers¨onliche Teezahl, die seinen Teezyklus beschreibt: Jemand mit
Teezahl t trinkt alle t Minuten
in einer Teek¨uche einen Tee und beginnt damit genau t Minuten nach dem
Arbeitsbeginn. Der
Arbeitsbeginn ist f ¨ur alle gleich.
Die Kreisrund AG befindet sich im obersten Stockwerk eines ringf¨ormigen
Geb¨audes. Die
Teek¨uchen liegen in gleichen Abst¨anden auf dem Flur und sind
nummeriert. Die erste und
letzte Teek¨uche sind benachbart. Um Tee zu trinken, geht ein
Mitarbeiter immer zur selben
Teek¨uche.
Hugo erinnert sich an die Elternbeitr¨age genau zum Arbeitsbeginn und
ist gerade in Teek¨uche
1. Wenn er sofort mit dem Einsammeln beginnt, k¨onnte er es vielleicht
noch schaffen. Damit er
einen Kollegen in dessen Teek¨uche trifft, muss Hugo gleichzeitig mit
ihm ankommen, oder dort
schon auf ihn warten. Hugo braucht 20 Sekunden von einer Teek¨uche zu
einer benachbarten.
Das Bezahlen geht sehr schnell, so dass man sagen kann, es kostet Hugo
keine Zeit.
in jedem Forum eine Aufgabe lösen lassen und schon hat man gewonnen :)
mit so einer Einstellung ist man zum BWL Studium predestiniert
>Hugo Langbein ist stolzer Vater zweier M¨adchen, die den>Betriebskindergarten seiner Firma>besuchen.
.. einfach von deren Lohn das Geld abziehen :-^^
es steht auch nirgends wieviel Kinder ein Mitarbeiter hat.
Hallo Marvin,
brute force bedeutet, alle denkbaren Möglichkeiten durchzurechnen. Die
damit verbundene Komplexität kann schnell zu hoch werden. Denke darüber
nach, welche Möglichkeiten einer Vereinfachung es gibt.
Außerdem kann es sinnvoll sein, aus einem komplexen Prblem mehrere
kleine zu machen - Stichwort Rekursion.
Gruß HT
>Hugo erinnert sich an die Elternbeiträge genau zum Arbeitsbeginn und>ist gerade in Teeküche
das würde ja bedeuten, Hugo hat die Teezahl 0 und würde den ganzen Tag
die Teeküche nicht verlassen. Wieso wurde er noch nicht gefeuert????
ok, spass beiseite.
Soll t eine Ganzzahl sein?
Was soll das Ziel dieser Aufgabe sein? Sollst du eine Ablauf erstellen,
der das bestmögliche Vorgehen beschreibt?
Danke für die doch kommenden Antworten.
Ziel der Aufgabe soll sein, herauszufinden ob oder ob nicht Herr
Langbein es in einer bestimmten Zeitspanne noch schaffen kann.
Wenn es möglich ist, soll der Weg angegeben werden.
Marvin
>Ziel der Aufgabe soll sein, herauszufinden ob oder ob nicht Herr>Langbein es in einer bestimmten Zeitspanne noch schaffen kann.
Ja er kann es in einer BESTIMMTEN Zeitspanne noch schaffen... >:->
Mir stellt sich eine ganz andere Frage. Warum will man an einem
Wettbewerb teilnehmen wenn Einem dazu die Grundlagen fehlen? Wäre es da
nicht sinnvoller an einem Preisauschreiben in der Bildzeitung
teilzunehmen? Die Eingangsvoraussetzungen dafür dürfen marvinkompatibler
sein...
Erste Frage: welche Angaben fehlen in der Aufgabenstellung:
Die Gesamtzahl der Kollegen ist nicht erwähnt.
Ob die Teezahlen lückenlos und z.B. bei 1 oder 2 beginnend vorhanden
sind - damit ergäbe sich mit einer (auch nicht vorgegebenen) maximalen
Tagesarbeitszeit wenigstens eine Obergrenze.
"Persönliche" Teezahl würde ich interpretieren als nur je einmal
vorhanden, auch das ist nicht sicher.
Die Anzahl der Teeküchen fehlt.
In dem obigen Zitat fehlt einfach der letzte Absatz, damit wird die
Aufgabenstellung klarer
http://www.bwinf.de/uploads/media/bwinf271-aufgabenblatt.pdf
"Hilf Hugo und schreibe ein Programm, das Hugo sagt, ob und, falls ja,
wie er es innerhalb der ihm verbleibenden Zeit noch schaffen kann, das
Geld einzusammeln. Als Eingabe erhält dein Programm Hugos Zeitlimit in
Sekunden, die Anzahl der Teeküchen und eine Liste der Elternkollegen mit
ihren Teezahlen und Teeküchennummern. Beispiele für Eingabedaten findest
du
unter http://www.bwinf.de/aufgaben/material . Teste dein Programm mit
diesen und eigenen Daten und dokumentiere die Ergebnisse."
http://www.bwinf.de/index.php?id=457
Das heißt, mit Erhalt der Liste ist die Belegung aller Teeküchen für den
ganzen Tag vollständig vorgegeben.
"Leerminuten" sind möglichst zu vermeiden.
Sprünge zu weiter entfernten Teeküchen kosten Zeit, Hugo sollte nur die
nächsten drei benachbarten links und rechts besuchen, die kann er in
einer Minute erreichen.
Ob es dazu eine geschlossene Lösung gibt? Ich vermute, man muß wie ein
Schachprogramm alle möglichen Züge durchprobieren und nach "Zugstärke"
bewerten, eventuell nur erfolgversprechendere Züge weiterverfolgen.
Wie es scheint ist es nicht die erste Aufgabe, bei der "Marvin" Hilfe
braucht.
Aufgabe 3 mit den Gebirkszügen, wurde hier auch schon erfragt.
Vielleicht können "wir" ja als Forum direkt dran teilnehmen das nächste
mal ;).
...ich habe es mal ausprobiert. Es lässt sich ein Algorithmus finden
wenn man überlegt, welche Besuche überhaupt stattfinden und die dann in
eine sinnvolle Reihenfolge bringt.
Für die Umsetzung habe ich 100 Codezeilen benötigt.
Die Lösung werde ich natürlich nicht online stellen, aber ich denke, ein
Hinweis ist ok.
@HT:
100 Zeilen? Für eine optimale Lösung?
Ich brauche wesentlich mehr und weiss dazu nicht mal sicher, ob die
Lösung in jedem Falle optimal ist.. Im ersten "Durchlauf" ist sie das
sicher, aber sobald der "Offset" durch die Intervallverschiebung hinzu
kommt, bin ich mir nicht mehr so ganz sicher..
Wäre an einem Lösungsaustausch interessiert, wie kann ich dich
erreichen?
LG
