Λύσεις για την Γ φάση

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Λύσεις για την Γ φάση

Δημοσίευση από pman »

Έλυσα το 3ο θέμα , αυτό ήθελα να γράψω αλλά δεν πρόλαβα

Κώδικας: Επιλογή όλων

/*
Made by Sotirios Nikoloutsopoulos
LANG C++
*/

#include<iostream>

int main()
{
 FILE* fin;
 FILE* fout;
 fin = fopen("cpu.in" , "r");
 fout = fopen("cpu.out" , "w");
 int eks; int add; int x[50000]; int y[50000]; int i; int j; int syn = 0 ; int x2; int y2; int t;
 fscanf(fin , "%d %d" , &eks , &add);
 int c[50000]; int d[50000];
 
 for(i = 1; i <= add ; i++)
 {
       fscanf(fin , "%d %d" , &x[i] , &y[i]);
 }    
 for(i = 1; i <= add; i++)
 {
   c[i] = 0; d[i] = 0;      
 }   
 for(i = 1; i <= add; i++)
 { 
    for(j =  1; j <= add; j++)
    {
          x2 = x[i]; y2 = y[j];
          
             if( x2 > y2 && c[i] != 1 && d[j] != 1)
          {
              t = x2 - y2;
             if(t == 1)
             {
               c[i] = 1;
               d[j] = 1;
               syn++;     
             }   
          } 
          
          if( y2 > x2 && c[i] != 1 && d[j] != 1)
          {
              t = y2 - x2;
             if(t == 1)
             {
               c[i] = 1;
               d[j] = 1;
               syn++;     
             }   
          }       
    }     
 }
 
 fprintf(fout , "%d" , syn);
 fclose(fin);
 fclose(fout);
 return 0;   
}
Τελευταία επεξεργασία από το μέλος Artakserksis την Σάβ Απρ 18, 2009 1:05 am, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: code tags
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από userresu »

πιάνει όλα τα τεστ?

άκυρο, αφού δεν μας τα έχουν δώσει ακόμα.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από compileGuy »

Μπορεί κάποιος να μου εξηγήσει καλύτερα το 3ο πρόβλημα γιατί δεν κατάλαβα τίποτα?? :roll:
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από pman »

φτιάξτε δικά σας τεστ.
εγώ έφτιαξα και δουλεύουν μια χαρά.
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

Re: Λύσεις για την Γ φάση

Δημοσίευση από Ελεύθεροσκοπευτής »

1) θα στείλουν αναλυτικά τις βαθμολογίες μας στα τεστκέησης, όπως κάθε φορά;;;
2) υπάρχει τρόπος να κατεβάσω τα τρία προγράμματα που έδωσα στο τάλος, γιατί ΒαΡιΈμΑι ελλεινά να τα ξαναγράφω;;;

εντιτ: τα γκρηκλις μου μεσα...
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από darksaga »

compileGuy
σιγουρα εχεις δει πλακετες απο καποιο ηλεκτρονικο εξαρτημα, εκεινα τα πρασσινα που εχουν μεσα διαφορα μοντιβα απο συρματακια
αυτα τα συρματακια οπως θα καταλαβες συνδεουν με διαφορους τροπους μεταξυ τους τις συσκευες που ειναι συνδεδεμενες με την παλκετα. Ειναι λοιπον εμφανες οτι δεν πρεπει το ενα συρματακια να ακουμπαει στο αλλο γιατι τοτε θα εχουμε το λεγομενο βραχυκυκλωμα οπως μαθαμε στην ταδε ταξη του γυμνασιου.
οι φοιτητες του προβληματος λοιπον εχουν κανει το εξης, εχουν σε μια πλακετα εναν αριθμο απο εξαρτηματα που ειναι συνδεδεμενα κυκλικα μεταξυ τους, θελουν ομως να κανουν καποιες επιπλεον συνδεσεις μεταξυ των συσκευων αυτων. Αυτες οι συνδεσεις γινονται με συρματακια τα οποια οπως ειδαμε δεν πρεπει να ακουμπανε το ενα το αλλο. Οπως ειναι εμφανες και απο το σχημα που δινει τ προβλημα δεν ειναι παντα εφικτο αν γινουν ολες οι συνδεσεις χωρις να βραχυκυκλωνονται. Το προβλημα σου ζηταει να βρεις το μεγιστο αριθμο δυνατων συνδεσεων που μπορουν να κανουν οι φοιτητες...

Δεν ξερω αν βοηθησα αλλα νομιζω οτι το προβλημα ειναι αρκετα παλο στην κατανοηση, το προβλημα ειναι κυριως οτι δεν εχουμε(εγω τουλ) λυσει πολλα παρομοια καοι μπορει να μας παρει απο κατω...καθαρα ψυχολογικο κατα τι γνωμη μου θεμα δεδομενου οτι υπαρχουν τουλαχιστον 2-3 διαφορετικες λυσεις.

Καποια στιγμη θα ξαναγραψω τη λυση μου και θα την ποσταρω γιτι πηγε στα θυμαρακια με το φορματ(με το που ξυπναω σημερα το πρωι παω να ανοιξω το πισι να δω αποτελεσματα γιατι χτες εφτασα 3 η ωρα σπιτι και μου μενει στα χερια ο xserver. βαριομουνα να δω τι φτεει οποτε τραβαω ενα format που ειναι η γρηγορη και ευκολη λυση οταν εχει backup το home σου...προσεχως και σε ξεχωριστο παρτισιον :P)
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από compileGuy »

darksaga έγραψε:compileGuy
σιγουρα εχεις δει πλακετες απο καποιο ηλεκτρονικο εξαρτημα, εκεινα τα πρασσινα που εχουν μεσα διαφορα μοντιβα απο συρματακια
αυτα τα συρματακια οπως θα καταλαβες συνδεουν με διαφορους τροπους μεταξυ τους τις συσκευες που ειναι συνδεδεμενες με την παλκετα. Ειναι λοιπον εμφανες οτι δεν πρεπει το ενα συρματακια να ακουμπαει στο αλλο γιατι τοτε θα εχουμε το λεγομενο βραχυκυκλωμα οπως μαθαμε στην ταδε ταξη του γυμνασιου.
οι φοιτητες του προβληματος λοιπον εχουν κανει το εξης, εχουν σε μια πλακετα εναν αριθμο απο εξαρτηματα που ειναι συνδεδεμενα κυκλικα μεταξυ τους, θελουν ομως να κανουν καποιες επιπλεον συνδεσεις μεταξυ των συσκευων αυτων. Αυτες οι συνδεσεις γινονται με συρματακια τα οποια οπως ειδαμε δεν πρεπει να ακουμπανε το ενα το αλλο. Οπως ειναι εμφανες και απο το σχημα που δινει τ προβλημα δεν ειναι παντα εφικτο αν γινουν ολες οι συνδεσεις χωρις να βραχυκυκλωνονται. Το προβλημα σου ζηταει να βρεις το μεγιστο αριθμο δυνατων συνδεσεων που μπορουν να κανουν οι φοιτητες...

Δεν ξερω αν βοηθησα αλλα νομιζω οτι το προβλημα ειναι αρκετα παλο στην κατανοηση, το προβλημα ειναι κυριως οτι δεν εχουμε(εγω τουλ) λυσει πολλα παρομοια καοι μπορει να μας παρει απο κατω...καθαρα ψυχολογικο κατα τι γνωμη μου θεμα δεδομενου οτι υπαρχουν τουλαχιστον 2-3 διαφορετικες λυσεις.

Καποια στιγμη θα ξαναγραψω τη λυση μου και θα την ποσταρω γιτι πηγε στα θυμαρακια με το φορματ(με το που ξυπναω σημερα το πρωι παω να ανοιξω το πισι να δω αποτελεσματα γιατι χτες εφτασα 3 η ωρα σπιτι και μου μενει στα χερια ο xserver. βαριομουνα να δω τι φτεει οποτε τραβαω ενα format που ειναι η γρηγορη και ευκολη λυση οταν εχει backup το home σου...προσεχως και σε ξεχωριστο παρτισιον :P)
Σε ευχαριστώ darksaga!! Το κατάλαβα τώρα 8-)
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από pman »

από ότι βλέπω η λύση μου δεν έχει κάτι σωστά , μάλλον δεν θα κατάλαβα καλά το θέμα θα το δω αργότερα
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από thetrojan01 »

Μια απλή προσπάθεια επίλυσης του Α θέματος (hydrologis)

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>

unsigned long long int paragontiko(unsigned long long int a);
unsigned long long int sigma(unsigned long long int a);

int main()
{
  unsigned int N, M, a, b;
  unsigned long long int V, Vr;
  FILE *fp;
  
  fp=fopen("hydrologis.in", "r");
  fscanf(fp, "%d\n\%d\n%lld\n%d\n%d", &N, &M, &Vr, &a, &b);
  fclose(fp);
  
  V = Vr + a * paragontiko(N)/1000000 - b * sigma(M);
  
  fp=fopen("hydrologis.out", "w");
  fprintf(fp, "%lld\n", V);
  fclose(fp); 
  
  return 0;
}

unsigned long long int paragontiko(unsigned long long int a)
{
  register unsigned long long int count;
  unsigned long long int solution=1;
  for(count=2; count <= a; ++count) solution = count * solution;
  return solution;
}

unsigned long long int sigma(unsigned long long int a)
{
  register unsigned long long int count;
  unsigned long long int solution=0;
  for(count=1; count <= a; ++count) solution =+ count;
  return solution;
}

ΜΠΟΡΕΙ ΚΑΠΟΙΟΣ ΝΑ ΜΟΥ ΠΕΙ ΠΟΥ ΕΙΝΑΙ ΤΟ ΛΑΘΟΣ?!?!?!
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
darksaga
Δημοσιεύσεις: 44
Εγγραφή: Δευ Μαρ 16, 2009 10:57 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από darksaga »

στην προτελεφτεα γραμμη παει solution+=count
θα μπορουσες το sigma να ειναι
inline unsigned long long int sigma(unsigned long long int a)
{ return( a*(a+1)/2 ); }

μαθηματικα 1ης γυμνασιου :P
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από compileGuy »

Το έτρεξα στο pc μου και στο 1ο test case αντι για 2257174 βγάζει 2306674 :?
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από thetrojan01 »

ooops!!!! :P τι τις θέλω τις συντομίες!

και σωστό το return (Gauss, ε;) αλλά είπα να το λύσω πρώτα απλά... :) αν και ομολογώ πως δε μου πέρασε από το μυαλό.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις για την Γ φάση

Δημοσίευση από thelastnicholas »

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

Y.Γ: Είναι σχετικά πρόχειρες υλοποιήσεις και απέχουν απο το να χαρακτηριστούν βελτιστές αλλα δουλεύουν.

Κώδικας: Επιλογή όλων

/*
Task : Hydrologis
*/
#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

inline double fac ( double n){
 double t=1;
 for(int i=1;i<=n;i++)
  t=t*i;
 return t;    
}

inline double sum (double n){
  return (n*(n+1))/2; 
}

double V (double a,double b, double  N,double M,double Vg){
       return Vg + a*fac(N)/1000000 - b*sum(M);
}
 
int main (){
    
    ifstream in  ("hydrologis.in");
    ofstream out ("hydrologis.out");
    double N,M,a,b,Vg;
    in>>N>>M>>Vg>>a>>b;
    
    out<<(unsigned long int)round(V(a,b,N,M,Vg))<<endl;
}

Κώδικας: Επιλογή όλων

/*
Task: Aegean
*/

#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>

using namespace std;

struct ship {
       int x,y;
       ship(int a,int b):x(a),y(b){}
       ship(){}
       };
typedef unsigned long int ulint;
typedef ship point;
bool operator < (const ship & a,const ship & b){
      return a.x<b.x;
}
vector <ship> ships;
map <ulint,ulint> ant1x,ant1y;
ulint N,M;
 
int main (){
    
    ifstream in  ("aegean.in");
    ofstream out ("aegean.out");
    
    in>>N;
    for(int i=0;i<N;i++){
     ulint x,y;
     in>>y>>x;
     ships.push_back(ship(x,y));
     }
    
    ulint M=0;
    
    for(int i=0;i<N;i++)
     if(ships[i].x> M )
      M=ships[i].x;
     else if( ships[i].y> M )
      M=ships[i].y;     


    for(int i=0;i<N;i++){
      ant1x[ ships[i].x] = max(ant1x[ ships[i].x], (ulint)(M- ships[i].y +1) );
      ant1y[ ships[i].y] = max(ant1y[ ships[i].y], (ulint)(M- ships[i].x +1) );      
     }        
     
   out<<M<<endl;
   out<<ant1y.size()<<" "<<ant1x.size()<<endl;

   map <ulint,ulint>::iterator ity= ant1y.begin();
   map <ulint,ulint>::iterator itx= ant1x.begin();
   vector <point> fx;
   vector <point> fy;
    for(;ity!=ant1y.end();ity++)
     fx.push_back(point((*ity).first,(*ity).second));
    for(;itx!=ant1x.end();itx++)
     fy.push_back(point((*itx).first,(*itx).second));
  
   sort(fx.begin(),fx.end());
   sort(fy.begin(),fy.end());

    for(int i=0;i<fx.size();i++)         
     out<<fx[i].x<<" "<<fx[i].y<<endl;
    for(int i=0;i<fy.size();i++)         
     out<<fy[i].x<<" "<<fy[i].y<<endl;
     
   out.close();
   in.close();
   return 0;
}

Κώδικας: Επιλογή όλων

/*
Task: Cpu
*/
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int N,M;
int K=0;
vector <pair<int,int> > connectionsOUT;
vector <pair<int,int> > connectionsIN;
inline bool isBetween (int left, int right, int n){
   
     if( left<=n && right>=n)
      return 1;
     return 0;
}     

inline bool crossovers (int left,int right,int l,int r){
     
     return !(( isBetween(left,right,l) && isBetween(left,right,r) ) || (!isBetween(left,right,l) && !isBetween(left,right,r))) ;
}

inline bool isOutOK (int l,int r){
     
     for(int i=0;i<connectionsOUT.size();i++)          
      if(crossovers(connectionsOUT[i].first,connectionsOUT[i].second,l,r))
       return 0;
      return 1;
}

inline bool isInOK (int l,int r){

     for(int i=0;i<connectionsIN.size();i++)          
      if(crossovers(connectionsIN[i].first,connectionsIN[i].second,l,r))
       return 0;
      return 1;
}
     
int main (){
    
  ifstream in ("cpu.in");
  ofstream out ("cpu.out");  

  in>>N>>M;
  int l,r;
  in>>l>>r;
  connectionsOUT.push_back( pair<int,int>(min(l,r),max(l,r))); 
  
  while(!in.eof() ){
   
  in>>l>>r;                  
  if( isOutOK(l,r) )
   connectionsOUT.push_back( pair<int,int>(min(l,r),max(l,r))); 
  else if (isInOK(l,r))
   connectionsIN.push_back( pair<int,int>(min(l,r),max(l,r))); 
  else 
   break;                  
                  
  }
  out<<connectionsOUT.size()+connectionsIN.size()<<endl;
    
}

Απάντηση