KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）题解

A - Takahashi san 2

Problem Statement
KEYENCE has a culture of addressing everyone with the suffix “-san,” regardless of roles, age, or positions.

You are given a string S consisting of lowercase English letters.

If S ends with san, print Yes; otherwise, print No.

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);string s;cin>>s;int n=s.length();if(n>=2) {if(s[n-1]=='n' && s[n-2]=='a' && s[n-3]=='s') puts("Yes");else puts("No");}return 0;
}

B - Unvarnished Report

給2个字符串，判断第一个字符不同的位置。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);string s,t;cin>>s>>t;Rep(i,s.length()) if(s[i]!=t[i]) {cout<<i+1<<endl;return 0;}if(s.length()<t.length()) {cout<<s.length()+1<<endl;}elseif(s.length()>t.length()) {cout<<t.length()+1<<endl;}else	cout<<"0";return 0;
}

C - Separated Lunch

给 $n$ 个数，分成两组，问其中和较大组的和的最小值。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);int n;cin>>n;vi a(n);Rep(i,n) cin>>a[i];int c=2e9;Rep(i,(1<<n)) {int p=0,q=0;Rep(j,n)if(i&(1<<j)) p+=a[j];else q+=a[j];gmin(c,max(p,q)	)}cout<<c;return 0;
}

D - Laser Marking

镭射 $n$ 个线段 $A_i,B_i)-(C_i,D_i)$ ，镭射机从原点开始，进行镭射，已知镭射时的速度 $S$ 和未镭射时的速度 $T$ ，求最小时间。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
ll sqr(ll x){return x*x;
}
int g[1010];
ll a[10],b[10],c[10],d[10];int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);int n,s,t;cin>>n>>s>>t;For(i,n) cin>>a[i]>>b[i]>>c[i]>>d[i];double p=0;For(i,n) {p+=sqrt(sqr(c[i]-a[i])+sqr(d[i]-b[i]));}	double q=1e18;For(i,n) g[i]=i;do{Rep(st,1<<n) {double cq=0;ll x=0,y=0;For(i,n) {if(st&(1<<i-1)) {cq+=sqrt(sqr(x-a[g[i]])+sqr(y-b[g[i]]));x=c[g[i]],y=d[g[i]];}else {cq+=sqrt(sqr(x-c[g[i]])+sqr(y-d[g[i]]));x=a[g[i]],y=b[g[i]];}}gmin(q,cq)}
//		cout<<p/(double)t+q/(double)s<<endl;}while(next_permutation(g+1,g+1+n));printf("%.10lf\n",p/(double)t+q/(double)s);return 0;
}

E - Sensor Optimization Dilemma 2

有 $n$ 个工序，每个工序 $i$ 提供两种不同的机器处理方案。对于第 $i$ 个工序，方案1是花费 $a_i$ 元可以处理 $p_i$ 台机器，方案2是花费 $b_i$ 元可以处理 $q_i$ 台机器。每台机器必须经过所有 $n$ 个工序的处理，恰好处理一次。

在给定的预算限制 $x$ 元内，求最多可以处理多少台机器。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
ll n,x,a[110],b[110],q[110],p[110];
bool ck(ll m) {ll an=0;For(i,n) {ll tp=1e18;Rep(j,101) {ll t1=b[i]*j;if(t1<m) {gmin(tp,j*q[i] +(m-t1+a[i]-1)/a[i] * p[i])}else gmin(tp,j*q[i] )}an+=tp;}return an<=x;
}
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);n=read(),x=read();For(i,n) {cin>>a[i]>>p[i]>>b[i]>>q[i];if(p[i]*b[i]>q[i]*a[i]) swap(a[i],b[i]),swap(p[i],q[i]);}int l=0,r=1e9,an=l;while(l<=r) {int m=(l+r)/2;if(ck(m)) l=m+1,an=m;else r=m-1;}cout<<an;return 0;
}

F - Shipping

有一系列订单，编号为 $1, 2, \dots, N$ ，每个订单i都有一个确定的放置日期 $T_i$ 。这些订单需要按照以下规则进行发货：

每天最多可以一起发货 $K$ 个订单。
订单 $i$ 只能在日期 $T_i$ 或之后发货。
一旦发货完成，需要等待 $X$ 天才能再次发货。也就是说，如果某天发货了，那么下一次发货只能在 $X$ 天后。
每个订单从放置到发货的每一天都会累积 $1$ 单位的不满。

目标是找到所有订单的总不满累积的最小可能值，通过最优地安排发货日期。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
ll n,k,x,a[110],s[110]={};
//ll f[1010]={},ans=0;
map<ll,ll> f[100+1];
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);cin>>n>>k>>x;For(i,n) cin>>a[i];For(i,n) s[i]+=s[i-1]+a[i];f[0][0]=0;For(i,n) {Fork(j,max(1,i-(int)k+1),i) {for(auto pp:f[j-1]) {ll tt=pp.fi,sc=pp.se;ll p=sc;ll nowt=a[i];if(j>1) gmax(nowt,tt+x)ll nc=p + nowt*(i-j+1) - (s[i]-s[j-1]);if(f[i].find(nowt)!=f[i].end()) gmin(f[i][nowt],nc)else f[i][nowt]=nc;}}}ll ans=1e18;for(auto pp:f[n]) gmin(ans,pp.se)cout<<ans;return 0;
}

G- Only One Product Name

所有KEYENCE产品名称由两个大写英文字母组成。已经使用了 $N$ 个产品名称，第 $i$ 个产品名称（ $\leq i \leq N$ ）是 $S_i$ 。一旦产品名称被使用，就不能重复使用，因此他们决定创建一个NG（Not Good）列表，以快速识别之前使用过的产品名称。

NG列表必须满足以下条件：

它由一个或多个字符串组成，每个字符串由大写英文字母组成。
对于每个已经使用的产品名称，列表中至少存在一个包含该名称作为（连续）子字符串的字符串。
列表中的任何字符串都不包含任何长度为2的（连续）子字符串，这些子字符串不是已经使用过的产品名称。

目标是找到NG列表中字符串的最小可能数量。

把字母当成点建边，本题变成链覆盖所有边。容易发现直接缩点后除非变成存在变成单点的情况，否则不影响答案。变成单点的情况需要额外给答案累加1.
先通过tarjen缩点把图变成DAG。
将边转成点，重新建图，直接使用最小链覆盖模型。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int f[30][30]={};const int MAXN = 500005;
std::vector<int> G[MAXN];
int dfn[MAXN], low[MAXN], scc_id[MAXN];
bool in_stack[MAXN];
int n, m, dfn_max, scc_count=1;
std::stack<int> s;void tarjan(int u) {dfn[u] = low[u] = ++dfn_max;s.push(u);in_stack[u] = true;for (int i = 0; i < G[u].size(); ++i) {int v = G[u][i];if (!dfn[v]) {tarjan(v);low[u] = std::min(low[u], low[v]);} else if (in_stack[v]) {low[u] = std::min(low[u], dfn[v]);}}if (low[u] == dfn[u]) {while (true) {int v = s.top(); s.pop();in_stack[v] = false;scc_id[v] = scc_count;if (v == u) break;}++scc_count;}
}#define MAXN (1000000+100)
#define MAXM (6000000+100)
class Max_flow  //dinic+当前弧优化   
{    
public:    int n,t;    int q[MAXN];    int edge[MAXM],Next[MAXM],Pre[MAXN],weight[MAXM],size;    void addedge(int u,int v,int w)      {      edge[++size]=v;      weight[size]=w;      Next[size]=Pre[u];      Pre[u]=size;      }      void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}     bool b[MAXN];    int d[MAXN];    bool SPFA(int s,int t)      {      For(i,n) d[i]=INF;    MEM(b)    d[q[1]=s]=0;b[s]=1;      int head=1,tail=1;      while (head<=tail)      {      int now=q[head++];      Forp(now)      {      int &v=edge[p];      if (weight[p]&&!b[v])      {      d[v]=d[now]+1;      b[v]=1,q[++tail]=v;      }      }          }      return b[t];      }     int iter[MAXN];  int dfs(int x,int f)  {  if (x==t) return f;  Forpiter(x)  {  int v=edge[p];  if (weight[p]&&d[x]<d[v])  {  int nowflow=dfs(v,min(weight[p],f));  if (nowflow)  {  weight[p]-=nowflow;  weight[p^1]+=nowflow;  return nowflow;  }  }  }  return 0;  }  int max_flow(int s,int t)  {  (*this).t=t;int flow=0;  while(SPFA(s,t))  {  For(i,n) iter[i]=Pre[i];  int f;  while (f=dfs(s,INF))  flow+=f;   }  return flow;  }   void mem(int n)    {    (*this).n=n;  size=1;    MEM(Pre)   }    
}S;  
int b[26*26+100]={};
int b2[26*26+100]={};int main()
{
//	freopen("g.in","r",stdin);
//	freopen(".out","w",stdout);m=read();For(i,m) {string s;cin>>s;f[s[0]-'A'][s[1]-'A']=1;}Rep(i,26) Rep(j,26) if(f[i][j]) G[i+1].pb(j+1);n=26;for (int i = 1; i <= n; ++i) {if (!dfn[i]) {tarjan(i);}}std::vector<int> new_G[MAXN];for (int u = 1; u <= n; ++u) {for (int v : G[u]) {if (scc_id[u] != scc_id[v]) {new_G[scc_id[u]].push_back(scc_id[v]);b[scc_id[u]]=1;b[scc_id[v]]=1;}else {b2[scc_id[u]]=1;}}}scc_count--;vector<pair<int,int> > ve;for (int i = 1; i <= scc_count; ++i) {for (int v : new_G[i]) {ve.pb(mp(i,v));}}int n2=SI(ve);ll g[26*26+10][26*26+10]={};Rep(i,n2) {auto p=ve[i];}Rep(i,n2) Rep(j,n2) {auto p=ve[i],q=ve[j];if(p.se==q.fi) g[i+1][j+1]=1;}For(k,n2) For(i,n2) For(j,n2) g[i][j]|=g[i][k]&g[k][j];S.mem(2*n2+2);Fork(i,2,n2+1) S.addedge2(1,i,1);Fork(i,n2+2,2*n2+1) S.addedge2(i,2*n2+2,1);For(i,n2) {For(j,n2) if(g[i][j]){S.addedge2(i+1,j+1+n2,1);}}int ans=0;For(i,scc_count) ans+=(b2[i]==1)&(b[i]==0);ll t=S.max_flow(1,2*n2+2);cout<<n2-t+ans;return 0;
}