From 9fe033ea88c2f705ec18c232873d056e0c229d72 Mon Sep 17 00:00:00 2001
From: Gaspard Coulet <gaspard.coulet@mines-ales.org>
Date: Wed, 28 Apr 2021 23:05:53 +0200
Subject: Initial commit

---
 sem_5/codingbattle/ex3/ex3.cpp | 98 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 98 insertions(+)
 create mode 100644 sem_5/codingbattle/ex3/ex3.cpp

(limited to 'sem_5/codingbattle/ex3/ex3.cpp')

diff --git a/sem_5/codingbattle/ex3/ex3.cpp b/sem_5/codingbattle/ex3/ex3.cpp
new file mode 100644
index 0000000..3d2d20b
--- /dev/null
+++ b/sem_5/codingbattle/ex3/ex3.cpp
@@ -0,0 +1,98 @@
+#include <iostream>
+#include <string>
+#include<vector>
+#include<algorithm>
+using namespace std;
+
+void printtab(int n, int tab[]);
+void printvec(int n, vector<int> tab);
+int main (int argc, char ** argv){
+  int L,N;
+  cin >> L>>N;
+  int  pos[N];
+  int size[N];
+  for (int i =0;i < N; i ++){
+    cin>>pos[i];
+  }
+  vector<int> ecart(N-1);//ecart entre le i eme poste et le i + 1 ieme
+  int nbchapsize[19];
+  for (int i =0; i < 19; i ++){
+    nbchapsize[i]= 0;
+  }
+  int totalchap=0;
+  for (int i = 0 ; i < N; i ++){
+    cin>>size[i];
+    if (i < N-1){
+      ecart[i]=pos[i+1]-pos[i];
+    }
+    nbchapsize[size[i]-1]++;
+    totalchap += size[i]*2;
+  }
+
+
+  vector<int> vraiecart(N-1);
+  // cout<<"Chapeau dispos"<<endl;
+  // printtab(19, nbchapsize);
+  // cout<<"Ecart"<<endl;
+  // printvec(N-1, ecart);
+
+  for (int i = 0 ; i <N-1;i++){
+    vraiecart[i]= max(ecart[i]%2==0?ecart[i]/2:ecart[i]/2+1,ecart[i+1]%2==0?ecart[i+1]/2:ecart[i+1]/2+1);
+  }
+  cout<<"Ecartreels"<<endl;
+  printvec(N-1, vraiecart);
+  if (totalchap < L){
+    cout<<"NO"<<endl;
+    return 0;
+  }
+  sort(vraiecart.begin(),vraiecart.begin()+N);
+  bool keepgoing = true;
+  bool answer= false;
+  int j =N-1;
+  int oldj= 0;
+  int h = 0;
+  while (keepgoing){
+    // cout << " j : "<<j<<"h : "<<h<<endl;
+    if (oldj!=j){
+      h= vraiecart[j]/2;
+      oldj=j;
+    }
+    if (h >= 20){
+      answer= false;
+      break;
+    }
+    if (j==0){
+      answer=true;
+      break;
+    }
+    if (nbchapsize[h]>0){
+      j --;
+      nbchapsize[h]--;
+       // cout<<"- 1 chapeau de taille "<< h+1<<endl;
+    }
+    else {
+       // cout<< "Pas de chapeau de taille "<<h+1<<endl;
+      h ++;
+
+    }
+  }
+  if (answer){
+    cout << "YES"<<endl;
+  }
+  else cout<<"NO"<<endl;
+
+  return 0;
+}
+
+void printtab(int n, int tab[]){
+  for (int i = 0; i < n; i ++){
+    cout <<tab[i]<<";";
+  }
+  cout<<endl;
+}
+void printvec(int n, vector<int> tab){
+  for (int i = 0; i < n; i ++){
+    cout <<tab[i]<<";";
+  }
+  cout<<endl;
+}
-- 
cgit v1.2.3