#include<iostream> #include<cstdio> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<set> #include<utility> #include<iomanip> #include<queue> #include<deque> #include<iterator> #include<assert.h> #include<bitset> #include<climits> #include<ctime> #include<complex> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define PB push_back #define PI acos(-1.0) #define MP(a,b) make_pair(a,b) #define PII pair<int,int> #define PCC pair<char,char> #define PIC pair<int,char> #define PCI pair<char,int> #define VS vector<string> #define VI vector<int> #define VC vector<char> #define max3(a,b,c) max(a,max(b,c) #define min3(a,b,c) min(a,min(b,c) #define READ freopen("input.txt", "r", stdin) #define WRITE freopen("output.txt", "w", stdout) #define LL long long #define FOR(i,a,b) for(int i=a;i<=b;i++) #define RFOR(i,a,b) for(int i=a;i>=b;i--) #define For(i,a) for(int i=0;i<a;i++) #define S(a) scanf("%d",&a) #define S2(a,b) scanf("%d%d",&a,&b) #define S3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define SLL(a) scanf("%lld",&a) #define SLL2(a,b) scanf("%lld%lld",&a,&b) #define SLL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c) #define SS(a) scanf("%s",a) #define SC(a) scanf("%c",&a) #define SD(a) scanf("%lf",&a) #define P(a) printf("%d",a) #define PLL(a) printf("%lld",a) #define PD(a) printf("%lf",a) #define PC(a) printf("%c",a) #define PS(a) printf("%s",a) #define KS printf("Case %d: ",kk++) #define KN printf("Case %d:\n",kk++) #define KH printf("Case #%d: ",kk++) #define NL printf("\n") #define DB cout<<"done"<<endl; #define EPS 1e-9 #define MOD 1000000007 #define INF INT_MAX/3 #define MX 100010 template<typename T>inline string tostring(T a){ostringstream os("");os << a;return os.str();} template<typename T>inline LL tolong(T a){LL res;istringstream os(a);os>>res;return res;} template<typename T>inline VI parse(T str){VI res;int s;istringstream os(str);while(os>>s)res.PB(s);return res;} template< class T > inline T _sqrt(T x) { return (T) sqrt( (double) x); } template< class T > inline T _bigmod(T n,T m) {T ans=1,mult=n%MOD; while(m){ if(m & 1) ans=(ans*mult)%MOD; m>>=1; mult=(mult*mult)%MOD; } ans%=MOD; return ans;} template< class T > inline T _modinv(T x) {return _bigmod(x,(T) MOD-2)%MOD;} inline int LEN(string a) {return a.length();} inline int LEN(char a[]) {return strlen(a);} template<class T> inline T _gcd(T a, T b){return (b.chk()==0) ? a : _gcd(b, a % b);} template< class T > inline T _lcm(T x,T y) { return x*y/_gcd(x,y);} //char ss[1010][1000010]; int main() { int tc,kk=1,n,m; string s[1010],tmp; cin>>tc; while(tc--) { cin>>n; int scnt=0; For(i,n) cin>>s[i]; sort(s,s+n); int cnt=0; int pos=0; int pos2=0; while(s[0][pos]==s[1][pos]) pos++; cnt+=pos+1; pos=0; while(s[n-1][pos]==s[n-2][pos]) pos++; cnt+=pos+1; //cout<<cnt<<endl; for(int i=1;i<n-1;i++) { pos=0; while(s[i][pos]==s[i-1][pos]) pos++; pos2=0; //DB; while(s[i][pos2]==s[i+1][pos2]) pos2++; //DB; pos=max(pos,pos2); cnt+=pos+1; } //cout<<cnt<<endl; P(cnt); NL; } return 0; }
Friday, 19 October 2012
UVa 12506 - Shortest Names Solution
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment