Ιστοσελίδες μονάδων

Αναφορά προβλημάτων

Διαδικτυακά εργαλεία τεχνικού ελέγχου

Θέμα Α' Φάσης: Μεγιστοποίηση Κέρδους

Οι τιμές κάποιων αγαθών ή τίτλων (π.χ. πετρελαίου, χρυσού, μετοχών αλλά και βασικών τροφίμων όπως των αλεύρων, της ζάχαρης κ.λπ.) διαμορφώνονται καθημερινά βάσει της προσφοράς και της ζήτησης, αλλά και με βάση την εκτίμηση για τη μελλοντική τους πορεία. Αποτέλεσμα αυτών των συναλλαγών είναι οι τιμές αυτές να αλλάζουν από μέρα σε μέρα. Κάποιοι εκμεταλλεύονται αυτήν την αυξομείωση των τιμών, αγοράζοντας μία ποσότητα (ή δικαίωμα σε ποσότητα) φθηνά, και έπειτα πουλούν την ίδια ποσότητα ή δικαίωμα ακριβότερα. Το κέρδος εκφράζεται από το λόγο της τιμής πώλησης προς την τιμή αγοράς. Έστω ότι γνωρίζουμε την τιμή που έχει κάποιο αγαθό κάθε μέρα για ένα μεγάλο χρονικό διάστημα. Θέλουμε να υπολογίσουμε το μέγιστο κέρδος που θα μπορούσε κάποιος να αποκομίσει με μία αγορά και στη συνέχεια μία πώληση.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα profit.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό N, το πλήθος των ημερών για τις οποίες είναι γνωστή η τιμή του αγαθού (1 ≤ N ≤ 1.000.000). Η δεύτερη γραμμή περιέχει N ακέραιους αριθμούς Χ_i (για 1 ≤ i ≤ N), χωρισμένους μεταξύ τους με κενά διαστήματα, την τιμή του αγαθού κάθε μέρα (1 ≤ Χ_i ≤ 1.000).

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

Τα αρχεία εξόδου με όνομα profit.out είναι αρχεία κειμένου με την εξής δομή: Έχουν μία γραμμή με έναν πραγματικό αριθμό P, το μέγιστο δυνατό κέρδος από μία αγορά και στη συνέχεια μία πώληση, δηλαδή τη μέγιστη τιμή του λόγου X_i / X_j όταν j ≤ i. Ο αριθμός P πρέπει να στρογγυλοποιείται με ακρίβεια τριών δεκαδικών ψηφίων.

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

Επεξήγηση παραδείγματος 1: Το μέγιστο κέρδος προκύπτει αν κάποιος αγοράσει την τρίτη μέρα (Χ₃ = 3) και πουλήσει την πέμπτη (Χ₅ = 11). Το κέρδος είναι Χ₅ / Χ₃ = 11 / 3 = 3.6666666…

Επεξήγηση παραδείγματος 2: Το μέγιστο κέρδος προκύπτει αν κάποιος αγοράσει την τέταρτη μέρα (Χ₄ = 5) και πουλήσει την όγδοη (Χ₈ = 10). Το κέρδος είναι Χ₈ / Χ₄ = 10 / 5 = 2.

Επεξήγηση παραδείγματος 3: Η τιμή του προϊόντος μειώνεται σταθερά, κατά συνέπεια δεν είναι δυνατό να προκύψει αληθινό κέρδος. Η μέγιστη τιμή του λόγου είναι 1, αν κάποιος αγοράσει και πουλήσει την ίδια μέρα.

Μέγιστος χρόνος: 1 sec

Ενδεικτική λύση σε C++

/* Ευστάθιος Μποζίκας */

#include <iostream>
#include <stdio.h>

int main(int argc, char** argv){
  int n,x,min,a=0;
  double tp=1.000,p;
  FILE *read = fopen("profit.in","r");
  fscanf(read,"%d",&n);
  fscanf(read,"%d",&x);
  min = x;
  while(a<=(n-1)){
    fscanf(read," %d",&x);
    if(x>min){p=(double)x/min;if(p>tp){tp=p;}}
    else{min=x;}
    if (tp==1000.000){break;}
    a++;
  }
  fclose(read);
  FILE *write = fopen("profit.out","w");
  fprintf(write,"%.3f\n",tp);
  fclose(write);
  return 0;
}     

Ενδεικτική λύση σε C

/* Νίκος Τζάμος */

#include<stdio.h>
#define BSIZE 1<<15

FILE *fin;
char buffer[BSIZE];
int bpos=0, bsize=0;

int readInt() {
  int d = 0,x = 0;
  char c;
  while(1) {
    if(bpos >= bsize) {
      bpos = 0;
      if(feof(fin)) return x;
      bsize = fread(buffer, 1, BSIZE, fin);
    }
    c = buffer[bpos++];
    if(c>='0' && c<='9') {
      x = x*10 + (c-'0');
      d = 1;
    } else if(d==1) return x;
  }
  return -1;
}

main(){
  double N,M = 0,a,m=1e6;
  fin = fopen("profit.in","r");
  freopen("profit.out","w",stdout);
  N = readInt();
  while(N--)a=readInt(),m=(m<a)?m:a,M=(M>a/m)?M:a/m;
  printf("%.3lf\n", M);
} 

Ενδεικτική λύση σε Pascal

(* Αλέξανδρος Μπιμπίκος *)

program pdp2011;
var
  N,xi,i,min,x1:integer;
  profit,cur_profit:real;
  input_file,output_file:Text;
begin
  assign(input_file,'profit.in');
  reset(input_file);
  readln (input_file,N);
  profit:=1;
  read(input_file,x1);
  min:=x1;
  for i:=2 to N do
    begin
      read(input_file,xi);
      if(xi<min) then
        begin
          min:=xi;
        end
      else
        begin
          cur_profit:=xi/min;
          if (cur_profit>profit) then
            profit:=cur_profit;
        end;
    end;
  assign(output_file,'profit.out');
  rewrite(output_file);
  writeln (output_file,profit:8:3);
  close(input_file);
  close(output_file);
end. 

Θέμα Β' Φάσης: Εταιρική Ιεραρχία (Μαθητές Λυκείων)

Πρόσφατη έρευνα ενός περιοδικού, υποστηρίζει ότι η απόδοση των εργαζόμενων σε μία επιχείρηση, βελτιώνεται όταν αισθάνονται ότι δεν υπάρχουν διακρίσεις αναφορικά με το φύλο μέσα σε αυτήν. Η έρευνα μάλιστα επισημαίνει, ότι αυτή η «αίσθηση» δεν καθορίζεται από το πλήθος των γυναικών και των ανδρών, αλλά από την διαφορά στο πλήθος των σχέσεων (προϊστάμενος - υφιστάμενος) όπου ο προϊστάμενος είναι γυναίκα και ο υφιστάμενος άνδρας, και στο αντίστοιχο πλήθος, όπου ο προϊστάμενος είναι άνδρας και ο υφιστάμενος γυναίκα. Πιο συγκεκριμένα, κάθε εργαζόμενος στην επιχείρηση, εκτός του διευθυντή, έχει έναν άμεσο προϊστάμενο, ο οποίος τον επιβλέπει. Για κάθε ακολουθία εργαζομένων, όπου ο κάθε εργαζόμενος είναι άμεσος προϊστάμενος του επόμενού του, ο εργαζόμενος που βρίσκεται στην αρχή της ακολουθίας είναι προϊστάμενος κάθε άλλου εργαζόμενου στην ακολουθία. Έτσι αν η ιεραρχία της επιχείρησης αποτυπωθεί σε ένα δέντρο με ρίζα το διευθυντή, ένας εργαζόμενος x είναι προϊστάμενος κάθε άλλου εργαζόμενου στο υποδέντρο με ρίζα τον εργαζόμενο x. Η έρευνα θεωρεί τα ζευγάρια εργαζόμενων διαφορετικού φύλου όπου ο πρώτος είναι προϊστάμενος του δεύτερου, όχι μόνο άμεση σχέση αλλά σε ολόκληρη την ιεραρχία. Ειδικότερα θεωρείται το πλήθος r_f των ζευγαριών, όπου ο προϊστάμενος (σε όλη την ιεραρχία) είναι γυναίκα και το πλήθος r_m των ζευγαριών, όπου ο προϊστάμενος (σε όλη την ιεραρχία) είναι άνδρας. Η έρευνα υποστηρίζει ότι οι εργαζόμενοι λειτουργούν αποδοτικότερα όταν η διαφορά r_m - r_f προσεγγίζει το 0.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο, αφού διαβάσει το συνολικό αριθμό των εργαζομένων μιας επιχείρησης και για κάθε εργαζόμενο τον αριθμό (θέση στο αρχείο) του προϊσταμένου του και το φύλο του, θα υπολογίζει τη διαφορά ζευγαριών, διαφορετικού φύλου, που ο προϊστάμενος είναι γυναίκα από τα ζευγάρια που ο προϊστάμενος είναι άνδρας.

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

Τα αρχεία εισόδου με όνομα company.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό N, 1 ≤ N ≤ 5000 το πλήθος των εργαζομένων της επιχείρησης. (Οι εργαζόμενοι λοιπόν αριθμούνται από 1 μέχρι N). Στην i-οστή από τις επόμενες N γραμμές δίνεται o αριθμός του άμεσου προϊσταμένου του i-οστού εργαζομένου. Για το διευθυντή, ο αριθμός άμεσου προϊσταμένου είναι 0. Στην ίδια γραμμή (i-οστή) ακολουθεί ένα κενό και το φύλο του i-οστού εργαζομένου (m για άντρα, f για γυναίκα). Να θεωρήσετε ότι κανένας εργαζόμενος δεν είναι προϊστάμενος του εαυτού του και ότι ο διευθυντής είναι προϊστάμενος κάθε άλλου εργαζομένου (δηλαδή στην ιεραρχία της επιχείρησης αντιστοιχεί σε ένα δέντρο με ρίζα τον διευθυντή).

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

Τα αρχεία εξόδου με όνομα company.out είναι αρχεία κειμένου με την εξής δομή: Στη μοναδική τους γραμμή έχουν έναν μόνο ακέραιο αριθμό D, -5000 < D < 5000 Ο αριθμός αυτός αντιστοιχεί στη διαφορά r_m - r_f .

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

Γραφική Επεξήγηση Παραδείγματος 1.

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

1. Μέγιστος χρόνος εκτέλεσης: 1 sec.
2. Μέγιστη διαθέσιμη μνήμη: 64 MB.
3. Όλες οι γραμμές τελειώνουν με new_line.

Ενδεικτική λύση σε C

/* Φοίβος Αντουλινάκης */

#include <stdio.h>
int *p1,*f1,*m;
char *c1;

void go(int i)
{
  if(p1[i])
  {
    if(f1[p1[i]-1]==-1)go(p1[i]-1);
    f1[i]=f1[p1[i]-1]+1;
    m[i]=m[p1[i]-1];
    if(c1[p1[i]-1]=='m')
    {
      m[i]++;
      f1[i]--;
    }
  }
  else
  {
    f1[i]=0;
    m[i]=0;
  }
}

int main()
{
  int N,i,r=0;
  FILE *f;
  f=fopen("company.in","r");
  fscanf(f,"%d",&N);
  int ma[N],fa[N],p[N];
  f1=fa;
  m=ma;
  p1=p;
  char c[N],t[3];
  c1=c;
  for(i=0;i<N;i++)
  {
    ma[i]=-1;
    fa[i]=-1;
    fscanf(f,"%d",p+i);
    fscanf(f,"%s",t);
    c[i]=t[0]; 
  }
  fclose(f);
  for(i=0;i<N;i++)
  {
    if(fa[i]==-1) go(i);
    if(c[i]=='m')
    {
      r-=fa[i];
    }
    else
    {
      r+=ma[i];
    }
  }
  f=fopen("company.out","w");
  fprintf(f,"%d\n",r); 
  return 0;
}

Ενδεικτική λύση σε C++

/* Κυριάκος Αξιώτης */ 

#include <cstdio>
#include <vector>
typedef long long ll;
using namespace std;int N,bpos,x;
vector<vector<int> > con(400001);
bool male[400001];
char buf[3610001],c;
ll tot[2];
FILE *fin,*fout;
struct st
{
  int x,y;
}tmp;

int readint ()
{
  x=0;
  while (1)
  {
    c=buf[bpos++];
    if (c>32) x=x*10+c-48;
    else return x;
  }
}

st dfs (int i)
{
  st t=(st){0,0};
  for (vector<int>::iterator J=con[i].begin();J!=con[i].end();++J)
    tmp=dfs(*J),t.x+=tmp.x,t.y+=tmp.y;
  if (male[i]) tot[1]+=t.y,++t.x;
  else tot[0]+=t.x,++t.y;
  return t;
}

int main ()
{
  fin=fopen("company.in","r");
  fout=fopen("company.out","w");
  fread(buf,1,3610000,fin);
  N=readint();
  int tmp,start,i;
  for (i=1;i<=N;++i)
  {
    tmp=readint();
    con[tmp].push_back(i);
    if (!tmp) start=i;
    male[i]=(buf[bpos]=='m'),bpos+=2;
  }
  dfs(start);
  ll res=tot[1]-tot[0];
  fprintf(fout,"%lld\n",res);
  return 0;
}

Ενδεικτική λύση σε Pascal

(* Δημήτρης Μπεχράκης *)

program company;
var
  p,N,x,i,r_m,r_f:LongInt;
  input_file,output_file:Text;
  S:string[2];
  R:array[1..400000] of LongInt;
  G:array[0..400000] of boolean;
  M:array[0..400000] of LongInt;
  F:array[0..400000] of LongInt;

procedure Calc(p: LongInt);
var
  Next: LongInt;
begin
  Next:=R[p];
  if Next<>0 then
    begin
      if M[Next]+F[Next]=0 then Calc(Next);
      if G[Next]=true then
        begin
          M[p]:=M[Next]+1;
          F[p]:=F[Next];
        end
      else
        begin
          M[p]:=M[Next];
          F[p]:=F[Next]+1;
        end;
    end
  else
    begin
      M[p]:=0;
      F[p]:=0;
    end;
end;

begin
  assign(input_file,'company.in');
  reset(input_file);
  readln (input_file,N);
  for i:=1 to N do
    begin
      read(input_file,R[i]);
      read(input_file,S);
      if S[2]='m' then G[i]:=true else G[i]:=false;
    end;
  r_m:=0;
  r_f:=0;
  for i:=1 to N do
    begin
      Calc(i);
      if G[i]=true then r_f:=r_f+F[i] else r_m:=r_m+M[i];
    end;
  assign(output_file,'company.out');
  rewrite(output_file);
  writeln (output_file,r_m-r_f);
  close(input_file);
  close(output_file);
end.

Θέμα Β' Φάσης: Χιονοδρομίες στα «Τρία – Πέντε Πηγάδια» (Μαθητές Γυμνασίου)

Η Ελλάδα εκτός από ξακουστός καλοκαιρινός προορισμός, αποτελεί και τόπο χειμερινού τουρισμού. Χιονισμένα βουνά, άγρια ποτάμια και μια συνεχής αλλαγή περιβάλλοντος μπορούν να ικανοποιήσουν κάθε σχετική προσδοκία. Ξεχωριστή φυσικά θέση στο χειμερινό τοπίο, έχουν τα 16 χιονοδρομικά κέντρα της χώρας μας. Μερικά από αυτά, όπως το χιονοδρομικό κέντρο στα «3 - 5 Πηγάδια» (Βέρμιο Ημαθίας) προσφέρει ψυχαγωγία όλο το χρόνο. Το κέντρο, διαθέτει τεχνική χιονόπτωση και την πίστα της μεγάλης κατάβασης από τα 2005 m στα 1430 m. Σε αυτήν τη μεγάλη πίστα μέσα στα έλατα, γίνεται ο τελικός ταχύτητας με ατομική χρονομέτρηση. Ο κάθε χιονοδρόμος κατεβαίνει τη διαδρομή και με βάση το χρόνο του, οι φωτεινοί πίνακες δίνουν τη θέση του στη γενική κατάταξη. Ο πρώτος για παράδειγμα θα έχει αναγκαστικά θέση 1. Ο δεύτερος 1 ή 2 και ο Νιοστός οποιαδήποτε θέση από 1 έως Ν.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο αφού διαβάσει τη θέση που παίρνει ο κάθε χιονοδρόμος στη γενική κατάταξη μέχρι εκείνη τη στιγμή, θα υπολογίζει την τελική θέση κάθε χιονοδρόμου μετά το τέλος του αγώνα.

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

Τα αρχεία εισόδου με όνομα snow_run.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό N. Τον αριθμό των χιονοδρόμων που λαμβάνουν μέρος στον αγώνα 10 ≤ N ≤ 40000. Οι επόμενες N γραμμές περιέχουν από έναν ακέραιο αριθμό. Τη θέση στη γενική κατάταξη που έχει μέχρι εκείνη τη στιγμή ο αντίστοιχος χιονοδρόμος.

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

Τα αρχεία εξόδου με όνομα snow_run.out είναι αρχεία κειμένου με την εξής δομή: Έχουν Ν γραμμές όσοι και οι χιονοδρόμοι. Σε κάθε γραμμή υπάρχει ακριβώς ένας αριθμός η θέση που έχει ο αντίστοιχος χιονοδρόμος στην τελική κατάταξη.

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

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

1. Δεν υπάρχουν σκιέρ με τον ίδιο χρόνο.
2. Όλες οι γραμμές τελειώνουν με new_line.
3. Μέγιστος χρόνος εκτέλεσης: 5 sec.
4. Μέγιστη διαθέσιμη μνήμη: 64 MB.
5. Η επιτροπή εκτός των 10 βασικών αρχείων με μέγεθος ≤ 10000 μπορεί να χρησιμοποιήσει (για επιπλέον μοριοδότηση) σε περίπτωση ισοβαθμίας δύο επιπλέον αρχεία με μέγεθος ≤ 100000.

Ενδεικτική λύση σε C

/* Θεοδώρα Παναγέα */

#include<stdio.h>

int main(){
  int arx[40002],tel[40002];
  int i,j=1,l,n,k=1;
  FILE *fpin;
  FILE *fpout;
  fpin = fopen("snow_run.in","r");
  fpout = fopen("snow_run.out","w");
     
  for(i<=0;i<=40000;i++){
    arx[i]=0;
    tel[i]=0; 
  }
     
  fscanf(fpin,"%d",&n);
     
  for(i=1;i<=n;i++){ 
    fscanf(fpin,"%d",&l);
    arx[i]=l;
     
    for (j=1;j<i;j++){
      if (l<=tel[j])
        tel[j]++;
    } 
    tel[i]=l;
  }
     
  for(i=1;i<=n;i++)
    fprintf(fpout,"%d\n",tel[i]);
  return 0; 
}

Ενδεικτική λύση σε C++

/* Κωνσταντίνος Ξανθόπουλος */

#include <iostream>
#include <fstream>
using namespace std;
#define nmax 100000

int main () { 
  ifstream fin;
  ofstream fout;
  long int ord[nmax];
  long int n, i, a1,a2;
  fin.open( "snow_run.in",ios::in); 
  fin >> n;
  fin>>ord[0];
  for (a1=1;a1<n;a1++){
    fin>>ord[a1];
    if (ord[a1]< a1+1){
      for (a2=0;a2<a1;a2++){
        if (ord[a2]>=ord[a1]) {
          ord[a2]=ord[a2]+1;
        }
      }
    }
  }
  fout.open("snow_run.out",ios::out); 
  for (i=0;i<n;i++) {
    fout<< ord[i] <<endl;
  } 
  fin.close();
  fout.close();
  
  return 0;
}

Ενδεικτική λύση σε Pascal

(* Αλέξανδρος Μπιμπίκος *)

program pdp23b;
var
  N,i,j,cur_pos:longint;
  a,b:array [1..100000] of longint;
  input_file,output_file:text;
begin
  assign (input_file,'snow_run.in');
  reset (input_file); 
  readln (input_file,N);
  for i:=1 to N do
    begin
      readln (input_file,cur_pos);
      for j:=i-1 downto cur_pos do
        begin
          a[j+1]:=a[j];
        end;
      a[cur_pos]:=i;
    end; 
  close(input_file); 
  for i:=1 to N do
    begin
      b[a[i]]:=i;
    end; 
  assign(output_file,'snow_run.out');
  rewrite (output_file);
  for i:=1 to N do
    begin
      writeln(output_file,b[i]);
    end; 
  close(output_file);
end.

Θέμα 1o Τελικής Φάσης: prevdiv

Δίνεται μία ακολουθία αποτελούμενη από Ν θετικούς ακέραιους αριθμούς. Ζητείται να βρεθεί ο μέγιστος αριθμός της ακολουθίας, ο οποίος διαιρείται ακριβώς από όλους τους αριθμούς που προηγούνται αυτού στην ακολουθία. Προφανώς ο αριθμός που εμφανίζεται πρώτος στην ακολουθία διαιρείται ακριβώς από όλους τους προηγούμενούς του (γιατί δεν έχει κανέναν προηγούμενο). Άρα, αν η ακολουθία δεν είναι κενή, υπάρχει πάντα λύση στο πρόβλημα.

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

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος των στοιχείων της ακολουθίας Ν. Η δεύτερη γραμμή θα περιέχει τους Ν ακέραιους αριθμούς της ακολουθίας, χωρισμένους μεταξύ τους με κενά διαστήματα.

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

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: το μεγαλύτερο αριθμό της ακολουθίας που διαιρείται ακριβώς από όλους τους προηγούμενούς του στην ακολουθία.

Περιορισμοί

• 1 ≤ Ν ≤ 3.000.000
• Όριο χρόνου εκτέλεσης: 1 sec.
• Το ελάχιστο κοινό πολλαπλάσιο όλων των αριθμών δε θα υπερβαίνει το 2.000.000.000.

Παράδειγμα Αρχείων Εισόδου - Εξόδου

Θέμα 2o Τελικής Φάσης: fishboats

Σε μία παραλία με σχήμα ευθείας γραμμής υπάρχει μία ψαροταβέρνα, στη συντεταγμένη μηδέν. Δεξιά και αριστερά από την ψαροταβέρνα (σε θετικές και αρνητικές συντεταγμένες) φτάνουν το πρωί κάθε μέρας Ν τράτες (ψαρόβαρκες), που κάθε μία έχει φέρει για να πουλήσει Μ κιλά ψάρια. Ο ταβερνιάρης, που ξέρει ότι το βράδυ θα έχει πολλή πελατεία, θέλει να αγοράσει όσο γίνεται περισσότερα κιλά ψάρια. Ξεκινάει λοιπόν από την ταβέρνα ακριβώς τη στιγμή που προσδένουν στην παραλία (όλες συγχρόνως) οι τράτες και διανύει απόσταση μίας μονάδας στη μονάδα του χρόνου. Κάθε φορά που φτάνει σε μία τράτα, ο ταβερνιάρης αγοράζει όσα κιλά ψάρια αυτή διαθέτει και αμέσως ξεκινά για την επόμενη τράτα (χωρίς να μεσολαβήσει χρόνος). Όμως, σε κάθε μονάδα του χρόνου μέχρι να φτάσει ο ταβερνιάρης, κάθε τράτα πουλάει ένα κιλό ψάρια σε τουρίστες που κάνουν βόλτα στην παραλία. Ζητείται να βρεθεί ο μέγιστος αριθμός κιλών ψαριών που μπορεί να αγοράσει ο ταβερνιάρης.

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

Η πρώτη γραμμή της εισόδου θα περιέχει ακριβώς δύο θετικούς ακέραιους αριθμούς χωρισμένους με ένα κενό διάστημα: τις τιμές των Ν και Μ. Η δεύτερη γραμμή θα περιέχει Ν μη μηδενικούς ακέραιους αριθμούς Χ₁, ... Χ_N χωρισμένους μεταξύ τους με κενά διαστήματα: τις συντεταγμένες των σημείων της παραλίας όπου φτάνουν οι τράτες.

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

Η έξοδος πρέπει να αποτελείταιαπό μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: το μέγιστο αριθμό κιλών ψαριών που μπορεί να αγοράσει ο ταβερνιάρης.

Περιορισμοί

• 1 ≤ Ν ≤ 300
• 1 ≤ Μ ≤ 1.000.000
• -10.000 ≤ Χ_i ≤ 10.000
• Όριο χρόνου εκτέλεσης: 1 sec.

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

Θέμα 3o Τελικής Φάσης: anneal

Το γυαλί παράγεται λιωμένο σε φούρνους τήξης, όπου επικρατούν πολύ υψηλές θερμοκρασίες, και ψύχεται σταδιακά, ομοιόμορφα, και με ελεγχόμενο τρόπο, ώστε να αποφευχθούν σπασίματα ή ρωγμές, και να διατηρηθεί υψηλή η ποιότητα του παραγόμενου προϊόντος. Μια εταιρεία παραγωγής γυαλιού διαθέτει μια σειρά από Ν θαλάμους ψύξης και ψύχει το προϊόν περνώντας τον διαδοχικά από όλους αυτούς. Οι θάλαμοι βρίσκονται σε μια ευθεία γραμμή και αριθμούνται κατά μήκος αυτής, ξεκινώντας από τον πλησιέστερο στο φούρνο τήξης. Πριν ξεκινήσει η διαδικασία παραγωγής, είναι γνωστή η θερμοκρασία a_i που επικρατεί σε κάθε θάλαμο ψύξης i. Για να προχωρήσει η διαδικασία ψύξης χωρίς προβλήματα, φροντίζουμε ώστε καθώς το γυαλί περνά από τον ένα θάλαμο στον επόμενο, να μην έχουμε αύξηση της θερμοκρασίας. Αυτό επιτυγχάνεται είτε μειώνοντας τη θερμοκρασία ενός θαλάμου i από a_i σε b_i, το οποίο απαιτεί ενέργεια ίση με τη διαφορά θερμοκρασίας a_i - b_i, είτε παρακάμπτοντας τον θάλαμο i, το οποίο απαιτεί ενέργεια ίση με το διπλάσιο της θερμοκρασίας a_i. Η υπάρχουσα υποδομή της εταιρείας δεν επιτρέπει ούτε την αύξηση της θερμοκρασίας ενός θαλάμου, ούτε οποιαδήποτε αντιμετάθεσή των θαλάμων στη σειρά με την οποία διέρχεται το γυαλί από αυτούς (δεν μπορεί δηλαδή το γυαλί να περάσει πρώτα από κάποιον θάλαμο j > i και εν συνεχεία να περάσει από τον θάλαμο i).

Ζητείται το ελάχιστο απαιτούμενο ποσό ενέργειας για να έχουμε μια σειρά θαλάμων κατά μήκος της οποίας η θερμοκρασία δεν αυξάνεται.

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

Η πρώτη γραμμή της εισόδου θα περιέχει ακριβώς έναν ακέραιο αριθμό: το πλήθος των θαλάμων Ν. Η δεύτερη γραμμή θα περιέχει Ν θετικούς ακέραιους αριθμούς α₁, ... α_N χωρισμένους μεταξύ τους με κενά διαστήματα: τις αρχικές θερμοκρασίες των θαλάμων.

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

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

Περιορισμοί

• 2 ≤ Ν ≤ 50.000
• 1 ≤ a_i ≤ 10.000.000
• Όριο χρόνου εκτέλεσης: 1 sec.

Παράδειγμα Αρχείων Εισόδου Εξόδου

Επεξήγηση Παραδείγματος

Παρακάμπτουμε τον 2ο και τον 5ο θάλαμο, και μειώνουμε τη θερμοκρασία του 3ου θαλάμου σε 55, και των θαλάμων 7 και 8 σε 40. Η ακολουθία θερμοκρασιών που προκύπτει είναι [55, x, 55, 50, x, 40, 40, 40], όπου το “x” δηλώνει τους θαλάμους που έχουν παρακαμφθεί. Το ενεργειακό κόστος είναι: (80–55) + (70–40) + (60–40) = 75 για την μείωση της θερμοκρασίας στους θαλάμους 3, 7 και 8 αντίστοιχα, και 2 X 10 + 2 X 20 = 60 για τους θαλάμους 2 και 5, αντίστοιχα, που παρακάμψαμε.