blob: 3d2d20b0843b2ad92c265070a6b6404faf7badb6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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;
}
|
