Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:64000000")
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- #define INF 1000*1000*1000
- vector<pair<int,int> > line;
- int m;
- int path[60002][4] = {0};
- int dp[60002];
- int dfs(int k)
- {
- if(dp[k] != -1)
- return dp[k];
- int a = line[k].first;
- int b = line[k].second;
- if(a <= m && b >= m)
- return 0;
- int mn = INF;
- for (int i = 0; i < line.size(); i++)
- {
- int L = line[i].first;
- int R = line[i].second;
- if(L > a && R > b && L <= b)
- {
- int r = dfs(i) + 1;
- if( r < mn)
- {
- mn = r;
- path[k][0] = L;
- path[k][1] = R;
- path[k][2] = i;
- }
- }
- }
- return dp[k] = mn;
- }
- int main()
- {
- memset(dp,255,sizeof dp);
- //freopen ("input.txt","r",stdin);
- scanf ("%d",&m);
- line.push_back(make_pair(-666666,0));
- while(1)
- {
- int a,b;
- scanf ("%d%d",&a,&b);
- if(a == 0 && b == 0)
- break;
- line.push_back(make_pair(a,b));
- }
- int ans = dfs(0);
- if(ans == INF)
- puts ("No solution");
- else
- {
- printf ("%d\n",ans);
- int j = 0;
- for (int i = 0; i < ans; i++)
- {
- printf ("%d %d\n",path[j][0],path[j][1]);
- j = path[j][2];
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement