Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.

Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Δημοσίευσηαπό infinity » Πέμ Φεβ 02, 2017 7:57 pm

Εδώ μπορείτε να δημοσιεύετε και να συζητάτε τις λύσεις σας για την πρώτη φάση του 29ου ΠΔΠ.

Καλά αποτελέσματα σε όλους :D
infinity
 
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Δημοσίευσηαπό root-expert » Τετ Φεβ 15, 2017 7:36 pm

Τι έγινε ρε παιδιά καμία λύση φέτος? :P :geek:
root-expert
 
Δημοσιεύσεις: 1
Εγγραφή: Τετ Φεβ 15, 2017 5:06 pm

Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Δημοσίευσηαπό Sinnosuke » Πέμ Φεβ 16, 2017 5:11 pm

Η λύση μου ήταν η εξής (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):

Κώδικας: Επιλογή όλων
#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;
}
Άβαταρ μέλους
Sinnosuke
 
Δημοσιεύσεις: 8
Εγγραφή: Τετ Αύγ 24, 2016 12:23 am

Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Δημοσίευσηαπό giorgosgiapis » Παρ Φεβ 17, 2017 5:41 pm

Η λύση μου:

Φτιάχνω ένα 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;
}
Εικόνα
giorgosgiapis
 
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Δεκ 31, 2016 5:50 pm

Re: Λύσεις προβλήματος α' φάσης 29ου ΠΔΠ

Δημοσίευσηαπό gtsiam » Σάβ Φεβ 18, 2017 12:33 am

Ουσιαστικά φτιάχνω ένα 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;
}
gtsiam
 
Δημοσιεύσεις: 1
Εγγραφή: Σάβ Φεβ 18, 2017 12:24 am


Επιστροφή στο Γενικά για το Διαγωνισμό

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης

cron