Skip to content

Commit 3253e45

Browse files
rajat2004rajat2004
committed
a2oj Ladder 13 67-71
1 parent 11649d6 commit 3253e45

5 files changed

Lines changed: 396 additions & 0 deletions

File tree

‎a2oj/ladder13/67.cpp‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
#pragma GCC optimize ("-O3")
2+
#include<bits/stdc++.h>
3+
using namespace std;
4+
5+
typedef long long int ll;
6+
typedef long long unsigned lluu;
7+
typedef long double ld;
8+
typedef pair<int,int> p32;
9+
typedef pair<ll,ll> p64;
10+
typedef pair<double,double> pdd;
11+
typedef vector<ll> v64;
12+
typedef vector<int> v32;
13+
typedef vector<vector<int> > vv32;
14+
typedef vector<vector<ll> > vv64;
15+
typedef vector<p64> vp64;
16+
typedef vector<p32> vp32;
17+
ll MOD = 998244353;
18+
ll NUM = 1e9+7;
19+
#define forn(i,e) for(ll i = 0; i < e; i++)
20+
#define forsn(i,s,e) for(ll i = s; i < e; i++)
21+
#define rforn(i,s) for(ll i = s; i >= 0; i--)
22+
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
23+
#define ln "\n"
24+
#define dbg(x) cout<<#x<<" = "<<x<<ln
25+
#define mp make_pair
26+
#define pb push_back
27+
#define ff first
28+
#define ss second
29+
#define INF 1e18
30+
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
31+
#define all(x) (x).begin(), (x).end()
32+
#define sz(x) ((ll)(x).size())
33+
#define zer ll(0)
34+
#define printarr(arr,n) forn(i,n) cout << arr[i] << " "
35+
#define input(arr,n) forn(i,n) cin >> arr[i]
36+
37+
void solve() {
38+
int n;
39+
cin >> n;
40+
v32 v(n);
41+
input(v,n);
42+
sort(v.begin(), v.end());
43+
44+
int ans=n;
45+
int gt=n/2;
46+
47+
for(int i=0; i<n/2; i++) {
48+
while(gt<n) {
49+
if (v[i]*2 <= v[gt]) {
50+
ans--;
51+
gt++;
52+
break;
53+
}
54+
else
55+
gt++;
56+
}
57+
if (gt>=n)
58+
break;
59+
}
60+
cout << ans << ln;
61+
}
62+
63+
int main() {
64+
fast_cin();
65+
int t=1;
66+
// cin >> t;
67+
while(t--) {
68+
solve();
69+
}
70+
return 0;
71+
}

‎a2oj/ladder13/68.cpp‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
#pragma GCC optimize ("-O3")
2+
#include<bits/stdc++.h>
3+
using namespace std;
4+
5+
typedef long long int ll;
6+
typedef long long unsigned lluu;
7+
typedef long double ld;
8+
typedef pair<int,int> p32;
9+
typedef pair<ll,ll> p64;
10+
typedef pair<double,double> pdd;
11+
typedef vector<ll> v64;
12+
typedef vector<int> v32;
13+
typedef vector<vector<int> > vv32;
14+
typedef vector<vector<ll> > vv64;
15+
typedef vector<p64> vp64;
16+
typedef vector<p32> vp32;
17+
ll MOD = 998244353;
18+
ll NUM = 1e9+7;
19+
#define forn(i,e) for(ll i = 0; i < e; i++)
20+
#define forsn(i,s,e) for(ll i = s; i < e; i++)
21+
#define rforn(i,s) for(ll i = s; i >= 0; i--)
22+
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
23+
#define ln "\n"
24+
#define dbg(x) cout<<#x<<" = "<<x<<ln
25+
#define mp make_pair
26+
#define pb push_back
27+
#define ff first
28+
#define ss second
29+
#define INF 1e18
30+
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
31+
#define all(x) (x).begin(), (x).end()
32+
#define sz(x) ((ll)(x).size())
33+
#define zer ll(0)
34+
#define printarr(arr,n) forn(i,n) cout << arr[i] << " "
35+
#define input(arr,n) forn(i,n) cin >> arr[i]
36+
37+
int median(const v32& v, int n, int x) {
38+
auto low = lower_bound(v.begin(), v.end(), x);
39+
auto high = upper_bound(v.begin(), v.end(), x);
40+
41+
int count=high-low, low_idx=low-v.begin(), high_idx=high-v.begin();
42+
int diff1 = low_idx - (n+1)/2 + 1;
43+
int diff2 = (n+1)/2-high_idx;
44+
// dbg(diff1);
45+
// dbg(diff2);
46+
if (diff1>0) {
47+
if (n%2==0)
48+
return 2*diff1-1;
49+
else
50+
return 2*diff1;
51+
}
52+
if (diff2>0) {
53+
if (n%2==0)
54+
return 2*diff2;
55+
else
56+
return 2*diff2-1;
57+
}
58+
// return 2*diff2;
59+
60+
return 0;
61+
}
62+
63+
void solve() {
64+
int n,x;
65+
cin >> n >> x;
66+
v32 v(n);
67+
input(v,n);
68+
sort(v.begin(), v.end());
69+
if (v[(n+1)/2 - 1] == x)
70+
cout << 0 << ln;
71+
else {
72+
int res=0;
73+
if (!binary_search(v.begin(), v.end(), x)) {
74+
v.push_back(x);
75+
sort(v.begin(), v.end());
76+
n++;
77+
res=1;
78+
if (v[(n+1)/2 - 1] == x) {
79+
// cout << "Here" << ln;
80+
cout << 1 << ln;
81+
return;
82+
}
83+
}
84+
res += median(v,n,x);
85+
cout << res << ln;
86+
}
87+
}
88+
89+
int main() {
90+
fast_cin();
91+
int t=1;
92+
// cin >> t;
93+
while(t--) {
94+
solve();
95+
}
96+
return 0;
97+
}

‎a2oj/ladder13/69.cpp‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#pragma GCC optimize ("-O3")
2+
#include<bits/stdc++.h>
3+
using namespace std;
4+
5+
typedef long long int ll;
6+
typedef long long unsigned lluu;
7+
typedef long double ld;
8+
typedef pair<int,int> p32;
9+
typedef pair<ll,ll> p64;
10+
typedef pair<double,double> pdd;
11+
typedef vector<ll> v64;
12+
typedef vector<int> v32;
13+
typedef vector<vector<int> > vv32;
14+
typedef vector<vector<ll> > vv64;
15+
typedef vector<p64> vp64;
16+
typedef vector<p32> vp32;
17+
ll MOD = 998244353;
18+
ll NUM = 1e9+7;
19+
#define forn(i,e) for(ll i = 0; i < e; i++)
20+
#define forsn(i,s,e) for(ll i = s; i < e; i++)
21+
#define rforn(i,s) for(ll i = s; i >= 0; i--)
22+
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
23+
#define ln "\n"
24+
#define dbg(x) cout<<#x<<" = "<<x<<ln
25+
#define mp make_pair
26+
#define pb push_back
27+
#define ff first
28+
#define ss second
29+
#define INF 1e18
30+
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
31+
#define all(x) (x).begin(), (x).end()
32+
#define sz(x) ((ll)(x).size())
33+
#define zer ll(0)
34+
#define printarr(arr,n) forn(i,n) cout << arr[i] << " "
35+
#define input(arr,n) forn(i,n) cin >> arr[i]
36+
37+
ll try0(ll r, ll g, ll b) {
38+
return (r/3 + g/3 + b/3);
39+
}
40+
41+
ll try1(ll r, ll g, ll b) {
42+
if (r<1 || g<1 || b<1) return 0;
43+
return ( (r-1)/3 + (g-1)/3 + (b-1)/3 + 1 );
44+
}
45+
46+
ll try2(ll r, ll g, ll b) {
47+
if (r<2 || g<2 || b<2) return 0;
48+
return ( (r-2)/3 + (g-2)/3 + (b-2)/3 + 2 );
49+
}
50+
51+
void solve() {
52+
ll r,g,b;
53+
cin >> r >> g >> b;
54+
55+
ll t0 = try0(r,g,b);
56+
ll t1 = try1(r,g,b);
57+
ll t2 = try2(r,g,b);
58+
59+
cout << max(max(t0,t1), t2) << ln;
60+
}
61+
62+
int main() {
63+
fast_cin();
64+
int t=1;
65+
// cin >> t;
66+
while(t--) {
67+
solve();
68+
}
69+
return 0;
70+
}

‎a2oj/ladder13/70.cpp‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
#pragma GCC optimize ("-O3")
2+
#include<bits/stdc++.h>
3+
using namespace std;
4+
5+
typedef long long int ll;
6+
typedef long long unsigned lluu;
7+
typedef long double ld;
8+
typedef pair<int,int> p32;
9+
typedef pair<ll,ll> p64;
10+
typedef pair<double,double> pdd;
11+
typedef vector<ll> v64;
12+
typedef vector<int> v32;
13+
typedef vector<vector<int> > vv32;
14+
typedef vector<vector<ll> > vv64;
15+
typedef vector<p64> vp64;
16+
typedef vector<p32> vp32;
17+
ll MOD = 998244353;
18+
ll NUM = 1e9+7;
19+
#define forn(i,e) for(ll i = 0; i < e; i++)
20+
#define forsn(i,s,e) for(ll i = s; i < e; i++)
21+
#define rforn(i,s) for(ll i = s; i >= 0; i--)
22+
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
23+
#define ln "\n"
24+
#define dbg(x) cout<<#x<<" = "<<x<<ln
25+
#define mp make_pair
26+
#define pb push_back
27+
#define ff first
28+
#define ss second
29+
#define INF 1e18
30+
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
31+
#define all(x) (x).begin(), (x).end()
32+
#define sz(x) ((ll)(x).size())
33+
#define zer ll(0)
34+
#define printarr(arr,n) forn(i,n) cout << arr[i] << " "
35+
#define input(arr,n) forn(i,n) cin >> arr[i]
36+
37+
void solve() {
38+
int n,a,b;
39+
lluu r,avg;
40+
cin >> n >> r >> avg;
41+
lluu sum=0;
42+
vp32 v(n);
43+
44+
forn(i,n) {
45+
cin >> a >> b;
46+
sum += a;
47+
v[i] = mp(b,a);
48+
}
49+
50+
lluu req = avg*n;
51+
52+
if (sum>=req) {
53+
cout << 0 << ln;
54+
return;
55+
}
56+
lluu count=0, diff=req-sum;
57+
sort(v.begin(), v.end());
58+
59+
forn(i,n) {
60+
int tmp_a=v[i].second, tmp_b=v[i].first;
61+
lluu tdiff = r - tmp_a;
62+
if (diff > tdiff) {
63+
count += tdiff*tmp_b;
64+
diff -= tdiff;
65+
}
66+
else {
67+
count += diff*tmp_b;
68+
break;
69+
}
70+
}
71+
cout << count << ln;
72+
}
73+
74+
int main() {
75+
fast_cin();
76+
int t=1;
77+
// cin >> t;
78+
while(t--) {
79+
solve();
80+
}
81+
return 0;
82+
}

0 commit comments

Comments
 (0)