| 1. Frage: |
Frage:
Die Erderwärmung macht auch vor dem Nordpol nicht halt und so hat der Weihnachtsmann ein Problem: Der Schnee am Nordpol wird immer weniger, die Rentiere beschweren sich schon über die unebene Start- und Landebahn. Deswegen hat sich der Weihnachtsmann ein paar Schneekanonen besorgt, die er entlang der Bahn aufgestellt hat. Jede Kanone hat ein (praktisch unbegrenzt) großes Wasserreservoir, aus dem sie Schnee macht.
Um diese Reservoire aufzufüllen, hat er also das Schmelzwasser aufgefangen und in den jeweils nächsten Behälter gebracht. Damit die Schneedecke schön gleichmäßig wird, muss aber in jedem Vorratsbehälter genau gleich viel Wasser sein. Leider hat er nur noch einen löchrigen Zinkeimer zum Transportieren, der pro Meter Wegstrecke 1 Liter Inhalt verliert.
Der Weihnachtsmann möchte nun Wasser umfüllen, so dass maximal viel Schnee erzeugt wird. Da für die nächsten Jahre keine Besserung der Lage in Sicht ist, hat er dich beauftragt, ein allgemeines Programm zum Lösen des Problems zu schreiben. Genauer soll es Folgendes tun:
Dein Programm bekommt über die Konsole eine Zeile mit einer einzigen Zahl n, der Anzahl der Schneekanonen, zwischen 1 und 10^5 (es ist eine lange Bahn). Es folgen n weitere Zeilen mit je zwei Zahlen p, der Position dieser Schneekanone in Metern, und w, dem Anfangsfüllstand in Litern, beide ganzzahlig und zwischen 0 und 10^12 (ja, es ist eine lange Bahn). Die erwartete Ausgabe ist die maximale ganze Zahl x, so dass nach Umfüllen jede Schneekanone mindestens x Liter enthält.
Der Weihnachtsmann war freundlich genug, die Kanonen in der Eingabe nach aufsteigender Position zu sortieren. Er versichert dir auch, dass keine zwei Schneekanonen die gleiche Position besitzen, da sie beim Aufeinanderstellen doch zu oft umkippen. Außerdem hat er seine handberechneten Lösungen früherer, schneereicherer Jahre herausgekramt, die er dir zur Hilfe gerne überlasst:
| Eingabe: | 3
5 70
15 100
1200 20 |
| Eingabe: | 4
20 300
40 400
340 700
360 600 |
Wenn du glaubst, eine allgemeine Lösung gefunden zu haben, kannst du deinen Quelltext hier hochladen (über eine etwaige Bezahlung wird der Weihnachtsmann dann zu einem späteren Zeitpunkt mit dir diskutieren):
www.entwickler-ecke.de/ags2012_upload.php
Wir akzeptieren natürlich unsere "Haussprachen" Delphi (Prism) und C#, aber auch alle anderen menschenverständlichen Sprachen, solange wir zum Kompilieren nicht gerade Geld ausgeben oder in ein Computermuseum einbrechen müssen.
Antworten:
- Ich habe meine Lösung abgegeben/hochgeladen
|
