33ος ΠΔΠ B’ Φάση Γυμνασίου

Τα δώρα των διδύμων (twingift)

Ο Ανδρέας και η Βάσω είναι δίδυμα αδέλφια. Την επόμενη εβδομάδα έχουν τα γενέθλιά τους και η γιαγιά τους ετοιμάζεται να τους πάρει από ένα δώρο στον καθέναν. Έχει μια λίστα A με όλα τα δώρα που θα άρεσαν στον Ανδρέα και άλλη μία λίστα B με όλα τα δώρα που θα άρεσαν στη Βάσω.

Θέλει να επιλέξει τα δώρα των δύο παιδιών έτσι ώστε το άθροισμα των τιμών των δύο δώρων να είναι μεταξύ L και R ευρώ.

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

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις τιμές των ορίων L και R και τις τιμές των δώρων που προορίζονται για τα δύο παιδιά και θα εκτυπώνει το πλήθος των διαφορετικών ζευγών δώρων που μπορεί η γιαγιά να αγοράσει για τα δύο παιδιά, έτσι ώστε το άθροισμα των τιμών τους να είναι εντός των ορίων.

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

Τα αρχεία εισόδου με όνομα twingift.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχουν τέσσερις ακέραιοι αριθμοί χωρισμένοι ανά δύο με ένα κενό διάστημα: το πλήθος N των υποψήφιων δώρων για τον Ανδρέα, το πλήθος M των υποψήφιων δώρων για τη Βάσω, η τιμή L του ελάχιστου επιθυμητού αθροίσματος και η τιμή R του μέγιστου επιθυμητού αθροίσματος. Οι επόμενες δύο γραμμές θα περιέχουν N και M ακέραιους αριθμούς, αντίστοιχα, χωρισμένους ανά δύο με ένα κενό διάστημα: τις τιμές A1,A2,…,AN των υποψήφιων δώρων για τον Ανδρέα και τις τιμές B1,B2,…,BM των υποψήφιων δώρων για τη Βάσω. Προσέξτε ότι οι τιμές θα δίνονται σε τυχαία σειρά και ότι είναι πιθανό δύο δώρα να έχουν την ίδια τιμή.

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

Τα αρχεία εξόδου με όνομα twingift.out είναι αρχεία κειμένου με την εξής δομή. Περιέχουν ακριβώς μία γραμμή η οποία περιέχει έναν ακέραιο αριθμό: το πλήθος των ζευγών διαφορετικών δώρων που μπορεί η γιαγιά να αγοράσει, δοθέντων των περιορισμών.

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

1≤N≤1.000.000,
1≤M≤1.000.000,
0≤Ai≤1.000.000.000,
0≤Bi≤1.000.000.000,
0≤L≤R≤2.000.000.000,
Η σωστή απάντηση δε θα υπερβαίνει το 2.000.000.000.

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

1^o

twingift.in	twingift.out
5 5 13 16 4 0 7 9 5 6 3 1 4 9	6

Εξήγηση: Υπάρχουν 6 ζεύγη δώρων με άθροισμα μεταξύ 13 και 16 ευρώ: 4+9, 7+6, 7+9, 9+6, 9+4, 5+9.

2^o

twingift.in	twingift.out
10 7 28 30 15 17 7 14 3 12 4 15 8 17 13 17 1 4 7 9 4	5

Εξήγηση: Yπάρχουν 5 ζεύγη δώρων με άθροισμα μεταξύ 28 και 30: 15+13, 17+13, 12+17, 15+13, 17+13. Προσέξτε ότι για τον Ανδρέα υπάρχουν δύο διαφορετικά δώρα με τιμή 15 και άλλα δύο διαφορετικά δώρα με τιμή 17.

Παρατηρήσεις

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