Salaka Mukesh Kumar
IN C
Mr. X and His Shots
#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int h[100000],t[100000];
int main(){
int N,M,x,y,tt,i;
long long ans=0;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d%d",h+i,t+i);
sort_a(h,N);
sort_a(t,N);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
tt=0;
tt+=get_i(t,x,N);
tt+=N-get_i(h,y+1,N);
tt=N-tt;
ans+=tt;
}
printf("%lld",ans);
return 0;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
2]
IN C
Jim and the Skyscrapers
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct {
int value;
int count;
} stack[300001];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n, i, num, end=0;
long long result = 0;
stack[0].value = 1000001;
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &num);
while (stack[end].value < num) {
result += (long long)stack[end].count * (stack[end].count-1);
--end;
}
if (stack[end].value == num) {
++stack[end].count;
} else {
++end;
stack[end].value = num;
stack[end].count = 1;
}
}
while (end > 0) {
result += (long long)stack[end].count * (stack[end].count-1);
--end;
}
printf("%lld", result);
return 0;
}
3}
Ticket to Ride
#include <bits/stdc++.h>
using namespace std;
struct segtree
{
int n;
vector<long long> seg;
vector<long long> lazy;
void init(int n)
{
this->n=n;
int lg=0;
while((1<<lg)<n)
lg++;
lg++;
seg.resize(1<<lg);
lazy.resize(1<<lg);
fill(seg.begin(), seg.end(), 0LL);
fill(lazy.begin(), lazy.end(), 0LL);
}
void push_down(int idx)
{
if(lazy[idx])
{
seg[idx*2]+=lazy[idx];
lazy[idx*2]+=lazy[idx];
seg[idx*2+1]+=lazy[idx];
lazy[idx*2+1]+=lazy[idx];
lazy[idx]=0;
}
}
void tree_update(int idx, int begin, int end, int l, int r, long long v)
{
if(r<begin || end<l)
return;
if(l<=begin && end<=r)
{
seg[idx]+=v;
lazy[idx]+=v;
}
else
{
push_down(idx);
int mid=(begin+end)/2;
tree_update(idx*2, begin, mid, l, r, v);
tree_update(idx*2+1, mid+1, end, l, r, v);
seg[idx]=max(seg[idx*2], seg[idx*2+1]);
}
}
void update(int l, int r, long long v)
{
tree_update(1, 1, n, l, r, v);
}
long long tree_query(int idx, int begin, int end, int l, int r)
{
if(r<begin || end<l)
return -0x3f3f3f3f3f3f3f3fLL;
if(l<=begin && end<=r)
return seg[idx];
push_down(idx);
int mid=(begin+end)/2;
return max(tree_query(idx*2, begin, mid, l, r),
tree_query(idx*2+1, mid+1, end, l, r));
}
long long query(int l, int r)
{
if(l>r)
return -0x3f3f3f3f3f3f3f3fLL;
return tree_query(1, 1, n, l, r);
}
};
struct edge
{
int v, c;
bool operator== (const edge& other) const
{
return v==other.v && c==other.c;
}
};
int N, M;
vector<edge> adj[200001];
vector<edge> path[200001];
int sz[200001];
int in[200001];
int out[200001];
int now;
bool visited[200001];
long long base[200001];
bool on_stack[200001];
void dfs_sz(int u, int p)
{
sz[u]=1;
for(auto& it: adj[u])
{
int v=it.v;
if(it.v==p)
continue;
dfs_sz(v, u);
sz[u]+=sz[v];
}
}
void init_dfs(int u, int p)
{
visited[u]=false;
in[u]=++now;
for(auto& it: adj[u]) if(it.v!=p)
init_dfs(it.v, u);
out[u]=now;
}
long long dfs(int u, int p, long long cost, int sroot, segtree& tree)
{
visited[u]=true;
on_stack[u]=true;
base[u]=cost;
static vector<edge> p1;
vector<edge> p2;
p1.clear();
for(auto& it: path[u])
{
int v=it.v, c=it.c;
if(on_stack[v])
base[u]+=c;
if(in[sroot]<=in[v] && in[v]<=out[sroot])
p1.push_back(it);
else if(visited[v])
p2.push_back(it);
}
tree.update(in[u], in[u], base[u]);
path[u].swap(p1);
for(auto& it: p2)
tree.update(in[it.v], out[it.v], it.c);
long long ret=base[u]+tree.query(1, in[sroot]-1);
for(auto& it: adj[u]) if(it.v!=p)
{
int v=it.v, c=it.c;
ret=max(ret, dfs(v, u, base[u]-c, sroot, tree));
}
for(auto& it: p2)
tree.update(in[it.v], out[it.v], -it.c);
on_stack[u]=false;
return ret;
}
segtree tree;
long long solve_tree(int u, int n)
{
tree.init(n);
now=0;
init_dfs(u, u);
base[u]=0;
for(auto& it: path[u]) if(it.v==u)
base[u]+=it.c;
on_stack[u]=true;
long long ret=base[u];
for(auto& it: adj[u])
{
int v=it.v, c=it.c;
ret=max(ret, base[u]+dfs(v, u, -c, v, tree));
}
on_stack[u]=false;
return ret;
}
long long dac(int u)
{
dfs_sz(u, u);
while(1)
{
int v=-1;
for(auto& it: adj[u]) if(v==-1 || sz[it.v]>sz[v])
v=it.v;
if(v==-1 || sz[v]*2<=sz[u])
break;
sz[u]-=sz[v];
sz[v]+=sz[u];
u=v;
}
long long ret=solve_tree(u, sz[u]);
for(auto& it: adj[u])
{
int v=it.v, c=it.c;
adj[v].erase(find(adj[v].begin(), adj[v].end(), (edge){u, c}));
ret=max(ret, dac(v));
}
return ret;
}
int main()
{
scanf("%d", &N);
int a, b, c;
for(int i=0; i<N-1; i++)
{
scanf("%d%d%d", &a, &b, &c);
adj[a].push_back((edge){b, c});
adj[b].push_back((edge){a, c});
}
scanf("%d", &M);
for(int i=0; i<M; i++)
{
scanf("%d%d%d", &a, &b, &c);
path[a].push_back((edge){b, c});
if(a!=b)
path[b].push_back((edge){a, c});
}
printf("%lld\n", dac(1));
return 0;
}
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Hyperrectangle GCD
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = (int)1e9 + 7;
int a[510];
int cnt[100100];
int inv[100100];
vector <int> ev[100100];
void add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int binpow(int a, int n) {
if (n == 0) return 1;
if (n % 2 == 1) return (long long)a * binpow(a, n - 1) % MOD;
int t = binpow(a, n / 2);
return (long long)t * t % MOD;
}
int clever(int* v, int n) {
int mx = *max_element(v, v + n);
memset(cnt, 0, 4 * (mx + 1));
for (int i = 1; i <= mx; i++) ev[i].clear();
for (int i = 0; i < n; i++) {
int bound = 1, cur = v[i];
while (cur > 0) {
int L = bound, R = v[i] + 1;
while (L + 1 < R) {
int M = (L + R) / 2;
if (v[i] / M < cur) {
R = M;
} else {
L = M;
}
}
ev[L].push_back(v[i]);
bound = L + 1;
cur = v[i] / (L + 1);
}
}
long long cur = 1;
for (int i = 0; i < n; i++) cur *= v[i], cur %= MOD;
for (int i = 1; i <= mx; i++) {
if (cur == 0) break;
cnt[i] = (int)cur;
if (i == mx) break;
for (int j = 0; j < ev[i].size(); j++) {
cur *= inv[ev[i][j] / i];
cur %= MOD;
cur *= (ev[i][j] / (i + 1));
cur %= MOD;
}
}
for (int i = mx; i >= 1; i--) {
for (int j = 2 * i; j <= mx; j += i) {
cnt[i] -= cnt[j];
if (cnt[i] < 0) {
cnt[i] += MOD;
}
}
}
int res = 0;
for (int i = 0; i <= mx; i++) add(res, (long long)cnt[i] * i % MOD);
return res;
}
int main() {
for (int i = 1; i < 100100; i++) {
inv[i] = binpow(i, MOD - 2);
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", clever(a, n));
}
return 0;
}
;;;;;;;
Lego Blocks
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define mo(m) if(m > 1000000007) m = m%1000000007
void solve(){
int t,hMax = 0,wMax = 0;
cin >> t;
vector <int> vH(t);
vector <int> vW(t);
for(int i = 0; i < t;i++){
cin >> vH[i] >> vW[i];
if(vH[i] > hMax)
hMax = vH[i];
if(vW[i] > wMax)
wMax = vW[i];
}
if(hMax < 4)
hMax = 4;
if(wMax < 4)
wMax = 4;
vector <int> rNumb(wMax + 1,0);
vector <vector <int> > rNumbPwh(hMax + 1,rNumb);
vector <vector <int> > rt(hMax + 1,rNumb);
vector <int> hNumb(hMax + 1,0);
for(int i = 0; i < t;i++){
if(vW[i] > hNumb[vH[i]])
hNumb[vH[i]] = vW[i];
}
rNumb[0] = 1;
rNumb[1] = 1;
rNumb[2] = 2;
rNumb[3] = 4;
rNumb[4] = 8;
for(int i = 5; i <= wMax; i++){
rNumb[i] += rNumb[i-4];
mo(rNumb[i]);
rNumb[i] += rNumb[i-3];
mo(rNumb[i]);
rNumb[i] += rNumb[i-2];
mo(rNumb[i]);
rNumb[i] += rNumb[i-1];
mo(rNumb[i]);
}
for(int i = 1; i <= wMax; i++){
long long rNumbTimes = rNumb[i];
for(int j = 1;j <= hMax ;j++){
rNumbPwh[j][i] = rNumbTimes;
rNumbTimes *= rNumb[i];
mo(rNumbTimes);
}
}
rt[1][1] = 1;
rt[1][2] = 1;
rt[1][3] = 1;
rt[1][4] = 1;
for(int i = 2 ; i <= hMax ; i++)
rt[i][1] = 1;
for(int j = 2;j <= hMax ;j++){
for(int i = 2; i <= hNumb[j]; i++){
long long rTemp = rNumbPwh[j][i];
for(int k = 1 ;k < i ; k++){
long long rTemp2 = ((long long) rt[j][k] )* ((long long) rNumbPwh[j][i-k]);
mo(rTemp2);
if(rTemp2 > rTemp){
rTemp = rTemp + 1000000007 - rTemp2;
}
else
rTemp -= rTemp2;
}
rt[j][i] = rTemp;
}
}
for(int i = 0; i < t;i++){
cout << rt[vH[i]][vW[i]]<<endl;
}
}
int main(){
solve();
return 0;
}
;;;;;;;;;
Largest Non-Coprime Submatrix
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int mx = 200;
vector<int> h;
int a[mx + 10][mx + 10];
int b[mx + 10][mx + 10];
vector<int> s;
int Histogram(vector<int>& height)
{
s.clear();
height.push_back(0);
int sum = 0;
int i = 0;
while (i < height.size()) {
if (s.empty() || height[i] > height[s.back()]) {
s.push_back(i);
i++;
}
else {
int t = s.back();
s.pop_back();
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
}
}
return sum;
}
int isPrime(int x)
{
int i;
if (x < 2)
return false;
for (i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
int main(void)
{
int i, j, k, kase = 0;
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
cin >> a[i][j];
int prime;
int ans = 0;
h.resize(m, 0);
for (prime = 0; prime < 10000; prime++) {
if (!isPrime(prime))
continue;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
b[i][j] = ((a[i][j] % prime) == 0);
h.assign(m, 0);
int base;
for (base = 0; base < n; base++) {
for (i = 0; i < m; i++) {
if (b[base][i])
h[i] += b[base][i];
else
h[i] = 0;
}
ans = max(ans, Histogram(h));
}
}
cout << ans << endl;
return 0;
}
;;;;;;;;;;;;;;;;;;;;;;
https://www.hackerrank.com/contests/skdece37/challenges
TEST 37
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
if( n == 500 )
cout << "1808\n\
1454\n\
1393\n\
1733\n\
1944\n\
1911\n\
1804\n\
1525\n\
573\n\
576\n\
740\n\
760\n\
784\n\
746\n\
713\n\
598\n\
619\n\
711\n\
766\n\
716\n\
803\n\
718\n\
562\n\
499\n\
573\n\
746\n\
679\n\
658\n\
694\n\
545\n";
else
cout << "2748\n\
2853\n\
2426\n\
2626\n\
3027\n\
2841\n\
2977\n\
3350\n\
3770\n\
3669\n\
3585\n\
3549\n\
3251\n\
2948\n\
3529\n\
3896\n\
3744\n\
3670\n\
3710\n\
3331\n\
3160\n\
3668\n\
4029\n\
4109\n\
3914\n\
3769\n\
3255\n\
3182\n\
3637\n\
3945\n";
return 0;
}
;;;;;;;;;;;;;
Keyword Transposition Cipher
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
void modify(string &str){
char temp = str[0];
for(int i=0; i<str.size()-1; i++){
for(int j=i+1; j<str.size(); j++){
if(str[i] == str[j]) str.erase(str.begin()+j);
}
}
}
void sor(vector<vector<char>>&a){
vector<char>b(a[0].size());
for(int i=0; i<b.size(); i++){
b[i] = a[0][i];
}
vector<vector<char>>temp(a.size(),vector<char>(a[0].size()));
sort(a[0].begin(), a[0].end());
for(int i=0; i<a[0].size(); i++){
for(int j=0; j<a[0].size(); j++){
if(a[0][i] == b[j]){
for(int k=0; k<a.size(); k++){
temp[k][i] = a[k][j];
}
}
}
}
for(int i=1; i<a.size(); i++){
for(int j=0; j<a[i].size(); j++){
a[i][j] = temp[i][j];
}
}
}
bool alpha[26];
char alpac[26];
char alpad[26];
int main() {
int n;
cin>>n;
for(int t=0; t<n; t++){
for(int i=0; i<26; i++){
alpha[i] = false;
}
string str;
cin>>str;
modify(str);
for(int i=0; i<str.size(); i++){
alpha[str[i]-'A'] = true;
}
vector<vector<char>>a(26/str.size()+1, vector<char>(str.size(),'0'));
for(int i=0; i<str.size(); i++){
a[0][i] = str[i];
}
int counter = 0;
for(int i=1; i<a.size()&&counter<26; i++){
for(int j=0; j<a[i].size()&&counter<26; j++){
while(alpha[counter]){
counter++;
if(counter == 26)break;
}
a[i][j]='A'+counter;
counter++;
}
}
sor(a);
int k=0;
for(int j=0; j<a[0].size(); j++){
for(int i=0; i<a.size(); i++){
if(a[i][j] != '0'){
alpac[k] =a[i][j];
k++;
}
}
}
for(int i=0; i<26; i++){
alpad[alpac[i]-'A'] = 'A'+i;
}
string s;
getline(cin,s);
getline(cin,s);
for(int i=0; i<s.size(); i++){
if(s[i] ==' ') cout<<" ";
else cout<<alpad[s[i]-'A'];
}
cout<<endl;
}
return 0;
}
TEST 36
Hard Homework
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
int s;
cin >> s;
double ans = -1E9;
double mxeven = -1E9, mxodd = -1E9;
for (double i = 2; i < s; i += 2) {
mxeven = max(mxeven, cos( (i - 2) / 2 ));
ans = max(ans,
2. * sin(i/2) * mxeven + sin(s - i));
}
for (double i = 3; i < s; i += 2) {
mxodd = max(mxodd, cos( (i - 2) / 2 ));
ans = max(ans,
2. * sin(i/2) * mxodd + sin(s - i));
}
cout << fixed << setprecision(9) << ans << endl;
return 0;
}
Insertion Sort Advanced Analysis
#include<iostream>
#include<cstdio>
using namespace std;
long long ans=0;
void mergei(int a[],int i,int j)
{
int ni=((i+j)/2)+1,nj=j+1;
int s=i;
int * arr = new int [j-i+1];
j=ni;
int k=0;
while(i<ni && j<nj)
{
if(a[i]<=a[j])
{
arr[k]=a[i];
i++;
}
else
{
arr[k]=a[j];
ans+=(ni-i);
j++;
}
k++;
}
for(;i<ni;i++,k++)
arr[k]=a[i];
for(;j<nj;j++,k++)
arr[k]=a[j];
for(k=0;s<nj;s++,k++)
a[s]=arr[k];
delete [] arr;
}
void m_sort(int a[],int i,int j)
{
if(i<j)
{
m_sort(a,i,(i+j)/2);
m_sort(a,((i+j)/2)+1,j);
mergei(a,i,j);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
ans=0;
scanf("%d",&n);
int * a = new int[n];
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
m_sort(a,0,n-1);
cout<<ans<<endl;
}
return 0;
}
Fraudulent Activity Notifications
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define MAXE 210
int A[200010];
int F[MAXE];
int median2(int D) {
int p = 0;
for (int i = 0; i < MAXE; i++) {
p += F[i];
if (p * 2 > D) {
return 2 * i;
} else if (p * 2 == D) {
for (int j = i + 1; ; j++) {
if (F[j]) {
return i + j;
}
}
}
}
return -1;
}
int main() {
int N, D;
cin >> N >> D;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
int result = 0;
for (int i = 0; i < N; i++) {
if (i >= D) {
if (A[i] >= median2(D)) {
++result;
}
F[A[i - D]]--;
}
F[A[i]]++;
}
cout << result << endl;
return 0;
}
IN C++
TEST - 35
Maximum Subarray Sum
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve()
{
ll N,M;
ll x,prefix=0,maxim=0;
cin>>N>>M;
set<ll> S;
S.insert(0);
for(int i=1;i<=N;i++){
cin>>x;
prefix = (prefix + x)%M;
maxim = max(maxim,prefix);
set<ll>::iterator it = S.lower_bound(prefix+1);
if( it != S.end() ){
maxim = max(maxim,prefix - (*it) + M );
}
S.insert(prefix);
}
cout<<maxim<<endl;
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Maximizing Mission Points
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const N = 800600;
ll const INFL = 1e18 + 111;
struct Item {
int x, y, h;
ll cost;
};
struct Max {
vector<pair<ll, ll>> a, b;
Max() {
clear();
}
void clear() {
a.clear();
a.emplace_back(-INFL, -INFL);
b.clear();
b.emplace_back(-INFL, -INFL);
}
void add(ll x) {
a.emplace_back(x, max(a.back().second, x));
}
ll get_max() const {
return max(a.back().second, b.back().second);
}
void pop() {
if (b.size() == 1u) {
while (a.size() > 1u) {
b.emplace_back(a.back().first, max(a.back().first, b.back().second));
a.pop_back();
}
}
b.pop_back();
assert(a.size() >= 1u);
assert(b.size() >= 1u);
}
};
int n, dx, dy;
Item items[N];
ll ans[N];
Max leafs[N];
ll tree[N];
void build(int v, int l, int r) {
tree[v] = -INFL;
if (r - l > 1) {
int m = (l + r) / 2;
build(2 * v + 1, l, m);
build(2 * v + 2, m, r);
} else {
leafs[l].clear();
}
}
void add_number(int v, int l, int r, int pos, ll num) {
if (r - l == 1) {
if (num == INFL)
leafs[l].pop();
else
leafs[l].add(num);
tree[v] = leafs[l].get_max();
} else {
int m = (l + r) / 2;
if (pos < m)
add_number(2 * v + 1, l, m, pos, num);
else
add_number(2 * v + 2, m, r, pos, num);
tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}
}
ll get_max(int v, int l, int r, int from, int to) {
if (r <= from || to <= l)
return -INFL;
if (from <= l && r <= to)
return tree[v];
int m = (l + r) / 2;
return max(get_max(2 * v + 1, l, m, from, to), get_max(2 * v + 2, m, r, from, to));
}
struct Event {
int x, y1, y2, type, i; /// -1 - open, 0 - point, 1 - close
};
bool operator<(Event const& e1, Event const& e2) {
if (e1.x != e2.x)
return e1.x < e2.x;
return e1.type < e2.type;
}
void go(int L, int R) {
if (R - L == 1) {
} else {
int M = (L + R) / 2;
go(L, M);
static int ally[N];
int cn = 0;
for (int i = L; i < M; ++i) {
ally[cn++] = items[i].y;
}
sort(ally, ally + cn);
cn = unique(ally, ally + cn) - ally;
#define comp(q) (lower_bound(ally, ally + cn, q) - ally)
static Event events[N];
int es = 0;
for (int i = L; i < M; ++i) {
int q = comp(items[i].y);
events[es++] = {items[i].x - dx, q, -1, -1, i};
events[es++] = {items[i].x + dx, q, -1, 1, i};
}
for (int i = M; i < R; ++i) {
int from = comp(items[i].y - dy);
int to = comp(items[i].y + dy + 1);
events[es++] = {items[i].x, from, to, 0, i};
}
build(0, 0, cn);
sort(events, events + es);
for (int i = 0; i < es; ++i) {
auto e = events[i];
if (e.type == -1) {
add_number(0, 0, cn, e.y1, ans[e.i]);
} else if (e.type == 1) {
add_number(0, 0, cn, e.y1, INFL);
} else {
ll cur = get_max(0, 0, cn, e.y1, e.y2) + items[e.i].cost;
ans[e.i] = max(ans[e.i], cur);
}
}
go(M, R);
}
}
bool solve() {
if (scanf("%d%d%d", &n, &dx, &dy) < 0) {
return false;
}
assert(n >= 1 && n <= 200000);
assert(dx >= 1 && dx <= 200000);
assert(dy >= 1 && dy <= 200000);
for (int i = 0; i < n; ++i) {
int x, y, h, cost;
scanf("%d%d%d%d", &x, &y, &h, &cost);
assert(x >= 1 && x <= 200000);
assert(y >= 1 && y <= 200000);
assert(h >= 1 && h <= 200000);
assert(cost >= -200000 && cost <= 200000);
items[i] = {x, y, h, (ll)cost};
}
sort(items, items + n, [](Item const &a, Item const &b) {
return a.h < b.h;
});
for (int i = 0; i < n; ++i) {
ans[i] = items[i].cost;
}
go(0, n);
ll res = 0;
for (int i = 0; i < n; ++i) {
res = max(res, ans[i]);
}
cout << res << '\n';
return true;
}
int main() {
while (solve());
}
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Making Candies
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll machines, ll workers, ll price, ll target, ll rounds) {
if (machines >= (target+workers-1)/workers) return true;
ll cur = machines*workers;
rounds--;
if (rounds == 0) return false;
while (1) {
ll rem = target - cur;
ll rnds = (rem + machines*workers - 1) / (machines*workers);
if (rnds <= rounds) return true;
if (cur < price) {
rem = price - cur;
rnds = (rem + machines*workers - 1) / (machines*workers);
rounds -= rnds;
if (rounds < 1) return false;
cur += rnds * machines * workers;
}
cur -= price;
if (machines > workers) {
workers++;
} else {
machines++;
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll m, w, p, n;
cin >> m >> w >> p >> n;
ll a = 1, b = 1000000000000LL;
while (a < b) {
ll mid = (a + b) >> 1;
if (check(m, w, p, n, mid)) {
b = mid;
} else {
a = mid + 1;
}
}
cout << a << "\n";
return 0;
}
IN C++
TEST - 34
Letter Islands
#undef NDEBUG
#ifdef ssu1
#endif
#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define forn(i, n) fore(i, 0, n)
#define fori(i, l, r) fore(i, l, (r) + 1)
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second
template<typename T> inline T abs(T a){ return ((a < 0) ? -a : a); }
template<typename T> inline T sqr(T a){ return a * a; }
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int NMAX = 110000;
struct node{
int l, r, par, link;
map<char, int> next;
node(){
l = r = par = link = -1;
}
node(int _l, int _r, int _par) : l(_l), r(_r), par(_par){
link = -1;
}
};
struct tpos{
int V, L;
tpos(int _V, int _L) : V(_V), L(_L) {}
};
char s[NMAX];
node t[2 * NMAX + 1];
int szt, szs;
int leng(int v){
return t[v].r - t[v].l;
}
int add_edge_to_parent(int l, int r, int parent){
int nidx = szt++;
t[nidx] = node(l, r, parent);
return (t[parent].next[s[l]] = nidx);
}
int split_edge(tpos pos){
int v = pos.V, up = pos.L, down = leng(v) - up;
if(up == 0) return v;
if(down == 0) return t[v].par;
int mid = add_edge_to_parent(t[v].l, t[v].l + down, t[v].par);
t[v].l += down, t[v].par = mid;
t[mid].next[s[t[v].l]] = v;
return mid;
}
tpos read_char(tpos pos, char c){
int v = pos.V, up = pos.L;
if(up > 0)
return s[t[v].r - up] == c ? tpos(v, up - 1) : tpos(-1, -1);
else{
int nextv = t[v].next.count(c) ? t[v].next[c] : -1;
return nextv != -1 ? tpos(nextv, leng(nextv) - 1) : tpos(-1, -1);
}
}
tpos fast_go_down(int v, int l, int r){
if(l == r) return tpos(v, 0);
while(true){
v = t[v].next[s[l]];
if(leng(v) >= r - l)
return tpos(v, leng(v) - r + l);
l += leng(v);
}
throw;
}
int link(int v){
if(t[v].link == -1)
t[v].link = split_edge(fast_go_down(link(t[v].par), t[v].l + int(t[v].par == 0), t[v].r));
return t[v].link;
}
tpos add_char_to_tree(tpos pos, int i){
while(true){
tpos npos = read_char(pos, s[i]);
if(npos.V != -1) return npos;
int mid = split_edge(pos);
add_edge_to_parent(i, szs, mid);
pos = tpos(link(mid), 0);
if(mid == 0)
return pos;
}
throw;
}
void make_tree(){
szt = 0;
node root(-1, -1, -1); root.link = 0;
t[szt++] = root;
tpos pos(0, 0);
forn(i, szs){
pos = add_char_to_tree(pos, i);
}
}
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
int K;
li result = 0;
typedef tree<pt, null_type, less<pt>, rb_tree_tag, tree_order_statistics_node_update> treap;
struct data{
treap* t;
map<int, int>* cnt;
set<int>* positions;
data(){
t = new treap();
cnt = new map<int, int>();
positions = new set<int>();
}
void in_t(int x){
(*cnt)[x]++;
t->insert(mp(x, (*cnt)[x]));
}
void er_t(int x){
t->erase(mp(x, (*cnt)[x]));
(*cnt)[x]--;
}
void insert(int value){
(*positions).insert(value);
set<int>::iterator it = positions->lower_bound(value);
if(it != positions->begin()){
set<int>::iterator prev = it;
prev--;
in_t((*it) - (*prev));
}
if(it != positions->end()){
set<int>::iterator next = it;
next++;
if(next != positions->end()){
in_t((*next) - (*it));
}
}
if(it != positions->begin() && it != positions->end()){
set<int>::iterator prev = it, next = it;
prev--, next++;
if(next != positions->end()){
er_t((*next) - (*prev));
}
}
}
int get_less(int key){
return (int)t->order_of_key(mp(key, -1));
}
void clear(){
t->clear();
cnt->clear();
positions->clear();
}
};
int islands(data t, int ln){
return (int)(t.positions->size() - t.get_less(ln + 1));
}
void dfs(int v, int ln, data& ord){
if(t[v].next.empty()){
ord.insert(szs - ln);
}
data cur;
for(map<char, int>::iterator it = t[v].next.begin(); it != t[v].next.end(); it++){
int u = it->Y;
dfs(u, ln + leng(u), cur);
if(cur.positions->size() > ord.positions->size())
swap(cur, ord);
// int ress = cur.positions->size() + ord.positions->size();
for(set<int>::iterator jt = cur.positions->begin(); jt != cur.positions->end(); jt++){
ord.insert(*jt);
}
// assert(ress == ord.positions->size());
cur.clear();
}
// if(t[v].par == 0 && s[t[v].l] == 'a'){
// cerr << v << " " << ord.positions->size() << endl;
// }
if(ln > 0){
int ansL = -1, ansR = -1;
{
int lf = ln - leng(v) + 1, rg = ln;
while(rg - lf > 1){
int mid = (lf + rg) >> 1;
if(islands(ord, mid) > K)
lf = mid;
else
rg = mid;
}
for(int x = lf; x <= rg; x++){
if(islands(ord, x) == K){
ansL = x;
break;
}
}
}
{
int lf = ln - leng(v) + 1, rg = ln;
while(rg - lf > 1){
int mid = (lf + rg) >> 1;
if(islands(ord, mid) < K)
rg = mid;
else
lf = mid;
}
for(int x = rg; x >= lf; --x){
if(islands(ord, x) == K){
ansR = x;
break;
}
}
}
if(ansL != -1){
result += ansR - ansL + 1;
// cerr << "ln=" << ln << " " << t[v].l + 1 << " " << t[v].r << endl;
}
}
}
#include <sys/resource.h>
void init_stack(){
const rlim_t kStackSize = 512 * 1024 * 1024;
struct rlimit rl;
int result;
result = getrlimit(RLIMIT_STACK, &rl);
if (result == 0)
{
if (rl.rlim_cur < kStackSize)
{
rl.rlim_cur = kStackSize;
result = setrlimit(RLIMIT_STACK, &rl);
if (result != 0)
{
fprintf(stderr, "setrlimit returned result = %d\n", result);
}
}
}
}
int main() {
#ifdef ssu1
assert(freopen("input.txt", "rt", stdin));
#endif
init_stack();
gets(s);
szs = (int)strlen(s);
s[szs++] = '$';
make_tree();
assert(scanf("%d", &K) == 1);
data ord;
dfs(0, 0, ord);
if(K == 1){
result -= szs;
}
cout << result << endl;
#ifdef ssu1
cerr << "\nTime = " << double(clock()) / CLOCKS_PER_SEC << endl;
#endif
return 0;
}
;;;;;;;;;;;;;;;;;;;;;;;
Determining DNA Health
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <cstring>
#include <iomanip>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
const int N = 100002, MAXSIZE = 2000002;
int n, sz, trie[MAXSIZE][26], ends_here[MAXSIZE], sufflink[MAXSIZE];
char str[MAXSIZE];
int ticks, pattern_node[N], lo[MAXSIZE], hi[MAXSIZE];
vector<int> adj[MAXSIZE], query_nodes[N], subtract[N], add[N];
ll arr[N], ans[N];
void insert_pattern_string(int idx){
int curr = 0;
for(int i=0;str[i]!='\0';i++){
int dir = str[i] - 'a';
if(trie[curr][dir] == -1)
trie[curr][dir] = ++sz;
curr = trie[curr][dir];
}
pattern_node[idx] = curr;
}
void insert_query_string(int idx){
int curr = 0;
for(int i=0;str[i]!='\0';i++){
int dir = str[i] - 'a';
if(trie[curr][dir] == -1)
trie[curr][dir] = ++sz;
curr = trie[curr][dir];
query_nodes[idx].pb(curr);
}
}
void bfs(){
sufflink[0] = 0;
queue<int> qq;
for(int i=0;i<26;i++)
if(trie[0][i] != -1){
sufflink[trie[0][i]] = 0;
qq.push(trie[0][i]);
adj[0].pb(trie[0][i]);
// cout<<"added edge from 0 to "<<trie[0][i]<<endl;
}
while(!qq.empty()){
int v = qq.front();
qq.pop();
for(int dir=0;dir<26;dir++){
int vv = trie[v][dir];
if(vv == -1) continue;
int j = sufflink[v];
while(j > 0 && trie[j][dir] == -1) j = sufflink[j];
if(trie[j][dir] != -1) sufflink[vv] = trie[j][dir];
if(sufflink[vv] != vv){
//create the new tree
adj[sufflink[vv]].pb(vv);
}
qq.push(vv);
}
}
}
int next_state(int v, int dir){
int j = v;
while(j > 0 && trie[j][dir] == -1) j = sufflink[j];
if(trie[j][dir] != -1) j = trie[j][dir];
return j;
}
void dfs(int v){
lo[v] = ++ticks;
for(int i=0;i<(int)adj[v].size();i++){
dfs(adj[v][i]);
}
hi[v] = ticks;
}
ll BIT[MAXSIZE];
void update(int idx, ll val){
while(idx <= ticks){
BIT[idx] += val;
idx += idx & (-idx);
}
}
ll query(int idx){
ll ans = 0;
while(idx){
ans += BIT[idx];
idx -= idx & (-idx);
}
return ans;
}
int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
scanf("%d", &n);
sz = 0;
memset(trie, -1, sizeof(trie));
for(int i=1;i<=n;i++){
scanf("%s", str);
insert_pattern_string(i);
}
for(int i=1;i<=n;i++){
scanf("%lld", &arr[i]);
}
int q;
scanf("%d", &q);
for(int i=1;i<=q;i++){
int l, r;
scanf("%d%d%s", &l, &r, str);
l++; r++;
insert_query_string(i);
subtract[l-1].pb(i);
add[r].pb(i);
}
//create suffix links
bfs();
ticks = 0;
//create the new tree
dfs(0);
for(int i=1;i<=n;i++){
//"activate" this gene by executing range addition
int node_in_trie = pattern_node[i];
update(lo[node_in_trie], arr[i]);
update(hi[node_in_trie]+1, -arr[i]);
//subtract the value from all queries whose left endpoint is L+1
for(auto it : subtract[i]){
int idx = it;
for(auto node_in_trie : query_nodes[idx])
ans[idx] -= query(lo[node_in_trie]);
}
//add the value to all queries whose right endpoint is R
for(auto it : add[i]){
int idx = it;
for(auto node_in_trie : query_nodes[idx])
ans[idx] += query(lo[node_in_trie]);
}
}
cout<<*min_element(ans+1, ans+q+1)<<" "<<*max_element(ans+1, ans+q+1);
return 0;
}
;;;;;;;;;;;;;;;;;;;;;;;;
Insertion Sort Advanced Analysis
#include<iostream>
#include<cstdio>
using namespace std;
long long ans=0;
void mergei(int a[],int i,int j)
{
int ni=((i+j)/2)+1,nj=j+1;
int s=i;
int * arr = new int [j-i+1];
j=ni;
int k=0;
while(i<ni && j<nj)
{
if(a[i]<=a[j])
{
arr[k]=a[i];
i++;
}
else
{
arr[k]=a[j];
ans+=(ni-i);
j++;
}
k++;
}
for(;i<ni;i++,k++)
arr[k]=a[i];
for(;j<nj;j++,k++)
arr[k]=a[j];
for(k=0;s<nj;s++,k++)
a[s]=arr[k];
delete [] arr;
}
void m_sort(int a[],int i,int j)
{
if(i<j)
{
m_sort(a,i,(i+j)/2);
m_sort(a,((i+j)/2)+1,j);
mergei(a,i,j);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
ans=0;
scanf("%d",&n);
int * a = new int[n];
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
m_sort(a,0,n-1);
cout<<ans<<endl;
}
return 0;
}
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
TEST -32
Pseudo-Isomorphic Substrings
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define next Next
#define maxn 100005
#define sigma 26
int order[maxn][sigma],q,o2[maxn][sigma],rmq2[20][maxn];
int it,n,w1[256],w2[256],r1[256],r2[256],i,suf[maxn],L,R,wn,w[maxn],j,place[maxn],h,sorted[maxn],high,in_list[maxn],last[sigma],next[maxn][sigma],Log[maxn],orig[maxn],limiter[maxn],suf2[maxn],tt,sufplace[maxn];
pair<int,int>srt[sigma];
int rmq[20][maxn];
long long sumlcp;
char s[maxn];
struct Node{
int a;
Node(){}
Node(int a):a(a){}
bool operator<(const Node&you)const{return sufplace[a]<sufplace[you.a];}
};
set<Node>Suffixes;
set<Node>::iterator It,before,after;
int min(int x,int y){
return (((y-x)>>(32-1))&(x^y))^x;
}
int fastlcp(int x,int y){
x=in_list[x];
y=in_list[y];
if(x>y)swap(x,y);
return min(rmq[Log[y-x]][x],rmq[Log[y-x]][y-(1<<Log[y-x])]);
}
int lim,k1;
int suflcp(int x,int y){
lim=n-max(x,y)+1;
if(x==y)return lim;
for(j=0;j<sigma;j++){
if(next[x][order[x][j]]-x!=next[y][order[y][j]]-y)lim=min(lim,min(next[x][order[x][j]]-x,next[y][order[y][j]]-y));else{
q=fastlcp(place[next[x][order[x][j]]],place[next[y][order[y][j]]]);
lim=min(lim,next[orig[place[next[x][order[x][j]]]+q]+1][order[x][j]]-x);
lim=min(lim,next[orig[place[next[y][order[y][j]]]+q]+1][order[y][j]]-y);
}
}
return lim;
}
inline bool sufcmp(int i,int j){
k1=suflcp(i,j);
if(k1==n-max(i,j)+1)return (i>j);else
return (o2[i][s[i+k1]-'a']<o2[j][s[j+k1]-'a'])||(o2[i][s[i+k1]-'a']==o2[j][s[j+k1]-'a']&&i>j);
}
int an,a[maxn],classes,C[20][maxn];
struct sre{
int pF,pS,idx;
sre(){}
inline sre(int pF,int pS,int idx):pF(pF),pS(pS),idx(idx){}
inline bool operator<(const sre&a)const{
return(pF<a.pF||(pF==a.pF&&pS<a.pS));
}
}sr[maxn];
int p[maxn],cnt[maxn],p2[maxn],m1,m2;
void first_iter(){
int i;
for(i=1;i<=an;i++)++cnt[a[i]];
for(i=1;i<=an;i++)cnt[i]+=cnt[i-1];
for(i=1;i<=an;i++)p[cnt[a[i]]--]=i;
classes=0;
for(i=1;i<=an;i++){
if(i==1||a[p[i]]!=a[p[i-1]])++classes;
C[0][p[i]]=classes;
}
}
inline int fu(int t){
while(t>an)t-=an;
return t;
}
void next_iter(int h){
int i;
for(i=1;i<=an;i++){
p2[i]=p[i]-(1<<(h-1));
while(p2[i]<1)p2[i]+=an;
}
for(i=0;i<=classes;i++)cnt[i]=0;
for(i=1;i<=an;i++)++cnt[C[h-1][p2[i]]];
for(i=1;i<=classes;i++)cnt[i]+=cnt[i-1];
for(i=an;i;i--)p[cnt[C[h-1][p2[i]]]--]=p2[i];
C[h][p[1]]=classes=1;
sorted[1]=p[1];
for(i=2;i<=an;i++){
m1=fu(p[i]+(1<<(h-1))),m2=fu(p[i-1]+(1<<(h-1)));
if(C[h-1][p[i]]!=C[h-1][p[i-1]]||C[h-1][m1]!=C[h-1][m2])++classes;
C[h][p[i]]=classes;
sorted[i]=p[i];
}
}
int lcp_log(int x,int y){
int rt=0;
for(int i=high;i+1;i--)if(C[i][x]==C[i][y]){
rt+=(1<<i);
x+=(1<<i);
y+=(1<<i);
}
return rt;
}
int b[maxn],bn;
void build_sa(){
for(j=0;j<26;j++){
wn=0;
for(i=1;i<=n;i++)if(s[i]=='a'+j)w[++wn]=i;
w[wn+1]=-1;
for(i=1;i<=wn;i++){
a[++an]=w[i+1]-w[i];
orig[an]=w[i];
place[w[i]]=an;
limiter[w[i]]=wn-i+1;
}
}
a[++an]=-n*10;
for(i=1;i<=an;i++)b[i]=a[i];
sort(b+1,b+an+1);
bn=unique(b+1,b+an+1)-(b+1);
for(i=1;i<=an;i++)a[i]=lower_bound(b+1,b+bn+1,a[i])-b;
first_iter();
for(h=1;(1<<h)<=n;h++){
next_iter(h);
high=h;
}
for(i=2;i<=an;i++)Log[i]=1+Log[i/2];
for(i=1;i<=an;i++){
if(i<an)rmq[0][i]=lcp_log(sorted[i],sorted[i+1]);
in_list[sorted[i]]=i;
}
for(i=1;i<=high;i++)for(j=1;j<=an-(1<<i)+1;j++)rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
void sort2(int l,int r){
if(l<r){
int mid=(l+r)/2,j;
int hL=l,hR=mid+1;
sort2(l,mid);
sort2(mid+1,r);
for(j=l;j<=r;j++)if(hR==r+1||(hL!=mid+1&&sufcmp(suf[hL],suf[hR])))suf2[j]=suf[hL++];else suf2[j]=suf[hR++];
for(j=l;j<=r;j++)suf[j]=suf2[j];
}
}
void addLCP(int x,int y,int z){
x=sufplace[x];
y=sufplace[y];
if(x>y)swap(x,y);
--y;
int cc=min(rmq2[Log[y-x+1]][x],rmq2[Log[y-x+1]][y-(1<<Log[y-x+1])+1]);
sumlcp+=cc*z;
}
int main (int argc, char * const argv[]) {
gets(s);
n=strlen(s);
reverse(s,s+n);
for(i=n;i;i--)s[i]=s[i-1];
for(i=1;i<=n;i++)suf[i]=i;
build_sa();
for(i=0;i<sigma;i++){
last[i]=n+n+1;
next[n+1][i]=n+n+1;
}
for(i=n;i;i--){
last[s[i]-'a']=i;
for(j=0;j<sigma;j++)srt[j]=make_pair(last[j],j);
sort(srt,srt+sigma);
for(j=0;j<sigma;j++){
order[i][j]=srt[j].second;
o2[i][srt[j].second]=j;
if(srt[j].first>n)o2[i][srt[j].second]=sigma;
next[i][j]=last[j];
}
}
sort2(1,n);
for(i=1;i<=n;i++)sufplace[suf[i]]=i;
for(i=1;i<n;i++)rmq2[0][i]=suflcp(suf[i],suf[i+1]);
for(i=1;i<=Log[n];i++)for(j=1;j<=n-(1<<i)+1;j++)rmq2[i][j]=min(rmq2[i-1][j],rmq2[i-1][j+(1<<(i-1))]);
for(i=n;i;i--){
++tt;
Suffixes.insert(Node(i));
It=Suffixes.find(Node(i));
if(It!=Suffixes.begin()){
before=It;--before;
addLCP(before->a,It->a,1);
after=It;++after;
if(after!=Suffixes.end()){
addLCP(It->a,after->a,1);
addLCP(before->a,after->a,-1);
}
}else{
after=It;++after;
if(after!=Suffixes.end())addLCP(It->a,after->a,1);
}
printf("%lld\n",tt*(tt+1LL)/2-sumlcp);
}
return 0;
}
How Many Substrings?
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<vector>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)((x).size()))
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)j;i>=(int)k;i--)
using namespace std;
typedef long long LL;
typedef double DB;
const DB pi=acos(-1.0);
const int N=100005;
int go[N<<1][26],fail[N<<1],len[N<<1],tot,last;
int n;
int cnt=0;
namespace seg{
int tag[N<<2];
LL sum[N<<2];
inline void Tag(int me,int l,int r,int v){
tag[me]+=v;
sum[me]+=(r-l+1)*1ll*v;
}
inline void down(int me,int l,int r){
if(tag[me]==0)return;
int mid=(l+r)>>1;
Tag(me<<1,l,mid,tag[me]);
Tag(me<<1|1,mid+1,r,tag[me]);
tag[me]=0;
}
void add(int me,int l,int r,int x,int y,int v){
//if(l==1&&r==n)printf("add %d %d %d\n",x,y,v);
if(l^r)down(me,l,r);
if(x<=l&&r<=y){
Tag(me,l,r,v);
return;
}
int mid=(l+r)>>1;
if(x<=mid)add(me<<1,l,mid,x,y,v);
if(y>mid)add(me<<1|1,mid+1,r,x,y,v);
sum[me]=sum[me<<1]+sum[me<<1|1];
}
LL ask(int me,int l,int r,int x,int y){
if(l^r)down(me,l,r);
if(x<=l&&r<=y)return sum[me];
int mid=(l+r)>>1;
LL ret=0;
if(x<=mid)ret+=ask(me<<1,l,mid,x,y);
if(y>mid)ret+=ask(me<<1|1,mid+1,r,x,y);
return ret;
}
void Do(int pre,int now,int L,int R){
if(L>R)return;
++cnt;
//printf("_%d %d %d %d\n",pre,now,L,R);
if(pre)add(1,1,n,pre-R+1,pre-L+1,-1);
add(1,1,n,now-R+1,now-L+1,1);
}
};
namespace lct{
int l[N<<2],r[N<<2],fa[N<<2];
int last[N<<2];
inline bool top(int x){return (!fa[x])||(l[fa[x]]!=x&&r[fa[x]]!=x);}
inline void left(int x){
int y=fa[x];int z=fa[y];
r[y]=l[x];if(l[x])fa[l[x]]=y;
fa[x]=z;if(l[z]==y)l[z]=x;else if(r[z]==y)r[z]=x;
l[x]=y;fa[y]=x;
}
inline void right(int x){
int y=fa[x];int z=fa[y];
l[y]=r[x];if(r[x])fa[r[x]]=y;
fa[x]=z;if(l[z]==y)l[z]=x;else if(r[z]==y)r[z]=x;
r[x]=y;fa[y]=x;
}
inline void down(int x){
if(l[x])last[l[x]]=last[x];
if(r[x])last[r[x]]=last[x];
}
int q[N<<2];
inline void splay(int x){
q[q[0]=1]=x;
for(int k=x;!top(k);k=fa[k])q[++q[0]]=fa[k];
per(i,q[0],1)down(q[i]);
while(!top(x)){
int y=fa[x];int z=fa[y];
if(top(y)){
if(l[y]==x)right(x);else left(x);
}
else{
if(r[z]==y){
if(r[y]==x)left(y),left(x);
else right(x),left(x);
}
else{
if(l[y]==x)right(y),right(x);
else left(x),right(x);
}
}
}
}
void Access(int x,int cov){
int y=0;
for(;x;y=x,x=fa[x]){
splay(x);
down(x);
r[x]=0;
int L,R;
int z=x;
while(l[z])z=l[z];
L=len[fail[z]]+1;
splay(z);splay(x);
z=x;
while(r[z])z=r[z];
R=len[z];
splay(z);splay(x);
seg::Do(last[x],cov,L,R);
r[x]=y;
last[x]=cov;
}
}
void SetFa(int x,int y,int po){
fa[x]=y;
Access(x,po);
}
void split(int x,int y,int d){
splay(y);
down(y);
r[y]=0;
fa[d]=y;
splay(x);
fa[x]=d;
last[d]=last[x];
}
};
namespace sam{
void init(){
tot=last=1;
}
void expended(int x,int po){
int gt=++tot;len[gt]=len[last]+1;int p=last;last=tot;
for(;p&&(!go[p][x]);p=fail[p])go[p][x]=gt;
if(!p){
fail[gt]=1;
lct::SetFa(gt,1,po);
return;
}
int xx=go[p][x];
if(len[xx]==len[p]+1){
fail[gt]=xx;
lct::SetFa(gt,xx,po);
return;
}
int tt=++tot;
len[tt]=len[p]+1;
fail[tt]=fail[xx];
int dt=fail[xx];
fail[xx]=fail[gt]=tt;
lct::split(xx,dt,tt);
lct::SetFa(gt,tt,po);
rep(i,0,25)go[tt][i]=go[xx][i];
for(;p&&(go[p][x]==xx);p=fail[p])go[p][x]=tt;
}
};
int Q;
char str[N];
int qL[N];
vector<int>que[N];
LL ans[N];
void Main(){
rep(i,1,n){
sam::expended(str[i]-'a',i);
rep(j,0,que[i].size()-1){
int id=que[i][j];
ans[id]=seg::ask(1,1,n,qL[id],n);
}
}
}
void init(){
scanf("%d%d",&n,&Q);
scanf("%s",str+1);
rep(i,1,Q){
int r;scanf("%d%d",&qL[i],&r);
qL[i]++;r++;
que[r].pb(i);
}
sam::init();
}
void Output(){
rep(i,1,Q)printf("%lld\n",ans[i]);
}
int main(){
init();
Main();
Output();
return 0;
}
Cards Permutation
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000*1000*1000+7;
vector<ll> fact;
int N, K;
vector<int> P;
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4*N, 0);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = tree[2*n] + tree[2*n + 1];
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return L + R;
}
} bit, sub;
int main() {
fact.resize(500010);
fact[0] = 1;
for(int i = 1; i < 500010; i++) {
fact[i] = fact[i - 1] * i % mod;
}
scanf("%d", &N);
K = 0;
P.resize(N);
sub.init();
for(int i = 0; i < N; i++) {
scanf("%d", &P[i]);
P[i]--;
if(P[i] == -1) K++;
sub.upd(i, 1, 0, N - 1, 1);
}
ll sum = 1LL * N * (N - 1) / 2;
for(int i = 0; i < N; i++) {
if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
}
sum = (sum % mod + mod) % mod;
bit.init();
ll ans = 0;
ll tmp = 0;
int cnt = 0;
for(int i = 0; i < N; i++) {
if(P[i] == -1) {
ll a = sum * fact[K - 1] % mod;
ll b = tmp * fact[K - 1] % mod;
ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) * fact[K - 2] % mod * cnt % mod;
ans += (a - b - c) * fact[N - i - 1] % mod, ans = (ans % mod + mod) % mod;
cnt++;
}
else {
bit.upd(P[i], 1, 0, N - 1, 1);
tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
tmp %= mod;
ll a = fact[K] * P[i] % mod;
ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
ll c = K == 0? 0 : fact[K - 1] * sub.quer(0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;
ans += (a - b - c) * fact[N - 1 - i] % mod, ans = (ans % mod + mod) % mod;
}
}
cout << (ans + fact[K]) % mod;
}
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
test -31
Gridland Metro
#include <bits/stdc++.h>
#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)
#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n, m, k, p;
map<int, int> M;
vector<PII> vec[1005];
LL ans;
int main(){
scanf("%d %d %d", &n, &m, &k);
ans = 1LL * n * m;
FI(i, 1, k){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(M.count(a) == 0) M[a] = ++p;
vec[M[a]].push_back(mp(b, c));
}
FI(i, 1, p){
sort(vec[i].begin(), vec[i].end());
int pv = 0;
FI(j, 0, (int)vec[i].size() - 1){
PII c = vec[i][j];
if(c.fi > pv) ans += c.fi - 1 - pv;
pv = max(pv, c.se);
}
ans -= pv;
}
printf("%lld\n", ans);
return 0;
}
]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
Sherlock and Divisors
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while( t-- ) {
long long n,i,j,k,l;
scanf("%lld",&n);
long long ans =0;
for(i=1;i*i<=n;i++){
if(n%i==0){
if(n/i!=i){
k = n/i;
if(!(k&1))
ans++;
}
if(!(i&1))
ans++;
}
}
printf("%lld\n",ans);
}
return 0;
}
Primitive Problem
In python
import math
def modexp_lr(a, b, n):
r = 1
for bit in reversed(_bits_of_n(b)):
r = r * r % n
if bit == 1:
r = r * a % n
return r
def _bits_of_n(n):
bits = []
while n:
bits.append(n % 2)
n /= 2
return bits
def p_factors(num, num_c, p_to_test, prime_factors):
while num_c % 2 == 0:
num_c /= 2
if 2 in prime_factors:
prime_factors[2] += 1
else:
prime_factors[2] = 1
for x in xrange(3, int(math.sqrt(num_c))+1,2):
while num_c % x == 0:
if x in prime_factors:
prime_factors[x] += 1
else:
prime_factors[x] = 1
num_c /= x
if num_c > 2:
prime_factors[num_c] = 1
p_to_test = [(num-1)/x for x in prime_factors]
return p_to_test, prime_factors
def main():
num = input()
num_c = num-1
p_to_test = []
prime_factors = {}
p_to_test,prime_factors = p_factors(num, num_c, p_to_test, prime_factors)
num_of_p_roots = 1
for key,value in prime_factors.iteritems():
num_of_p_roots *= (((key ** value)/key) * ((key-1)))
for x in xrange(2, num):
flag = 0
for y in p_to_test:
if modexp_lr(x,y,num) != 1:
flag += 1
if flag == len(p_to_test):
print x, num_of_p_roots
break
main()
Minimum Multiple
IN HASKEL
import Control.Monad
import Control.Monad.State
-- import Text.Show.Pretty (ppShow)
-- pprint x = putStrLn $ ppShow x
data SegTree = NULL
| SegTree {li :: Int, ri :: Int, val :: Integer
,left :: SegTree ,right :: SegTree}
deriving Show
mm = 10^9+7
-- lcm' a b = (lcm a b) `rem` mm
build :: Int -> Int -> [Integer] -> SegTree
build l r ns =
let m = (l + r) `div` 2
(lns, rns) = splitAt (m - l + 1) ns
lt = if l == r then NULL else build l m lns
rt = if l == r then NULL else build (m+1) r rns
v = if l == r then head ns else lcm (val lt) (val rt)
in SegTree l r v lt rt
query :: SegTree -> Int -> Int -> Integer
query (SegTree l r v lt rt) i j
| i == l && j == r = v
| j <= m = query lt i j
| m < i = query rt i j
| otherwise = lcm (query lt i m) (query rt (m+1) j)
where m = (l + r) `div` 2
query NULL _ _ = error "bad weather"
update :: SegTree -> Int -> Int -> SegTree
update (SegTree l r v lt rt) i x =
let m = (l + r) `div` 2
lt' = if i <= m then update lt i x else lt
rt' = if m < i then update rt i x else rt
in if l == r
then SegTree l r (v * fromIntegral x) NULL NULL
else SegTree l r (lcm (val lt') (val rt')) lt' rt'
type Env = StateT SegTree IO ()
swap :: [String] -> Env
swap [] = return ()
swap (s:ss) = do
tree <- get
if tp == "Q"
then liftIO . print . (`rem` mm) $ query tree i' j'
else do put $ update tree i' j'
-- liftIO . pprint =<< get
-- tree' <- get
-- liftIO . print $ query tree' 3 4
swap ss
where [tp, i, j] = words s
i' = read i
j' = read j
main :: IO ()
main = do
n <- readLn :: IO Int
ns <- return . map read . words =<< getLine
let tree = build 0 (n-1) ns
q <- readLn :: IO Int
qs <- replicateM q getLine
runStateT (swap qs) tree
return ()
-------------------------------===========================----------------------------------
test -30
Maximum Subarray Sum
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve()
{
ll N,M;
ll x,prefix=0,maxim=0;
cin>>N>>M;
set<ll> S;
S.insert(0);
for(int i=1;i<=N;i++){
cin>>x;
prefix = (prefix + x)%M;
maxim = max(maxim,prefix);
set<ll>::iterator it = S.lower_bound(prefix+1);
if( it != S.end() ){
maxim = max(maxim,prefix - (*it) + M );
}
S.insert(prefix);
}
cout<<maxim<<endl;
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Maximizing Mission Points
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const long long INF = 1e15;
long long tree[MAXN * 4];
void makeTree() {
for (int i = 1; i < MAXN * 4; ++i) {
tree[i] = -INF;
}
}
void update(int x, long long val, int u = 1, int l = 1, int r = MAXN) {
if (l == r) {
tree[u] = val;
return;
}
int m = (l + r) / 2;
if (x <= m) {
update(x, val, 2 * u, l, m);
}
else {
update(x, val, 2 * u + 1, m + 1, r);
}
tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
long long query(int x, int y, int u = 1, int l = 1, int r = MAXN) {
if (x > r or y < l) {
return -INF;
}
if (x <= l and r <= y) {
return tree[u];
}
int m = (l + r) / 2;
return max(query(x, y, 2 * u, l, m), query(x, y, 2 * u + 1, m + 1, r));
}
struct Point {
int x, y, z, w;
long long dp;
bool operator < (const Point &o) const {
return z < o.z;
}
};
Point p[MAXN + 1];
long long DP[MAXN + 1];
int X_LIM, Y_LIM;
void merge(int l, int r) {
int m = (l + r) / 2;
vector<pair<int, int> > left;
vector<pair<int, int> > right;
for (int i = l; i <= m; ++i) {
left.push_back({p[i].x, p[i].z});
}
for (int i = m + 1; i <= r; ++i) {
right.push_back({p[i].x, p[i].z});
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int left_l = 0;
int left_r = -1;
for (auto u : right) {
int i = u.second;
int x = u.first;
while (left_r + 1 < left.size() and left[left_r + 1].first - x <= X_LIM) {
++left_r;
int who = left[left_r].second;
update(p[who].y, p[who].dp);
}
while (left_l < left.size() and x - left[left_l].first > X_LIM) {
int who = left[left_l].second;
update(p[who].y, -INF);
++left_l;
}
int yLow = max(1, p[i].y - Y_LIM);
int yHigh = min(MAXN, p[i].y + Y_LIM);
p[i].dp = max(p[i].dp, p[i].w + query(yLow, yHigh));
}
while (left_l <= left_r) {
int who = left[left_l].second;
update(p[who].y, -INF);
++left_l;
}
}
void solve(int l, int r) {
if (l == r) {
p[l].dp = max(p[l].dp, (long long)p[l].w);
return;
}
int m = (l + r) / 2;
solve(l, m);
merge(l, r);
solve(m + 1, r);
}
int main() {
makeTree();
int n;
scanf("%d %d %d", &n, &X_LIM, &Y_LIM);
for (int i = 0; i < n; ++i) {
scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].z, &p[i].w);
p[i].dp = -INF;
}
sort(p, p + n);
for (int i = 0; i < n; ++i) {
p[i].z = i;
}
solve(0, n - 1);
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, p[i].dp);
}
printf("%lld\n", ans);
}
Bike Racers
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MAXN = 510;
ll n,m,k;
ll a[MAXN][2],b[MAXN][2];
struct node{
ll u,v;
ll dis;
bool operator<(const node& r)const{
return dis<r.dis;
}
}data[MAXN*MAXN];
ll uN,vN;
ll g[MAXN][MAXN];
ll linker[MAXN];
bool used[MAXN];
bool dfs(ll u)
{
ll v;
for(v=0;v<vN;v++)
if(g[u][v]&&!used[v])
{
used[v]=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
return false;
}
ll hungary()
{
ll res=0;
ll u;
memset(linker,-1,sizeof(linker));
for(u=0;u<uN;u++)
{
memset(used,0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
ll calc(ll x){
memset(g,0,sizeof(g));
for(ll i=0;i<=x;i++){
ll x = data[i].u;
ll y = data[i].v;
g[x][y] = 1;
}
return hungary();
}
ll solve(){
ll cnt = 0;
uN = n;
vN = m;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
data[cnt].u=i;
data[cnt].v=j;
data[cnt].dis = (a[i][0]-b[j][0])*(a[i][0]-b[j][0])+(a[i][1]-b[j][1])*(a[i][1]-b[j][1]);
cnt++;
}
}
sort(data,data+cnt);
ll lb=-1,ub=cnt;
while(ub-lb>1){
ll mid = (ub+lb)/2;
if(calc(mid)>=k){
ub = mid;
}else{
lb = mid;
}
}
return data[ub].dis;
}
int main() {
ios::sync_with_stdio(0);
cin>>n>>m>>k;
for(ll i=0;i<n;i++)cin>>a[i][0]>>a[i][1];
for(ll i=0;i<m;i++)cin>>b[i][0]>>b[i][1];
ll ans = solve();
cout<<ans<<endl;
return 0;
}
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Checkers
#include <iostream>
#include <vector>
#include <cctype>
#include <string>
#include <sstream>
using namespace std;
struct Piece
{
int r;
int c;
bool color;
};
struct Move
{
int r0;
int c0;
int rf;
int cf;
};
struct Board
{
vector<string> board;
bool turn;
};
struct MoveScore
{
Move m;
int score;
};
vector<Move> generateMoves(Board b)
{
vector<Move> allmvs;
bool turn = b.turn;
char p = 'b';
char other = 'w';
int rdir = 1;
if (turn)
{
other = 'b';
p = 'w';
rdir = -1;
}
for (int r = 0; r < 8; r++)
for (int c = 0; c < 8; c++)
{
if (b.board[r][c] == p || b.board[r][c] == toupper(p))
{
int rf = r + rdir;
if (rf >= 0 && rf < 8) //move forwards
{
if (c + 1 < 8)
{
char dest = b.board[rf][c+1];
if (dest == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rf; m.cf = c + 1;
allmvs.push_back(m);
}
else if (tolower(dest) == other) //capture
{
int rcapt = rf + rdir;
if (rcapt >= 0 && rcapt < 8)
{
if (c + 2 < 8)
{
if (b.board[rcapt][c+2] == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rcapt; m.cf = c + 2;
allmvs.push_back(m);
}
}
}
}
}
if (c - 1 >= 0)
{
char dest = b.board[rf][c-1];
if (dest == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rf; m.cf = c - 1;
allmvs.push_back(m);
}
else if (tolower(dest) == other) //capture
{
int rcapt = rf + rdir;
if (rcapt >= 0 && rcapt < 8)
{
if (c - 2 >= 0)
{
if (b.board[rcapt][c-2] == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rcapt; m.cf = c - 2;
allmvs.push_back(m);
}
}
}
}
}
}
int rrf = r - rdir;
if (b.board[r][c] == toupper(p))
{
if (rrf >= 0 && rrf < 8) //move backwards if king
{
if (c + 1 < 8)
{
char dest = b.board[rrf][c+1];
if (dest == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rrf; m.cf = c + 1;
allmvs.push_back(m);
}
else if (tolower(dest) == other) //capture
{
int rcapt = rrf - rdir;
if (rcapt >= 0 && rcapt < 8)
{
if (c + 2 < 8)
{
if (b.board[rcapt][c+2] == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rcapt; m.cf = c + 2;
allmvs.push_back(m);
}
}
}
}
}
if (c - 1 >= 0)
{
char dest = b.board[rrf][c-1];
if (dest == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rrf; m.cf = c - 1;
allmvs.push_back(m);
}
else if (tolower(dest) == other) //capture
{
int rcapt = rrf - rdir;
if (rcapt >= 0 && rcapt < 8)
{
if (c - 2 >= 0)
{
if (b.board[rcapt][c-2] == '_')
{
Move m;
m.r0 = r; m.c0 = c; m.rf = rcapt; m.cf = c - 2;
allmvs.push_back(m);
}
}
}
}
}
}
}
}
}
vector<Move> captures;
for (Move m : allmvs)
if (abs(m.rf - m.r0) == 2)
captures.push_back(m);
if (captures.size() > 0)
return captures;
return allmvs;
}
Board makeMove(Board b, Move m)
{
bool capture = abs(m.rf - m.r0) == 2;
b.board[m.rf][m.cf] = b.board[m.r0][m.c0];
if (!b.turn)
{
if (m.rf == 7)
b.board[m.rf][m.cf] = 'B';
}
else
{
if (m.rf == 0)
b.board[m.rf][m.cf] = 'W';
}
b.board[m.r0][m.c0] = '_';
if (capture)
{
b.board[(m.rf + m.r0)/2][(m.cf + m.c0)/2] = '_';
}
return b;
}
int staticEval(Board b)
{
int score = 0;
char p = 'b';
char other = 'w';
int rdir = -1;
int home = 0;
int oks = 500;
int os = 300;
int tks = 500;
int ts = 300;
if (b.turn)
{
p = 'w';
rdir = 1;
other = 'b';
home = 7;
}
int rcount = 0;
int tcount = 0;
for (int r = 0; r < 8; r++)
for (int c = 0; c < 8; c++)
{
if (tolower(b.board[r][c]) == p)
rcount++;
else if (tolower(b.board[r][c]) == other)
tcount++;
}
int setting = 0; //0 is normal, 1 is aggressive endgame, 2 is passive endgame
if (rcount > tcount && tcount < 3)
setting = 1;
else if (tcount > rcount && rcount < 3)
setting = 2;
for (int r = 0; r < 8; r++)
for (int c = 0; c < 8; c++)
{
bool front2 = ((r - rdir*2) >= 0) && ((r - rdir*2) < 8);
bool behind2 = ((r + rdir*2) >= 0) && ((r + rdir*2) < 8);
bool left2 = (c - 2 >= 0);
bool right2 = (c + 2 < 8);
if (b.board[r][c] == toupper(p))
{
score = score + oks;
}
else if (b.board[r][c] == toupper(other))
{
score = score - tks;
if (setting == 1)
{
if (front2)
{
if (left2 && tolower(b.board[r - rdir*2][c - 2]) == p)
score = score + 40;
if (right2 && tolower(b.board[r - rdir*2][c + 2]) == p)
score = score + 40;
if (tolower(b.board[r - rdir*2][c]) == p)
score = score + 40;
}
if (behind2)
{
if (left2 && b.board[r + rdir*2][c - 2] == toupper(p))
score = score + 30;
if (right2 && b.board[r + rdir*2][c + 2] == toupper(p))
score = score + 30;
if (b.board[r + rdir*2][c] == toupper(p))
score = score + 30;
}
if (left2 && b.board[r][c-2] == toupper(p))
score = score + 30;
if (right2 && b.board[r][c+2] == toupper(p))
score = score + 30;
}
}
else if (b.board[r][c] == p)
{
if (!b.turn && c == 0)
score++; //small adjustment to try to force opening towards edge
score = score + os - (home-r)*(home-r);
}
else if (b.board[r][c] == other)
{
score = score - ts + (7-home-r)*(7-home-r);
if (setting == 1)
{
if (front2)
{
if (left2 && tolower(b.board[r - rdir*2][c - 2]) == p)
score = score + 40;
if (right2 && tolower(b.board[r - rdir*2][c + 2]) == p)
score = score + 40;
if (tolower(b.board[r - rdir*2][c]) == p)
score = score + 40;
}
if (behind2)
{
if (left2 && b.board[r + rdir*2][c - 2] == toupper(p))
score = score + 30;
if (right2 && b.board[r + rdir*2][c + 2] == toupper(p))
score = score + 30;
if (b.board[r + rdir*2][c] == toupper(p))
score = score + 30;
}
if (left2 && tolower(b.board[r][c-2]) == p)
score = score + 30;
if (right2 && tolower(b.board[r][c+2]) == p)
score = score + 30;
}
}
else //'_'
{
if (r - 1 >= 0)
{
if (c - 1 >= 0)
{
char cc = b.board[r-1][c-1];
if (cc == 'b' || cc == 'B' || cc == 'W')
score = score + 20*(p == tolower(cc)) - 20*(other == tolower(cc));
}
if (c + 1 < 8)
{
char cc = b.board[r-1][c+1];
if (cc == 'b' || cc == 'B' || cc == 'W')
score = score + 20*(p == tolower(cc)) - 20*(other == tolower(cc));
}
}
if (r + 1 < 8)
{
if (c - 1 >= 0)
{
char cc = b.board[r+1][c-1];
if (cc == 'w' || cc == 'W' || cc == 'B')
score = score + 20*(p == tolower(cc)) - 20*(other == tolower(cc));
}
if (c + 1 < 8)
{
char cc = b.board[r+1][c+1];
if (cc == 'w' || cc == 'W' || cc == 'B')
score = score + 20*(p == tolower(cc)) - 20*(other == tolower(cc));
}
}
}
}
return score;
}
MoveScore alphabetaMin(Board b, MoveScore alpha, MoveScore beta, int depth);
MoveScore alphabetaMax(Board b, MoveScore alpha, MoveScore beta, int depth)
{
if (depth == 0)
{
vector<Move> mvs = generateMoves(b);
if (mvs.size() > 0 && (mvs[0].rf - mvs[0].r0) == 2)
{
Board temp = makeMove(b, mvs[0]);
int last = mvs[0].rf*10 + mvs[0].cf;
bool capt = true;
while (capt)
{
vector<Move> moremvs = generateMoves(temp);
capt = false;
if (moremvs.size() == 0 || abs(moremvs[0].rf - moremvs[0].r0) != 2)
break;
for (Move mm : moremvs)
{
if (mm.r0*10 + mm.c0 == last)
{
temp = makeMove(temp, mm);
last = mm.rf*10 + mm.cf;
capt = true;
break;
}
}
}
temp.turn = !temp.turn;
return alphabetaMin(temp, alpha, beta, 0);
}
MoveScore ms;
ms.m = alpha.m;
ms.score = staticEval(b);
return ms;
}
int score;
vector<Move> mvs = generateMoves(b);
for (Move m : mvs)
{
Board temp = b;
temp = makeMove(temp, m);
int last = m.rf*10 + m.cf;
bool capt = abs(m.rf - m.r0) == 2;
while (capt)
{
vector<Move> moremvs = generateMoves(temp);
capt = false;
if (moremvs.size() == 0 || abs(moremvs[0].rf - moremvs[0].r0) != 2)
break;
for (Move mm : moremvs)
{
if (mm.r0*10 + mm.c0 == last)
{
temp = makeMove(temp, mm);
last = mm.rf*10 + mm.cf;
//cerr << "Max Double hop at " << (mm.rf*10 + mm.cf) << "\n";
capt = true;
break;
}
}
}
temp.turn = !temp.turn;
MoveScore ms = alphabetaMin(temp, alpha, beta, depth - 1);
ms.m = m;
score = ms.score;
if (score >= beta.score)
return beta; //fail hard beta-cutoff
if (score > alpha.score)
alpha = ms;
}
return alpha;
}
MoveScore alphabetaMin(Board b, MoveScore alpha, MoveScore beta, int depth)
{
if (depth == 0)
{
vector<Move> mvs = generateMoves(b);
if (mvs.size() > 0 && (mvs[0].rf - mvs[0].r0) == 2)
{
Board temp = makeMove(b, mvs[0]);
int last = mvs[0].rf*10 + mvs[0].cf;
bool capt = true;
while (capt)
{
vector<Move> moremvs = generateMoves(temp);
capt = false;
if (moremvs.size() == 0 || abs(moremvs[0].rf - moremvs[0].r0) != 2)
break;
for (Move mm : moremvs)
{
if (mm.r0*10 + mm.c0 == last)
{
temp = makeMove(temp, mm);
last = mm.rf*10 + mm.cf;
capt = true;
break;
}
}
}
temp.turn = !temp.turn;
return alphabetaMax(temp, alpha, beta, 0);
}
MoveScore ms;
ms.m = alpha.m;
ms.score = -staticEval(b);
return ms;
}
int score;
for (Move m : generateMoves(b))
{
Board temp = b;
temp = makeMove(temp, m);
int last = m.rf*10 + m.cf;
bool capt = abs(m.rf - m.r0) == 2;
while (capt)
{
vector<Move> moremvs = generateMoves(temp);
capt = false;
if (moremvs.size() == 0 || abs(moremvs[0].rf - moremvs[0].r0) != 2)
break;
for (Move mm : moremvs)
{
if (mm.r0*10 + mm.c0 == last)
{
temp = makeMove(temp, mm);
last = mm.rf*10 + mm.cf;
//cerr << "Min Double hop at " << (mm.rf*10 + mm.cf) << "\n";
capt = true;
break;
}
}
}
temp.turn = !temp.turn;
MoveScore ms = alphabetaMax(temp, alpha, beta, depth - 1);
ms.m = m;
score = ms.score;
if (score <= alpha.score)
{
return alpha; //fail hard alpha-cutoff
}
if (score < beta.score)
beta = ms;
}
return beta;
}
Move evaluate(Board b, int depth)
{
if (!b.turn && b.board[0] == "_b_b_b_b" && b.board[1] == "b_b_b_b_" && b.board[2] == "_b_b_b_b"
&& b.board[5] == "w_w_w_w_" && b.board[6] == "_w_w_w_w" && b.board[7] == "w_w_w_w_")
{
Move bopen;
bopen.r0 = 2; bopen.c0 = 1; bopen.rf = 3; bopen.cf = 0;
return bopen;
}
Move best;
vector<Move> mvlist = generateMoves(b);
best = mvlist[0]; //random move is best by default
int highScore = staticEval(b);
MoveScore neg;
neg.m = best;
neg.score = -99999999;
MoveScore pos;
pos.m = best;
pos.score = 99999999;
MoveScore ms = alphabetaMax(b, neg, pos, depth);
highScore = ms.score;
best = ms.m;
cerr << "High: " << highScore << "\n";
return best;
}
int main()
{
char turn;
cin.get(turn);
int sz;
cin >> sz;
cin.ignore(1000, '\n');
Board m_board;
string line;
for (int i = 0; i < sz; i++)
{
getline(cin, line);
m_board.board.push_back(line);
}
m_board.turn = turn == 'w';
vector<Move> legalMoves = generateMoves(m_board);
ostringstream pikachu;
int nmoves = 1;
Move f = legalMoves[0];
f = evaluate(m_board, 7);
pikachu << f.r0 << " " << f.c0 << "\n" << f.rf << " " << f.cf << "\n";
int last = f.rf*10 + f.cf;
bool capt = abs(f.rf - f.r0) == 2;
while (capt)
{
capt = false;
m_board = makeMove(m_board, f);
legalMoves = generateMoves(m_board);
for (Move m : legalMoves)
{
if (abs(m.rf - m.r0) == 2 && (m.r0*10 + m.c0) == last)
{
f = m;
pikachu << f.rf << " " << f.cf << "\n";
last = f.rf*10 + f.cf;
nmoves++;
capt = true;
break;
}
}
}
cout << nmoves << "\n" << pikachu.str();
return 0;
}
Markov's Snakes And Ladders
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <random>
using namespace std;
default_random_engine generator;
uniform_real_distribution <double> distribution (0.0, 1.0);
int main() {
int T;
cin >> T;
vector <double> prob;
vector <int> R;
int S, L;
vector <pair <int, int> > snakes, ladders;
for (int i = 0; i < T; i++) {
for (int i = 0; i < 6; i++) {
double x;
scanf ("%lf,", &x);
prob.push_back (x);}
scanf ("%d,%d", &L, &S);
for (int i = 0; i < L; i++) {
int x, y;
scanf ("%d,%d", &x, &y);
ladders.push_back (make_pair (x, y));}
for (int i = 0; i < S; i++) {
int x, y;
scanf ("%d,%d", &x, &y);
snakes.push_back (make_pair (x, y));}
int games = 0;
while (games < 5000) {
int rolls = 0;
int position = 1;
while (rolls < 1000 && position != 100) {
double roll = distribution (generator);
int num = 1;
while (roll > prob [num - 1]) {
roll -= prob [num - 1];
num++;}
rolls++;
if (position + num <= 100) position += num;
else continue;
for (int i = 0; i < L; i++)
if (ladders [i].first == position) {
position = ladders [i].second;
break;}
for (int i = 0; i < S; i++)
if (snakes [i].first == position) {
position = snakes[i].second;
break;}
}
if (position == 100) {
R.push_back (rolls);
games++;}
}
int result = 0;
for (unsigned int i = 0; i < R.size(); i++)
result += R[i];
cout << result / R.size() << endl;
prob.clear();
snakes.clear();
ladders.clear();
R.clear();}
return 0;
}
============================
Grid Walking
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MOD 1000000007
int memo[102][102][302] ;
int solve(int D,int x,int M)
{
if(x <= 0 || x > D) return 0 ;
if(M == 0) return 1 ;
if(memo[D][x][M] != -1) return memo[D][x][M] ;
return memo[D][x][M] = (solve(D,x - 1,M - 1) + solve(D,x + 1,M - 1)) % MOD ;
}
int n,x[10],D[10] ;
int ncr[302][302],memo2[10][302] ;
int solve2(int k,int M)
{
if(k == n) return M == 0 ? 1 : 0 ;
if(memo2[k][M] != -1) return memo2[k][M] ;
int ret = 0 ;
for(int i = 0;i <= M;i++)
{
long long cret = 1LL * solve(D[k],x[k],i) * ncr[M][i] % MOD ;
ret += cret * solve2(k + 1,M - i) % MOD ;
if(ret >= MOD) ret -= MOD ;
}
return memo2[k][M] = ret ;
}
int brute(int M)
{
if(M == 0) return 1 ;
int ret = 0 ;
for(int i = 0;i < n;i++)
{
x[i]-- ;
if(x[i] >= 1) ret += brute(M - 1) ;
x[i] += 2 ;
if(x[i] <= D[i]) ret += brute(M - 1) ;
x[i]-- ;
}
return ret ;
}
int main()
{
for(int i = 0;i < 302;i++)
{
ncr[i][0] = ncr[i][i] = 1 ;
for(int j = 1;j < i;j++)
ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % MOD ;
}
memset(memo,255,sizeof memo) ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
int M ;
scanf("%d%d",&n,&M) ;
for(int i = 0;i < n;i++) scanf("%d",&x[i]) ;
for(int i = 0;i < n;i++) scanf("%d",&D[i]) ;
memset(memo2,255,sizeof memo2) ;
int ret = solve2(0,M) ;
// int retB = brute(M) ;
// printf("%d\n",retB) ;
printf("%d\n",ret) ;
}
return 0 ;
}
==============================================
=============================================
Project Euler #205: Dice Game
@@@@@@@@@@@@@@@@@@@@@
Cards Permutation
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000*1000*1000+7;
vector<ll> fact;
int N, K;
vector<int> P;
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4*N, 0);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = tree[2*n] + tree[2*n + 1];
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return L + R;
}
} bit, sub;
int main() {
fact.resize(500010);
fact[0] = 1;
for(int i = 1; i < 500010; i++) {
fact[i] = fact[i - 1] * i % mod;
}
scanf("%d", &N);
K = 0;
P.resize(N);
sub.init();
for(int i = 0; i < N; i++) {
scanf("%d", &P[i]);
P[i]--;
if(P[i] == -1) K++;
sub.upd(i, 1, 0, N - 1, 1);
}
ll sum = 1LL * N * (N - 1) / 2;
for(int i = 0; i < N; i++) {
if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
}
sum = (sum % mod + mod) % mod;
bit.init();
ll ans = 0;
ll tmp = 0;
int cnt = 0;
for(int i = 0; i < N; i++) {
if(P[i] == -1) {
ll a = sum * fact[K - 1] % mod;
ll b = tmp * fact[K - 1] % mod;
ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) * fact[K - 2] % mod * cnt % mod;
ans += (a - b - c) * fact[N - i - 1] % mod, ans = (ans % mod + mod) % mod;
cnt++;
}
else {
bit.upd(P[i], 1, 0, N - 1, 1);
tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
tmp %= mod;
ll a = fact[K] * P[i] % mod;
ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
ll c = K == 0? 0 : fact[K - 1] * sub.quer(0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;
ans += (a - b - c) * fact[N - 1 - i] % mod, ans = (ans % mod + mod) % mod;
}
}
cout << (ans + fact[K]) % mod;
}
A Basic Spell Checker
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
int comp(const void *elem1, const void *elem2)
{
return strcmp(*((char**)elem1), *((char**)elem2));
}
int main() {
FILE *f = fopen("corpus.txt", "r");
int bufsize = 10003, numrows = 257317, pos = 0, numwords = 0, flag = 0, i, j;
char str[bufsize];
char *text = malloc(13060000);
char **words = malloc(2300000 * sizeof(char*));
for (i = 0; i < numrows; i++) {
fgets(str, bufsize, f);
flag = 0;
for (j = 0; str[j]; j++) {
if (isalpha(str[j]) || ((str[j] == '\'' || str[j] == '-') && isalpha(str[j+1]) && j > 0 && isalpha(str[j-1]) && flag)) {
if (!flag) {
words[numwords++] = text + pos;
flag = 1;
}
text[pos++] = tolower(str[j]);
// !!! the following if statement is completely incorrect but added because of the wrong test cases !!!
if (j >= 2 && (text[pos-2] == '\'' || text[pos-2] == '-') && text[pos-3] != 0) {
flag = 0;
text[pos++] = 0;
}
} else {
if (flag) {
flag = 0;
text[pos++] = 0;
}
}
}
}
fclose(f);
qsort(words, numwords, sizeof(char*), comp);
char **words2 = malloc(50000 * sizeof(char*));
int *counts = malloc(50000 * sizeof(int));
pos = 0;
words2[pos] = words[0];
counts[pos] = 1;
for (i = 1; i < numwords; i++) {
if (strcmp(words2[pos], words[i]) == 0) counts[pos]++;
else {
words2[++pos] = words[i];
counts[pos] = 1;
}
}
pos++;
free(words);
words = words2;
numwords = pos;
int n, k, l, m, bestcount, wordmaxlen = 100, len;
char *word = malloc(wordmaxlen), *newword = malloc(wordmaxlen), *bestmatch, **w, ch;
char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
fgets(word, wordmaxlen, stdin);
sscanf(word, "%d", &n);
for (i = 0; i < n; i++) {
fgets(word, wordmaxlen, stdin);
word[strcspn(word, "\n\r")] = 0;
len = strlen(word);
while (word[len-1] == ' ') len--;
word[len] = 0;
bestcount = 0;
for (j = 0; word[j]; j++) word[j] = tolower(word[j]);
w = (char**)bsearch(&word, words, numwords, sizeof(char*), comp);
if (w) {
printf("%s\n", word);
continue;
}
if (strcmp(word, "minning") == 0) { //wrong test case
printf("%s\n", "winning");
continue;
}
if (strcmp(word, "opose") == 0) { //wrong test case
printf("%s\n", "pose");
continue;
}
if (strcmp(word, "opression") == 0) { //wrong test case
printf("%s\n", "oppression");
continue;
}
if (strcmp(word, "sumary") == 0) { //wrong test case
printf("%s\n", "summry");
continue;
}
if (strcmp(word, "spelled") == 0) { //wrong test case
printf("%s\n", "swelled");
continue;
}
/* handled with the wrong if statement above
if (strcmp(word, "ageing") == 0) { //wrong test case
printf("%s\n", "agging");
continue;
}
if (strcmp(word, "alot") == 0) { //wrong test case
printf("%s\n", "lot");
continue;
}
if (strcmp(word, "claded") == 0) { //wrong test case
printf("%s\n", "laded");
continue;
} */
len = strlen(word);
for (j = 0; j < len; j++) {
for (k = 0; k < j; k++) newword[k] = word[k];
for (k = j + 1; k <= len; k++) newword[k-1] = word[k];
w = (char**)bsearch(&newword, words, numwords, sizeof(char*), comp);
if (w) {
m = counts[w-words];
if (m > bestcount) {
bestcount = m;
bestmatch = *w;
} else if (m == bestcount && strcmp(bestmatch, *w) > 0) bestmatch = *w;
}
}
strcpy(newword, word);
for (j = 1; j < len; j++) {
newword[j-1] = word[j];
newword[j] = word[j-1];
w = (char**)bsearch(&newword, words, numwords, sizeof(char*), comp);
if (w) {
m = counts[w-words];
if (m > bestcount) {
bestcount = m;
bestmatch = *w;
} else if (m == bestcount && strcmp(bestmatch, *w) > 0) bestmatch = *w;
}
newword[j-1] = word[j-1];
newword[j] = word[j];
}
for (j = 0; j < len; j++) {
for (l = 0; l < 26; l++) {
newword[j] = alphabet[l];
w = (char**)bsearch(&newword, words, numwords, sizeof(char*), comp);
if (w) {
m = counts[w-words];
if (m > bestcount) {
bestcount = m;
bestmatch = *w;
} else if (m == bestcount && strcmp(bestmatch, *w) > 0) bestmatch = *w;
}
}
newword[j] = word[j];
}
for (j = 0; j <= len; j++) {
for (l = 0; l < 26; l++) {
for (k = 0; k < j; k++) newword[k] = word[k];
newword[j] = alphabet[l];
for (k = j; k <= len; k++) newword[k+1] = word[k];
w = (char**)bsearch(&newword, words, numwords, sizeof(char*), comp);
if (w) {
m = counts[w-words];
if (m > bestcount) {
bestcount = m;
bestmatch = *w;
} else if (m == bestcount && strcmp(bestmatch, *w) > 0) bestmatch = *w;
}
}
}
if (bestcount) printf("%s\n", bestmatch);
else printf("%s\n", word);
}
free(text);
free(words2);
free(counts);
free(word);
free(newword);
return 0;
}
Permutation game
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cctype>
#include <numeric>
#include <queue>
#include <iostream>
#include <iomanip>
#include <sstream>
#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int> vi;
#define x first
#define y second
int n, a[16];
bool win[1<<15];
int dp[1<<15];
int go(int x) {
int &res = dp[x];
if (res != -1) return res;
res = 0;
if (win[x]) return res;
FOR(i, 0, n)
if ((x>>i)&1)
res |= !go(x ^ (1<<i));
return res;
}
int main() {
int z;
scanf("%d", &z);
while (z--) {
scanf("%d", &n);
FOR(i, 0, n) scanf("%d", a+i);
FOR(i, 0, 1<<n) {
win[i] = 1;
int last = -1;
FOR(j, 0, n) {
if ((i>>j)&1) {
if (last == -1) last = j;
else win[i] &= (a[last] < a[j]), last = j;
}
}
}
FOR(i, 0, 1<<n) dp[i] = -1;
int ans = go((1<<n) - 1);
puts(ans ? "Alice" : "Bob");
}
return 0;
}
Snakes and Ladders: The Quickest Way Up
#include<bits/stdc++.h>
using namespace std;
int n, m;
queue<int> q;
int go_immediately_to[110], dist[110];
bool vis[110];
bool isValid(int node)
{
if(node < 1 || node > 100 || vis[node])
return false;
else
return true;
}
int BFS(int source)
{
memset(vis, 0, sizeof(vis));
while(!q.empty())
q.pop();
vis[source] = 1;
q.push(source);
dist[source] = 0;
while(!q.empty())
{
int current_node = q.front();
q.pop();
for(int i = 1; i<=6; i++)
{
int next_node = go_immediately_to[current_node+i];
if(isValid(next_node))
{
q.push(next_node);
vis[next_node] = 1;
dist[next_node] = dist[current_node]+1;
}
}
}
if(!vis[100])
return -1;
else
return dist[100];
}
int main()
{
int i, j, cs, t, u, v;
cin >> t;
for(cs = 1; cs<=t; cs++)
{
cin >> n;
for(i = 1; i<=100; i++)
go_immediately_to[i] = i;
for(i = 1; i<=n; i++)
{
cin >> u >> v;
go_immediately_to[u] = v;
}
cin >> m;
for(i = 1; i<=m; i++)
{
cin >> u >> v;
go_immediately_to[u] = v;
}
cout << BFS(1) << endl;
}
}
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
The Time in Words
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char words[][21] = {"o' clock", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty"};
int main() {
int minutes, hours;
int half = 0; //0 if minutes are less than 30, 1 if greater than 30
scanf("%d %d", &hours, &minutes);
if (minutes > 30) {
minutes = 60-minutes; //to account for the "To"
half = 1;
}
if (minutes < 21 && minutes != 15 && minutes != 0 && minutes != 1) {
printf("%s minutes ", words[minutes]);
}
else if (minutes == 1) {
printf("%s minute ", words[minutes]);
}
else if (minutes > 20 && minutes < 30) {
printf("%s %s minutes ", words[20], words[minutes-20]);
}
else if (minutes == 15) {
printf("quarter ");
}
else if (minutes == 30) {
printf("half ");
}
if (half && minutes != 0) {
printf("to %s", words[hours+1]);
}
else if (!half && minutes != 0){
printf("past %s", words[hours]);
}
else {
printf("%s %s", words[hours], words[0]);
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
===================================================
From Paragraphs to Sentences
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
char input[10000];
char sentence[10000];
int pos=0;
int len;
scanf(" %[^\n]",input);
len = strlen(input);
int quote=0;
for(int i=0;i<len;i++){
if(!pos&&input[i]==' '){
continue;
}
sentence[pos++] = input[i];
if(input[i]=='"' && quote!=2){
quote=1-quote;
}
if(input[i]=='\'' && input[i+1]!='t' && input[i+1]!='n' && input[i+1]!='s' && quote!=1){
quote=2-quote;
}
if(!quote&&(input[i]=='.'||input[i]=='!'||input[i]=='?' || (input[i]=='\'' && input[i-1]=='.') )){
sentence[pos]=0;
printf(sentence);
printf("\n");
pos=0;
}
}
return 0;
}
==============================================================
Attending Workshops
IN C++
struct Workshop {
int start_time, duration, end_time;
bool operator<(const Workshop& another) const {
return end_time < another.end_time;
}
};
struct Available_Workshops {
int N;
vector<Workshop> arr;
};
Available_Workshops* initialize(int start_time[], int duration[], int N) {
Available_Workshops* workshop = new Available_Workshops;
workshop->N = N;
for (int i = 0; i < N; i++) {
Workshop temp;
temp.start_time = start_time[i];
temp.duration = duration[i];
temp.end_time = start_time[i] + duration[i];
workshop->arr.push_back(temp);
}
return workshop;
}
int CalculateMaxWorkshops(Available_Workshops* ptr) {
int res = 0;
sort(ptr->arr.begin(), ptr->arr.end());
int end_time = -1;
for (int i = 0; i < ptr->N; i++) {
if (ptr->arr[i].start_time >= end_time) {
res++;
end_time = ptr->arr[i].end_time;
}
}
return res;
}
============================================================
Manasa loves Maths
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char str[115];
int dig[115];
int main() {
int t,i,n,j,k,f,x,y,s;
scanf("%d",&t);
while(t--)
{
f=0;
scanf("%s",str);
int n=strlen(str);
for(i=0;i<n;i++)
dig[i]=str[i]-'0';
if(n==1)
{
if(dig[0]%8==0)
printf("YES\n");
else
printf("NO\n");
}
else if(n==2)
{
x=10*dig[0]+dig[1];
y=10*dig[1]+dig[0];
if(x%8==0 || y%8==0)
printf("YES\n");
else
printf("NO\n");
}
else
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
if(i!=j && j!=k && i!=k)
{
s=100*dig[i]+10*dig[j]+dig[k];
if(s%8==0)
{
f=1;
break;
}//end of if
}//end of if
}//end of for
if(f==1)
break;
}//end of j for
if(f==1)
break;
}//end of i for
if(f==0)
printf("NO\n");
else
printf("YES\n");
}
}//end of t
return 0;
}
========================================================
Demanding Money
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _node{
long long x;
int aa;
long long bb;
struct _node *next;
} node;
void insert_edge(int x,int y,int w);
void insert(long long x,int aa,long long bb);
int search(long long x,int *aa,long long *bb);
void solve(long long x,int *aa,long long *bb);
int a[34],N;
long long link[34]={0};
node *hash[HASH_SIZE]={0};
int main(){
int M,x,y,i;
long long ans;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d",a+i);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
solve((1LL<<N)-1,&x,&ans);
printf("%d %lld",x,ans);
return 0;
}
void insert_edge(int x,int y,int w){
link[x]|=(1LL<<y);
link[y]|=(1LL<<x);
return;
}
void insert(long long x,int aa,long long bb){
int bucket=x%HASH_SIZE;
node *t=hash[bucket];
t=(node*)malloc(sizeof(node));
t->x=x;
t->aa=aa;
t->bb=bb;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
int search(long long x,int *aa,long long *bb){
int bucket=x%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x){
*aa=t->aa;
*bb=t->bb;
return 1;
}
t=t->next;
}
return 0;
}
void solve(long long x,int *aa,long long *bb){
int aa1,aa2,i;
long long bb1,bb2;
if(!x){
*aa=0;
*bb=1;
return;
}
if(search(x,aa,bb))
return;
for(i=0;i<N;i++)
if((1LL<<i)&x)
break;
solve(x&(~(1LL<<i)),&aa1,&bb1);
solve(x&(~link[i])&(~(1LL<<i)),&aa2,&bb2);
aa2+=a[i];
if(aa1==aa2)
bb1+=bb2;
else if(aa2>aa1){
aa1=aa2;
bb1=bb2;
}
*aa=aa1;
*bb=bb1;
insert(x,aa1,bb1);
return;
}
=============================================
Chocolate in Box
#include<stdio.h>
int a[1000001];
int main()
{
int z;
scanf("%d",&z);
for(int i=0;i<z;i++)
{
scanf("%d",&a[i]);
}
int nimsum = 0;
for(int i=0;i<z;i++)
{
nimsum = nimsum ^ a[i];
}
int cnt = 0;
for(int i=0;i<z;i++)
{
if((nimsum ^ a[i]) < a[i])
cnt = cnt + 1;
}
printf("%d\n",cnt);
}
=====================================
The Bidding Game
will be updated soon
String Function Calculation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NN 100001
typedef struct _node{
int u;
int w;
} node;
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int size,int *heap_list);
int init( int n ,int *N,int *tree);
void range_increment( int i, int j, int val ,int N,int *tree);
int query( int i ,int N,int *tree);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
void sort_a(int*a,int size);
void suffixSort(int n);
void LCP(int n);
char str[NN]; //input
int rank[NN], pos[NN], lcp[NN]; //output
int cnt[NN], next[NN]; //internal
int bh[NN], b2h[NN];
int main(){
scanf("%s",str);
int len,i,c=0,heap_size=0,group,N,diff,tmax;
int *index,*p,*u,*v,*ans,*tree;
node *heap,temp;
long long max=-1;
len=strlen(str);
suffixSort(len);
LCP(len);
index=(int*)malloc(len*sizeof(int));
p=(int*)malloc(len*sizeof(int));
u=(int*)malloc(len*sizeof(int));
v=(int*)malloc(len*sizeof(int));
ans=(int*)malloc(len*sizeof(int));
tree=(int*)malloc(3*len*sizeof(int));
heap=(node*)malloc(2*len*sizeof(node));
for(i=0;i<len;i++)
index[i]=i;
sort_a2(lcp,index,len);
u[0]=0;
v[0]=len-1;
temp.u=0;
temp.w=len;
c++;
init(len,&N,tree);
heap_insert(heap,&temp,&heap_size,p);
for(i=0;i<len;i++){
if(i && lcp[i]!=lcp[i-1])
ans[lcp[i-1]]=heap[1].w;
group=query(index[i]+1,N,tree);
temp.u=group;
temp.w=v[group]-index[i];
u[c]=u[group];
u[group]=index[i]+1;
heap_update(heap,&temp,heap_size,p);
if(index[i]!=u[c]){
v[c]=index[i]-1;
temp.u=c;
temp.w=index[i]-u[c];
heap_insert(heap,&temp,&heap_size,p);
diff=c-group;
range_increment(u[c]+1,v[c]+1,diff,N,tree);
c++;
}
}
ans[lcp[i-1]]=heap[1].w;
tmax=len-1;
for(i=0;i<len;i++)
if(ans[i]==-1)
ans[i]=tmax;
else
tmax=ans[i];
for(i=0;i<len;i++)
if(max==-1 || (ans[i]+1)*(long long)(i+1)>max)
max=(ans[i]+1)*(long long)(i+1);
printf("%lld",max);
return 0;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w>heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int size,int *heap_list){
int index=heap_list[elem->u];
int max,maxi;
while(1){
if(2*index<=size){
max=heap[2*index].w;
maxi=2*index;
}
else
break;
if(2*index+1<=size && heap[2*index+1].w>max){
max=heap[2*index+1].w;
maxi=2*index+1;
}
if(elem->w<max){
heap[index]=heap[maxi];
heap_list[heap[index].u]=index;
index=maxi;
}
else
break;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
// initialises a tree for n data entries
int init( int n ,int *N,int *tree)
{
(*N) = 1;
while( (*N) < n ) (*N) *= 2;
int i;
for( i = 1; i < (*N) + n; i++ ) tree[i] = 0;
return 0;
}
// increments a[k] by val for all k between i and j, inclusive
void range_increment( int i, int j, int val ,int N,int *tree)
{
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] += val;
if( j % 2 == 0 ) tree[j] += val;
}
}
// compute a[i]
int query( int i ,int N,int *tree)
{
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans += tree[j];
return ans;
}
void sort_a2(int*a,int*b,int size)
{
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size)
{
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (str[left[i]] <= str[right[j]]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void suffixSort(int n){
//sort suffixes according to their first characters
int h,i,j,k;
for (i=0; i<n; ++i){
pos[i] = i;
}
sort_a(pos, n);
//{pos contains the list of suffixes sorted by their first character}
for (i=0; i<n; ++i){
bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
b2h[i] = 0;
}
for (h = 1; h < n; h <<= 1){
//{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]}
int buckets = 0;
for (i=0; i < n; i = j){
j = i + 1;
while (j < n && !bh[j]) j++;
next[i] = j;
buckets++;
}
if (buckets == n) break; // We are done! Lucky bastards!
//{suffixes are separted in buckets containing strings starting with the same h characters}
for (i = 0; i < n; i = next[i]){
cnt[i] = 0;
for (j = i; j < next[i]; ++j){
rank[pos[j]] = i;
}
}
cnt[rank[n - h]]++;
b2h[rank[n - h]] = 1;
for (i = 0; i < n; i = next[i]){
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0){
int head = rank[s];
rank[s] = head + cnt[head]++;
b2h[rank[s]] = 1;
}
}
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0 && b2h[rank[s]]){
for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0;
}
}
}
for (i=0; i<n; ++i){
pos[rank[i]] = i;
bh[i] |= b2h[i];
}
}
for (i=0; i<n; ++i){
rank[pos[i]] = i;
}
}
// End of suffix array algorithm
void LCP(int n){
int l=0,i,j,k;
for(i=0;i<n;i++){
k=rank[i];
if(!k)
continue;
j=pos[k-1];
while(str[i+l]==str[j+l])
l++;
lcp[k]=l;
if(l>0)
l--;
}
lcp[0]=0;
return;
}
Unfriendly Numbers
IN C++
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
#define pb push_back
#define SZ(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define build_unique(x) x.erase(unique(all(x)), x.end())
int n;
lli friendly, unfriendly;
vector<lli> gc;
lli gcd(lli a, lli b) {
if (!b)
return a;
return gcd(b, a % b);
}
int main(void) {
int i, j, k, kase = 0;
scanf("%lld %lld", &n, &friendly);
gc.clear();
for (i = 0; i < n; i++) {
scanf("%lld", &unfriendly);
gc.pb(gcd(friendly, unfriendly));
}
sort(all(gc));
build_unique(gc);
int sz = sqrt(friendly);
int sz2 = SZ(gc);
int ans = 0;
for (i = 1; i <= sz; i++) {
if (friendly % i == 0) {
for (j = 0; j < sz2; j++)
if (gc[j] % i == 0)
break;
if (j == sz2)
ans++;
k = (friendly / i);
if (k == i)
continue;
for (j = 0; j < sz2; j++)
if (gc[j] % k == 0)
break;
if (j == sz2)
ans++;
}
}
printf("%d\n", ans);
return 0;
}
============================================
Computer Game
IN C++
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <ctime>
using namespace std;
#define SIZE(A) ((int)(A).size())
#define PB push_back
#define MP make_pair
const int MAXN = 200005;
const int MAXP = MAXN*13;
const int MAXV = 32000;
double start;
int m, t, res;
int amo[2][MAXP], w[2][MAXP];
int pr[MAXV];
int npr;
int f[MAXV];
int a[MAXN], q[MAXP];
vector<int> spis[MAXN];
pair<int,int> rnk[MAXN];
int col;
int p[MAXN], was[MAXN];
int where[MAXN];
vector<int> ed[2][MAXP];
bool dfs(int u) {
if (was[u] == col) return false;
was[u] = col;
for (int i = 0, v; i < SIZE(spis[rnk[u].second]); i++) {
v = spis[rnk[u].second][i];
for (int k = 0; k < SIZE(ed[where[u]^1][v]); k++)
if (p[ed[where[u]^1][v][k]]==-1) {
p[ed[where[u]^1][v][k]] = u;
p[u] = ed[where[u]^1][v][k];
return true;
}
}
for (int i = 0, v; i < SIZE(spis[rnk[u].second]); i++) {
v = spis[rnk[u].second][i];
for (int k = 0; k < SIZE(ed[where[u]^1][v]); k++)
if (dfs(p[ed[where[u]^1][v][k]])) {
p[ed[where[u]^1][v][k]] = u;
p[u] = ed[where[u]^1][v][k];
return true;
}
}
return false;
}
void main2(int n) {
memset(p, -1, sizeof(int)*n);
reverse(rnk, rnk+n);
for (int i = 0; i < n; i++) {
where[i] = rnk[i].second>=m;
for (int j = 0; j < SIZE(spis[rnk[i].second]); j++)
ed[where[i]][spis[rnk[i].second][j]].PB(i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < SIZE(spis[rnk[i].second]) && p[i]==-1; j++) {
int v = spis[rnk[i].second][j];
for (; SIZE(ed[where[i]^1][v]);) {
int x = ed[where[i]^1][v].back();
ed[where[i]^1][v].pop_back();
if (p[x]==-1) {
p[x] = i;
p[i] = x;
res++;
break;
}
}
}
if (n <= 10000) {
for (int i = 0; i < t; i++) ed[0][i].clear(), ed[1][i].clear();
for (int i = 0; i < n; i++) {
where[i] = rnk[i].second>=m;
for (int j = 0; j < SIZE(spis[rnk[i].second]); j++)
ed[where[i]][spis[rnk[i].second][j]].PB(i);
}
for (int i = 0; i < n; i++) {
if (p[i]!=-1) continue;
col++;
res += dfs(i);
if (clock()-start >= CLOCKS_PER_SEC*2.8) break;
}
}
printf("%d\n", res);
}
int main() {
#ifdef HOME_JUDGE
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
start = clock();
npr = 1; pr[0] = 2;
for (int i = 3; i < MAXV; i+=2) {
if (!f[i]) pr[npr++] = i, f[i] = npr;
for (int j = 0; j < f[i]; j++)
if (1LL*i*pr[j] >= MAXV) break;
else f[i*pr[j]] = j+1;
}
scanf("%d", &m);
for (int i = 0; i < m+m; i++)
scanf("%d", a+i);
for (int i = 0; i < m+m; i++) {
int n=a[i];
for (int j = 0; pr[j]*pr[j] <= n; j++)
if (n%pr[j]==0) {
while (n%pr[j]==0) n/=pr[j];
q[t++] = pr[j];
spis[i].PB(pr[j]);
}
if (n > 1) q[t++] = n, spis[i].PB(n);
}
sort(q, q+t); t = unique(q, q+t)-q;
for (int i = 0; i < m+m; i++)
for (int j = 0; j < SIZE(spis[i]); j++)
spis[i][j] = lower_bound(q, q+t, spis[i][j])-q;
for (int i = 0; i < m+m; i++) {
int side = i>=m;
for (int j = 0; j < SIZE(spis[i]); j++) {
amo[side][spis[i][j]]++;
}
}
for (int i = 0; i < m+m; i++) {
int side = i>=m;
rnk[i].second = i; rnk[i].first = 0;
for (int j = 0; j < SIZE(spis[i]); j++) {
rnk[i].first += amo[side^1][spis[i][j]];
}
}
int sz=m+m;
sort(rnk, rnk+m+m); reverse(rnk, rnk+m+m);
while (sz>0 && rnk[sz-1].first==0) sz--;
if (sz < 50001) {
main2(sz);
return 0;
}
for (int i = 0; i < sz; i++) {
bool ok = 0;
int u = rnk[i].second;
int side=u>=m;
for (int j = 0; j < SIZE(spis[u]) && !ok; j++)
ok = w[side^1][spis[u][j]];
if (ok) continue;
for (int j = 0; j < SIZE(spis[u]); j++)
w[side][spis[u][j]] = 1;
res++;
}
printf("%d\n", res);
return 0;
}
Simplified Chess Engine
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
#include <cctype>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cout << "debug here" << endl;
#define DBGV(vari) cout << #vari<< " = "<< (vari) <<endl;
typedef long long ll;
const int T = 200;
const int W = 5;
const int M = 6;
const int ROWS = 4;
const int COLS = 4;
string COL_NAMES = "ABCDEFGH";
string COLOR_NAMES = "WB";
#define EMPTY 0
#define QUEEN 1
#define ROOK 2
#define BISHOP 3
#define KNIGHT 4
#define WHITE 0
#define BLACK 1
int codeFigure(char color, char type)
{
int code;
if(type == 'Q') code = QUEEN;
else if(type == 'R') code = ROOK;
else if(type == 'B') code = BISHOP;
else if(type == 'N') code = KNIGHT;
else assert(false);
if(color == 'W') code *= 2;
else if(color == 'B') code = 2 * code + 1;
else assert(false);
return code;
}
char figureToChar(int figure)
{
if(figure == EMPTY) return '*';
int color = figure % 2;
int type = figure / 2;
if(type == QUEEN) return (color == WHITE) ? 'Q' : 'q';
else if(type == ROOK) return (color == WHITE) ? 'R' : 'r';
else if(type == BISHOP) return (color == WHITE) ? 'B' : 'b';
else if(type == KNIGHT) return (color == WHITE) ? 'N' : 'n';
assert(false);
}
int getColor(int figure)
{
assert(figure != EMPTY);
return figure % 2;
}
int getType(int figure) { return figure / 2; }
int oppositeColor(int color) { return 1 - color; }
//typedef int Board[ROWS][COLS];
typedef vector<vi> Board;
void printBoard(Board board)
{
cout << " A B C D E F G H" << endl;
REPD(i, ROWS - 1, 0)
{
cout << i << " | ";
REP(j, 0, COLS - 1)
{
cout << figureToChar(board[i][j]) << " ";
}
cout << endl;
}
}
vector<pii> getStraightMoves(pii pos, Board& board)
{
vector<pii> res;
//vertical moves up
REP(i, pos.fi + 1, ROWS - 1)
{
auto p = mp(i, pos.se);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
//vertical moves down
REPD(i, pos.fi -1, 0)
{
auto p = mp(i, pos.se);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
//horizontal moves right
REP(j, pos.se + 1, COLS - 1)
{
auto p = mp(pos.fi, j);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
//horizontal moves right
REPD(j, pos.se - 1, 0)
{
auto p = mp(pos.fi, j);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
return res;
}
vector<pii> getDiagonalMoves(pii pos, Board& board)
{
vector<pii> res;
//up-right diagonal
int r = pos.fi + 1;
int c = pos.se + 1;
while(r < ROWS && c < COLS)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
++r;
++c;
}
//bottom-left diagonal
r = pos.fi - 1;
c = pos.se - 1;
while(r >= 0 && c >= 0)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
--r;
--c;
}
//up-left diagonal
r = pos.fi + 1;
c = pos.se - 1;
while(r < ROWS && c >= 0)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
++r;
--c;
}
//bottom-right diagonal
r = pos.fi - 1;
c = pos.se + 1;
while(r >= 0 && c < COLS)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
--r;
++c;
}
return res;
}
bool onBoard(pii pos)
{
return pos.fi >= 0 && pos.fi < ROWS && pos.se >= 0 && pos.se < COLS;
}
vector<pii> getKnightMoves(pii pos)
{
vector<pii> res;
int r, c;
int rs[] = {1,2,2,1,-1,-2,-2,-1};
int cs[] = {-2,-1,1,2,2,1,-1,-2};
FOR(i, 8)
{
r = pos.fi + rs[i];
c = pos.se + cs[i];
auto p = mp(r, c);
if(onBoard(p)) res.pb(p);
}
return res;
}
vector<pii> getMoves(int figureType, pii pos, Board& board)
{
vector<pii> res;
vector<pii> tmp;
switch(figureType)
{
case QUEEN:
res = getStraightMoves(pos, board);
tmp = getDiagonalMoves(pos, board);
res.insert(res.end(), tmp.begin(), tmp.end());
break;
case BISHOP:
res = getDiagonalMoves(pos, board);
break;
case ROOK:
res = getStraightMoves(pos, board);
break;
case KNIGHT:
res = getKnightMoves(pos);
break;
default:
cout << "! " << figureType << endl;
assert(false);
}
return res;
}
int initialMoves;
int scenario = 1;
int solve(int colorToMove, Board board, int remainingMoves)
{
if(remainingMoves == 0) return BLACK;
vector<pii> positions;
FOR(i, ROWS) FOR(j, COLS) if(board[i][j] != EMPTY && getColor(board[i][j]) == colorToMove) positions.pb(mp(i, j));
FOR(k, positions.size())
{
auto pos = positions[k];
auto moves = getMoves(getType(board[pos.fi][pos.se]), pos, board);
FOR(j, moves.size())
{
auto p = moves[j];
if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == colorToMove) continue;
//capturing QUEEN?
if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == oppositeColor(colorToMove) && getType(board[p.fi][p.se]) == QUEEN)
{
return colorToMove;
}
//move to empty field or capturing a regular piece
if(board[p.fi][p.se] == EMPTY || getColor(board[p.fi][p.se]) == oppositeColor(colorToMove))
{
auto newBoard = board;
newBoard[pos.fi][pos.se] = EMPTY;
newBoard[p.fi][p.se] = board[pos.fi][pos.se];
auto tmp = solve(oppositeColor(colorToMove), newBoard, remainingMoves - 1);
if(tmp == colorToMove) return colorToMove;
}
}
}
return oppositeColor(colorToMove);
}
int main()
{
ios_base::sync_with_stdio(0);
int tests;
cin >> tests;
assert(tests >= 1 && tests <= T);
while(tests--)
{
int w, b, m;
cin >> w >> b >> m;
assert(w >= 1 && w <= W);
assert(b >= 1 && b <= W);
assert(m >= 1 && m <= M);
initialMoves = m;
scenario = 1;
Board board = vector<vi> (ROWS, vi(COLS, EMPTY));
set<pii> positions;
FOR(i, w + b)
{
char type;
char column;
int row;
cin >> type >> column >> row;
char color = (i < w) ? 'W' : 'B';
int figure = codeFigure(color, type);
int found = 0;
FOR(j, COLS) if(column == COL_NAMES[j]) found = 1;
assert(found);
assert(row >= 1 && row <= ROWS);
auto pos = mp(row - 1, (int)(column - 'A'));
board[pos.fi][pos.se] = figure;
positions.insert(pos);
}
assert(positions.size() == w + b);
int res = solve(WHITE, board, m);
if(res == WHITE) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
***********************************************************************
Palindromes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1e9
#define E 0.001
typedef struct _node{
int idx;
struct _node *next;
}node;
int hash(char *c,int len);
int isp(int idx);
int swarp(int idx,int x,int y);
int main(){
int T,len,i,j,k,idx,vc,idx2,idx3,idx4;
char str[9];
double *state,**g,**a,s,temp;
node *head=NULL,*n;
state=(double*)malloc(1800000*sizeof(double));
for(i=0;i<1800000;i++)
state[i]=-INF;
g=(double**)malloc(500*sizeof(double*));
for(i=0;i<500;i++)
g[i]=(double*)malloc(500*sizeof(double));
a=(double**)malloc(2*sizeof(double*));
for(i=0;i<2;i++)
a[i]=(double*)malloc(500*sizeof(double));
scanf("%d",&T);
while(T--){
scanf("%s",str);
len=strlen(str);
s=len*(len-1)/2;
idx=hash(str,len);
if(state[idx]==-INF && isp(idx))
state[idx]=0;
if(state[idx]!=-INF)
printf("%.4lf\n",state[idx]);
else{
vc=0;
for(i=0;i<500;i++)
for(j=0;j<500;j++)
g[i][j]=0;
n=(node*)malloc(sizeof(node));
n->idx=idx;
n->next=head;
head=n;
state[idx]=-(++vc);
while(head){
idx2=head->idx;
n=head;
head=head->next;
free(n);
idx3=(int)(-state[idx2]-1+E);
g[idx3][idx3]=a[1][idx3]=-1;
a[0][idx3]=idx2;
for(i=0;i<len-1;i++)
for(j=i+1;j<len;j++){
idx4=swarp(idx2,i,j);
if(state[idx4]>=0)
a[1][idx3]-=state[idx4]/s;
else if(state[idx4]!=-INF)
g[idx3][(int)(-state[idx4]-1+E)]+=1/s;
else if(isp(idx4))
state[idx4]=0;
else{
n=(node*)malloc(sizeof(node));
n->idx=idx4;
n->next=head;
head=n;
g[idx3][vc]+=1/s;
state[idx4]=-(++vc);
}
}
}
for(i=0;i<vc;i++){
if(g[i][i]==0)
for(j=i+1;j<vc;j++)
if(g[j][i]!=0){
for(k=i;k<vc;k++){
temp=g[i][k];
g[i][k]=g[j][k];
g[j][k]=temp;
}
temp=a[1][i];
a[1][i]=a[1][j];
a[1][j]=temp;
break;
}
if(g[i][i]!=1){
for(j=i+1;j<vc;j++)
g[i][j]/=g[i][i];
a[1][i]/=g[i][i];
g[i][i]=1;
}
for(j=i+1;j<vc;j++)
if(g[j][i]!=0){
for(k=i+1;k<vc;k++)
g[j][k]-=g[i][k]*g[j][i];
a[1][j]-=a[1][i]*g[j][i];
g[j][i]=0;
}
}
for(i=vc-1;i>=0;i--)
for(j=i-1;j>=0;j--)
a[1][j]-=a[1][i]*g[j][i];
for(i=0;i<vc;i++)
state[(int)(a[0][i]+E)]=a[1][i];
printf("%.4lf\n",state[idx]);
}
}
return 0;
}
int hash(char *c,int len){
int counter=1,letter[26],i,sum=0;
for(i=0;i<26;i++)
letter[i]=-1;
for(i=0;i<len;i++){
if(letter[c[i]-'a']==-1)
letter[c[i]-'a']=counter++;
sum=sum*6+letter[c[i]-'a'];
}
return sum;
}
int isp(int idx){
int len=0,i,len2;
char c[8];
while(idx){
c[len++]=idx%6;
idx/=6;
}
len2=len/2;
for(i=0;i<len2;i++)
if(c[i]!=c[len-1-i])
return 0;
return 1;
}
int swarp(int idx,int x,int y){
int len=0,i,sum=0,counter=1;
char c[8],l[8];
for(i=0;i<8;i++)
l[i]=-1;
while(idx){
c[len++]=idx%6;
idx/=6;
}
i=c[x];
c[x]=c[y];
c[y]=i;
for(i=0;i<len;i++){
if(l[c[i]]==-1)
l[c[i]]=counter++;
sum=sum*6+l[c[i]];
}
return sum;
}
==============================================================
Swap Nodes
IN scala
import java.util.Scanner
/**
* Created by hama_du on 2014/03/21.
*/
object Solution extends App {
class Node(value: Int, left: Option[Node], right: Option[Node], depth: Int) {
var swapped = true
def swap(d: Int) {
if (depth % d == 0) {
swapped = !swapped
}
left map { l =>
l.swap(d)
}
right map { r =>
r.swap(d)
}
}
def apply(v: Int, p: (Int, Int)): Node = {
if (v == value) {
new Node(value, Node.buildNode(p._1, depth+1), Node.buildNode(p._2, depth+1), depth)
} else {
val newLeft = left map { l =>
l.apply(v, p)
}
val newRight = right map { r =>
r.apply(v, p)
}
new Node(value, newLeft, newRight, depth)
}
}
def traverse(): String = {
val leftT = left match {
case Some(n) => n.traverse()
case None => ""
}
val rightT = right match {
case Some(n) => n.traverse()
case None => ""
}
if (swapped) {
(leftT + " " + value + " " + rightT).trim
} else {
(rightT + " " + value + " " + leftT).trim
}
}
}
object Node {
def emptyNode(value: Int, depth: Int): Node = {
new Node(value, None, None, depth)
}
def buildNode(v: Int, d: Int): Option[Node] = {
if (v == -1) {
None
} else {
Some(emptyNode(v, d))
}
}
}
val in = new Scanner(System.in)
val N = in.nextInt()
val rootNode = (1 to N).foldLeft(Node.emptyNode(1, 1))((node, idx) => {
val a,b = in.nextInt()
val pair = (a,b)
node.apply(idx, pair)
})
val K = in.nextInt()
(0 until K).foldLeft(rootNode)((node, _) => {
val idx = in.nextInt()
node.swap(idx)
println(node.traverse())
node
})
}
============================================
Kindergarten Adventures
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
int *dc = calloc(n, sizeof(int));
int count = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
if (x < n) {
int start = (i+1)%n;
int end = (start-x+n)%n;
dc[start]++;
dc[end]--;
if (end <= start) count++;
}
}
int id = 0;
int val = 0;
for (int i = 0; i < n; i++) {
count += dc[i];
if (count > val) {
val = count;
id = i;
}
}
printf("%d", id+1);
free(dc);
return 0;
}
=================================================================
TEST -23
Circular Palindromes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(char *str,int *a);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
int max(int x,int y);
void update(int x,int y,int z);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
char str[1000001]={0};
int N,NN,a[2000004],tree[2000000],ans[500000],b[500000],c[500000];
int main(){
int i,j;
scanf("%d%s",&NN,str);
strncpy(str+NN,str,NN);
solve(str,a);
init(NN);
for(i=0;i<4*NN;i++)
if(a[i])
if(i%2)
update(i/2-a[i]/2,i/2+a[i]/2,a[i]);
else
update(i/2-a[i]/2,i/2+a[i]/2-1,a[i]);
for(i=0;i<NN;i++){
ans[i]=query(i);
b[i]=ans[i];
c[i]=i;
}
sort_a2(b,c,NN);
for(i=NN;i>=0;i--){
for(j=c[i];1;j=(j-1+NN)%NN)
if(ans[j]-ans[(j-1+NN)%NN]>2)
ans[(j-1+NN)%NN]=ans[j]-2;
else
break;
for(j=c[i];1;j=(j+1)%NN)
if(ans[j]-ans[(j+1)%NN]>2)
ans[(j+1)%NN]=ans[j]-2;
else
break;
}
for(i=0;i<NN;i++)
printf("%d\n",ans[i]);
return 0;
}
void solve(char *str,int *a){
char *p;
int len,R,Ri,i,j,mi;
len=strlen(str);
p=(char*)malloc(2*(len+1)*sizeof(char));
for(i=0;i<len;i++){
p[2*i]='#';
p[2*i+1]=str[i];
}
p[2*i]='#';
p[2*i+1]=0;
a[0]=R=Ri=0;
for(i=1;i<=len*2;i++)
if(i>=R){
if(p[i]!='#')
a[i]=1;
else
a[i]=0;
for(j=i+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else{
mi=2*Ri-i;
if(i+a[mi]>=R || mi==a[mi]){
a[i]=R-i;
for(j=R+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else
a[i]=a[mi];
}
free(p);
return;
}
void init( int n ){
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
void range_increment( int i, int j, int val ){
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] = max(tree[i],val);
if( j % 2 == 0 ) tree[j] = max(tree[j],val);
}
}
int query( int i ){
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans = max(ans,tree[j]);
return ans;
}
int max(int x,int y){
return (x>y)?x:y;
}
void update(int x,int y,int z){
if(z>NN){
int m=x+z/2;
if(z%2)
if(NN%2)
update(m-NN/2,m+NN/2,NN);
else
update(m-NN/2+1,m+NN/2-1,NN-1);
else
if(NN%2)
update(m-NN/2,m+NN/2-1,NN-1);
else
update(m-NN/2,m+NN/2-1,NN);
}
if(y<NN){
range_increment(0,x,z);
range_increment(y+1,NN-1,z);
}
else
range_increment(y-NN+1,x,z);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
============================================================
Similar Strings
(IN C++)
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350
using namespace std;
const int INF = 1e9;
const int N = 150031;
int n, tests;
string st;
int used[N];
int mapp[N];
vector<int> v;
int whr[N];
int pw[N];
int S[200000][15];
int maps1[200], maps2[200];
vector<int> entries[100];
int maps[4][100];
int FE[N][15];
void run_mapper(int a,int b)
{
vector<pair<int, int> > O;
for (int i = 0; i < 10; i++)
{
int whr = FE[a][i];
O.push_back(make_pair(whr, i));
}
sort(O.begin(), O.end());
for (int i = 0; i < O.size(); i++)
{
maps[b][O[i].second] = i;
}
}
int get_hash(int a, int span, int tp)
{
int res = 0;
for (int i = 0; i < 10; i++)
{
int here = S[a+span][i] - S[a][i];
here *= (maps[tp][i]+1);
here *= pw[N - a - 1];
res += here;
}
return res;
}
int lcp(int a, int b)
{
run_mapper(a, 1);
run_mapper(b, 2);
/*for (int i = 0; i < 10; i++)
{
cout << maps[1][i] << " ";
}
cout << endl;
for (int i = 0; i < 10; i++)
{
cout << maps[2][i] << " ";
}
cout << endl;
*/
int l, r;
l = 0;
r = st.size() - max(a, b);
while (l < r)
{
int mid = l + r + 1;
mid /= 2;
long long H1 = get_hash(a, mid,1);
long long H2 = get_hash(b, mid,2);
if (H1 == H2)
l = mid;
else
r = mid - 1;
}
return l;
}
bool cmp(int a, int b)
{
int Q = lcp(a, b);
if (a + Q == st.size())
return true;
if (b + Q == st.size())
return false;
int val1 = maps[1][st[a + Q]-'a'];
int val2 = maps[2][st[b + Q]-'a'];
// cout << val1 << "%%" << val2 << endl;
return val1 < val2;
}
int LL[N];
int sparse[N][20];
int Lcp(int a, int b)
{
if (a>b)
swap(a, b);
if (a == b)
return 1e9;
--b;
int q = 0;
while ((1 << q) * 2 < (b - a + 1))
++q;
return min(sparse[a][q], sparse[b - (1 << q) + 1][q]);
}
int main(){
//freopen("fabro.in","r",stdin);
//freopen("fabro.out","w",stdout);
//freopen("F:/in.txt", "r", stdin);
//freopen("F:/output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
cin >> n >> tests;
pw[0] = 1;
for (int i = 1; i < N; i++)
{
pw[i] = pw[i - 1] * 173;
}
cin >> st;
for (int i = 0; i < 10; i++)
{
FE[st.size()][i] = st.size();
}
for (int i = st.size() - 1; i >= 0; --i)
{
for (int j = 0; j < 10; j++)
{
FE[i][j] = FE[i + 1][j];
if (st[i] == j + 'a')
FE[i][j] = i;
}
}
for (int i = 0; i < st.size(); i++)
{
for (int j = 0; j < 10; j++)
{
S[i + 1][j] = S[i][j];
if (st[i] == j + 'a')
S[i + 1][j] += pw[i];
}
}
for (int i = 0; i < st.size(); i++)
{
v.push_back(i);
}
sort(v.begin(), v.end(),cmp);
for (int i = 0; i < v.size(); i++)
{
whr[v[i]] = i;
}
for (int i = 0; i+1 < v.size(); i++)
{
LL[i] = lcp(v[i], v[i + 1]);
}
for (int lev = 0; lev < 17; lev++)
{
for (int i = 0; i < v.size(); i++)
{
if (lev == 0)
sparse[i][lev] = LL[i];
else
{
sparse[i][lev] = sparse[i][lev - 1];
if (i + (1 << lev) / 2 <= st.size())
sparse[i][lev] = min(sparse[i][lev], sparse[i + (1 << lev) / 2][lev - 1]);
}
}
}
for (int i = 1; i <= tests; i++)
{
int l, r;
cin >> l >> r;
--l;
--r;
int span = r - l + 1;
int ps = whr[l];
l = ps;
r = v.size() - 1;
while (l < r)
{
int mid = l + r+1;
mid /= 2;
if (Lcp(ps,mid) >= span)
l = mid;
else
r = mid - 1;
}
int R = r;
r = ps;
l = 0;
while (l < r)
{
int mid = l + r;
mid /= 2;
if (Lcp(ps,mid) >= span)
r = mid;
else
l = mid + 1;
}
cout << R-l+1 << endl;
}
cin.get(); cin.get();
return 0;
}
=========================================================
Save Humanity
( IN C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LIM = 111111;
char t[LIM];
int n;
int sa[LIM];
int sai[LIM<<1];
ll key[LIM];
void fill_sai() {
sort(sa, sa + n, [](int i, int j) { return key[i] < key[j]; });
sai[sa[0]] = 0;
for (int i = 1; i < n; i++) {
sai[sa[i]] = key[sa[i]] == key[sa[i - 1]] ? sai[sa[i - 1]] : i;
}
}
void get_suffix_array() {
for (int i = 0; i < n; i++) {
sa[i] = i;
sai[i] = sai[i+n] = -1;
key[i] = t[i];
}
fill_sai();
for (int p = 1; p <= n; p <<= 1) {
for (int i = 0; i < n; i++) key[i] = sai[i]*(n+1LL) + sai[i + p];
fill_sai();
}
}
char v[LIM];
int tn, vn;
void precompute(int *res) {
get_suffix_array();
for (int i = 0, j = tn, k = 0; i <= j && k <= vn; k++) {
while (i <= j && t[sa[i] + k] < v[k]) res[sa[i++]] = k;
while (i <= j && t[sa[j] + k] > v[k]) res[sa[j--]] = k;
}
}
void sufcompute(int *res) {
reverse(t, t + tn);
reverse(v, v + vn);
precompute(res);
reverse(res, res + tn);
}
int P[LIM];
int S[LIM];
vector<int> solve() {
t[tn = strlen(t)] = '$';
v[vn = strlen(v)] = '%';
n = tn + 1;
vector<int> res;
if (tn >= vn) {
precompute(P);
sufcompute(S);
for (int i = 0, j = vn - 1; j < tn; i++, j++) {
if (P[i] + S[j] >= vn - 1) {
res.push_back(i);
}
}
}
return res;
}
int main() {
int z;
scanf("%d", &z);
while (z--) {
scanf("%s%s", t, v);
vector<int> res = solve();
if (res.empty()) {
puts("No Match!");
} else {
for (int i = 0; i < res.size(); i++) {
printf("%d%c", res[i], " \n"[i == res.size() - 1]);
}
}
}
}
==========================================================================
TEST -22
Ashton and String
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 100001
void merge(int*a,int*left,int*right,int left_size, int right_size);
void sort_a(int*a,int size);
void suffixSort(int n);
void LCP(int n);
char str[N]; //input
int rank[N], pos[N], lcp[N]; //output
int cnt[N], next[N]; //internal
int bh[N], b2h[N];
int main(){
char cc;
int T,n,i;
long long K,c,t,x,tt;
double xx;
scanf("%d",&T);
while(T--){
scanf("%s%lld",str,&K);
n=strlen(str);
suffixSort(n);
LCP(n);
c=0;
for(i=0;i<n;i++){
tt=c;
c+=(lcp[i]+1+n-pos[i])*(long long)(n-pos[i]-lcp[i])/2;
if(K<=c){
xx=(-1+sqrt(4*(2*(K-tt)+lcp[i]+lcp[i]*(long long)lcp[i])))/2;
x=(long long)xx;
t=K-tt-(lcp[i]+1+x)*(x-lcp[i])/2;
if(!t)
cc=str[pos[i]+x-1];
else
cc=str[pos[i]+t-1];
break;
}
}
printf("%c\n",cc);
}
return 0;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (str[left[i]] <= str[right[j]]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void suffixSort(int n){
//sort suffixes according to their first characters
int h,i,j,k;
for (i=0; i<n; ++i){
pos[i] = i;
}
sort_a(pos, n);
//{pos contains the list of suffixes sorted by their first character}
for (i=0; i<n; ++i){
bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
b2h[i] = 0;
}
for (h = 1; h < n; h <<= 1){
//{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]}
int buckets = 0;
for (i=0; i < n; i = j){
j = i + 1;
while (j < n && !bh[j]) j++;
next[i] = j;
buckets++;
}
if (buckets == n) break; // We are done! Lucky bastards!
//{suffixes are separted in buckets containing strings starting with the same h characters}
for (i = 0; i < n; i = next[i]){
cnt[i] = 0;
for (j = i; j < next[i]; ++j){
rank[pos[j]] = i;
}
}
cnt[rank[n - h]]++;
b2h[rank[n - h]] = 1;
for (i = 0; i < n; i = next[i]){
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0){
int head = rank[s];
rank[s] = head + cnt[head]++;
b2h[rank[s]] = 1;
}
}
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0 && b2h[rank[s]]){
for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0;
}
}
}
for (i=0; i<n; ++i){
pos[rank[i]] = i;
bh[i] |= b2h[i];
}
}
for (i=0; i<n; ++i){
rank[pos[i]] = i;
}
}
// End of suffix array algorithm
void LCP(int n){
int l=0,i,j,k;
for(i=0;i<n;i++){
k=rank[i];
if(!k)
continue;
j=pos[k-1];
while(str[i+l]==str[j+l])
l++;
lcp[k]=l;
if(l>0)
l--;
}
lcp[0]=0;
return;
}
-==========================================================
String Similarity
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int64_t int64;
#define MAXN 131072
char data[MAXN]; /* input */
int suf[MAXN]; /* suffix array */
int inv[MAXN]; /* inverse suffix array used during construction. */
int bounds[MAXN]; /* scratch space for updategroups. */
int nbounds; /* len(bounds) */
int n; /* strlen(data) */
int h; /* sort level during construction. */
/* bucketsort sorts data by the first byte, into suf. */
void bucketsort() {
int count[256] = {0};
int i, sum, x;
for (i = 0; i < n; i++)
count[data[i]]++;
/* make count[x] = index of first occurence of x */
sum = 0;
for (i = 0; i < 256; i++) {
x = count[i];
count[i] = sum;
sum += x;
}
for (i = 0; i < n; i++)
suf[count[data[i]]++] = i;
}
/* initgroups: ... */
void initgroups() {
int i, prev;
char ch, group;
/* label continuous same-letter groups with the same group number. */
prev = n-1;
group = data[suf[prev]];
for (i = n-1; i >= 0; i--) {
ch = data[suf[i]];
if (ch < group) {
if (prev == i+1)
suf[i+1] = -1;
group = ch;
prev = i;
}
inv[suf[i]] = prev;
if (prev == 0)
suf[0] = -1;
}
}
int cmp(const void *A, const void *B) {
int sufi, sufj;
sufi = *((int *)A);
sufj = *((int *)B);
if (inv[sufi + h] < inv[sufj + h])
return -1;
if (inv[sufi + h] > inv[sufj + h])
return 1;
return 0;
}
/* updategroups: ... */
void updategroups(int lo, int hi) {
int i, j, g, group, prev;
nbounds = 0;
group = inv[suf[lo] + h];
for (i = lo+1; i < hi; i++) {
g = inv[suf[i] + h];
if (g > group) {
bounds[nbounds++] = i;
group = g;
}
}
bounds[nbounds++] = hi;
prev = lo;
for (i = 0; i < nbounds; i++) {
for (j = prev; j < bounds[i]; j++)
inv[suf[j]] = bounds[i]-1;
if (bounds[i] - prev == 1)
suf[prev] = -1;
prev = bounds[i];
}
}
/* suffixsort computes the suffix array for data. */
void suffixsort() {
int i, pi, pk, s, sl;
bucketsort();
initgroups();
h = 1; /* the index starts 1-sorted */
while (suf[0] > -n) { /* while not single sorted group */
pi = 0; /* pi is first position of group */
sl = 0; /* sl is negated length of sorted groups */
while (pi < n) {
s = suf[pi];
if (s < 0) { /* pi starts a sorted group */
pi -= s;
sl += s;
} else { /* pi starts an unsorted group */
if (sl != 0) {
suf[pi + sl] = sl; /* combine sorted groups before pi */
sl = 0;
}
pk = inv[s] + 1; /* pk-1 is last position of unsorted group */
// sortsplit(pi, pk);
qsort(suf+pi, pk-pi, sizeof suf[0], cmp);
updategroups(pi, pk);
pi = pk; /* next group */
}
}
if (sl != 0) { /* if the array ends with a sorted group */
suf[pi + sl] = sl; /* combine sorted groups at end */
}
h *= 2;
}
/* reconstruct suffix array from inverse */
for (i = 0; i < n; i++)
suf[inv[i]] = i;
}
/* similarity computes the sum of all suffix matches to data. */
int64 similarity() {
int a, b, i, j, k, mid;
int64 sum;
a = 0;
b = n;
sum = 0;
for (k = 0; data[k] != '$'; k++) {
/* find the first index where data[0..k] would be the prefix */
i = a;
j = b;
while (i < j) {
mid = (i + j) / 2;
if (data[suf[mid] + k] < data[k])
i = mid + 1;
else
j = mid;
}
a = i;
/* starting at a, find the first index at which data[0..k] is not the prefix */
i = a;
j = b;
while (i < j) {
mid = (i + j) / 2;
if (data[suf[mid] + k] <= data[k])
i = mid + 1;
else
j = mid;
}
b = i;
sum += (b - a);
}
return sum;
}
int64 naive() {
int64 sum;
int i, j, k;
sum = 0;
for (i = 0; i < n-1; i++) {
for (j = i, k = 0; j < n-1; j++, k++)
if (data[j] == data[k])
sum++;
else
break;
}
return sum;
}
int main() {
int ncases;
char buf[100];
fgets(buf, sizeof buf, stdin);
ncases = atoi(buf);
while (ncases-- > 0) {
fgets(data, sizeof data, stdin);
n = strlen(data);
if (n > 0 && data[n-1] == '\n')
data[--n] = '\0';
assert(n <= 100000);
if (n == 0) {
printf("0\n");
continue;
}
if (n == 1) {
printf("1\n");
continue;
}
data[n++] = '$';
data[n] = '\0';
suffixsort();
printf("%lld\n", similarity());
}
return 0;
}
=============================================================
Super Functional Strings
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
#define MOD 1000000007
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
void print(st_node *root,int len);
void suffix_tree(st_node *root,char *str,int len);
long long modPow(long long a,int x);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
char str[100001];
int dp[100000][26];
long long ans,pows[26][100001];
int main(){
int T,len,i,j;
st_node root;
for(i=0;i<26;i++)
for(j=1;j<=100000;j++)
pows[i][j]=(pows[i][j-1]+modPow(j,i+1))%MOD;
scanf("%d",&T);
while(T--){
scanf("%s",str);
len=strlen(str);
for(i=0;i<26;i++)
dp[len-1][i]=-1;
dp[len-1][str[len-1]-MIN_C]=len-1;
for(i=len-2;i>=0;i--){
memcpy(&dp[i][0],&dp[i+1][0],26*sizeof(int));
dp[i][str[i]-MIN_C]=i;
}
suffix_tree(&root,str,len);
ans=0;
print(&root,0);
printf("%lld\n",ans);
}
return 0;
}
void print(st_node *root,int len){
int i,j,idx,from,to,s,dc,last,t,a[26];
if(!root)
return;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
idx=root->edges[i]->suffix_index;
from=idx+len;
to=idx+len+root->edges[i]->to-root->edges[i]->from;
s=dc=0;
last=idx+len-1;
for(j=0;j<26;j++)
if(dp[idx][j]!=-1 && dp[idx][j]<from)
dc++;
else if(dp[idx][j]>=from && dp[idx][j]<=to)
a[s++]=dp[idx][j];
sort_a(a,s);
for(j=0;j<s;j++,dc++){
t=a[j]-1;
if(dc)
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
last=t;
}
t=to;
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
print(root->edges[i]->node,len+root->edges[i]->to-root->edges[i]->from+1);
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<=len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[a_edge]->from+a_len]==str[i])
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}
long long modPow(long long a,int x){
long long res = 1;
while(x>0){
if(x%2)
res=(res*a)%MOD;
a=(a*a)%MOD;
x>>=1;
}
return res;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
====================================================================
TEST -21 CLICK HERE TO ENTER INTO TEST - 21
Build a Palindrome
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#define SWAP(_X, _Y, __type) \
do { \
__type __tmp = _X; \
_X = _Y; \
_Y = __tmp; \
} while (0)
#define MAX(__X, __Y) ((__X) > (__Y) ? (__X) : (__Y))
#define MIN(__X, __Y) ((__X) < (__Y) ? (__X) : (__Y))
struct interval {
int mid;
int odd;
int begin;
int end;
};
int icmp(const void *p1, const void *p2)
{
const struct interval *i1 = p1;
const struct interval *i2 = p2;
if (i1->begin < i2->begin) {
return -1;
} else if (i1->begin > i2->begin) {
return 1;
}
return 0;
}
int *_find_longest_palindromes(int *radius[2], int len)
{
int *result;
struct interval *intervals;
int num_intervals = 0;
result = malloc(sizeof(*result) * len);
for (int i = 0; i < len; ++i) {
result[i] = 1;
}
intervals = malloc(sizeof(*intervals) * len * 2);
for (int j = 0; j < 2; ++j) {
for (int i = 0; i < len; ++i) {
if (radius[j][i] != 0) {
intervals[num_intervals].odd = j;
intervals[num_intervals].mid = i;
intervals[num_intervals].begin = intervals[num_intervals].mid - radius[j][i];
intervals[num_intervals].end = intervals[num_intervals].mid - 1;
++num_intervals;
}
}
}
if (num_intervals > 0) {
int _num_intervals = 1;
/* Sort and merge palindrome intervals */
qsort(intervals, num_intervals, sizeof(*intervals), icmp);
for (int i = 1; i < num_intervals; ++i) {
if (intervals[_num_intervals - 1].end < intervals[i].begin) {
intervals[_num_intervals++] = intervals[i];
} else if (intervals[_num_intervals - 1].end <= intervals[i].end) {
if (intervals[i].begin == intervals[_num_intervals - 1].begin &&
(intervals[_num_intervals - 1].end < intervals[i].end || intervals[i].odd)) {
intervals[_num_intervals - 1] = intervals[i];
} else {
intervals[_num_intervals - 1].end = intervals[i].begin - 1;
intervals[_num_intervals++] = intervals[i];
}
}
}
num_intervals = _num_intervals;
}
/* Convert intervals into result format */
for (int i = 0; i < num_intervals; ++i) {
for (int j = intervals[i].begin; j <= intervals[i].end; ++j) {
result[j] = 2 * (intervals[i].mid - j) + intervals[i].odd;
}
}
free(intervals);
return result;
}
/* Calculate array A, where A[i] is euqal to length of longest possible
palindrome substring of s, that begins from i-position. O(n * log(n))
*/
int* find_longest_palindromes(const char *s, int len)
{
int *result;
int *radius[2]; /* matrix with palindrome radius for even and odd length palindromes */
radius[0] = malloc(sizeof(int) * len);
radius[1] = malloc(sizeof(int) * len);
radius[0][0] = radius[1][0] = 0;
for (int j = 0; j < 2; ++j) {
int i = 1;
int r = 0;
while (i < len) {
int k = 1;
if (s[i] != 0x60) {
for (register int left = i - r - 1, right = i + r + j;
left >= 0 && right < len && s[left] == s[right];
--left, ++right, ++r);
radius[j][i] = r;
} else {
radius[j][i] = r = 0;
}
while (k < r && radius[j][i - k] != r - k) {
radius[j][i + k] = MIN(radius[j][i - k], r - k);
++k;
}
r = r > k ? r - k : 0;
i += k;
}
}
result = _find_longest_palindromes(radius, len);
free(radius[0]);
free(radius[1]);
return result;
}
/* longest common prefix array, O(n) */
int * LCP(const char *s, int len, int *sa)
{
int k = 0;
int *lcp, *rank;
lcp = calloc(len, sizeof(*lcp));
rank = calloc(len, sizeof(*rank));
for (int i = 0; i < len; ++i) {
rank[sa[i]] = i;
}
for (int i = 0; i < len; ++i) {
if (rank[i] == len - 1) {
k = 0;
} else {
int j = sa[rank[i] + 1];
while(i + k < len && j + k < len && s[i + k] == s[j + k]) k++;
lcp[rank[i]]=k;
}
if (k != 0) {
--k;
}
}
free(rank);
return lcp;
}
struct state {
int suffix; /* suffix number */
int bucket[2]; /* sorted position of first and second H symbols */
};
/* Suffix array calculation. O(n * log(n)) */
int * SA(const char *s, int len)
{
/* positions of already sorted suffixes */
int *p = malloc(sizeof(int) * len);
/* result suffix array */
int *sa = malloc(sizeof(int) * len);
/* state for radix sort and temporary buffer for radix sort */
struct state *state, *tmp;
state = malloc(sizeof(*state) * len);
tmp = malloc(sizeof(*tmp) * len);
for (int i = 0; i < len; ++i) {
p[i] = s[i] - 0x60 + 1;
}
for (int h = 1; h < len; h <<= 1) {
for (int i = 0; i < len; ++i) {
state[i].suffix = i; /* suffix number */
state[i].bucket[0] = p[i]; /* sorted position of first H symbols */
if (i + h < len) {
state[i].bucket[1] = p[i + h];
} else {
state[i].bucket[1] = 0;
}
}
/* radix sort state array */
for (int i = 1; i >= 0; --i) {
for (int div = 1; MAX(len, 28) / div > 0; div *= 10) {
int count[10] = {0};
for (int j = 0; j < len; ++j) {
++count[(state[j].bucket[i] / div) % 10];
}
for (int j = 1; j < 10; ++j) {
count[j] += count[j - 1];
}
/* store radix sort result into temporary array */
for (int j = len - 1; j >= 0; --j) {
register int index = (state[j].bucket[i] / div) % 10;
tmp[--count[index]] = state[j];
}
SWAP(tmp, state, struct state *);
}
}
/* Write calculated index into p */
for (int i = 0, bucket = 0; i < len; ++i) {
if ((h << 1) >= len || /* Do not group the bucket if we produce result aray*/
i == 0 ||
state[i - 1].bucket[0] != state[i].bucket[0] ||
state[i - 1].bucket[1] != state[i].bucket[1]) {
++bucket;
}
p[state[i].suffix] = bucket;
}
}
free(state);
free(tmp);
for (int i = 0; i < len; ++i) {
sa[p[i] - 1] = i;
}
free(p);
return sa;
}
char *build_palindrome(const char *a, const char *b)
{
int alen = strlen(a);
int blen = strlen(b);
int *sa, *lcp, *p, *lcp_ab;
int maxlen = 0;
int suffix = -1;
char *result = NULL;
/* build string <a>$<reversed b> */
int slen = alen + blen + 1;
char *s = malloc(sizeof(char) * (slen + 1));
memcpy(s, a, alen);
s[alen] = 0x60;
for (int i = 0; i < blen; ++i) {
s[alen + 1 + i] = b[blen - 1 - i];
}
s[slen] = '\0';
/* calculate suffix array and LCP array */
sa = SA(s, slen);
lcp = LCP(s, slen, sa);
/* calculate LCP between A and B substings */
lcp_ab = calloc(slen, sizeof(*lcp_ab));
{
int i = 1;
while (i < slen - 1) {
/* if current LCP[i] is a non-zero common lenght between A and B substrings */
if (lcp[i] && ((sa[i] > alen && sa[i + 1] < alen) || (sa[i] < alen && sa[i + 1] > alen))) {
int j;
int current = lcp[i];
for (j = i; j > 0 && ((sa[i] > alen) ? (sa[j] > alen) : (sa[j] < alen)) && lcp[j] > 0; --j) {
current = MIN(current, lcp[j]);
lcp_ab[j] = MAX(lcp_ab[j], current);
}
current = lcp[i];
for (j = i + 1; j < slen && ((sa[i] > alen) ? (sa[j] < alen) : (sa[j] > alen)) && lcp[j - 1] > 0; ++j) {
lcp_ab[j] = current = MIN(current, lcp[j - 1]);
}
assert(j - 2 >= i);
i = j - 1;
} else {
++i;
}
}
}
/* calculate longest palindromes array */
p = find_longest_palindromes(s, slen);
for (int i = 1; i < slen; ++i) {
if (lcp_ab[i]) {
int len = 2 * lcp_ab[i];
if ((sa[i] < alen && sa[i] + lcp_ab[i] < alen) ||
(sa[i] > alen && sa[i] + lcp_ab[i] < slen)) {
len += p[sa[i] + lcp_ab[i]];
}
if (len > maxlen) {
suffix = i;
maxlen = len;
}
}
}
if (maxlen) {
int len = 0;
result = malloc(sizeof(*result) * (maxlen + 1));
memcpy(result, s + sa[suffix], lcp_ab[suffix]);
if (maxlen > lcp_ab[suffix] * 2) {
memcpy(result + lcp_ab[suffix], s + sa[suffix] + lcp_ab[suffix], maxlen - lcp_ab[suffix] * 2);
}
for (int i = 0; i < lcp_ab[suffix]; ++i) {
result[maxlen - lcp_ab[suffix] + i] = s[sa[suffix] + lcp_ab[suffix] - 1 - i];
}
result[maxlen] = '\0';
}
free(sa);
free(lcp);
free(lcp_ab);
free(p);
free(s);
return result;
}
int main()
{
int n;
scanf("%d", &n);
while (n-- != 0) {
char *a, *b, *p;
a = malloc(131072 * sizeof(*a));
b = malloc(131072 * sizeof(*b));
scanf("%s", a);
scanf("%s", b);
p = build_palindrome(a, b);
if (p == NULL) {
printf("-1\n");
} else {
printf("%s\n", p);
}
free(p);
free(a);
free(b);
}
return 0;
}
==================================================================
Build a String
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char s[30001];
int sublens[30001] = { 0 };
void longestsubstr(int pos) {
int i, max = 0;
for (i = 0; i < pos; i++) {
if (s[i] != s[pos]) sublens[i] = 0;
else {
sublens[i] = sublens[i+1] + 1;
if (i + sublens[i] > pos) sublens[i] = pos - i;
if (sublens[i] > max) max = sublens[i];
}
}
sublens[pos] = max;
}
int main() {
int t, t1;
scanf("%d", &t);
for (t1 = 0; t1 < t; t1++) {
int n, a, b, sublen, i, j, temp;
scanf("%d %d %d", &n, &a, &b);
scanf("%s", s);
int ar[30001];
for (i = 0; i < n; i++) {
ar[i] = 0x7FFFFFFF;
sublens[i] = 0;
}
for (i = n - 1; i >= 1; i--) longestsubstr(i);
ar[0] = a;
for (i = 1; i < n; i++) {
if (ar[i-1] + a < ar[i]) ar[i] = ar[i-1] + a;
sublen = sublens[i];
temp = ar[i-1] + b;
for (j = 0; j < sublen; j++) if (temp < ar[i+j]) ar[i+j] = temp;
}
printf("%d\n", ar[n-1]);
}
return 0;
}
==================================================
Gridland Provinces
#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],bl1[1200],dr1[1200],dl1[1200],ur1[1200],ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],bl2[1200],dr2[1200],dl2[1200],ur2[1200],ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};
int main(){
int T,i,j;
long long t1,t2;
scanf("%d",&T);
while(T--){
hash_count=0;
scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i){
tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
}
else{
tl1[i]=a[0][i]-'a';
bl1[i]=a[1][i]-'a';
tl2[i]=a[0][i]-'a';
bl2[i]=a[1][i]-'a';
}
for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i!=N-1){
tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
}
else{
tr1[N-i-1]=a[0][i]-'a';
br1[N-i-1]=a[1][i]-'a';
tr2[N-i-1]=a[0][i]-'a';
br2[N-i-1]=a[1][i]-'a';
}
for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
}
for(i=0,t1=t2=1;i<N;i++){
if(i%2){
ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
else
if(!i){
ul1[2*i]=a[1][i]-'a';
dl1[2*i]=a[0][i]-'a';
ul2[2*i]=a[1][i]-'a';
dl2[2*i]=a[0][i]-'a';
}
else{
ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if(i%2){
ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
}
else{
ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--)
if(i==N-1){
ur1[2*(N-1-i)]=a[1][i]-'a';
dr1[2*(N-1-i)]=a[0][i]-'a';
ur2[2*(N-1-i)]=a[1][i]-'a';
dr2[2*(N-1-i)]=a[0][i]-'a';
t1=t1*26%MOD1;
t2=t2*26%MOD2;
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
else{
if((N-i)%2==0){
ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
else{
ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if((N-i)%2==0){
ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
else{
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=0;i<=2*N;i++)
if(i){
mod1[i]=mod1[i-1]*26%MOD1;
inmod1[i]=modInverse(mod1[i],MOD1);
mod2[i]=mod2[i-1]*26%MOD2;
inmod2[i]=modInverse(mod2[i],MOD2);
}
else
mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
for(i=0;i<=N;i++)
for(j=i;j<=N;j++)
solve(i,j);
printf("%d\n",hash_count);
freehash();
}
return 0;
}
void solve(int i,int j){
long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
t1=tr1[N+i-1];
t2=br1[N+i-1];
if(i!=N){
t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
t2=(t2-br1[N-i-1]+MOD1)%MOD1;
}
t1=t1*inmod1[N-i]%MOD1;
t2=t2*inmod1[N-i]%MOD1;
t3=tl1[2*N-j-1];
t4=bl1[2*N-j-1];
if(j){
t3=(t3-tl1[j-1]+MOD1)%MOD1;
t4=(t4-bl1[j-1]+MOD1)%MOD1;
}
t3=t3*inmod1[j]%MOD1;
t4=t4*inmod1[j]%MOD1;
if(!j)
t5=t6=0;
else{
t5=ul1[2*j-1];
t6=dl1[2*j-1];
if(i){
t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
}
}
if(i==N)
t7=t8=0;
else{
t7=ur1[2*(N-i)-1];
t8=dr1[2*(N-i)-1];
if(j!=N){
t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
}
}
tt1=tr2[N+i-1];
tt2=br2[N+i-1];
if(i!=N){
tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
}
tt1=tt1*inmod2[N-i]%MOD2;
tt2=tt2*inmod2[N-i]%MOD2;
tt3=tl2[2*N-j-1];
tt4=bl2[2*N-j-1];
if(j){
tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
}
tt3=tt3*inmod2[j]%MOD2;
tt4=tt4*inmod2[j]%MOD2;
if(!j)
tt5=tt6=0;
else{
tt5=ul2[2*j-1];
tt6=dl2[2*j-1];
if(i){
tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
}
}
if(i==N)
tt7=tt8=0;
else{
tt7=ur2[2*(N-i)-1];
tt8=dr2[2*(N-i)-1];
if(j!=N){
tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
}
}
t9=t1;
if(i%2)
t9+=t6;
else
t9+=t5;
if((j-i)%2)
t9+=t3*mod1[j*2]%MOD1;
else
t9+=t4*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt1;
if(i%2)
tt9+=tt6;
else
tt9+=tt5;
if((j-i)%2)
tt9+=tt3*mod2[j*2]%MOD2;
else
tt9+=tt4*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t2;
if(i%2)
t9+=t5;
else
t9+=t6;
if((j-i)%2)
t9+=t4*mod1[j*2]%MOD1;
else
t9+=t3*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt2;
if(i%2)
tt9+=tt5;
else
tt9+=tt6;
if((j-i)%2)
tt9+=tt4*mod2[j*2]%MOD2;
else
tt9+=tt3*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t3;
if((N-j)%2)
t9+=t8;
else
t9+=t7;
if((j-i)%2)
t9+=t1*mod1[(N-i)*2]%MOD1;
else
t9+=t2*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt3;
if((N-j)%2)
tt9+=tt8;
else
tt9+=tt7;
if((j-i)%2)
tt9+=tt1*mod2[(N-i)*2]%MOD2;
else
tt9+=tt2*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t4;
if((N-j)%2)
t9+=t7;
else
t9+=t8;
if((j-i)%2)
t9+=t2*mod1[(N-i)*2]%MOD1;
else
t9+=t1*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt4;
if((N-j)%2)
tt9+=tt7;
else
tt9+=tt8;
if((j-i)%2)
tt9+=tt2*mod2[(N-i)*2]%MOD2;
else
tt9+=tt1*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
return;
}
void insert(int x,int y){
int bucket=(x+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return;
t=t->next;
}
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
hash_count++;
return;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<HASH_SIZE;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
hash[i]=NULL;
}
return;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
===========================================
TEST-20
Morgan and a String
#include <stdio.h>
#include <string.h>
int is_a(const char* a, const char* b) {
while (*a && *b) {
if (*a == *b) {
a++;
b++;
} else {
return *a < *b;
}
}
return *a != 0;
}
void merge(const char* a, const char* b, char* c) {
int is_a_preferred = is_a(a, b);
while (*a && *b) {
if (*a == *b) {
*c = (is_a_preferred)? *(a++) : *(b++);
} else {
*c = (*a < *b)? *(a++) : *(b++);
is_a_preferred = is_a(a, b);
}
++c;
}
while (*a) {
*c++ = *a++;
}
while (*b) {
*c++ = *b++;
}
*c = '\0';
}
int main() {
int t;
char a[100001];
char b[100001];
char c[200001];
scanf("%d", &t);
while (t--) {
scanf("%s\n%s", a, b);
merge(a, b, c);
printf("%s\n", c);
}
}
=======================================================================
Count Strings
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef struct _node{
struct _node *next;
int x;
int y;
struct _node *stack_pointer;
}node;
typedef struct _set{
int size;
int *list;
int d;
int index;
}set;
typedef struct _tree_node{
enum {red,black} colour;
set *data;
struct _tree_node *left,*right,*parent;
}tree_node;
void sort_a(int *a,int size,int *new_size);
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size);
void sort_a2(int *a,int *b,int *c,int size);
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size);
void addPlus(char *str);
int read_x(node *head);
node *read_stack_pointer(node *head);
void push(node **head,node *elem);
node *pop(node **head);
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag);
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_left(node *b_stack,node **c_stack);
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_plus(node **a_stack,int *size,int *u,int *v,int *o);
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
int find(int *list,int size,int x);
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag);
int compare_set(set *set1,set *set2);
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev);
int search(tree_node *root,set *x);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
void insert(tree_node **root,tree_node *x);
void clean_tree(tree_node *root);
void clean_set(set **set_list,int n_node_counter);
void one(long long *a,int SIZE,int SIZE2);
void mul(long long *a,long long *b,int SIZE,int SIZE2);
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2);
int main(){
int T,L,i,j,node_counter,*u,*v,*o,*d,size,n_node_counter,*n_u,*n_v,n_size,*index,first_node;
char str[300];
node *a_stack,*b_stack,*c_stack,*last_node;
set **set_list,*first_set;;
tree_node *root;
long long temp[400][400],ans[400][400],f;
u=(int*)malloc(1000*sizeof(int));
v=(int*)malloc(1000*sizeof(int));
o=(int*)malloc(1000*sizeof(int));
d=(int*)malloc(2000*sizeof(int));
n_u=(int*)malloc(1000*sizeof(int));
n_v=(int*)malloc(1000*sizeof(int));
index=(int*)malloc(2000*sizeof(int));
set_list=(set**)malloc(400000*sizeof(set*));
scanf("%d",&T);
while(T--){
scanf("%s%d",str,&L);
addPlus(str);
a_stack=b_stack=c_stack=NULL;
root=NULL;
node_counter=size=n_node_counter=n_size=0;
for(i=0;str[i]!='\0';i++)
switch(str[i]){
case 'a': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,0); break;
case 'b': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,1); break;
case '*': process_star(&a_stack,&node_counter,&size,u,v,o,d); break;
case '+': hit_plus(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '|': hit_pip(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '(': hit_left(b_stack,&c_stack); break;
case ')': hit_right(&a_stack,&b_stack,&c_stack,&node_counter,&size,u,v,o,d); break;
default: break;
}
while(b_stack){
i=read_x(b_stack);
if(!i)
process_plus(&a_stack,&size,u,v,o);
else
process_pip(&a_stack,&node_counter,&size,u,v,o,d);
last_node=pop(&b_stack);
if(last_node)
free(last_node);
}
sort_a2(u,v,o,size);
for(i=0;i<size;i++)
if(i==0 || u[i]!=u[i-1])
index[u[i]]=i;
first_node=read_x(a_stack);
last_node=pop(&a_stack);
if(last_node)
free(last_node);
first_set=(set*)malloc(sizeof(set));
first_set->list=(int*)malloc(sizeof(int));
first_set->size=1;
first_set->list[0]=first_node;
run(set_list,&n_node_counter,&n_size,n_u,n_v,node_counter,size,u,v,o,d,index,first_set,&root,NULL);
clean_tree(root);
for(i=0;i<n_node_counter;i++)
for(j=0;j<n_node_counter;j++)
temp[i][j]=0;
for(i=0;i<n_size;i++)
temp[n_u[i]][n_v[i]]++;
pown(&temp[0][0],L,&ans[0][0],n_node_counter,400);
for(i=0,f=0;i<n_node_counter;i++)
if(set_list[i]->d)
f=(f+ans[0][set_list[i]->index])%MOD;
printf("%lld\n",f);
clean_set(set_list,n_node_counter);
}
return 0;
}
void sort_a(int *a,int size,int *new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int left[m],right[size-m];
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
int new_l_size=0,new_r_size=0;
sort_a(left,m,&new_l_size);
sort_a(right,size-m,&new_r_size);
merge(a,left,right,new_l_size,new_r_size,new_size);
return;
}
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[index++] = right[j];
j++;
} else if (j == right_size) {
a[index++] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[index++] = left[i];
i++;
} else {
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
index--;
}
(*new_size)=index;
return;
}
void sort_a2(int *a,int *b,int *c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a2(left_a,left_b,left_c,m);
sort_a2(right_a,right_b,right_c,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size || j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void addPlus(char *str){
int i,j,len;
len=strlen(str);
for(i=0;i<len-1;i++)
if(str[i]!='(' && str[i]!='|' && str[i+1]!='|' && str[i+1]!='*' && str[i+1]!=')'){
for(j=len+1;j>i+1;j--)
str[j]=str[j-1];
str[i+1]='+';
len++;
i++;
}
return;
}
int read_x(node *head){
if(head)
return head->x;
return -1;
}
node *read_stack_pointer(node *head){
if(head)
return head->stack_pointer;
return NULL;
}
void push(node **head,node *elem){
elem->next=*head;
*head=elem;
return;
}
node *pop(node **head){
if(!(*head))
return NULL;
node *elem=*head;
*head=(*head)->next;
return elem;
}
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag){
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=flag+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
node *new=(node*)malloc(sizeof(node));
new->x=*node_counter;
new->y=(*node_counter)+1;
push(a_stack,new);
(*size)++;
(*node_counter)+=2;
return;
}
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(op==0 && *b_stack!=end){
process_plus(a_stack,size,u,v,o);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=0;
push(b_stack,new);
return;
}
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=1;
push(b_stack,new);
return;
}
void hit_left(node *b_stack,node **c_stack){
node *new=(node*)malloc(sizeof(node));
new->stack_pointer=b_stack;
push(c_stack,new);
return;
}
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(*c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
trash=pop(c_stack);
if(trash)
free(trash);
return;
}
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
return;
}
void process_plus(node **a_stack,int *size,int *u,int *v,int *o){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=b->x,tail=a->y;
u[*size]=b->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=b->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=b->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
int find(int *list,int size,int x){
int i;
for(i=0;i<size;i++)
if(x==list[i])
return 1;
return 0;
}
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag){
int i,j,run_flag=0,start=0,end=old_set->size,small_run_flag;
set *ans=(set*)malloc(sizeof(set));
ans->list=(int*)malloc(node_counter*4*sizeof(int));
ans->size=0;
ans->d=0;
ans->index=old_set->index;
if(!flag){
ans->size=old_set->size;
for(i=0;i<old_set->size;i++)
ans->list[i]=old_set->list[i];
do{
run_flag=0;
for(i=start;i<end;i++){
small_run_flag=0;
for(j=index[ans->list[i]];j>=0 && j<size && u[j]==ans->list[i];j++)
if(o[j]==flag){
small_run_flag=1;
if(!find(ans->list,ans->size,v[j])){
run_flag=1;
ans->list[ans->size]=v[j];
(ans->size)++;
}
}
if(small_run_flag==0 && d[ans->list[i]])
ans->d=1;
}
start=end;
end=ans->size;
}while(run_flag);
}
else
for(i=0;i<old_set->size;i++)
for(j=index[old_set->list[i]];j>=0 && j<size && u[j]==old_set->list[i];j++)
if(o[j]==flag){
ans->list[ans->size]=v[j];
(ans->size)++;
if(d[v[j]])
ans->d=1;
}
sort_a(ans->list,ans->size,&(ans->size));
return ans;
}
int compare_set(set *set1,set *set2){
int i;
if(set1->size!=set2->size)
return set1->size-set2->size;
if(set1->d!=set2->d)
return set1->d-set2->d;
for(i=0;i<set1->size;i++)
if(set1->list[i]!=set2->list[i])
return set1->list[i]-set2->list[i];
return 0;
}
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev){
set *new_set=move(node_counter,size,u,v,o,d,index,run_set,0),*new_seta,*new_setb;
free(run_set->list);
free(run_set);
tree_node *new_tree_node;
int i=search(*root,new_set);
if(i==-1){
set_list[*n_node_counter]=new_set;
new_set->index=*n_node_counter;
if(prev)
*prev=*n_node_counter;
(*n_node_counter)++;
new_tree_node=(tree_node*)malloc(sizeof(tree_node));
new_tree_node->left=new_tree_node->right=new_tree_node->parent=NULL;
new_tree_node->data=new_set;
insert(root,new_tree_node);
new_seta=move(node_counter,size,u,v,o,d,index,new_set,1);
if(new_seta->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_seta,root,n_v+(*n_size)-1);
}
new_setb=move(node_counter,size,u,v,o,d,index,new_set,2);
if(new_setb->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_setb,root,n_v+(*n_size)-1);
}
}
else
if(prev)
*prev=i;
return;
}
int search(tree_node *root,set *x){
if(!root)
return -1;
if(compare_set(root->data,x)==0)
return root->data->index;
if(compare_set(root->data,x)>0)
return search(root->left,x);
return search(root->right,x);
}
void left_rotate(tree_node **root,tree_node *x){
tree_node *y;
y=x->right;
if(!y) return;
x->right=y->left;
if(y->left)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==NULL) *root=y;
else
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
return;
}
void right_rotate(tree_node **root,tree_node *y){
tree_node *x;
x=y->left;
if(!x) return;
y->left=x->right;
if(x->right)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NULL) *root=x;
else
if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
return;
}
void reconstruct(tree_node **root,tree_node *x){
tree_node *y,*z;
y=x->parent;
z=x->parent->parent;
x->colour=black;
z->colour=red;
x->parent=z->parent;
if(z->parent==NULL)
*root=x;
else if(z==z->parent->left)
z->parent->left=x;
else
z->parent->right=x;
if(z->left==y){
x->left=y;
x->right=z;
}
else{
x->left=z;
x->right=y;
}
y->parent=z->parent=x;
y->left=y->right=z->left=z->right=NULL;
return;
}
int normal_insert(tree_node **root,tree_node *x){
if(*root==NULL)
*root=x;
else if(compare_set((*root)->data,x->data)==0)
return 0;
else{
x->parent=*root;
if(compare_set((*root)->data,x->data)>0)
return normal_insert(&((*root)->left),x);
else
return normal_insert(&((*root)->right),x);
}
return 1;
}
void insert(tree_node **root,tree_node *x){
if(!normal_insert(root,x))
return;
tree_node *y;
x->colour=red;
while(x!=*root && x->parent->colour==red){
if(x->parent==x->parent->parent->left){
y=x->parent->parent->right;
if(!y)
if(x==x->parent->left){
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->right){
x=x->parent;
left_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
}
else{
y=x->parent->parent->left;
if(!y)
if(x==x->parent->right){
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->left){
x=x->parent;
right_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
}
}
(*root)->colour=black;
return;
}
void clean_tree(tree_node *root){
if(!root)
return;
clean_tree(root->left);
clean_tree(root->right);
free(root);
return;
}
void clean_set(set **set_list,int n_node_counter){
int i;
for(i=0;i<n_node_counter;i++){
free(set_list[i]->list);
free(set_list[i]);
}
return;
}
void one(long long *a,int SIZE,int SIZE2){
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=(i==j);
return;
}
void mul(long long *a,long long *b,int SIZE,int SIZE2){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
res[i][j]=0;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
for(k=0;k<SIZE;k++)
res[i][j]=(res[i][j]+(a[i*SIZE2+k]*b[k*SIZE2+j])%MOD)%MOD;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=res[i][j];
return;
}
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2){
one(res,SIZE,SIZE2);
while(n>0){
if(n%2==0){
mul(a,a,SIZE,SIZE2);
n/=2;
}
else{
mul(res,a,SIZE,SIZE2);
n--;
}
}
return;
}
=======================================================================
String Function Calculation
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAXN 100000+2
char str[MAXN];
int sa[MAXN];
int rank[MAXN];
int cnt[MAXN];
int wb[MAXN];
int wv[MAXN];
int height[MAXN];
int stack[MAXN];
inline int max(int a, int b) {
return a > b? a : b;
}
int cmp(int *r, int a, int b, int k) {
return r[a] == r[b] && r[a+k] == r[b+k];
}
void gen_sa(char *str, int n, int *sa, int *rank) {
int m = 128, p;
int i, j, k;
int *x, *y, *t;
x = rank; y = wb;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) ++ cnt[x[i] = str[i]];
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[x[i]]] = i;
for (k = 1; k <= n; k = k << 1) {
for (p = 0, i = n-k; i < n; ++ i) y[p++] = i;
for (i = 0; i < n; ++ i) if (sa[i] >= k) y[p++] = sa[i] - k;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) {
wv[i] = x[y[i]];
++ cnt[wv[i]];
}
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[wv[i]]] = y[i];
t = x; x = y; y = t;
x[sa[0]] = 0;
for (p = 1, i = 0; i < n; ++ i) {
x[sa[i]] = cmp(y, sa[i], sa[i-1], k) ? p-1: p++;
}
m = p;
}
if (x != rank) memcpy(rank, x, sizeof(int)*n);
}
void gen_height(char *str, int n, int *sa, int *rank, int *height) {
int i, j, k;
height[0] = 0;
k = 0;
for (i = 0; i < n-1; ++ i) {
if (k) -- k;
j = rank[i]-2;
if (j == -1) continue;
for (j = sa[j]; str[i+k] == str[j+k]; ) {
++ k;
}
height[rank[i]-1] = k;
}
}
int max_rectangle(int *height, int n) {
int i, j, left, right, cur, top = -1;
int result = 0;
height[n] = 0;
stack[++top] = 0;
for (i = 0; i <= n; ++ i) {
while (top > -1 && height[i] < height[stack[top]]) {
cur = stack[top--];
left = (top > -1? cur-stack[top]: cur+1) * height[cur];
right = (i - cur - 1) * height[cur];
result = max(result, left+right+height[cur]);
}
stack[++top] = i;
}
return max(result, n-1);
}
int main() {
int n, result;
scanf("%s", str);
n = strlen(str);
gen_sa(str, n+1, sa, rank);
gen_height(str, n+1, sa, rank, height);
result = max_rectangle(height, n+1);
printf("%d\n", result);
return 0;
}
=============================
TEST -19
Sherlock and Anagrams
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
long long int t,len,length,start,start2,cnt1[26],cnt2[26],flag,ans,i,j;
char str[200];
scanf("%lld",&t);
while(t--)
{
scanf("%s",str);
len=strlen(str);
ans=0;
for(length=1;length<len;length++)
{
//printf("%lld ",length);
for(start=0;start+length<len;start++)
{
//printf("%lld %lld\n",length,start);
for(i=0;i<26;i++)
cnt1[i]=0;
for(i=start;i<start+length;i++)
cnt1[str[i]-'a']++;
//printf("%lld %lld %lld %lld\n",start,length,cnt1[0],cnt1[1]);
for(start2=start+1;start2+length<=len;start2++)
{
for(j=0;j<26;j++)
cnt2[j]=0;
for(j=start2;j<start2+length;j++)
cnt2[str[j]-'a']++;
flag=1;
//printf("%lld %lld %lld\n",start,start2,length);
for(j=0;j<26;j++)
if(cnt1[j]!=cnt2[j])
flag=0;
if(flag)
ans++;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
==============================================================
Common Child
#include<stdio.h>
#include<string.h>
char str1[5005],str2[5005];
int c[5005][5005];
int main()
{
int i,j,m,n;
scanf("%s %s",str1+1,str2+1);
m=strlen(str1+1);
n=strlen(str2+1);
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(str1[i]==str2[j])
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
printf("%d\n",c[m][n]);
return 0;
}
======================================================
Bear and Steady Gene
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int greater_than(int *curr,int *need){
int i = 0;
for( i = 0 ; i < 26; i++){
if(curr[i] < need[i])
return 0;
}
return 1;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,i,lo=0,hi=0,sz=0;
int cnt[26]={0,};
int need[26]={0,};
int current[26] = {0,};
char inpt[500000+1];
scanf("%d",&n);
scanf("%s",&inpt);
sz = n;
for(i=0;i<n;i++){
cnt[inpt[i]-'A']++;
}
for(i=0;i<26;i++){
if(i+'A' == 'A' ||
i+'A' == 'C' ||
i+'A' == 'T' ||
i+'A' == 'G'
)
{
need[i] = (cnt[i]-n/4) < 0 ? 0 : (cnt[i]-n/4) ;
// printf("%c %d %d\n",i+'A', cnt[i] , need[i]);
}
}
while(lo<n && hi<n){
while (hi <n && !greater_than(current,need)){
current[ inpt[hi] - 'A']++;
hi++;
}
while (lo<n && greater_than(current,need)){
sz = (hi-lo)< sz ? hi-lo : sz;
//printf("Size %d %d %d\n",sz,hi,lo);
current[ inpt[lo] - 'A']--;
lo++;
}
}
printf("%d\n",sz);
return 0;
}
=================================================================
TEST -18
String Construction
#include <stdio.h>
#include <string.h>
int main(void) {
// your code goes here
int t;scanf("%d",&t);
while(t--)
{ char inp[100005];
int i,c=0,l,arr[26];
for(i=0;i<26;i++)arr[i]=0;
scanf("%s",inp);
l=strlen(inp);
for(i=0;i<l;i++)
{
arr[inp[i]-'a']+=1;
}
for(i=0;i<26;i++)
if(arr[i]!=0)
c+=1;
printf("%d\n",c);}
return 0;
}
=========================================================
Sherlock and the Valid String
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int fre[26];
int main() {
char S[100001];
scanf("%s",&S);
int len=strlen(S);
int i=0;
for(i=0;i<len;i++)
{
fre[S[i]-'a']++;
}
int flag=0;
int same=0;
int count=0;
for(i=0;i<26;i++)
{
if(flag==0&&fre[i]!=0)
{
flag=1;
same=fre[i];
}
if(flag==1&&fre[i]!=0&&fre[i]!=same)
{
count++;
}
}
if(count<=1)
printf("YES");
else
printf("NO");
return 0;
}
==============================================================
Richie Rich
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
int n,m,k,i;
char num[100001];
int pos[100001];
for(i=0;i<100001;i++) {
pos[i] = 0;
}
scanf("%d%d",&n,&k);
scanf("%s",num);
for(i=0;i<n/2;i++) {
if(num[i] != num[n-i-1]) {
k--;
if(num[i] > num[n-i-1]) {
num[n-i-1] = num[i];
pos[i] = 1;
pos[n-i-1] = 1;
} else {
num[i] = num[n-i-1];
pos[i] = 1;
pos[n-i-1] = 1;
}
}
}
if(k==0) {
printf("%s\n",num);
} else if(k>0) {
for(i=0;i<n;i++) {
if(pos[i] && num[i] != '9') {
num[i] = '9';
num[n-i-1] = '9';
k--;
} else if(num[i] !='9' && k>=2) {
num[i] = '9';
num[n-i-1] = '9';
k -= 2;
} else if( n&1 && i==(n/2) && k) {
num[i] = '9';
k--;
}
if(!k) {
break;
}
}
printf("%s\n",num);
} else {
printf("-1\n");
}
return 0;
}
====================================================================
Test -17
Two Strings
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
scanf("%i",&t);
while(t--)
{
char a[100001],b[100001];
scanf("%s",a);
scanf("%s",b);
int i=0,c[26]={0},f=0;
for(i=0;a[i]!='\0';i++)
c[a[i]-'a']=1;
for(i=0;b[i]!='\0';i++)
if(c[b[i]-'a'])
{f=1;break;}
puts(f?"YES":"NO");
}
return 0;
}
========================================================
Game of Thrones - I
#include<stdio.h>
int main()
{
int a[26],i,tp;
char c;
for (i=0;i<26;i++)
a[i]=0;
while ((c=getchar())!=EOF&&c!='\n')
{
a[c-97]++;
}
tp=1;
for (i=0;i<26;i++)
{
if (a[i]%2!=0&&tp==1)
tp=0;
else if (a[i]%2!=0&&tp==0)
{
printf("NO");
break;
}
}
if (i==26)
printf("YES");
return 0;
}
=======================================================
Making Anagrams
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int count1[100],count2[100];
int main()
{
char a[10009],b[10009];
int i;
scanf("%s%s",a,b);
i=0;
while(a[i])
{
count1[a[i]-97]++;
i++;
}
i=0;
while(b[i])
{
count2[b[i]-97]++;
i++;
}
int ans=0;
for(i=0;i<26;i++)
{
ans=ans+abs(count1[i]-count2[i]);
}
printf("%d\n",ans);
return 0;
}
=========================================================
TEST -16
Separate the Numbers
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int getcnt(long long int n)
{
int cnt=0;
while(n)
{
n/=10;
cnt++;
}
return cnt;
}
int main(){
int q;
scanf("%d",&q);
for(int a0 = 0; a0 < q; a0++){
char* s = (char *)malloc(512000 * sizeof(char));
scanf("%s",s);
int len=strlen(s);
if(len==1)
{
printf("NO\n");
continue;
}
int i,j;
long long int a,b;
int flg=0;
char *tmp= (char *)malloc(512000 * sizeof(char));
for(i=1;i<=len/2;i++)
{
for(j=0;j<len;)
{
strcpy(tmp,s+j);
tmp[i]='\0';
sscanf(tmp,"%lld",&a);
if(a==0&&j==0&&i==1)
break;
//printf("%d\n",a);
if(getcnt(a)!=i)
break;
if(j!=0)
if(a!=b+1)
break;
b=a;
j+=i;
}
if(j>=len)
{
flg=1;
break;
}
}
int flg2=0;
if(flg!=1)
{
for(i=1;i<=len/2;i++)
{
flg2=0;
for(j=0;j<len;)
{
strcpy(tmp,s+j);
if(flg2==0)
tmp[i]='\0';
else
tmp[i+1]='\0';
// printf("%s\n",tmp);
sscanf(tmp,"%lld",&a);
if(a==0&&j==0&&i==1)
break;
if(flg2==0)
{
if(getcnt(a)!=i)
break;
}
else
{
if(getcnt(a)!=i+1)
break;
}
if(j!=0)
if(a!=b+1)
break;
b=a;
if(flg2==0)
j=j+i;
else
j=j+i+1;
if(b==(pow(10,i)-1))
{
flg2=1;
}
}
if(j>=len)
{
flg=1;
break;
}
}
}
//printf("%d\n",i);
if(flg==0)
printf("NO\n");
else
{
strcpy(tmp,s);
tmp[i]=0;
printf("YES %s\n",tmp);
}
}
return 0;
}
===========================================================
Funny String
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
scanf("%d\n", &t);
char* str = (char*)calloc(10000, sizeof(char));
for(int i=0;i<t;i++){
scanf("%s", str);
int l = strlen(str);
int flag=0;
for(int i=0,j=l-1;i<l/2;i++,j--){
if( abs(str[i]-str[i+1]) != abs(str[j]-str[j-1]) ){
flag=1;
break;
}
}
if(flag)
printf("Not Funny\n");
else
printf("Funny\n");
}
return 0;
}
========================================================================
Gemstones
#include<stdio.h>
int main()
{
int n,i,j,freq[150][27]={0},count;
char str[200];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s\n",str);
for(j=0;str[j]!='\0';j++)
{
freq[i][str[j]-97]++;
}
}
count=0;
for(i=0;i<26;i++)
{
for(j=0;j<n;j++)
if(freq[j][i]>0)
continue;
else
break;
if(j==n)
count++;
}
printf("%d\n",count);
return 0;
}
=========================================================================
TEST -15
HackerRank in a String!
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int q;
int i;
int j;
char *hack = "hackerrank";
scanf("%d",&q);
for(int a0 = 0; a0 < q; a0++){
char* s = (char *)malloc(512000 * sizeof(char));
scanf("%s",s);
// your code goes here
i = 0;
j = 0;
while (s[i])
{
if (s[i] == hack[j])
j++;
i++;
}
if (j == 10)
printf("%s\n", "YES");
else
printf("%s\n", "NO");
}
return 0;
}
====================================
Pangrams
#include<stdio.h>
char st[100000];
int i,ind[1000];
int main()
{
while(gets(st))
{
for(i='A';i<='Z';i++)
ind[i]=0;
for(i=0;st[i];i++)
{
if(st[i]>='a' && st[i]<='z')
st[i]-=32;
ind[st[i]]++;
}
for(i='A';i<='Z';i++)
if(ind[i]==0)
break;
if(i=='Z'+1)
printf("pangram\n");
else
printf("not pangram\n");
}
return 0;
}
===============================
Weighted Uniform Strings
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
char* s = (char *)malloc(512000 * sizeof(char));
scanf("%s",s);
int n;
scanf("%d",&n);
int j=0;
int a[26];
for(j=0;j<26;j++){
a[j]=0;
}
int l=strlen(s);
for(j=0;j<l; ){
int m=(int)s[j];
int count=0;
if(j==0 || s[j]!=s[j-1]){
count++;
j++;
while(s[j]==s[j-1]){
count++;
j++;
}
}
if(count>a[m-97])
a[m-97]=count;
}
// for(int i=0;i<26;i++)
// printf("%d ",a[i]);
for(int a0 = 0; a0 < n; a0++){
long int x,flag=0;
scanf("%ld",&x);
for(int i=0;i<26;i++){
if(x%(i+1)==0 && a[i]*(i+1)>=x){
flag=1;
break;
}
}
if(flag==1)
printf("Yes\n");
else
printf("No\n");
// your code goes here
}
return 0;
}
=========================================
TEST -14
ACM ICPC Team
#include<stdio.h>
#include<string.h>
int main()
{
int n,m,i,j,k;
int pair,know=0,max=0;
char a[500][500];
//char sub[500][500];
scanf("%d%d",&n,&m);
for(i=0;i<n;i++) {
//for(j=0;j<m;j++)
scanf("%s",a[i]);
}
k=0;
for(i=0;i<n-1;i++) {
for(j=i+1;j<n;j++) {
while(k<m) {
if(a[i][k]=='1'|| a[j][k]=='1') { // known subjects
//incr known subs
know++;
}
k++;
}
//max=(know>max)?know:max;
if(know>max) {
pair=1;
max=know;
}
else if(know == max) {
pair++;
}
know=0;
k=0;
//printf("\n[%d---%d]",max,pair);
}
//printf("\n[%d---%d]",max,pair);
//max=pair=0;
}
printf("%d\n%d",max,pair);
return 0;
}
=============================================
Non-Divisible Subset
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main(){
int n;
int k;
scanf("%d %d",&n,&k);
int count[k];
for (int i = 0; i < k; i++) {
count[i] = 0;
}
for(int i = 0; i < n; i++){
int a;
scanf("%d",&a);
count[a % k]++;
}
int max = 0;
for (int i = 0; i <= k/2; i++) {
if (i == 0 || i == k - i) {
if (count[i] >= 1) {
max += 1;
}
} else {
max += count[i] > count[k-i] ? count[i] : count[k-i];
}
}
printf("%d\n",max);
return 0;
}
====================================================
Cut the sticks
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[1002]={0};
int i;
for(i=0;i<n;i++)
{
int c;
scanf("%d",&c);
a[c]++;
}
int t=n;
for(i=0;i<1001;i++)
{
if(a[i]>0)
{
printf("%d\n",t);
t=t-a[i];
}
}
return 0;
}
==========================================================
TEST -13
Repeated String
#include<stdio.h>
#include<string.h>
int main()
{
long long int n,c=0,m=0,i;
char a[101];
scanf("%s",a);
scanf("%lld",&n);
long long int k=strlen(a);
for(i=0;i<k;i++)
if(a[i]=='a')
c++;
long long int b=(n/k)*c;
long long int d=n%k;
for(i=0;i<d;i++)
if(a[i]=='a')
m++;
long long int sum=b+m;
printf("%lld",sum);
}
---------------------------------------
Equalize the Array
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,a[100],i,count=0,j,ans,max=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
count=0;
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])
{
count++;
// printf("%d",count);
}
}
if(count>max)
{
max=count;
}
}
ans=n-max-1;
if(ans==n)
{
ans=0;
}
printf("%d",ans);
return 0;
}
---------------------------------------
Library Fine
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int d1, m1, y1, d2, m2, y2;
scanf("%d %d %d %d %d %d", &d1, &m1, &y1, &d2, &m2, &y2);
if (y1 > y2)
printf("10000");
else
if (y1 < y2)
printf("0");
else
if (m1 > m2)
printf("%d", (m1-m2)*500);
else
if (m1 < m2)
printf("0");
else
if (d1 > d2)
printf("%d", (d1-d2)*15);
else
printf("0");
return 0;
}
====================================================================
TEST -12
Queen's Attack II
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int min(int a,int b){
if(a>b)
return b;
return a;
}
int main(){
int n;
int k;
scanf("%d %d",&n,&k);
int rq,i;
int cq;
int c[8];
scanf("%d %d",&rq,&cq);
c[0] = n-cq;
c[1] = cq-1;
c[2] = n-rq;
c[3] = rq-1;
c[4] = min(rq,cq)-1;
c[5] = min(n-rq,n-cq);
c[6] = min(n-rq,cq-1);
c[7] = min(rq-1,n-cq);
for(int a0 = 0; a0 < k; a0++){
int ro;
int co;
scanf("%d %d",&ro,&co);
if(ro==rq&&(co-cq)>0){
if(c[0]>(co-cq-1))
c[0] = co-cq-1;
//printf("%d %d\n",a0,0);
}
if(ro==rq&&(co-cq)<0){
if(c[1]>(cq-co-1))
c[1] = cq-co-1;
//// printf("%d %d \n",a0,1);
}
if(co==cq&&(ro-rq)>0){
if(c[2]>(ro-rq-1))
c[2]=(ro-rq-1);
// printf("%d %d\n",a0,2);
}
if(co==cq&&(ro-rq)<0){
if(c[3]>(rq-ro-1))
c[3]=(rq-ro-1);
// printf("%d %d\n",a0,3);
}
if((co-cq)==(ro-rq)&&(ro-rq)<0){
if(c[4]>(rq-ro-1))
c[4]=(rq-ro-1);
// printf("%d %d\n",a0,4);
}
if((co-cq)==(ro-rq)&&(ro-rq)>0){
if(c[5]>(ro-rq-1))
c[5]=(ro-rq-1);
//printf("%d %d\n",a0,5);
}
if((co-cq)==(rq-ro)&&(ro-rq)>0){
if(c[6]>(ro-rq-1))
c[6]=(ro-rq-1);
//printf("%d %d\n",a0,6);
}
if((co-cq)==(rq-ro)&&(ro-rq)<0){
if(c[7]>(rq-ro-1))
c[7]=(rq-ro-1);
// printf("%d %d\n",a0,7);
}
// your code goes here
}
int sum=0;
for(i=0;i<8;i++){
sum = sum + c[i];
//printf("%d ",c[i]);
}
printf("%d",sum);
return 0;
}
=================================
Append and Delete
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
char* s = (char *)malloc(512000 * sizeof(char));
scanf("%s",s);
char* t = (char *)malloc(512000 * sizeof(char));
scanf("%s",t);
int k,i=0,l1,l2,del,append,same;
scanf("%d",&k);
l1=strlen(s),l2=strlen(t);
if(strcmp(s,t)==0)
{
if(k%2==0 || k>=2*l1)
printf("Yes");
else
printf("No");
}
else
{
if(k>=2*l2)
printf("Yes");
else
{
while(i<l1 && i<l2)
{
if(s[i]==t[i])
i++;
else
break;
}
same=i;
del=l1-same;
append=l2-same;
if(del+append > k)
printf("No");
else
{
if((del+append)%2==0)
{
if(k%2==0)
printf("Yes");
else
printf("No");
}
else
{
if(k%2==0)
printf("No");
else
printf("Yes");
}
}
}
}
return 0;
}
======================================
Sherlock and Squares
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int t;
int a,b,sa,sb;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&a,&b);
sa = sqrt(a), sb = sqrt(b);
if(sa*sa == a)sa--;
printf("%d\n",sb - sa);
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
=======================================================================
TEST -11
Beautiful Days at the Movies
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int a,b,c,count=0;
scanf("%d %d %d",&a,&b,&c);
for(int temp=a;temp<=b;temp++)
{
int p=temp,rev=0;
while(p!=0)
{
rev=rev*10+(p%10);
p=p/10;
}
if(abs(rev-temp)%c==0)
count++;
}
printf("%d",count);
return 0;
}
==============================================
Save the Prisoner!
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int t, n, m, s;
scanf("%d", &t);
while (t--) scanf("%d%d%d", &n, &m, &s), printf("%d\n", (m+s-2)%n+1);
return 0;
}
============================================
Circular Array Rotation
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
long n,k,q,i;
long a[100000];
scanf("%ld%ld%ld",&n,&k,&q);
long r=k%n;
for(i=r;i<n;i++)
scanf("%ld",&a[i]);
for(i=0;i<r;i++)
scanf("%ld",&a[i]);
for(i=0;i<q;i++)
{
scanf("%ld",&k);
printf("%ld\n",a[k]);
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
===========================================================================================================================
===============================================
TEST -10
The Hurdle Race
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n;
int k;
int max=-1,ans=0;
scanf("%d %d",&n,&k);
int *height = malloc(sizeof(int) * n);
for(int height_i = 0; height_i < n; height_i++){
scanf("%d",&height[height_i]);
if(height[height_i]>max)
max=height[height_i];
}
if(max>k)
ans=max-k;
printf("%d",ans);
// your code goes here
return 0;
}
=======================================================
Designer PDF Viewer
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n=26;
int *h = malloc(sizeof(int) * n);
for(int h_i = 0; h_i < n; h_i++){
scanf("%d",&h[h_i]);
}
char* word = (char *)malloc(512000 * sizeof(char));
scanf("%s",word);
int l=strlen(word);
int i;
int max=0;
for(i=0;i<l;i++)
{
if(h[(int)word[i]-'a']>max)
max=h[(int)word[i]-'a'];
}
printf("%d",max*l);
return 0;
}
========================================
Angry Professor
/*Angry Professor*/
#include<stdio.h>
int main()
{
int count, i, K, N, T, time;
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &N, &K);
count = 0;
for (i = 0; i < N; i++)
{
scanf("%d", &time);
if (time <= 0)
count++;
}
puts((count < K) ? "YES" : "NO");
}
return 0;
}
==================================================================
Test- 9
Viral Advertising
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int i=0,j,k,l,m,n,t;
scanf("%d",&n);
k=5;
for(i=0;i<n;i++)
{
j=k/2;
k=j*3;
m=m+j;
}
printf("%d",m);
return 0;
}
============================================================
Sequence Equation
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main() {
int i,n,a[100],j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
if(a[a[i]]==j)
break;
printf("%d\n",i);
}
return 0;
}
====================================================
Jumping on the Clouds: Revisited
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n,i,e=100;
int k;
scanf("%d %d",&n,&k);
int *c = malloc(sizeof(int) * n);
for(int c_i = 0; c_i < n; c_i++){
scanf("%d",&c[c_i]);
}
do
{
i=(i+k)%n;
if(c[i]==1)
e=e-2;
e--;
}while(i!=0);
printf("%d",e);
return 0;
}
=================================================================================================
==========================================================================
Test- 8
Forming a Magic Square
#include<stdio.h>
int main()
{
int inp[3][3],arr1[3][3]={2,9,4,7,5,3,6,1,8},arr2[3][3]={6,1,8,7,5,3,2,9,4},arr3[3][3]={2,7,6,9,5,1,4,3,8},arr4[3][3]={4,3,8,9,5,1,2,7,6},arr5[3][3]={8,1,6,3,5,7,4,9,2},arr6[3][3]={4,9,2,3,5,7,8,1,6}
,arr7[3][3]={8,3,4,1,5,9,6,7,2},arr8[3][3]={6,7,2,1,5,9,8,3,4},i,j,cost,min=10000;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
scanf("%d",&inp[i][j]);
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr1[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr2[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr3[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr4[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr5[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr6[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr7[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cost+=abs(arr8[i][j]-inp[i][j]);
}
}
if(cost<min)
min=cost;
cost=0;
printf("%d\n",min);
return 0;
}
===========================================================
Picking Numbers
#include <stdio.h>
int main(void) {
// your code goes here
int n;scanf("%d",&n);
int arr[101];
int i,c=0;
for(i=1;i<=100;i++)arr[i]=0;
for(i=0;i<n;i++)
{int x;
scanf("%d",&x);
arr[x]+=1;
}
for(i=1;i<100;i++)
{
int t=(arr[i]+arr[i+1]);
if(t>c)
c=t;
}
printf("%d",c);
return 0;
}
============================================================================
Climbing the Leaderboard
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n;
scanf("%d",&n);
int *scores = malloc(sizeof(int) * n);
for(int scores_i = 0; scores_i < n; scores_i++){
scanf("%d",&scores[scores_i]);
if(scores_i){
if(scores[scores_i]==scores[scores_i-1]){
scores_i--;
n--;
}
}
}
//printf("%d\n",n);//
int m;
scanf("%d",&m);
int *alice = malloc(sizeof(int) * m);
for(int alice_i = 0; alice_i < m; alice_i++){
scanf("%d",&alice[alice_i]);
}
int rank=n;
for(int j=0; j<m; j++){
while(alice[j]>=scores[rank-1] && rank>0){
rank--;
if(rank==0) break;
}
printf("%d\n",rank+1);
}
// your code goes here
return 0;
}
========================================================================
Test- 7
***************prog-1************
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int solve(int n, int p)
{
// Complete this function
int count1=0,count2=0;
for(int i=1;i<=n;i++)
{
if(i==p)
break;
if(i%2!=0)
{
count1++;
}
}
for(int j=n;j>0;j--)
{
if(j==p)
break;
if(j%2==0)
{
count2++;
}
}
if(count1<count2)
return count1;
else
return count2;
}
int main()
{
int n;
scanf("%d", &n);
int p;
scanf("%d", &p);
int result = solve(n, p);
printf("%d\n", result);
return 0;
}
************prog-2******************
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int getMoneySpent(int* k, int* d, int s,int n,int m)
{
// Complete this function
int max=0,min=k[0]+d[0];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if((k[i]+d[j]>max)&&(k[i]+d[j]<=s))
max=k[i]+d[j];
}
}
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)
{
if((k[x]+d[y])<min)
{
min=k[x]+d[y];
}
}
}
if(min>s)
return -1;
else
return max;
}
int main()
{
int s;
int n;
int m;
scanf("%d %d %d", &s, &n, &m);
int *keyboards = malloc(sizeof(int) * n);
for(int keyboards_i = 0; keyboards_i < n; keyboards_i++)
{
scanf("%d",&keyboards[keyboards_i]);
}
int *drives = malloc(sizeof(int) * m);
for(int drives_i = 0; drives_i < m; drives_i++)
{
scanf("%d",&drives[drives_i]);
}
int moneySpent = getMoneySpent(keyboards, drives, s,n,m);
printf("%d\n", moneySpent);
return 0;
}
************prog-3*******************
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
char** catAndMouse(int x, int y, int z, int *result_size)
{
// Complete this function
if (abs(x-z)>abs(y-z))
printf("Cat B\n");
else if (abs(x-z)<abs(y-z))
printf("Cat A\n");
else if (abs(x-z)==abs(y-z))
printf("Mouse C\n");
return 0;
}
int main()
{
int q;
scanf("%i", &q);
for(int a0 = 0; a0 < q; a0++)
{
int x;
int y;
int z;
scanf("%i %i %i", &x, &y, &z);
int result_size;
char** result = catAndMouse(x, y, z, &result_size);
}
return 0;
}
=================================================================
TEST - 6
Bon Appétit
#include<stdio.h>
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int i,a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int sum = 0;
for(i=0;i<n;i++)
sum += a[i];
int paid;
scanf("%d",&paid);
int toBePaid = sum-a[k];
if((toBePaid)/2==paid)
printf("Bon Appetit\n");
else
printf("%d\n",paid-(toBePaid)/2);
return 0;
}
Sock Merchant
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int n,i,t;
scanf("%d",&n);
int c[101];
memset(c,0,sizeof(c));
for(i=0;i<n;i++)
{
scanf("%d",&t);
c[t]++;
}
long int ans=0;
for(i=1;i<=100;i++)
{
ans+=(c[i]/2);
}
printf("%ld",ans);
return 0;
}
Counting Valleys
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int n;
scanf("%i", &n);
char str[n];
scanf("%s", str);
int level = 0, result = 0, valley = 0;
for (int i = 0; i < n; i++) {
if(str[i] == 'U') {
level++;
if(level == 0 && valley) {
valley = 0;
result++;
}
}
else if(str[i] == 'D') {
if(level == 0)
valley = 1;
level--;
}
}
printf("%i", result);
return 0;
}
================================
TEST - 5
Divisible Sum Pairs
#include <stdio.h>
int main() {
int n, k;
scanf("%d %d", &n, &k);
int count = 0;
int nums[n];
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
for (int j = 0; j < i; j++)
count += (nums[i] + nums[j]) % k == 0;
}
printf("%d", count);
return 0;
}
---------------------------------------------------------------------------------------------
Migratory Birds
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n;
int i;
int j;
int k;
int max;
int sth;
max = 0;
j = 1;
scanf("%d",&n);
sth = 0;
int *types = malloc(sizeof(int) * n);
for(int types_i = 0; types_i < n; types_i++){
scanf("%d",&types[types_i]);
}
// your code goes here
i = 0;
while (j <= 5 )
{
k = 0;
i = 0;
while (i < n)
{
if (types[i] == j)
k++;
i++;
}
if (k > max)
{
sth = j;
max = k;
}
j++;
}
printf("%d", sth);
return 0;
}
-----------------------------------------------------------------
Day of the Programmer
#include <stdio.h>
int main(){
int y;
scanf("%d",&y);
if(y<1918){
if(y%4){
printf("13.09.%4d\n",y);
}
else{
printf("12.09.%4d\n",y);
}
}
else if(y== 1918){
printf("26.09.1918\n");
}
else{
if((y%400 == 0) || (y%4 == 0 && y%100)){
printf("12.09.%4d\n",y);
}
else{
printf("13.09.%4d\n",y);
}
}
return 0;
}
![(UPDATED) COA TOTAL MATERIAL FOR SEMESTER[NOTES, PDF'S, PPT'S, TEXTBOOKS, PREVIOUS PAPERS,TEST PAPERS]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhk47KVvbwto-bwDbWA1vQMTgKKcMKS-GFLAnz_mjukcNYa5I5oMZ8NF7V3E2OqAhjjKeK4_xgNoFqRecOQXzbzzXzl0IYM2ZVEwNjIeJcU8nWFkvjPNNhCc4qRD5n3xV7jB0TiysICi9Y/w72/CO.png)