Εδώ μπορείτε να δημοσιεύετε και να συζητάτε τις λύσεις σας για την πρώτη φάση του 29ου ΠΔΠ.
Καλά αποτελέσματα σε όλους
Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ
-
- Δημοσιεύσεις: 1
- Εγγραφή: Τετ Φεβ 15, 2017 5:06 pm
Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ
Τι έγινε ρε παιδιά καμία λύση φέτος?
Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ
Η λύση μου ήταν η εξής (O(N) πολυπλοκότητας):
Φτιάχνω 3 pair που αποθηκεύουν 2 ακεραίους το καθένα ,τον ίδιο τον αριθμό και τον αριθμό κλήσεων του, τα ans1,ans2,ans3.Θέτουμε τον 2ο ακέραιο κάθε pair 0 και ορίζουμε ένα array από ακεραίους με 10000 θέσεις ,η iοστή θέση του array θα αποθηκεύει τον αριθμό κλήσεων του αριθμού i+1.Τέλος διαβάζουμε την είσοδο και για κάθε αριθμό που διαβάζουμε κάνουμε τα εξής:
1)αυξάνουμε κατά 1 τον αριθμό εμφανίσεων του αριθμού που διαβάσαμε
2)ελέγχουμε αν αυτός ο αριθμός έχει περισσότερες κλήσεις από το ans1,αν ναι τότε βάλε αυτό τον αριθμό ως ans1,το ans1 πήγαινε το στο ans2 και το ans2 στο ans3.Ομοίως ελέγχουμε και για τα ans2 και ans3.
Παρακάτω ο κώδικάς μου.(Πιθανώς να γίνεται και με λιγότερα if):
Φτιάχνω 3 pair που αποθηκεύουν 2 ακεραίους το καθένα ,τον ίδιο τον αριθμό και τον αριθμό κλήσεων του, τα ans1,ans2,ans3.Θέτουμε τον 2ο ακέραιο κάθε pair 0 και ορίζουμε ένα array από ακεραίους με 10000 θέσεις ,η iοστή θέση του array θα αποθηκεύει τον αριθμό κλήσεων του αριθμού i+1.Τέλος διαβάζουμε την είσοδο και για κάθε αριθμό που διαβάζουμε κάνουμε τα εξής:
1)αυξάνουμε κατά 1 τον αριθμό εμφανίσεων του αριθμού που διαβάσαμε
2)ελέγχουμε αν αυτός ο αριθμός έχει περισσότερες κλήσεις από το ans1,αν ναι τότε βάλε αυτό τον αριθμό ως ans1,το ans1 πήγαινε το στο ans2 και το ans2 στο ans3.Ομοίως ελέγχουμε και για τα ans2 και ans3.
Παρακάτω ο κώδικάς μου.(Πιθανώς να γίνεται και με λιγότερα if):
Κώδικας: Επιλογή όλων
#include <iostream>
#include <sstream>
#include <fstream>
#include <utility>
using namespace std;
int main() {
ifstream fin;
ofstream fout;
fin.open("sch.in");
fout.open("sch.out");
int IP[10000];
int N;
for(int ii=0;ii<10000;ii++)IP[ii]=0;
fin >> N;
// Τα 3 ζεύγη ακεραίων
pair<int,int> ans_1,ans_2,ans_3;
ans_1.second=-1;
ans_2.second=-1;
ans_3.second=-1;
for(int ii=0;ii<N;ii++){
// Διάβασε το χ
int x;
fin >> x;
// +1 κλήσεις στο χ
IP[x-1]++;
// Έλεγξε αν το χ έχει περισσότερες κλήσεις από το ans1
if(IP[x-1]>ans_1.second){
//Αν το χ είναι το ans1
if(x==ans_1.first)ans_1.second++;
//Αν το χ είναι το ans2
else if(x==ans_2.first){
ans_2.first=ans_1.first;
ans_2.second=ans_1.second;
ans_1.first=x;
ans_1.second=IP[x-1];
}
// Αλλιώς βάλε το χ στο ans1,το ans1 στο ans2 και το ans2 στο ans3
else{
ans_3.first=ans_2.first;
ans_3.second=ans_2.second;
ans_2.first=ans_1.first;
ans_2.second=ans_1.second;
ans_1.first=x;
ans_1.second=IP[x-1];
}
continue;
}
// Έλεγξε αν το χ έχει περισσότερες κλήσεις από το ans2
if(IP[x-1]>ans_2.second){
//έλεγξε αν το χ είναι το ans2
if(x==ans_2.first)ans_2.second++;
//βάλε το χ στο ans2
else{
ans_3.first=ans_2.first;
ans_3.second=ans_2.second;
ans_2.first=x;
ans_2.second=IP[x-1];
}
continue;
}
// έλεγξε αν το χ έχει περισσότερες κλήσεις από το ans3
if(IP[x-1]>ans_3.second){
//έλεγξε αν το χ είναι το ans3
if(x==ans_3.first)ans_3.second++;
// βάλε το χ στο ans3
else{
ans_3.first=x;
ans_3.second=IP[x-1];
}
continue;
}
}
fout << ans_1.first <<" "<< ans_2.first<< " " << ans_3.first<< endl;
return 0;
}
-
- Δημοσιεύσεις: 2
- Εγγραφή: Σάβ Δεκ 31, 2016 5:50 pm
Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ
Η λύση μου:
Φτιάχνω ένα map όπου το κλειδί είναι ο αριθμός του server και η τιμή του κλειδιού οι επισκέψεις του. Μετα περνάω σε ένα vector τα ζευγάρια (επισκέψεις, server) και τον ταξινομώ σε φθίνουσα σειρά με βάση τις επισκέψεις. Τέλος εκτυπώνω τους 3 πρώτους servers.
Πολυπλοκοτητα: Ο(S log S) [S εδώ είναι το id του κάθε server (S <= 10000)]
Κώδικας:
Φτιάχνω ένα map όπου το κλειδί είναι ο αριθμός του server και η τιμή του κλειδιού οι επισκέψεις του. Μετα περνάω σε ένα vector τα ζευγάρια (επισκέψεις, server) και τον ταξινομώ σε φθίνουσα σειρά με βάση τις επισκέψεις. Τέλος εκτυπώνω τους 3 πρώτους servers.
Πολυπλοκοτητα: Ο(S log S) [S εδώ είναι το id του κάθε server (S <= 10000)]
Κώδικας:
Κώδικας: Επιλογή όλων
#include <bits/stdc++.h>
using namespace std;
int N, S;
map<int, int> visit;
map<int, int>::iterator it;
vector<pair<int, int> > ans;
int main(){
freopen("sch.in", "r", stdin);
freopen("sch.out", "w", stdout);
cin >> N;
while(N--){
cin >> S;
visit[S]++;
}
for(it = visit.begin(); it != visit.end(); ++it){
ans.push_back(make_pair(it -> second, it -> first));
}
sort(ans.rbegin(), ans.rend());
for(int i = 0; i < 3; i++){
cout << ans[i].second << ' ';
}
cout << '\n';
return 0;
}
Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ
Ουσιαστικά φτιάχνω ένα map, με τα ids των server για key και τις εμφανίσεις για value, διαβάζω το input, μετράω τις εμφανίσεις στο map, φτιάχνω ένα vector από pairs με τα περιεχόμενα του map, κάνω sort με βάση το δεύτερο στοιχείο (τις εμφανίσεις) στα πρώτα μόνο τρία στοιχεία (με την partial_sort), και βάζω στο output τα τρία πρώτα αυτά στοιχεία.
Κώδικας: Επιλογή όλων
#define IN_FILE "sch.in"
#define OUT_FILE "sch.out"
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
using namespace std;
#define gc fgetc
void get_int(FILE* in, int& x) {
register int c = gc(in);
x = 0;
while (c < '0' || c > '9') c = gc(in);
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = gc(in);
}
}
template <typename T1, typename T2>
struct greater_second {
bool operator ()(pair<T1, T2> const& a, pair<T1, T2> const& b) const {
return a.second > b.second;
}
};
int main() {
// IN/OUT initialization
FILE* in = fopen(IN_FILE, "r");
FILE* out = fopen(OUT_FILE, "w");
int N, S, i;
get_int(in, N);
map<int, int> m;
for (i = 0; i < N; i++) {
get_int(in, S);
m[S]++;
}
vector< pair<int, int> > vec(m.begin(), m.end());
partial_sort(vec.begin(), vec.end(), vec.begin() + 3, greater_second<int, int>());
fprintf(out, "%d %d %d", vec[0].first, vec[1].first, vec[2].first);
fclose(in);
fclose(out);
return 0;
}