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

[infinity]

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

Καλά αποτελέσματα σε όλους

[root-expert]

Τι έγινε ρε παιδιά καμία λύση φέτος?

[Sinnosuke]

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

[giorgosgiapis]

Η λύση μου:

Φτιάχνω ένα 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;
}

[gtsiam]

Ουσιαστικά φτιάχνω ένα 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;
}