# UVa 10296 – Jogging Trails

0

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1237

Solution Idea:
—————–
Light OJ: 1086 – Jogging Trails is a similar problem. The main idea behind this problem is Chinese Postman Problem.

For details about this theorem is described in book Competitive programming 3 by Steven Halim.

```
#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf(&quot;Case %d:\n&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));
}
/*------------------------------------------------*/

ll g[16][16];
int degree[16];
ll dp[1&lt;&lt;16];
int n,m;

void floyed_warshal()
{
for(int k=0; k&lt;n; k++)
for(int i=0; i&lt;n; i++)
for(int j=0; j&lt;n; j++)
{
if(g[i][j]&gt;g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
}
}

{
if(ret!=-1) return ret;
int pos=0;
for(int i=0; i&lt;n; i++)
{
pos=i;
break;
}
ret=INT_MAX;
for(int i=pos+1;i&lt;n;i++)
{
{
}
}
return ret;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
//    sf(t);
//    TEST_CASE(t)
while(sf(n) &amp;&amp; n)
{
sf(m);
//        sff(n,m);
ll ans=0;
for(int i=0; i&lt;=n; i++) for(int j=0; j&lt;=n; j++) g[i][j]=INT_MAX;
ms(degree,0);
for(int i=0; i&lt;m; i++)
{
ll a,b,c;
sfffl(a,b,c);
a--;
b--;
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
degree[a]++;
degree[b]++;
ans+=c;
}

floyed_warshal();

for(int i=0; i&lt;n; i++)
if(degree[i]%2)

//        PRINT_CASE;
ms(dp,-1);
}

return 0;
}

```

# SPOJ KALTSUM – k Alternating Sum

0

Problem Link : http://www.spoj.com/problems/KALTSUM/

Solution Idea:
``` Break the problem into two cases: When k is greater than sqrt(n) and when k is less tahn or equal sqrt(n). Deal with them in different ways.```

``` Case 1: For any k>sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query. Case 2: Now when k <= sqrt(n), you need to do some preprocessing. ```

```let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1). ```
This solution idea is from this link.

```
#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf(&quot;Case %d:\n&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));}
/*------------------------------------------------*/

ll dp[318][100005];
ll csum[100005];
ll ara[100005];

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n,q;

sff(n,q);
for(int i=1;i&lt;=n;i++)
{
sfl(ara[i]);
csum[i]=csum[i-1]+ara[i];
}

int root=ceil(sqrt(n));

for(int i=1;i&lt;=root;i++)
{
ll temp=0,sub=0;
for(int j=n;j&gt;=1;j--)
{
temp+=ara[j];
if(j+i&gt;n)
sub=0;
else
sub=ara[j+i];
temp-=sub;

if(j+i-1&gt;n)
dp[i][j]=0;
else
dp[i][j]=temp-dp[i][j+i];
}
}
//
//    for(int i=1;i&lt;=root;i++,cout&lt;&lt;endl)
//        for(int j=1;j&lt;=n;j++)
//        cout&lt;&lt;dp[i][j]&lt;&lt;&quot; &quot;;

while(q--)
{
int a,b,k;
sfff(a,b,k);
ll ans=0;
if(k&gt;root)
{
for(int i=a,j=0;i&lt;=b;i+=k,j++)
{
if(j%2==0)
ans+=csum[i+k-1]-csum[i-1];
else
ans-=csum[i+k-1]-csum[i-1];
}
pf(&quot;%lld\n&quot;,ans);
}
else
{
int turn=(b-a+1)/k;
if(turn%2==1)
pf(&quot;%lld\n&quot;,dp[k][a]+dp[k][b+1]);
else
pf(&quot;%lld\n&quot;,dp[k][a]-dp[k][b+1]);
}
}

return 0;
}

```

# 1217 – Neighbor House (II)

0

Problem Link : http://lightoj.com:81/volume/problem/1217

```
#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf(&quot;Case %d:\n&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 n;
int ara[1001];

int    dp[1001][1001][3];
bool xxxxx[1001][1001][3];
int yy=1;

int func(int idx, int last, int state)
{

if(idx&gt;n)
{
if(state==0 &amp;&amp; last!=n)
return ara[1];
return 0;
}

int &amp;ret=dp[idx][last][state];
bool &amp;cas=xxxxx[idx][last][state];
if(cas) return ret;
cas=1;

////    if(ret!=-1) return ret;

int p=0,q=0;

if(idx==1)
{
p=ara[1]+func(idx+2,idx,1);
q=func(idx+1,last,state);
}
else if(idx==2)
{
p=ara[2]+func(idx+2,idx,2);
q=func(idx+1,0,state);
}
else if(idx==n)
{
if(last!=n-1 &amp;&amp; state!=1)
p=ara[n]+func(idx+2,idx,state);
q=func(idx+1,last,state);
}
else
{
p=ara[idx]+func(idx+2,idx,state);
q=func(idx+1,last,state);
}

return ret=max(p,q);

}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
sf(n);
for(int i=1; i&lt;=n; i++) sf(ara[i]);
//        ms(dp,-1);
//        yy++;
ms(xxxxx,0);
PRINT_CASE;
printf(&quot;%d\n&quot;,func(1,0,0));

}

return 0;
}

```

# Light OJ: 1421 – Wavio Sequence

0

Problem Link : http://lightoj.com:81/volume/problem/1421

```
#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 ara[100006];
int lis[100005];
int lds[100005];
int temp[100005];

void LIS(int n)
{
loop(i,n+5) temp[i]=infinity;
temp[0]=-infinity;
int len=0;
for(int i=0; i&lt;n; i++)
{
int lo=0,hi=len;
while(lo&lt;=hi)
{
int mid=(lo+hi)/2;
if(temp[mid]&lt;ara[i])
lo=mid+1;
else
hi=mid-1;
}
temp[lo]=ara[i];
lis[i]=lo;
if(lo&gt;len) len++;
}
}

void LDS(int n)
{
loop(i,n+5) temp[i]=infinity;
temp[0]=-infinity;
int len=0;
for(int i=0; i&lt;n; i++)
{
int lo=0,hi=len;
while(lo&lt;=hi)
{
int mid=(lo+hi)/2;
if(temp[mid]&lt;ara[i])
lo=mid+1;
else
hi=mid-1;
}
temp[lo]=ara[i];
lds[i]=lo;
if(lo&gt;len) len++;
}
}

int main()
{

//     freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n;
int t;
sf(t);
TEST_CASE(t)
{
sf(n);
loop(i,n) sf(ara[i]);
LIS(n);
reverse(ara,ara+n);
LDS(n);
//        loop(i,n) cout&lt;&lt;lis[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;
//        loop(i,n) cout&lt;&lt;lds[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;
reverse(lds,lds+n);
int ans=0;
for(int i=0; i&lt;n; i++)
{
ans=max(ans,(2*min(lis[i],lds[i]))-1);
}
PRINT_CASE;
printf(&quot;%d\n&quot;,ans);
}

return 0;
}

```

# Light OJ: 1326 – Race

0

Problem Link : http://lightoj.com:81/volume/problem/1326

Solution Idea:

Let’s define dp(i) as the number of ways in which a race with “i” horses can finish.

Suppose we have “i” horses at the race and we will choose k of them for the first place, leaving “i – k” for the second (or higher) place. The process to count the number of ways to choose horses for the second place is equals to the original problem. This is the reason why we use dp.

(This Solution idea is from Manuel Pinda)

```
#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              10056
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf(&quot;Case %d:\n&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));}
/*------------------------------------------------*/

ll dp[1003][1003];
ll ans[1003];

ll nCr(int n, int r)
{
if(r==1) return n;
if(n==r) return 1;

ll &amp;ret=dp[n][r];

if(ret!=-1) return ret;

return ret=(nCr(n-1,r-1)%MOD+nCr(n-1,r)%MOD)%MOD;
}

ll func(int n)
{
if(n==0) return 1;
if(ans[n]!=-1) return ans[n];

ll ret=0;

for(int i=1;i&lt;=n;i++)
{
ret+=(nCr(n,i)*func(n-i))%MOD;
ret%=MOD;
}

return ans[n]=ret;
}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);

ms(dp,-1);
ms(ans,-1);

TEST_CASE(t)
{
int n;
sf(n);
PRINT_CASE;

printf(&quot;%lld\n&quot;,func(n));

}

return 0;
}

```

# Light OJ: 1095 – Arrange the Numbers

0

Problem Link : http://lightoj.com:81/volume/problem/1095

```
#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf(&quot;Case %d:\n&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));}
/*------------------------------------------------*/

ll fact[1005];

ll dp[1005][1005];

ll nCk(int n, int k)
{
if(k==1) return n;
if(n==k) return 1;

if(dp[n][k]!=-1) return dp[n][k];

return dp[n][k]= (nCk(n-1,k-1)+nCk(n-1,k))%MOD;
}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

fact[0]=1;

for(ll i=1; i&lt;1002; i++) fact[i]=(fact[i-1]*i)%MOD;

int t;
sf(t);
ms(dp,-1);

TEST_CASE(t)
{
ll n,m,k;
sfffl(n,m,k);
ll ans=nCk(m,k);

int nn=n-k;

ll ans1=fact[n-k];

for(int i=1; i&lt;=(m-k); i++)
{
if(i%2==1)
ans1-= (nCk(m-k,i)*fact[nn-i])%MOD;
else
ans1+= (nCk(m-k,i)*fact[nn-i])%MOD;
ans1=(ans1+MOD)%MOD;
}

PRINT_CASE;

printf(&quot;%lld\n&quot;,(ans*ans1)%MOD);

}

return 0;
}

```

# Light OJ: 1127 – Funny Knapsack

0

Problem Link : http://lightoj.com:81/volume/problem/1127

```

#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 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 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));}
/*------------------------------------------------*/

ll ara[50];
ll l[65536],r[65536];

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int t;
sf(t);
TEST_CASE(t)
{
ms(l,0);
ms(r,0);
ll n,w;
sffl(n,w);
loop(i,n)
{
sfl(ara[i]);
}

int m1=n/2;
//        if(m1==0) m1++;
int m2=(n-m1);

{
loop(j,m1)
if(check(i,j))
{
l[i]+=ara[j];
}
}

{
loop(j,m2)
{
if(check(i,j))
r[i]+=ara[m1+j];
}
}

sort(r,r+bb);

ll ans=0;

loop(i,aa)
{
if(w-l[i]&gt;=0)
ans+= upper_bound(r,r+bb,w-l[i])-r;
}

PRINT_CASE;
pf(&quot;%lld\n&quot;,ans);
}
return 0;
}

```

# Light OJ: 1170 – Counting Perfect BST

0

Problem Link : http://lightoj.com:81/volume/problem/1170

```
#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              100000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.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 loop1(i,n)       for(int i=1;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));}
/*------------------------------------------------*/

ll numbers[1000006];
int cnt=0;
void generate_num()
{
for(ll i=2;i&lt;=100000;i++)
{
ll num=i*i;
while(num&lt;=10000000000)
{
numbers[cnt++]=num;
num*=i;
}
}

sort(numbers,numbers+cnt);
cnt=unique(numbers,numbers+cnt)-numbers;
numbers[cnt++]=1000000000000000;

}

ll fact[1000006];

void gen_fact()
{
fact[0]=1;
for(int i=1;i&lt;=1000005;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
}

ll mod_inv(ll n, ll pow)
{
if(pow==0) return 1;
if(pow%2==0)
{
ll ret=mod_inv(n,pow/2)%MOD;
return (ret*ret)%MOD;
}
return ((n%MOD)*(mod_inv(n,pow-1)%MOD))%MOD;
}

int main()
{

///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

generate_num();
gen_fact();

int t;
sf(t);
TEST_CASE(t)
{
ll a,b;
sffl(a,b);

ll r=upper_bound(numbers,numbers+cnt,b)-numbers;
ll l=lower_bound(numbers,numbers+cnt,a)-numbers;
ll n=(r-l);
PRINT_CASE;
if(n==0)
pf(&quot;0\n&quot;);
else
{
ll ans=(fact[n+1]*fact[n])%MOD;
ans=mod_inv(ans,MOD-2);
ans=(fact[2*n]*ans)%MOD;
pf(&quot;%lld\n&quot;,ans);
}

}

return 0;
}

```

# UVa 11795 – Mega Man’s Mission

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2895

```
/*
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 n;
ll dp[18][(1&lt;&lt;17)+100];
int ara[18][18];
int temp[18];

ll func(int idx, int mask)
{

if(ret!=-1) return ret;

ll p=0;

for(int i=0; i&lt;n; i++)
{
{
if(ara[idx][i] || ara[0][i] || temp[i])
{
vector&lt;int&gt;v;
loop(j,n)
{
if(temp[j]==0 &amp;&amp; ara[idx][j])
{
temp[j]=1;
v.pb(j);
}
}
loop(j,SZ(v)) temp[v[j]]=0;
}
}
}

return ret=p;

}

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

int t;
cin&gt;&gt;t;
TEST_CASE(t)
{
cin&gt;&gt;n;
loop(i,n+1)
{
string str;
cin&gt;&gt;str;
loop(j,n) ara[i][j]=(str[j]=='1');
}

ms(dp,-1);
CASE_PRINT;
cout&lt;&lt;func(0,0)&lt;&lt;endl;

}

return 0;
}

```

# UVa 10131 – Is Bigger Smarter?

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1072

## Solution Idea:

Given some pairs where in each pair fist integer is weight and second integer is IQ. Now we have to select some pairs from the given pairs where –

W[a[1]] < W[a[2]] < … < W[a[n]]

and  S[a[1]] > S[a[2]] > … > S[a[n]]

Here n is the number of pairs which we select and a[] contain the index of the pairs which is given in the input order.

After reading the problem statement we can understand that this is a LIS(Longest Increasing Sub-sequence) problem. Generally we can calculate LIS of an array of integers by comparing the values. But In this case we need one first element of the pair in strictly increasing order and second element of the pair in strictly decreasing order. So for solving this problem we can sort one element of the input pairs initially in a order which we want in the output and run LIS on all the input pairs.

In this solution I am sorting the IQ elements in Descending Order because we want it in the output in descending order. After sorting we need to run LIS for every input pair. We need to do this because we have to calculate the maximum LIS and for this we are taking every input pair as the staring element of the LIS and we are taking the maximum one as our ans.

Note that in the problem statement the inequalities are “strict”. Therefore within LIS algorithm, we need to check that the next weight in the sequence is greater than the previous weight, and the next IQ is less than the previous one.

LIS algorithm tutorial in Bengali is Here.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 w, s, id;
};

vector&lt;data&gt;v;

int n=0;

int dp[1005];
int path[1005];

bool cmp(data a, data b)
{
return a.s&gt;b.s;

}

int LIS(int idx)
{

int &amp;ret=dp[idx];
if(ret!=-1) return ret;

int maxi=0;

for(int i=idx+1;i&lt;n;i++)
{
if(v[i].w&gt;v[idx].w)
{
if(LIS(i)&gt;maxi)
{
maxi=LIS(i);
path[idx]=i;
}
}
}

return dp[idx]=1+maxi;
}

void path_print(int idx)
{
if(idx==-1) return;
printf(&quot;%d\n&quot;,v[idx].id);
path_print(path[idx]);
}

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

int a,b;
while(sff(a,b)==2)
{
data temp;
temp.w=a;
temp.s=b;
temp.id=n+1;
v.pb(temp);
n++;
}

sort(all(v),cmp);
ms(dp,-1);
ms(path,-1);

int ans=-1,start;

loop(i,n)
{
if(LIS(i)&gt;ans)
{
ans=LIS(i);
start=i;
}
}
printf(&quot;%d\n&quot;,ans);
path_print(start);

return 0;
}

```