Wednesday, July 17, 2013

Codingame octobre 2012

Premier post d’une longue série (ou pas) où je voudrais partager mes algos et mes codes utilisés pour la résolution des CodinGames. La page d’entrainement est ici.

Le premier exo, demande de convertir une phrase en ASCII art. La façon de représenter chaque lettre est donnée. Attention, on demande de transformer des phrases et non des mots (et par défaut cin saute les espaces). Pour ne pas avoir de problème entre minuscules et majuscules, j’ai tout converti en majuscule avec transform et toupper. Pour ce dernier attention à utiliser la fonction toute bête C et pas celle C++ qui prend en compte la locale. Voici mon code:
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  int L,H;
  string T;
  cin >> L >> H;
  cin.ignore();
  getline(cin,T);
  vector<string> m(H);
  
  for(int i=0;i<H;++i)
    getline(cin, m[i]);
  
  transform(begin(T), end(T), begin(T), ::toupper); 

  for(int i=0;i<H;++i){
    for(int j=0;j<int(T.size());++j)
      if(isalpha(T[j]))
    for(int k=0;k<L;++k)
      cout << m[i][L*int((T[j]-'A'))+k];
      else
    for(int k=0;k<L;++k)
      cout << m[i][L*int('Z'-'A'+1)+k];
    cout << '\n';
  }
}
L’exo suivant demande la perte maximale en bourse d’un cours donné. Une (mauvaise) façon de faire serait pour chaque date d’achat, regarder toutes les dates suivantes et vendre au cours le plus bas. Cette solution n’est pas assez efficace.
Il faut plutôt parcourir le cours avec une variable retenant le cours au moment de notre achat (initialisée au cours au temps zéro). Et à chaque instant, commencer par regarder la perte si on vend à ce moment. Et si le cours et plus haut que lorsqu’on a acheté affecter notre variable d’achat à ce cours. Autrement dit, on cherche à acheter au plus haut, quitte à revoir notre position si on trouve un cours plus haut, et on cherche la perte maximale. Voici mon code:
#include<iostream>
#include<vector>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> t(n);
  for(int i=0;i<n;++i)
    cin >> t[i];

  int res=0;
  int maxi=t[0];
  for(int i=1;i<n;++i){
    res=min(res, t[i]-maxi);
    maxi=max(maxi, t[i]);
  }


  cout << res;
}
Le dernier exo demande de câbler des maisons en utilisant le moins de câbles possible. La forme du câblage est fixée, il doit y avoir une ligne centrale horizontale et chaque maison sera connectée par une ligne verticale privée. Une fois trouvé l’emplacement de la ligne centrale, le calcul de la longueur de câble est très simple. On peut ensuite voir qu’une position optimale demande d’avoir autant de maisons en dessus qu’en dessous de la ligne centrale. Par exemple si j’ai 3 maisons au-dessus et 7 en-dessous, déplacer un peu (1 cm) ma ligne centrale va me faire économiser 7cm moins les 3 supplémentaire requis pour les maisons du haut. Il suffit alors de trier les maisons par ordonnée et de prendre celle du milieu qui sera celle par laquelle passera la ligne.
Remarquez que s’il y a un nombre pair de maisons, la ligne peut passer n’importe où entre les deux maisons centrales, ça reste le placement optimal. Voici mon code:
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> pi;

int main(){
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<pi> t(n);
  for(int i=0;i<n;++i)
    cin >> t[i].second >> t[i].first;
  sort(begin(t), end(t));
  int yres=t[n/2].first;

  long long res=0;
  int maxi=t[0].second, mini=t[0].second;
    for(int i=0;i<n;++i){
      maxi=max(maxi, t[i].second);
      mini=min(mini, t[i].second);
      res+=abs(t[i].first-yres);
    }

    res+=maxi-mini;
    cout << res;
}

No comments:

Post a Comment