/***********Template Starts Here***********/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <climits>
#include <iomanip>
#include <cassert>
//#include <unordered_map>
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((int)(x).size())
#define NORM(x) if(x>=mod)x-=mod;
using namespace std;
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;
#ifdef forthright48
#include <ctime>
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
#define debug(args...) // Just strip off all debug tokens
#define timeStamp
#endif
struct debugger{
template<typename T> debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
inline vlong gcd ( vlong a, vlong b ) {
a = ABS ( a ); b = ABS ( b );
while ( b ) { a = a % b; swap ( a, b ); } return a;
}
vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
x2 = 1; y2 = 0;
x1 = 0; y1 = 1;
for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
q = r2 / r1;
r = r2 % r1;
x = x2 - (q * x1);
y = y2 - (q * y1);
}
*X = x2; *Y = y2;
return r2;
}
inline vlong modInv ( vlong a, vlong m ) {
vlong x, y;
ext_gcd( a, m, &x, &y );
if ( x < 0 ) x += m; //modInv is never negative
return x;
}
inline vlong power ( vlong a, vlong p ) {
vlong res = 1, x = a;
while ( p ) {
if ( p & 1 ) res = ( res * x );
x = ( x * x ); p >>= 1;
}
return res;
}
inline vlong bigmod ( vlong a, vlong p, vlong m ) {
vlong res = 1 % m, x = a % m;
while ( p ) {
if ( p & 1 ) res = ( res * x ) % m;
x = ( x * x ) % m; p >>= 1;
}
return res;
}
/***********Template Ends Here***********/
/*********** Hasib Templates Starts Here**********/
#include<bits/stdc++.h>
using namespace std;
#define loop(i, n) for(int i=0; i<(n); i++)
#define sf scanf
#define pf printf
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) (v).begin(), (v).end()
#define PI acos(-1.0)
#define mem(ara, val) memset(ara, val, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define vdump(x) cerr<<#x<<" = "<<x<<endl;
#define dump(args...) cerr,args; cerr<<endl
template<typename T>
ostream& operator<<(ostream& out, vector<T> v)
{
out<<"[ ";
loop(i, SZ(v))
{
if(i) out<<", ";
out<<v[i];
}
out<<" ]";
return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &out, pair<T1, T2> p)
{
out<<"( "<<p.fr<<", "<<p.sc<<")";
return out;
}
template<typename T>
ostream& operator,(ostream &out, T x)
{
out<<x<<" ";
return out;
}
/**********Hasib Templates Ends Here**************/
/**
* WARTNING for me:
* Never use FOR
* Never use pii, pll, vi, vi
* Never use ff, ss, phl, sp, nl
*/
#define NODE 107
struct KUHN{
int left[NODE], right[NODE], vis[NODE], cc;
vector<int> adj[NODE];
KUHN() : cc(1) {
}
void clear(int n)
{
FOR(i, 0, n) adj[i].clear();
}
bool tryK(int v)
{
if(vis[v] == cc) return false;
vis[v] = cc;
loop(i, SZ(adj[v]))
{
int t = adj[v][i];
if(right[t] == -1)
{
right[t] = v; left[v] = t;
return true;
}
}
loop(i, SZ(adj[v]))
{
int t = adj[v][i];
if( tryK(right[t]))
{
right[t] = v; left[v] = t;
return true;
}
}
return false;
}
int match(int n)
{
int res = 0;
bool done;
CLR(left, -1); CLR(right, -1);
do{
done = true; cc++;
FOR(i, 0, n)
{
if(left[i] == -1 && tryK(i))
{
done = false;
}
}
}while(!done);
FOR(i, 0, n) res += (left[i] != -1);
return res;
}
};
vector<int>original[NODE], modified[NODE];
int orgN, modN;
bool orgVisited[NODE], modVisited[NODE];
bool isMatch[NODE][NODE];
bool match(int u, int v)
{
orgVisited[u] = modVisited[v] = true;
int uu, vv;
KUHN kuhn;
/// !wow! Got WA because I took kuhn as local variable, and didn't clear visited!
mem(kuhn.vis, 0);
kuhn.clear(NODE-1);
loop(i, SZ(original[u]))
{
uu = original[u][i];
if(orgVisited[uu]) continue;
loop(j, SZ(modified[v]))
{
vv = modified[v][j];
if(modVisited[vv]) continue;
if(match(uu, vv))
{
kuhn.adj[i].pb(j);
}
}
}
orgVisited[u] = modVisited[v] = false;
int m = kuhn.match( SZ(original[u]) + 2 );
int child = SZ(original[u]) - 1;
if(u == 1) child++;
bool ret = (m == child);
return ret;
}
void solve()
{
//mem(orgVisited, 0); ///
//mem(modVisited, 0); ///
bool ret = match(1, 1);
if(ret)
{
pf("Yes\n");
}
else
{
pf("No\n");
}
}
int main ()
{
#ifdef hasibpc
read("input.txt");
//write("output.txt");
#endif // hasibpc
int kases, kaseno = 0;
int u, v;
sf("%d", &kases);
while(kases--)
{
sf("%d", &modN);
FOR(i, 0, modN) modified[i].clear();
for(int i=1; i<modN; i++)
{
sf("%d %d", &u, &v);
//debug(u, v);
modified[u].pb(v);
modified[v].pb(u);
}
//vdump(endl);
sf("%d", &orgN);
FOR(i, 0, orgN) original[i].clear();
for(int i=1; i<orgN; i++)
{
sf("%d %d", &u, &v);
//debug(u, v);
original[u].pb(v);
original[v].pb(u);
}
pf("Case %d: ", ++kaseno);
solve();
}
return 0;
}
Category Archives: Recursion
(UVA) 369 – Combinations
0
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
#define MAXX 107
ll nCr[MAXX][MAXX];
ll ncr(int n, int r)
{
if(r == 0)
{
return 1;
}
if(n < r)
{
return 0;
}
ll &ret = nCr[n][r];
if(ret != -1) return ret;
return ret = ncr(n-1, r) + ncr(n-1, r-1);
}
void init()
{
mem(nCr, -1);
}
int main()
{
init();
ll N, R;
while(true)
{
sf("%lld %lld", &N, &R);
if(N==0 && R == 0)
{
break;
}
else
{
pf("%lld things taken %lld at a time is %lld exactly.\n", N, R, ncr(N,R));
}
}
return 0;
}
(USACO) Shopping Offers (IOI’95)
0
/*
ID: himuhas1
TASK: shopping
LANG: C++
*/
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
#define MAXX 107
#define MAX_N 7
struct DATA{
int n;
vector<paii>v;
int p;
};
DATA offers[MAXX];
int s, b;
map<int, int>cart_elements;
paii cart[MAX_N];
int dp[MAX_N][MAX_N][MAX_N][MAX_N][MAX_N][MAXX];
int rec(int items[MAX_N], int pos)
{
int &ret = dp[ items[1] ][ items[2] ][ items[3] ][ items[4] ][ items[5] ][pos];
if(ret != -1)
{
return ret;
}
if(pos >= s)
{
/// applied all the offers.
ret = 0;
for(int i=1; i<=5; i++)
{
//dump(items[i]);
ret += (items[i] * cart[i].sc);
}
//cout<<endl;
return ret;
}
else
{
ret = rec(items, pos+1);
bool can_take_this_offer = true;
loop(i, offers[pos].n)
{
if( cart_elements.find(offers[pos].v[i].fr) == cart_elements.end() || offers[pos].v[i].sc > items[ cart_elements[offers[pos].v[i].fr] ] )
{
can_take_this_offer = false;
}
}
if(can_take_this_offer)
{
loop(i, offers[pos].n)
{
items[ cart_elements[offers[pos].v[i].fr] ] -= offers[pos].v[i].sc;
}
}
ret = min(ret, rec(items, pos) + offers[pos].p);
ret = min(ret, rec(items, pos+1) + offers[pos].p);
if(can_take_this_offer)
{
loop(i, offers[pos].n)
{
items[ cart_elements[offers[pos].v[i].fr] ] += offers[pos].v[i].sc;
}
}
return ret;
}
}
int main()
{
#ifndef hasibpc
read("shopping.in");
write("shopping.out");
#endif // hasibpc
sf("%d", &s);
loop(i, s)
{
sf("%d", &offers[i].n);
loop(j, offers[i].n)
{
int c, k;
sf("%d %d", &c, &k);
offers[i].v.pb(MP(c, k));
}
sf("%d", &offers[i].p);
}
sf("%d", &b);
int id, quantity, price;
int tmp = 1;
int items[MAX_N];
mem(items, 0);
loop(i, b)
{
sf("%d %d %d", &id, &quantity, &price);
cart[i+1] = MP(quantity, price);
items[tmp] = quantity;
cart_elements[id] = tmp++;
}
mem(dp, -1);
cout<<rec(items, 0)<<endl;
}
(LightOj) 1033 – Generating Palindromes
0
//link: http://lightoj.com/volume_showproblem.php?problem=1033
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 102
char str[MAXX];
int dp[MAXX][MAXX];
int len;
int min_cost(int i, int j)
{
if(i < 0) return len - j;
if(j >= len) return i+1;
int &ret = dp[i][j];
if(ret != -1) return ret;
if(str[i] == str[j])
{
return ret = min_cost(i-1, j+1);
}
else
{
return ret = 1 + min( min_cost(i-1, j), min_cost(i, j+1) );
}
}
int main()
{
int kases, kaseno = 0;
take(kases);
while(kases--)
{
scanf("%s", str);
len = strlen(str);
mem(dp, -1);
int res = 1<<29;
for(int i=0; i<len-1; i++)
{
res = min( res, min_cost(i, i) );
res = min(res, min_cost(i, i+1));
}
pf("Case %d: %d\n", ++kaseno, len==1?0:res);
}
}
Another solution using LCS directly
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 102
char str[MAXX];
int dp[MAXX][MAXX];
int len;
int LCS(int i, int j)
{
if(i<0 || j>=len) return 0;
int &ret = dp[i][j];
if(ret != -1) return ret;
if(str[i] == str[j]) return ret = 1 + LCS(i-1, j+1);
return ret = max(LCS(i-1, j), LCS(i, j+1));
}
int main()
{
int kases, kaseno = 0;
take(kases);
while(kases--)
{
scanf("%s", str);
len = strlen(str);
mem(dp, -1);
int res = 1<<29;
for(int i=0; i<len-1; i++)
{
res = min(res, len+1 - 2*LCS(i, i));
res = min(res, len - 2*LCS(i, i+1));
}
pf("Case %d: %d\n", ++kaseno, len==1?0:res);
}
}
(SPOJ) 8425. Coloring Trees
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define MAXX 100002
char color[MAXX];
int parent[MAXX];
vector<int>graph[MAXX];
int find(int u)
{
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
int main()
{
int N;
int x, a, b;
sf("%d", &N);
loop(i, N)
{
color[i] = -1;
parent[i] = i;
}
N--;
loop(i, N)
{
sf("%d %d", &a, &b);
graph[a].pb(b);
graph[b].pb(a);
}
int Q;
sf("%d", &Q);
loop(i, Q)
{
sf("%d %d %d", &x, &a, &b);
if(x == 1)
{
color[a] = b;
loop(i, SZ(graph[a]))
{
if(color[graph[a][i]] == b)
{
parent[find(a)] = find(graph[a][i]);
}
}
}
else if(x==2)
{
if(find(a) == find(b))
{
if(a!=b || color[a] != -1 )
pf("YES\n");
else
pf("NO\n");
}
else
pf("NO\n");
}
}
return 0;
}
(SPOJ) 61. Brackets
0
//link: http://www.spoj.com/problems/BRCKTS/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
struct DATA
{
int needed_opening;
int needed_closing;
DATA()
{
needed_closing = needed_opening = 0;
}
};
#define MAXX 30002
DATA sum[4*MAXX];
char str[MAXX];
void insert(int idx, int st, int ed)
{
if(st == ed)
{
if(str[st] == '(')
{
sum[idx].needed_closing = 1;
sum[idx].needed_opening = 0;
}
else
{
sum[idx].needed_opening = 1;
sum[idx].needed_closing = 0;
}
}
else
{
int l = idx*2;
int r = l +1;
int mid = (st+ed)/2;
insert(l, st, mid);
insert(r, mid+1, ed);
int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);
sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;
sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
}
}
void update(int idx, int st, int ed, int pos)
{
if(st == ed)
{
if(str[pos] == '(')
{
sum[idx].needed_closing--;
sum[idx].needed_opening++;
str[pos] = ')';
}
else
{
sum[idx].needed_closing++;
sum[idx].needed_opening--;
str[pos] = '(';
}
}
else
{
int l = idx*2;
int r = l + 1;
int mid = (st+ed)/2;
if(pos <= mid)
{
update(l, st, mid, pos);
}
else
{
update(r, mid+1, ed, pos);
}
int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);
sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;
sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
}
}
int main()
{
int stlen, m, k;
loop(kaseno, 10)
{
pf("Test %d:\n", kaseno+1);
sf("%d", &stlen);
stlen--;
sf("%s", str);
insert(1, 0, stlen);
sf("%d", &m);
loop(i, m)
{
sf("%d", &k);
if(k == 0)
{
if(sum[1].needed_closing == 0 && sum[1].needed_opening == 0)
{
pf("YES\n");
}
else
{
pf("NO\n");
}
}
else
{
update(1, 0, stlen, k-1);
}
}
}
return 0;
}
(USACO) Zero Sum
0/*
ID: himuhas1
TASK: zerosum
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<map>
#include
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair
#define pall pair
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
int n;
vectorv;
void rec(int nxt)
{
if(nxt == n+1)
{
#if 0
loop(j, SZ(v))
{
if(v[j] > 9)
cout<<(char)v[j];
else
cout<<v[j];
}
cout<<endl;
#endif
int lastSum = 0, tmp = 0;
char sign = '+';
int i = 0;
while(i 9)
{
break;
}
lastSum = lastSum*10 + v[i];
i++;
}
while(i < SZ(v))
{
if(v[i] < 10)
{//a number
tmp = tmp*10 + v[i];
}
else
{
if(sign == '+')
{
lastSum += tmp;
}
else
{
lastSum -= tmp;
}
tmp = 0;
sign = v[i];
}
i++;
}
if(sign == '+')
{
lastSum += tmp;
}
else
{
lastSum -= tmp;
}
if(lastSum == 0)
{
cout< 9)
{
pf("%c", v[i]);
}
else
{
if(v[i-1] < 10)
{
pf(" ");
}
pf("%d", v[i]);
}
}
cout<<endl;
}
//cout<<lastSum<>n;
v.pb(1);
rec(2);
return 0;
}
(UVa) 10226 – Hardwood Species
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
#define ALPHA_LIST 128
struct node{
int cnt_trees;
node *child[ALPHA_LIST];
node()
{
cnt_trees = 0;
loop(i, ALPHA_LIST)
{
child[i] = NULL;
}
}
}*head;
int total;
/*
void clearTree(node *p)
{
loop(i, ALPHA_LIST)
{
if(p->child[i] != NULL)
{
clearTree(p->child[i]);
}
}
delete p;
}
void init()
{
head = new node();
}
int toint(char c)
{
if(c== ' ')
return 26;
if('a' <= c && c <= 'z')
return c - 'a';
else
return c - 'A';
}
*/
void insert(char *word)
{
//cout<<"inserting " << word<<endl;
node *current = head;
int ch;
while(*word != '\0')
{
ch = *word;
if(current->child[ch] == NULL)
current->child[ch] = new node();
current = current->child[ch];
word++;
}
current->cnt_trees++;
}
vector<char> name_list;
void printTree(node *current)
{
if(current->cnt_trees)
{
FOR(i, 0, SZ(name_list))
{
pf("%c", name_list[i]);
}
pf(" %.4lf\n", (100.0*current->cnt_trees)/(double)total);
//current->cnt_trees = 0;
}
loop(i, ALPHA_LIST)
{
if(current->child[i] != NULL)
{
name_list.pb(i);
printTree(current->child[i]);
name_list.pop_back();
}
}
delete current;
//current = NULL;
}
int main()
{
int kases;
char names[35];
bool blank = 0;
gi(kases);
cin.ignore();
cin.ignore();
while(kases--)
{
if(blank) pf("\n");
blank = 1;
head = new node();
//init();
//cout<<head<<endl;
total = 0;
while(gets(names))
{
if(strlen(names) == 0) break;
insert(names);
total++;
}
printTree(head);
//head = NULL;
//cout<<head<<endl<<endl<<endl;
//clearTree(head);
}
return 0;
}
(USACO) Checker Challenge
0
/*
user: php
link: http://cerberus.delos.com:790/usacoprob2?a=T7bTTAFb5qU&S=checker
*/
/*
ID: himuhas1
TASK: checker
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
#define MAXX 14
int N;
int cnt = 0;
int mask[MAXX][MAXX];
bool used[MAXX][MAXX];
/*
void getState()
{
loop(i, N)
{
loop(j, N)
{
if((mask[i] & (1<<j)) != 0)
{
pf("1 ");
}
else
{
pf("0 ");
}
}
pf("\n");
}
}
*/
void rec(int row)
{
if(row == N)
{
if(cnt < 3)
{
loop(i, N)
{
if(i) pf(" ");
loop(j, N)
{
if(used[i][j])
{
pf("%d", j+1);
break;
}
}
}
pf("\n");
}
cnt++;
return;
}
else
{
loop(i, N)
{
if( mask[row][i] == 0 )
{
for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
{
mask[r][p]++;
}
for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
{
mask[r][q]++;
}
for(int r=row+1; r<N; r++)
{
mask[r][i]++;
}
used[row][i] = 1;
//getState();
//cout<<endl<<endl;
rec(row+1);
for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
{
mask[r][p]--;
}
for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
{
mask[r][q]--;
}
for(int r=row+1; r<N; r++)
{
mask[r][i]--;
}
used[row][i] = 0;
}
}
}
}
int main()
{
freopen("checker.in", "r", stdin);
freopen("checker.out", "w", stdout);
mem(mask, 0);
mem(used, 0);
int row = 0;
cin>>N;
loop(i, N)
{
for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
{
mask[r][p]++;
}
for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
{
mask[r][q]++;
}
for(int r=row+1; r<N; r++)
{
mask[r][i]++;
}
used[row][i] = 1;
//getState();
//cout<<endl<<endl;
rec(row+1);
for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
{
mask[r][p]--;
}
for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
{
mask[r][q]--;
}
for(int r=row+1; r<N; r++)
{
mask[r][i]--;
}
used[row][i] = 0;
}
cout<<cnt<<endl;
//getState();
return 0;
}
(lightoj) 1087 – Diablo
0
/*
link: http://lightoj.com/volume_showproblem.php?problem=1087
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 10000000000
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 150005
int cnt_elements[4*MAXX];
vector<int>ids;
int cnt;
int cnt_query;
int total;
void update(int idx, int st, int ed, int pos, int value)
{
//cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<endl;
if(st == pos && pos == ed)
{
cnt_elements[idx] += value;
return;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed) / 2;
if(pos <= mid)
{
update(l, st, mid, pos, value);
}
else
{
update(r, mid+1, ed, pos, value);
}
cnt_elements[idx] = cnt_elements[l] + cnt_elements[r];
}
int get(int idx, int st, int ed, int pos)
{
//cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<" and number of elements = "<<cnt_elements[idx]<<endl;
cnt_elements[idx]--;
if(st == ed )
{
return st;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed) / 2;
if( pos <= cnt_elements[l] )
{
return get(l, st, mid, pos);
}
else
{
return get(r, mid +1, ed, pos - cnt_elements[l]);
}
}
int main()
{
//read();
//write();
int kases, kaseno = 0;
getint(kases);
int num;
char cmd[4];
int id;
int temp;
while(kases--)
{
pf("Case %d:\n", ++kaseno);
getint(cnt); getint(cnt_query);
total = cnt + cnt_query;
temp = cnt;
mem(cnt_elements, 0);
ids.clear();
loop(i, cnt)
{
getint(num);
ids.pb(num);
update(1, 1, total, i+1, 1);
}
loop(t, cnt_query)
{
sf("%s", cmd);
getint(num);
if(cmd[0] == 'c')
{
if(num > cnt)
{
pf("none\n");
continue;
}
cnt--;
id = get(1,1, total, num);
pf("%d\n", ids[id-1]);
}
else
{
ids.pb(num);
temp++;
cnt++;
update(1, 1, total, temp, 1);
}
}
}
return 0;
}
UnLucky Codes 