Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received embosser and was to take stock of the whole exposition.
Embosser is a special devise that allows to "print" the text of a plastic tape. Text is printed sequentially, character by character. The device consists of a wheel with a lowercase English letters written in a circle, static pointer to the current letter and a button that print the chosen letter. At one move it's allowed to rotate the alphabetic wheel one step clockwise or counterclockwise. Initially, static pointer points to letter 'a'. Other letters are located as shown on the picture:
After Grigoriy add new item to the base he has to print its name on the plastic tape and attach it to the corresponding exhibit. It's not required to return the wheel to its initial position with pointer on the letter 'a'.
Our hero is afraid that some exhibits may become alive and start to attack him, so he wants to print the names as fast as possible. Help him, for the given string find the minimum number of rotations of the wheel required to print it.
The only line of input contains the name of some exhibit — the non-empty string consisting of no more than 100 characters. It's guaranteed that the string consists of only lowercase English letters.
Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input.
zeus
18
map
35
ares
34
To print the string from the first sample it would be optimal to perform the following sequence of rotations:
- from 'a' to 'z' (1 rotation counterclockwise),
- from 'z' to 'e' (5 clockwise rotations),
- from 'e' to 'u' (10 rotations counterclockwise),
- from 'u' to 's' (2 counterclockwise rotations).
题意：
题解：
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set> 10 #include<cmath> 11 #include<queue> 12 #include<bitset> 13 #include<math.h> 14 #include<vector> 15 #include<string> 16 #include<stdio.h> 17 #include<cstring> 18 #include<iostream> 19 #include<algorithm> 20 #pragma comment(linker, "/STACK:102400000,102400000") 21 using namespace std; 22 #define A first 23 #define B second 24 const int mod=1000000007; 25 const int MOD1=1000000007; 26 const int MOD2=1000000009; 27 const double EPS=0.00000001; 28 //typedef long long ll; 29 typedef __int64 ll; 30 const ll MOD=1000000007; 31 const int INF=1000000010; 32 const ll MAX=1ll<<55; 33 const double eps=1e-5; 34 const double inf=~0u>>1; 35 const double pi=acos(-1.0); 36 typedef double db; 37 typedef unsigned int uint; 38 typedef unsigned long long ull; 39 int n; 40 char a[105]; 41 int main() 42 { 43 cin>>a; 44 int len=strlen(a); 45 int sum=0; 46 char be='a'; 47 for(int i=0;i<len;i++) 48 { 49 int exm=0; 50 exm=abs(a[i]-be); 51 if(exm>13) 52 exm=26-exm; 53 sum=sum+exm; 54 be=a[i]; 55 } 56 cout<<sum<<endl; 57 return 0; 58 }
题意：
题解：
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set> 10 #include<cmath> 11 #include<queue> 12 #include<bitset> 13 #include<math.h> 14 #include<vector> 15 #include<string> 16 #include<stdio.h> 17 #include<cstring> 18 #include<iostream> 19 #include<algorithm> 20 #pragma comment(linker, "/STACK:102400000,102400000") 21 using namespace std; 22 #define A first 23 #define B second 24 const int mod=1000000007; 25 const int MOD1=1000000007; 26 const int MOD2=1000000009; 27 const double EPS=0.00000001; 28 //typedef long long ll; 29 typedef __int64 ll; 30 const ll MOD=1000000007; 31 const int INF=1000000010; 32 const ll MAX=1ll<<55; 33 const double eps=1e-5; 34 const double inf=~0u>>1; 35 const double pi=acos(-1.0); 36 typedef double db; 37 typedef unsigned int uint; 38 typedef unsigned long long ull; 39 int n; 40 int a[200005]; 41 int main() 42 { 43 int n; 44 scanf("%d",&n); 45 for(int i=1;i<=n;i++) 46 scanf("%d",&a[i]); 47 int flag=0; 48 for(int i=1;i<n;i++) 49 { 50 a[i]=a[i]%2; 51 if(a[i]<=a[i+1]) 52 a[i+1]-=a[i]; 53 else 54 { 55 flag=1; 56 break; 57 } 58 } 59 if((n==1)&&(a[1]%2)) 60 flag=1; 61 if(flag==0&&a[n]%2) 62 flag=1; 63 if(flag==0) 64 cout<<"YES"<<endl; 65 else 66 cout<<"NO"<<endl; 67 return 0; 68 }
Arseniy is already grown-up and independent. His mother decided to leave him alone for m days and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy's clothes.
Ten minutes before her leave she realized that it would be also useful to prepare instruction of which particular clothes to wear on each of the days she will be absent. Arseniy's family is a bit weird so all the clothes is enumerated. For example, each of Arseniy's n socks is assigned a unique integer from 1 to n. Thus, the only thing his mother had to do was to write down two integers li and ri for each of the days — the indices of socks to wear on the day i (obviously, li stands for the left foot and ri for the right). Each sock is painted in one of k colors.
When mother already left Arseniy noticed that according to instruction he would wear the socks of different colors on some days. Of course, that is a terrible mistake cause by a rush. Arseniy is a smart boy, and, by some magical coincidence, he posses k jars with the paint — one for each of k colors.
Arseniy wants to repaint some of the socks in such a way, that for each of m days he can follow the mother's instructions and wear the socks of the same color. As he is going to be very busy these days he will have no time to change the colors of any socks so he has to finalize the colors now.
The new computer game Bota-3 was just realised and Arseniy can't wait to play it. What is the minimum number of socks that need their color to be changed in order to make it possible to follow mother's instructions and wear the socks of the same color during each of mdays.
The first line of input contains three integers n, m and k (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000, 1 ≤ k ≤ 200 000) — the number of socks, the number of days and the number of available colors respectively.
The second line contain n integers c1, c2, ..., cn (1 ≤ ci ≤ k) — current colors of Arseniy's socks.
Each of the following m lines contains two integers li and ri (1 ≤ li, ri ≤ n, li ≠ ri) — indices of socks which Arseniy should wear during the i-th day.
Print one integer — the minimum number of socks that should have their colors changed in order to be able to obey the instructions and not make people laugh from watching the socks of different colors.
3 2 3
1 2 3
1 2
2 3
2
3 2 2
1 1 2
1 2
2 1
0
In the first sample, Arseniy can repaint the first and the third socks to the second color.
In the second sample, there is no need to change any colors.
题意：
题解：
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set> 10 #include<cmath> 11 #include<queue> 12 #include<bitset> 13 #include<math.h> 14 #include<vector> 15 #include<string> 16 #include<stdio.h> 17 #include<cstring> 18 #include<iostream> 19 #include<algorithm> 20 #pragma comment(linker, "/STACK:102400000,102400000") 21 using namespace std; 22 #define A first 23 #define B second 24 const int mod=1000000007; 25 const int MOD1=1000000007; 26 const int MOD2=1000000009; 27 const double EPS=0.00000001; 28 //typedef long long ll; 29 typedef __int64 ll; 30 const ll MOD=1000000007; 31 const int INF=1000000010; 32 const ll MAX=1ll<<55; 33 const double eps=1e-5; 34 const double inf=~0u>>1; 35 const double pi=acos(-1.0); 36 typedef double db; 37 typedef unsigned int uint; 38 typedef unsigned long long ull; 39 int n,m,k; 40 int a[200005]; 41 int ans=0; 42 int fa[200005]; 43 vector<int>f[200005]; 44 map<int,int> mp; 45 int find(int root) 46 { 47 if(fa[root]!=root) 48 return fa[root]=find(fa[root]); 49 else 50 return fa[root]; 51 } 52 void unio(int a,int b) 53 { 54 int aa=find(a); 55 int bb=find(b); 56 if(aa!=bb) 57 fa[aa]=bb; 58 } 59 int main() 60 { 61 ans=0; 62 scanf("%d %d %d",&n,&m,&k); 63 for(int i=1;i<=n;i++) 64 { 65 scanf("%d",&a[i]); 66 fa[i]=i; 67 } 68 int xx,yy; 69 for(int i=1;i<=m;i++) 70 { 71 scanf("%d %d",&xx,&yy); 72 unio(xx,yy); 73 } 74 for(int i=1;i<=n;i++) 75 f[find(i)].push_back(a[i]); 76 for(int i=1;i<=n;i++) 77 if(f[i].size()) 78 { 79 mp.clear(); 80 int sum=f[i].size(); 81 int jishu=0; 82 for(int j=0;j<f[i].size();j++) 83 { 84 mp[f[i][j]]++; 85 jishu=max(jishu,mp[f[i][j]]); 86 } 87 ans=ans+sum-jishu; 88 } 89 cout<<ans<<endl; 90 return 0; 91 }