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

35ος ΠΔΠ Γ' Φάση
Χημικές Ενώσεις (chemicals)

[30 Μονάδες]

Ο μικρός Βέρνερ αφότου τακτοποίησε τις διαφορές που είχε με τον Μπορ, αποφάσισε να ασχοληθεί σοβαρά με την έρευνα και να ανακαλύψει μια νέα συνθετική ουσία. Αποφασισμένος, λοιπόν, τρέχει στο κοντινότερο εργοστάσιο, ώστε να προμηθευτεί χημικά στοιχεία.

Το εργοστάσιο εκείνη την ημέρα έχει διαθέσιμα \(N\) χημικά στοιχεία τα οποία είναι τοποθετημένα σε μια σειρά. Ο ατομικός αριθμός των στοιχείων είναι γνωστός και ο Βέρνερ είναι διατεθειμένος να αγοράσει όσο πιο πολλά μπορεί και να τα χρησιμοποιήσει όλα για τη νέα του συνθετική ουσία. Ωστόσο, γνωρίζει πως πρέπει να είναι προσεκτικός με τις επιλογές του καθώς έχει παρατηρήσει πως όταν ενώνει δύο στοιχεία που το άθροισμα των ατομικών τους αριθμών είναι πολλαπλάσιο του αριθμού \(K\), τότε προκαλείται έκρηξη, και αυτό θέλει να το αποφύγει. Επίσης, γνωρίζει πως τα στοιχεία τα οποία θα αποφασίσει να αγοράσει θα πρέπει να είναι συνεχόμενα στην σειρά καθώς είναι ευκολότερο και οικονομικότερο να εξάγονται μαζί ως ομάδα, παρά μεμονωμένα.

Ο μικρός Βέρνερ βιάζεται να γυρίσει στο εργαστήριο του και καθώς δυσκολεύεται να βρει ποιό είναι το μέγιστο πλήθος από στοιχεία που μπορεί να αγοράσει, αναθέτει το πρόβλημα αυτό σε εσάς.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες PASCAL, C, C++, Java το οποίο θα διαβάζει τις τιμές του \(N\) και του \(K\), καθώς και τους ατομικούς αριθμούς των στοιχείων κατά σειρά και θα εκτυπώνει το μέγιστο πλήθος από στοιχεία που μπορεί να αγοράσει ο Βέρνερ.

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

Το αρχείο εισόδου με όνομα chemicals.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς \(N\), δηλαδή το πλήθος των χημικών στοιχείων, και \(K\), χωρισμένους με ένα κενό διάστημα. Στην επόμενη γραμμή ακολουθούν οι \(N\) ατομικοί αριθμοί \(A_i\) (όπου \(1 \leq i \leq N\)) των χημικών στοιχείων, κατά σειρά.

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

Το αρχείο εξόδου με όνομα chemicals.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το μέγιστο πλήθος από στοιχεία που μπορεί να αγοράσει ο Βέρνερ.

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

1o

chemicals.in chemicals.out
3 5
1 2 1
3

Εξήγηση: Ο Βέρνερ μπορεί να πάρει και τα τρία στοιχεία της σειράς.

2o

chemicals.in chemicals.out
6 3
6 7 9 1 4 5
4

Εξήγηση: Ο Βέρνερ μπορεί να πάρει τα τέσσερα στοιχεία \(7, 9, 1\) και \(4\), που είναι συμβατά μεταξύ τους. Δεν τον συμφέρει να πάρει το \(6\), γιατί \(6+9=15\) που είναι πολλαπλάσιο του \(3\), οπότε τότε θα έπρεπε να μην πάρει το \(9\). Επίσης, δεν τον συμφέρει να πάρει το \(5\), γιατί \(4+5=9\) που επίσης είναι πολλαπλάσιο του \(3\).

3o

chemicals.in chemicals.out
8 13
13 12 14 10 8 12 10 8
5

Περιορισμοί:

  • \(1 \leq N \leq 1.000.000\)
  • \(1 \leq K \leq 1.000.000.000\)
  • \(1 \leq A_i \leq 1.000.000.000\)
  • Οι ατομικοί αριθμοί των στοιχείων δεν είναι απαραίτητα διαφορετικοί.
  • Για περιπτώσεις ελέγχου συνολικής αξίας 30%, θα είναι \(K = 3\).
  • Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(N \leq 10.000\).

Προσοχή:

Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.