0

## Solution Idea:

The tricky part in this problem statement is this –

” Can Brenda drive her car from Dawson City to Delta Junction and back? ”

So Brenda need to reach her destination and return his start point. So just take input all the points and sort then in acceding order and check that the distance between two consecutive points is less than or equal to 200 or not. If it’s not then the ans will be impossible and if the 2*(distance between the last point and and destination) >200 the ans will be impossible. Otherwise the ans is possible.

```
/*
If opportunity doesn't knock, build a door.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Success is how high you bounce when you hit bottom.
*/

#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int main()
{
//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int n;
while(cin&gt;&gt;n &amp;&amp; n)
{
vector&lt;int&gt;v;

loop(i,n)
{
int a;
cin&gt;&gt;a;
v.pb(a);
}

sort(all(v));

bool test=0;

REP(i,1,n)
{
if(v[i]-v[i-1]&gt;200)
{
cout&lt;&lt;&quot;IMPOSSIBLE&quot;&lt;&lt;endl;
test=1;
break;
}
}

if(test==1) continue;

if((1422-v[n-1])*2&gt;200) test=1;

if(test==0)
cout&lt;&lt;&quot;POSSIBLE&quot;&lt;&lt;endl;
else
cout&lt;&lt;&quot;IMPOSSIBLE&quot;&lt;&lt;endl;

}
return 0;
}

```

# USACO: Ordered Fractions

0

```
/*
PROG: frac1
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;=b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int n;

map&lt;double,bool&gt;mp;
vector&lt; pair&lt;double, pii &gt; &gt; v;

int main()
{
freopen(&quot;frac1.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;frac1.out&quot;,&quot;w&quot;,stdout);
cin&gt;&gt;n;
mp[0/1.0]=1;
v.pb(MP(0/1.0,MP(0,1)));

REP(i,1,n) REP(j,1,n)

{
double a=i*1.0;
double b=j*1.0;
if(a/b&lt;=1.0)
{
if(!mp[a/b])
{
mp[a/b]=1;
v.pb(MP(a/b,MP(i,j)));
}
}
}

sort(all(v));
loop(i,SZ(v))
cout&lt;&lt;v[i].ss.ff&lt;&lt;&quot;/&quot;&lt;&lt;v[i].ss.ss&lt;&lt;endl;
return 0;
}

```

# USACO: The Castle

0

```
/*
PROG: castle
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;=b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
bool check(int N,int pos)
{
return (bool)(N &amp; (1&lt;&lt;pos));
}
/*------------------------------------------------*/

int graph[52][52];
int dp[2505];
int visited[52][52];

int r,c,s,extend=0;

int dfs(int i, int j, int x)
{
//    if(visited[i][j]) return 0;
visited[i][j]=x;
int d=0;
if(!check(graph[i][j],0) &amp;&amp; !visited[i][j-1]) d+=1+dfs(i,j-1,x);
if(!check(graph[i][j],2) &amp;&amp; !visited[i][j+1]) d+=1+dfs(i,j+1,x);
if(!check(graph[i][j],1) &amp;&amp; !visited[i-1][j]) d+=1+dfs(i-1,j,x);
if(!check(graph[i][j],3) &amp;&amp; !visited[i+1][j]) d+=1+dfs(i+1,j,x);
return d;
}

int n,m;

void func(int i, int j,int x)
{
int t=visited[i][j];
int d=0;
if(check(graph[i][j],0) &amp;&amp; t!=visited[i][j-1] &amp;&amp; j-1&gt;=1)
{
d=dp[t]+dp[visited[i][j-1]];
if(d&gt;extend)
{
extend=d;
r=i,c=j;
s=0;
}
else if(d==extend)
{
if(j&lt;c)
{
r=i,c=j;
s=0;
}
else if(j==c)
{
if(i&gt;r)
{
r=i,j=c;
s=0;
}
}
}
}

if(check(graph[i][j],2) &amp;&amp; t!=visited[i][j+1] &amp;&amp; j+1&lt;=m)
{
d=dp[t]+dp[visited[i][j+1]];
if(d&gt;extend)
{
extend=d;
r=i,c=j;
s=2;
}
else if(d==extend)
{
if(j&lt;c)
{
r=i,c=j;
s=2;
}
else if(j==c)
{
if(i&gt;r)
{
r=i,j=c;
s=2;
}
else if(i==r)
{
if(s!=1)
{
r=i,j=c;
s=2;
}
}
}
}
}

// if(check(graph[i][j],2) &amp;&amp; !visited[i][j+1]) d+=1+dfs(i,j+1,x);
//if(check(graph[i][j],1) &amp;&amp; !visited[i-1][j]) d+=1+dfs(i-1,j,x);
if(check(graph[i][j],1) &amp;&amp; t!=visited[i-1][j] &amp;&amp; i-1&gt;=1)
{
d=dp[t]+dp[visited[i-1][j]];
if(d&gt;extend)
{
extend=d;
r=i,c=j;
s=1;
}
else if(d==extend)
{
if(j&lt;c)
{
r=i,c=j;
s=1;
}
else if(j==c)
{
if(i&gt;r)
{
r=i,j=c;
s=1;
}
else if(i==r)
{
r=i,j=c;
s=1;
}
}
}
}
//if(check(graph[i][j],3) &amp;&amp; !visited[i+1][j]) d+=1+dfs(i+1,j,x);

if(check(graph[i][j],3) &amp;&amp; t!=visited[i+1][j] &amp;&amp; i+1&lt;=n)
{
d=dp[t]+dp[visited[i+1][j]];
if(d&gt;extend)
{
extend=d;
r=i,c=j;
s=3;
}
else if(d==extend)
{
if(j&lt;c)
{
r=i,c=j;
s=3;
}
else if(j==c)
{
if(i&gt;r)
{
r=i,j=c;
s=3;
}
}
}
}
}

int main()
{
freopen(&quot;castle.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;castle.out&quot;,&quot;w&quot;,stdout);
cin&gt;&gt;n&gt;&gt;m;
swap(n,m);
REP(i,1,n) REP(j,1,m) cin&gt;&gt;graph[i][j];

int k=0;
int ans=-1;
REP(i,1,n) REP(j,1,m)
{
if(!visited[i][j])
{
k++;
dp[k]=dfs(i,j,k)+1;
ans=max(ans,dp[k]);
}
}

cout&lt;&lt;k&lt;&lt;endl&lt;&lt;ans&lt;&lt;endl;
REP(i,1,n) REP(j,1,m)
{
func(i,j,visited[i][j]);
//        cout&lt;&lt;i&lt;&lt;&quot; &quot;&lt;&lt;j&lt;&lt;&quot; &quot;&lt;&lt;extend&lt;&lt;&quot; &quot;&lt;&lt;s&lt;&lt;endl;
}
cout&lt;&lt;extend&lt;&lt;endl;
cout&lt;&lt;r&lt;&lt;&quot; &quot;&lt;&lt;c;
if(s==2)pf(&quot; E\n&quot;);
else
pf(&quot; N\n&quot;);
return 0;
}

```

# USACO: Superprime Rib

0

```
/*
PROG: sprime
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

vector&lt;ll&gt;v;
int n;

bool isprime(ll n)
{
if(n==2) return 1;
if(!(n &amp; 1)) return 0;

for(int i=3; i*i&lt;=n; i+=2)
if(n%i==0) return 0;
return 1;
}

void dfs(ll u,int m)
{
if(!isprime(u)) return;
if(m==n)
{
v.pb(u);
return;
}
for(int i=1; i&lt;=9; i+=2)
{
int x=u*10+i;
dfs(x,m+1);
}
}

int main()
{
freopen(&quot;sprime.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;sprime.out&quot;,&quot;w&quot;,stdout);
cin&gt;&gt;n;
for(int i=2; i&lt;=9; i++)
dfs(i,1);
sort(all(v));
loop(i,SZ(v)) cout&lt;&lt;v[i]&lt;&lt;endl;
return 0;
}

```

# USACO : Prime Palindromes

0

```
/*
PROG: pprime
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;=b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

bool isPrime(ll n)
{
if(!(n &amp; 1))
return false;
else
{
int root= sqrt(n);
for(int i=3; i&lt;=root+1; i+=2)
if(n%i==0) return false;
}
return true;
}

vector&lt;ll&gt;v;

int main()
{
freopen(&quot;pprime.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;pprime.out&quot;,&quot;w&quot;,stdout);

ll a,b;
cin&gt;&gt;a&gt;&gt;b;

bool test=1;

for(int i=0; i&lt;10 &amp;&amp; test; i++)
for(int j=0; j&lt;10 &amp;&amp; test; j++)
for(int k=0; k&lt;10 &amp;&amp; test; k++)
for(int l=0; l&lt;10 &amp;&amp; test; l++)
{
ll palin=10*l+l;
if(k)
{
palin=1000*k+k+palin*10;
}
if(j)
{
if(k==0) palin=100000*j+j+palin*100;
else
palin=100000*j+j+palin*10;
}
if(i)
{
if(k==0 &amp;&amp; j==0) palin=10000000*i+i+palin*1000;
else if(k!=0 &amp;&amp; j==0) palin=10000000*i+i+palin*100;
else
palin=10000000*i+i+palin*10;
}
if(palin&gt;b)
{
test=0;
break;
}
if(palin&gt;=a &amp;&amp; isPrime(palin))
v.pb(palin);
}

test=1;

for(int i=0; i&lt;10 &amp;&amp; test; i++)
for(int j=0; j&lt;10 &amp;&amp; test; j++)
for(int k=0; k&lt;10 &amp;&amp; test; k++)
for(int l=0; l&lt;10 &amp;&amp; test; l++)
{
ll palin=l;
if(k)
{
palin=100*k+k+palin*10;
}
if(j)
{
if(k==0) palin=10000*j+j+palin*100;
else
palin=10000*j+j+palin*10;
}
if(i)
{
if(k==0 &amp;&amp; j==0) palin=1000000*i+i+palin*1000;
else if(k!=0 &amp;&amp; j==0) palin=1000000*i+i+palin*100;
else
palin=1000000*i+i+palin*10;
}
if(palin&gt;b)
{
test=0;
break;
}
if(palin&gt;=a &amp;&amp; isPrime(palin))
v.pb(palin);
}
sort(all(v));
loop(i,SZ(v)) cout&lt;&lt;v[i]&lt;&lt;endl;
return 0;
}

```

# USACO: Number Triangles

0

```
/*
PROG: numtri
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;=b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int ara[1005][1005];
int dp[1005][1005];
int r;

int func(int i,int j)
{
if(i&gt;r || j&gt;r) return 0;

int &amp;ret=dp[i][j];
if(ret!=-1) return ret;
ret=0;
//    return ret=max(ara[i][j]+func(i+1,j),ara[i][j]+func(i+1,j+1));
return ret=ara[i][j]+max(func(i+1,j),func(i+1,j+1));
}

int main()
{
CIN;
freopen(&quot;numtri.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;numtri.out&quot;,&quot;w&quot;,stdout);

cin&gt;&gt;r;
REP(i,1,r) REP(j,1,i) cin&gt;&gt;ara[i][j];
ms(dp,-1);
cout&lt;&lt;func(1,1)&lt;&lt;endl;
return 0;
}

```

# USACO: Mother’s Milk

0

```
/*
PROG: milk3
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

struct data
{
int a,b,c;
data()
{
;
}
data(int x, int y, int z)
{
a=x,b=y,c=z;
}
};

int A,B,C;

bool ans[30];

bool visited[30][30][30];
int first=100;

void BFS(data x)
{
map&lt;data,bool&gt;mp;
queue&lt;data&gt;Q;
visited[x.a][x.b][x.c]=1;
Q.push(x);
while(!Q.empty())
{
data u=Q.front();
Q.pop();
if(u.a==0) ans[u.c]=1,first=min(first,u.c);
int bb=B-u.b,aa=A-u.a,cc=C-u.c;
if(u.c)
{
data c2b=u,c2a=u;
if(bb&gt;=u.c)
{
c2b.b+=u.c;
c2b.c=0;
}
else if(bb&lt;u.c)
{
c2b.b=B;
c2b.c-=bb;
}

if(aa&gt;=u.c)
{
c2a.a+=u.c;
c2a.c=0;
}
else if(aa&lt;u.c)
{
c2a.a=A;
c2a.c-=aa;
}
if(!visited[c2b.a][c2b.b][c2b.c])
{
Q.push(c2b);
visited[c2b.a][c2b.b][c2b.c]=1;
}
if(!visited[c2a.a][c2a.b][c2a.c])
{
Q.push(c2a);
visited[c2b.a][c2b.b][c2b.c]=1;
}
}

if(u.b)
{
data b2a=u,b2c=u;
if(aa&gt;=u.b)
{
b2a.a+=u.b;
b2a.b=0;
}
else
{
b2a.a=A;
b2a.b-=aa;
}
if(cc&gt;=u.b)
{
b2c.c+=u.b;
b2c.b=0;
}
else
{
b2c.c=C;
b2c.b-=cc;
}
if(!visited[b2a.a][b2a.b][b2a.c])
{
visited[b2a.a][b2a.b][b2a.c]=1;
Q.push(b2a);
}
if(!visited[b2c.a][b2c.b][b2c.c])
{
visited[b2c.a][b2c.b][b2c.c]=1;
Q.push(b2c);
}
}

if(u.a)
{
data a2b=u,a2c=u;
if(bb&gt;=u.a)
{
a2b.b+=u.a;
a2b.a=0;
}
else
{
a2b.b=B;
a2b.a-=bb;
}
if(cc&gt;=u.a)
{
a2c.c+=u.a;
a2c.a=0;
}
else
{
a2c.c=C;
a2c.c-=cc;
}
if(!visited[a2c.a][a2c.b][a2c.c])
{
visited[a2c.a][a2c.b][a2c.c]=1;
Q.push(a2c);
}
if(!visited[a2b.a][a2b.b][a2b.c])
{
visited[a2b.a][a2b.b][a2b.c]=1;
Q.push(a2b);
}
}

}
}

int main()
{
freopen(&quot;milk3.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;milk3.out&quot;,&quot;w&quot;,stdout);
cin&gt;&gt;A&gt;&gt;B&gt;&gt;C;
BFS(data(0,0,C));

cout&lt;&lt;first;
for(int i=first+1; i&lt;=C; i++) if(ans[i]) cout&lt;&lt;&quot; &quot;&lt;&lt;i;
cout&lt;&lt;endl;
return 0;
}

```

# USACO : Arithmetic Progressions

0

```
/*
PROG: ariprog
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;=b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int n,m;

bool present[300000];

int main()
{
freopen(&quot;ariprog.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;ariprog.out&quot;,&quot;w&quot;,stdout);
int maxx=INT_MIN;
cin&gt;&gt;n&gt;&gt;m;
for(int i=0; i&lt;=m; i++) for(int j=0; j&lt;=m; j++) present[i*i+j*j]=1,maxx=max(maxx,i*i+j*j);
vector&lt;int&gt;v;
REP(i,0,maxx) if(present[i]) v.pb(i);

vector&lt;pii&gt;ans;

int l=SZ(v);

for(int i=0; i&lt;l; i++)
for(int j=i+1; j&lt;l; j++)
{
int dis=v[j]-v[i];
int k;
int sum=v[i]+dis;
for(k=0; k&lt;n-2; k++)
{
sum+=dis;
if(!present[sum] || sum&gt;2*m*m)
{
break;
}
}
if(k==n-2)
ans.pb(MP(dis,v[i]));
}
sort(all(ans));
if(SZ(ans))
loop(i,SZ(ans)) cout&lt;&lt;ans[i].ss&lt;&lt;&quot; &quot;&lt;&lt;ans[i].ff&lt;&lt;endl;
else
cout&lt;&lt;&quot;NONE&quot;&lt;&lt;endl;
return 0;
}

```

# USACO: Ski Course Design

0

```
/*
PROG: skidesign
LANG: C++
*/

#include &lt;bits/stdc++.h&gt;

#define pii             pair &lt;int,int&gt;
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int main()
{
freopen(&quot;skidesign.in&quot;,&quot;r&quot;,stdin);
freopen(&quot;skidesign.out&quot;,&quot;w&quot;,stdout);
int n,x;
sf(n);
vector&lt;int&gt;v;
loop(i,n) sf(x),v.pb(x);
ll ans=INT_MAX;

for(int i=1; i&lt;=83; i++)
{
ll temp=0;
for(int j=0; j&lt;n; j++)
{
if(v[j]&lt;i) temp+=sqr(i-v[j]);
else if(v[j]&gt;i+17) temp+=sqr(v[j]-i-17);
}
ans=min(ans,temp);
}
cout&lt;&lt;ans&lt;&lt;endl;
return 0;
}

```

# USACO : Wormholes

0

```
/*
PROG: wormhole
LANG: C++
*/

#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
#define MAX_N 12

int N, X[MAX_N+1], Y[MAX_N+1];
int wife[MAX_N+1];
int next_on_right[MAX_N+1];

bool cycle_exists(void)
{
for (int start=1; start&lt;=N; start++)
{
int pos = start;
for (int count=0; count&lt;N; count++)
pos = next_on_right[wife[pos]];
if (pos != 0) return true;
}
return false;
}

int solve(void)
{
int i, total=0;
for (i=1; i&lt;=N; i++)
if (wife[i] == 0) break;

// everyone paired?
if (i &gt; N)
{
if (cycle_exists()) return 1;
else return 0;
}

// try pairing i with all possible other wormholes j
for (int j=i+1; j&lt;=N; j++)
if (wife[j] == 0)
{
// try pairing i &amp; j, let recursion continue to
// generate the rest of the solution
wife[i] = j;
wife[j] = i;
total += solve();
wife[i] = wife[j] = 0;
}
}

int main(void)
{
ifstream fin(&quot;wormhole.in&quot;);
fin &gt;&gt; N;
for (int i=1; i&lt;=N; i++) fin &gt;&gt; X[i] &gt;&gt; Y[i];
fin.close();

for (int i=1; i&lt;=N; i++) // set next_on_right[i]...
for (int j=1; j&lt;=N; j++)
if (X[j] &gt; X[i] &amp;&amp; Y[i] == Y[j]) // j right of i...
if (next_on_right[i] == 0 ||
X[j]-X[i] &lt; X[next_on_right[i]]-X[i])
next_on_right[i] = j;

ofstream fout(&quot;wormhole.out&quot;);
fout &lt;&lt; solve() &lt;&lt; &quot;\n&quot;;
fout.close();
return 0;
}

```