Αρχική > 22ος ΠΔΠ

22ος ΠΔΠ Καμπ (juniors)
Κύκλος πόλης (citycirc)

Δίνονται \(N\) πόλεις, αριθμημένες από \(1\) μέχρι \(N\) (συμπεριλαμβανομένων) και διατεταγμένες κατά μήκος μιας κυκλικής διαδρομής (η επόμενη της πόλης \(k\) στην κυκλική διαδρομή είναι η πόλη \(k+1\), όταν \(k < N\), και η πόλη \(1\), όταν \(k = N\)). Ένας κρατικός υπάλληλος πρόκειται να επισκεφθεί όλες τις πόλεις με τη σειρά που προαναφέρθηκε και να διευθετήσει τις φορολογικές εκκρεμότητες των πολιτών απέναντι στο κράτος (καταβολή φόρου) και του κράτους απέναντι στους πολίτες (επιστροφή φόρου) σε κάθε πόλη. Για κάθε πόλη \(k\) (όπου \(1 \leq k \leq N\)) δίνεται ένας ακέραιος \(b_k\) που ισούται με το άθροισμα των φορολογικών εκκρεμοτήτων των κατοίκων της πόλης \(k\) (ο αριθμός αυτός μπορεί να είναι θετικός, αρνητικός, ή \(0\)). Έτσι αν το \(b_k\) είναι θετικό, ο υπάλληλος φεύγει από την πόλη \(k\) με \(b_k\) ευρώ περισσότερα απ’ όσα είχε όταν ήρθε, αν το \(b_k\) είναι αρνητικό, ο υπάλληλος φεύγει από την πόλη \(k\) με \(\lvert b_k \rvert\) ευρώ λιγότερα, και αν το \(b_k\) είναι \(0\), ο υπάλληλος φεύγει από την πόλη \(k\) με το ίδιο διαθέσιμο ποσό. Ο υπάλληλος δεν μπορεί να συνεχίσει την περιοδεία του αν εμφανίζεται ότι διαθέτει αρνητικό ποσό μετά την επίσκεψή του σε κάποια πόλη, αφού αυτό δηλώνει αδυναμία εκπλήρωσης κάποιων υποχρεώσεων επιστροφής φόρου στην πόλη.

Πρόβλημα

Γράψτε ένα πρόγραμμα που να βρίσκει την πρώτη πόλη (δηλαδή αυτή με τον μικρότερο αριθμό), από την οποία αν ξεκινήσει ο κρατικός υπάλληλος την περιοδεία του με μηδέν ευρώ, θα μπορέσει να την ολοκληρώσει.

Αρχεία εισόδου

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος των πόλεων \(N\). Η δεύτερη γραμμή της εισόδου θα περιέχει τους \(N\) ακέραιους αριθμούς \(b_1, b_2, ..., b_N\), χωρισμένους με κενά διαστήματα.

Αρχεία εξόδου

Η έξοδος πρέπει να αποτελείται από μία μόνο γραμμή που να περιέχει ακριβώς έναν φυσικό αριθμό: τον αριθμό της πρώτης πόλης από την οποία αν ξεκινήσει ο κρατικός υπάλληλος την περιοδεία του με μηδέν ευρώ, μπορεί να την ολοκληρώσει. Αν δεν υπάρχει τέτοια πόλη, ο αριθμός στην έξοδο πρέπει να είναι \(0\).

Παράδειγμα Αρχείων Εισόδου - Εξόδου:

1o

citycirc.in citycirc.out
6
-50 20 15 30 0 -5
2

2o

citycirc.in citycirc.out
8
35 10 -55 -40 30 -70 60 30
7

3o

citycirc.in citycirc.out
6
-50 20 -15 30 18 -5
0

Περιορισμοί

  • \(2 \leq N \leq 2.000.000\).