Contest Link : https://vjudge.net/contest/257453#overview
This was our first ICPC-18 practice contest arranged by Abul Kalam Azad Sir. This was Team
Contest and the team members of our team was Sajal, Samiul and me. The contest was very
interesting. At the last moment we solve problem A and got back to top beating DivByZero.
We have managed to solve 7 problems.
Problem A : Triangular N-queen Problem
Category : Add Hoc
Solution : Dipu and Sajal
#include "bits/stdc++.h"
using namespace std;
int getMax(int n)
{
int sum = 2*n+1;
return sum/3;
}
#define pii pair <int,int>
vector <pii> ans;
void print(int n)
{
int g = getMax(n);
int s = 1;
int last = 1;
for (int i = n-g+1; i<= n; i++)
{
int ii = i;
int jj = last;
//cout << "jj " << jj << " " << ii << endl;
if (jj > ii)
{
s++;
last = s;
jj = last;
}
ans.emplace_back(ii, jj);
//cout << ii << " " << jj << endl;
last += 2;
}
}
int main()
{
// freopen("in.txt", "r", stdin);
int tc;
cin >> tc;
int tcase = 1;
while (tc--)
{
int n;
cin >> n;
cout << tcase++ << " " << n << " " << getMax(n) << endl;
print(n);
for (int i = 0; i < ans.size(); i++)
{
cout << "[" << ans[i].first << "," << ans[i].second << "]";
if (i+1 == ans.size()) cout << endl;
else cout << " ";
}
ans.clear();
cout << endl;
}
}
Problem : C - String Cutting
Category : Data Structure
Solution : Dipu
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;
template <typename T> using orderSet = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
static const int maxn = 10000 + 5;
int cut, cutPos[maxn];
string s;
int arr[maxn];
orderSet <int> X;
struct segmentTree
{
int cumsum[27];
void assignLeaf(const int c)
{
for (int i = 0; i <= 26; i++) cumsum[i] = 0;
cumsum[c]++;
}
void clean()
{
for (int i = 1; i <= 26; i++) cumsum[i] = 0;
}
void marge(const segmentTree &l, const segmentTree &r)
{
for (int i = 1; i <= 26; i++) cumsum[i] = l.cumsum[i] + r.cumsum[i];
}
int getCount(int c)
{
return cumsum[c];
}
} stree[maxn*4];
void build(int node, int a, int b)
{
if (a > b) return;
if (a == b)
{
stree[node].assignLeaf(arr[a]);
return;
}
int left = node << 1;
int right = left | 1;
int mid = (a + b) >> 1;
build(left, a, mid);
build(right, mid+1, b);
stree[node].marge(stree[left], stree[right]);
}
segmentTree query(int node, int a, int b, int i, int j)
{
if (a > b || a > j || b < i)
{
segmentTree nul;
for (int i = 1; i <= 26; i++) nul.cumsum[i] = 0;
return nul;
}
if (a >= i && b <= j) return stree[node];
int left = node << 1;
int right = left | 1;
int mid = (a + b) >> 1;
segmentTree p = query(left, a, mid, i, j);
segmentTree q = query(right, mid+1, b, i, j);
segmentTree res;
res.marge(p, q);
return res;
}
int main()
{
//freopen("in.txt", "r", stdin);
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
cin >> cut;
for (int i = 1; i <= cut; i++) cin >> cutPos[i];
cin >> s;
int len = s.size();
for (int i = 0; i <= len; i++)
{
int c = s[i] - 'a' + 1;
arr[i+1] = c;
}
build(1, 1, len);
X.insert(1);
X.insert(len);
int ans = 0;
for (int i = 1; i <= cut; i++)
{
int ct = cutPos[i];
int greaterr = *X.upper_bound(ct);
int id = X.order_of_key(ct);
int lesser = *X.find_by_order(id);
if (lesser > ct) lesser = *X.find_by_order(id-1);
X.insert(ct);
X.insert(ct+1);
int l1 = lesser;
int r1 = ct;
int l2 = ct+1;
int r2 = greaterr;
segmentTree left = query(1, 1, len, l1, r1);
segmentTree right = query(1, 1, len, l2, r2);
int cnt = 0;
for (int j = 1; j <= 26; j++)
{
if (left.getCount(j) == 0 && right.getCount(j) > 0)
cnt++;
else if (left.getCount(j) > 0 && right.getCount(j) == 0)
cnt++;
}
ans += cnt;
//cout << "cnt " << cnt << endl;
}
cout << ans << endl;
X.clear();
for (int i = 0; i < 4*maxn; i++) stree[i].clean();
}
}
Problem : E - Pipecuts
Category : Basic Probability
Solution : Samiul
#include <bits/stdc++.h>
using namespace std;
class PipeCuts {
public:
double probability(vector <int> weldLocations, int L)
{
int c=0,cc=0,i,j,mn,mx,x,y,z,comb;
int n=weldLocations.size();
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
mn=min(weldLocations[i],weldLocations[j]);
mx=max(weldLocations[i],weldLocations[j]);
x=mn,y=mx-mn,z=100-mx;
if(x>L || y>L || z>L) c++;
cc++;
}
}
double p=(double)c/(double)cc;
return p;
}
};
Problem : G - Division
Category : STL
Solution : Dipu
#include "bits/stdc++.h"
using namespace std;
#define ll long long
set <string> upor[100], nich[100];
string tostring(ll num)
{
stringstream iss;
iss << num;
return iss.str();
}
void getAns()
{
vector <int> vec;
for (int i = 0; i < 10; i++) vec.emplace_back(i);
do {
bool vis[10] = {0};
ll val = 0;
for (int i = 0; i < 5; i++)
{
vis[ vec[i] ] = 1;
val = val * 10 + vec[i];
}
ll val2 = 0;
for (int i = 5; i < 10; i++) val2 = val2 * 10 + vec[i];
ll temp = val2;
string s2 = tostring(val);
string s = tostring(val2);
bool flag = true;
if (s2.size() < 5 && s.size() < 5) flag = false;
if ((int)s.size() < 5) s = "0" + s;
if ((int)s2.size() < 5) s2 = "0" + s2;
if (val2%val == 0 && flag == true)
{
ll N = val2/val;
if (N >= 2 && N <= 79) upor[N].emplace(s), nich[N].emplace(s2);
}
} while (next_permutation(vec.begin(), vec.end()));
}
int main()
{
ll num;
bool newline = false;
getAns();
while (cin >> num)
{
if (num == 0) break;
if (newline == true) cout << endl;
newline = true;
int sze = upor[num].size();
if (sze == 0)
{
cout << "There are no solutions for " << num << ".\n";
}
else
{
set <string> ::iterator it1, it2;
for (it1 = upor[num].begin(), it2 = nich[num].begin(); it1 != upor[num].end(); it1++, it2++)
cout << *it1 << " / " << *it2 << " = " << num << endl;
}
}
}
Problem : H - Identifying Tea
Category : Add Hoc
Solution : Samiul
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,x;
while(cin>>t){
int c=0,i;
for(i=0;i<5;i++){
cin>>x;
if(x==t) c++;
}
cout<<c<<"\n";
}
}
Problem : I - K12 - Building Construction
Category : Ternary Search
Solution : Dipu
#include "bits/stdc++.h"
using namespace std;
#define ll long long
static const int maxn = 1e4 + 5;
int n;
ll height[maxn], cost[maxn];
ll getCost(ll make)
{
ll sum = 0;
for (int i = 1; i <= n; i++)
{
ll need = abs(make - height[i]);
sum += need * cost[i];
}
return sum;
}
ll getMin()
{
ll low = 0;
ll high = 10000+5;
while (true)
{
if (high - low < 3)
{
ll min1 = getCost(low);
ll min2 = getCost(high);
ll min3 = 1e18;
if (low+1 < high) min3 = getCost(low+1);
return min(min1, min(min2, min3));
}
ll mid1 = low + (high - low) / 3;
ll mid2 = high - (high - low) / 3;
ll fmid1 = getCost(mid1);
ll fmid2 = getCost(mid2);
if (fmid1 <= fmid2) high = mid2;
else low = mid1;
}
}
int main()
{
// freopen("in.txt", "r", stdin);
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> height[i];
for (int i = 1; i <= n; i++) cin >> cost[i];
ll ans = getMin();
cout << ans << endl;
}
}
Problem : J - Beggar My Neighbour
Category : Add Hoc
Solution : Sajal
#include<bits/stdc++.h>
using namespace std;
#define PLAYER 1
#define DEALER 2
deque<string> deal,play1,hp,tmp;
int firstPlayer(int n){
while(n--){
if(play1.empty())
return -1;
string ss = play1.back();
play1.pop_back();
hp.push_back(ss);
if(ss[1] == 'J')
return 1;
else if(ss[1] == 'Q')
return 2;
else if(ss[1] == 'K')
return 3;
else if(ss[1] == 'A')
return 4;
}
return 0;
}
int dealer(int n){
while(n--){
if(deal.empty())
return -1;
string ss = deal.back();
deal.pop_back();
hp.push_back(ss);
if(ss[1] == 'J')
return 1;
else if(ss[1] == 'Q')
return 2;
else if(ss[1] == 'K')
return 3;
else if(ss[1] == 'A')
return 4;
}
return 0;
}
int player_first(){
int p,d;
while((p=firstPlayer(1))==0 && (d=dealer(1))==0);
if(p==-1||d==-1)
return -1;
if(p!=0){
while((d=dealer(p))!=0 && d!=-1 && (p=firstPlayer(d))!=0 && p!=-1);
if(d==-1 || p==-1)
return -1;
if(d==0)
return PLAYER;
else if(p==0)
return DEALER;
}
else if(d!=0){
while((p=firstPlayer(d))!=0 && p!=-1 && (d=dealer(p))!=0 && d!=-1);
if(d==-1 || p==-1)
return -1;
if(p==0)
return DEALER;
else if(d==0)
return PLAYER;
}
//cout<< "Player: " << play1.size() << " " << deal.size() << " " << hp.size() << endl;
return 0;
}
int dealer_first(){
int p,d;
while((d=dealer(1))==0 && (p=firstPlayer(1))==0);
if(p==-1||d==-1)
return -1;
if(d!=0){
while((p=firstPlayer(d))!=0 && p!=-1 && (d=dealer(p))!=0 && d!=-1);
if(d==-1 || p==-1)
return -1;
if(p==0)
return DEALER;
else if(d==0)
return PLAYER;
}
else if(p!=0){
while((d=dealer(p))!=0 && d!=-1 && (p=firstPlayer(d))!=0 && p!=-1);
if(d==-1 || p==-1)
return -1;
if(d==0)
return PLAYER;
else if(p==0)
return DEALER;
}
//cout<< "Dealer: " << play1.size() << " " << deal.size() << " " << hp.size() << endl;
return 0;
}
void player_take(){
int hp_si = hp.size();
for(int i=0; i<hp_si; i++){
play1.push_front(hp[i]);
}
hp.clear();
//cout<< "Player: " << play1.size() << " " << deal.size() <<endl;
}
void dealer_take(){
int hp_si = hp.size();
for(int i=0; i<hp_si; i++){
deal.push_front(hp[i]);
}
hp.clear();
//cout << "Dealer: " << play1.size() << " " << deal.size() << endl;
}
void clean()
{
deal.clear();
play1.clear();
hp.clear();
tmp.clear();
}
int main()
{
// freopen("in.txt", "r+", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string st;
while(1){
cin>>st;
if(st[0]=='#')
return 0;
play1.push_back(st);
for(int i=1; i<52; i++){
cin>>st;
if(i&1){
deal.push_back(st);
// cout << st << endl;
}
else{
play1.push_back(st);
}
}
int chq = player_first();
while(chq!=-1){
if(chq == DEALER){
dealer_take();
chq = dealer_first();
}
else if(chq == PLAYER){
player_take();
chq = player_first();
}
// else if(chq == 0)
// cout << "Why Zero!!"<< endl;
// cout << "What: " << chq<<endl;
}
int winP, winB;
if(deal.empty()) winP = 2, winB = play1.size();
if(play1.empty()) winP = 1, winB = deal.size();
cout << winP << " ";
if (winB < 10) cout << " " << winB << endl;
else cout << winB << endl;
clean();
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.