#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; int n; string str; int main() { int t; cin>>t; while(t–) { cin>>n; cin>>str; int i=0,j=1,k; while(i<n && j<n) { for(k=0;k<n;k++) { if(str[(k+i)%n]!=str[(k+j)%n]) break; } if(k==n) break; if(str[(k+i)%n]>str[(k+j)%n]) i=i+k+1; else if(str[(k+i)%n]<str[(k+j)%n]) j=j+k+1; if(i==j) j+=1; } cout<<((i>j)?j:i)<<"\n"; } return 0; }
Month: April 2015
10199
#include <iostream> #include <cstdio> #include <vector> #include <sstream> #include <string> #include <algorithm> #include <queue> #include <cstring> #include <map> #include <set> using namespace std; map<string,int> mp; map<int,string> mp2; vector<int> gr[105]; //vector<int> V; bool visit[105]; bool ap[105]; int discTime[105]; int low[105]; int par[105]; int cnt; set<string> SET; void cutvertex(int u) { static int dsc_time=0; low[u]=discTime[u]=dsc_time++; visit[u]=1; int
482
#include <iostream> #include <sstream> #include <map> #include <string> #include <cstring> #include <queue> using namespace std; map<int,string> mp; int main() { int* arr; string db; int t,n; string str,s1,s2,s3; queue<int> q; getline(cin,str); stringstream ss; ss<<str; ss>>t; getline(cin,str); while(t–) { getline(cin,s1); getline(cin,s2); //q.clear(); ss.clear(); ss<<s1; int mx=0; while(ss>>n) { q.push(n); if(n>mx) mx=n; } mp.clear(); ss.clear(); ss<<s2; while(!q.empty())
Longest Increasing Subsequence
LIS problem has a recursive solution and this also can be solved using DP. Recursive solution: #include <iostream> #include <cstdlib> using namespace std; int lis(int arr[],int length,int *max_length) { if(length==1) return 1; int res,max_end_here=1; //recursively we get all LIS those are ending with arr[0],arr[1] //…and arr[length-1] and if max ending with arr[length-1] //requires to be
315
A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks. For
11677
#include <iostream> using namespace std; int main() { int h1,h2,m1,m2; int a,b; while(cin>>h1) { cin>>m1>>h2>>m2; if(h1+h2+m1+m2==0) break; a = h1*60+m1; b = h2*60+m2; if(b<a) { cout<<(24*60)-a+b<<"\n"; } else { cout<<b-a<<"\n"; } } return 0; }
11777
#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; int main() { int tt,kase=1; double s,a,MN,avg; cin>>tt; while(tt–) { MN=25; s = 0; avg = 0; for(int i=0;i<4;i++) { cin>>a; s+=a; } for(int i=0;i<3;i++) { cin>>a; avg+=a; if(a<MN) MN=a; } avg-=MN; avg/=2; s+=avg; if(s>=90) cout<<"Case "<<kase++<<": A\n"; else if(s>=80) cout<<"Case "<<kase++<<": B\n"; else
473
This solution is based on 0/1 knapsack problem. dp[i][j][k] is the maximum amount of songs with i songs while k unit time is left in disk j. #include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <string> using namespace std; int N,T,M; int song[800]; int dp[800][100][100]; void DP() { for(int i=0;i<N;i++) { for(int j=0;j<=M;j++) {
10943
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; ll dp[105][105];//length,sum int N,K; void DP() { memset(dp,0,sizeof(dp)); for(int i=0;i<105;i++) dp[1][i]=1; for(int length = 2;length<=K;length++) { dp[length][0]=1; for(int sum=1;sum<=N;sum++) { for(int j=0;j<=sum;j++) { dp[length][sum]+=dp[length-1][sum-j]; dp[length][sum]%=1000000; } } } } int main() { while(scanf("%d%d",&N,&K),N+K) { DP(); cout<<dp[K][N]<<"\n"; } return 0; }
10616
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int N,Q; int M,D; int num[210]; int tt; int dp[210][15][25]; void DP() { dp[0][0][0]=1; for(int i=1;i<=N;i++) { for(int j=0;j<=M;j++) { for(int k=0;k<D;k++) { dp[i][j][k]=dp[i-1][j][k];//as no element is added if(j) { int tmp = (D+k-num[i]%D)%D;//in case k-num[i]%10 is less than 0 , D is added dp[i][j][k]+=dp[i-1][j-1][tmp]; //from