ecjtu-summer training #7

New Skateboard

 

Max wants to buy a new skateboard. He has calculated the amount of money that is needed to buy a new skateboard. He left a calculator on the floor and went to ask some money from his parents. Meanwhile his little brother Yusuf came and started to press the keys randomly. Unfortunately Max has forgotten the number which he had calculated. The only thing he knows is that the number is divisible by 4.

You are given a string s consisting of digits (the number on the display of the calculator after Yusuf randomly pressed the keys). Your task is to find the number of substrings which are divisible by 4. A substring can start with a zero.

A substring of a string is a nonempty sequence of consecutive characters.

For example if string s is 124 then we have four substrings that are divisible by 4: 12, 4, 24 and 124. For the string 04 the answer is three: 0, 4, 04.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The only line contains string s (1 ≤ |s| ≤ 3·10⁵). The string s contains only digits from 0 to 9.

Output

Print integer a — the number of substrings of the string s that are divisible by 4.

Note that the answer can be huge, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Examples

Input

124

Output

4

Input

04

Output

3

Input

5810438174

Output

9

求字串中有多少个能被4整除的数，0也算。先算出每个子串长度为1的有多少被4整除，然后算出子串长度为2有多少被4整除，而长度为3是建立在长度为2的基础上的，
那个长度为2能被4整除的那个位置，加上前面的也都能被4整除。说的不好，打个比方吧，123312   最后12能被4整除，那么312 3312 23312 123312都能被4整除。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define ll long long
using namespace std;
const int N = 3e5+10;
char str[N];
int main(){
    scanf("%s",str);
    ll ans = 0;
    int len = strlen(str);
    for(int i = 0; i < len; i ++) {
        if((str[i]-'0')%4==0) ans++;
    }
    for(int i = 0; i < len-1; i ++) {
        int tem = 0;
        for(int j = i;j <= i+1; j ++) {
            tem = tem*10 + (str[j]-'0');
        }
        if(tem%4==0) ans+=(i+1);
    }
    cout << ans << endl;
    return 0;
}

最短路

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！

所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。

每组数据第一行是两个整数N,M表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0

M=0,N=0表示输入结束。

接下来M行，每行包括3个整数A,B,C表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。

输入保证至少存在1

条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

Sample Input

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

最短路径模板题。

#include <iostream>
#include <stdio.h>
#include <string.h>
#define ll long long
using namespace std;
const int MAX = 1010;
const int INF = 0xffffff;
int g[MAX][MAX],ans,dist[MAX],n,m;
bool vis[MAX];
void dijistra(int x){
    int pos = x;
    for(int i = 1; i <= n; i ++){
        dist[i] = g[i][pos];
    }
    vis[pos] = true;
    for(int i = 1; i <= n; i ++){
        int mins = INF;
        for(int j = 1; j <= n; j ++){
            if(!vis[j] && dist[j] < mins){
                pos = j;
                mins = dist[j];
            }
        }
        vis[pos] = true;
        for(int j = 1; j <= n; j ++){
            if(!vis[j] && dist[j] > dist[pos] + g[pos][j]){
                dist[j] = dist[pos] + g[pos][j];
            }
        }
    }
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0&&m==0)break;
        for(int i = 0; i <= n; i ++)
            for(int j = 0; j <= n; j ++)
                g[i][j] = (i==j)?0:INF;
        for(int i = 0; i < m; i ++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if(c < g[a][b]){
                g[a][b] = c;
                g[b][a] = c;
            }
        }
        ans = 0;
        dijistra(1);
        printf("%d
",dist[n]);
        memset(g,0,sizeof(g));
        memset(vis,false,sizeof(vis));
        memset(dist,0,sizeof(dist));
    }
    return 0;
}

Prime Distance

Description

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

Input

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

Output

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

Sample Input

2 17
14 17

Sample Output

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.


求给定区间内，相邻最短的两个素数和相邻最长的两个素数，区间内素数小于2个就不要求。
由于数字很大，所以要用到来两次筛选法，比赛时真心想不到。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
const int N = 5e5;
const int M = 1e6+10;
int pre[N], f[M], vis[N], t;
void getPri() {
    for(int i = 2; i <= N; i ++) {
        if(!vis[i]) {
            pre[++t] = i;
            for(int j = i+i; j <= N; j += i)
                vis[j] = 1;
        }
    }
}
int main() {
    getPri();
    int L, U;
    while(scanf("%d%d",&L,&U)!=EOF) {
        if(L < 2) L = 2;
        memset(f,0,sizeof(f));
        for(int i = 1; i <= t; i ++) {
            int s = L/pre[i], e = U/pre[i];
            if(L%pre[i]) s++;
            if(s < 2) s = 2;
            for(int j = s; j <= e; j ++)
                f[j*pre[i]-L] = 1;
        }
        int p = -1, Max = -1, Min = 1000000000, x1, x2, y1, y2;
        for(int i = 0; i <= U-L; i ++) {
            if(!f[i]){
                if(p == -1){
                    p = i;continue;
                }
                if(i-p > Max){
                    Max = i-p; x1 = p+L; y1 = i+L;
                }
                if(i-p < Min) {
                    Min = i-p; x2 = p+L; y2 = i+L;
                }
                p = i;
            }
        }
        if(Max == -1) printf("There are no adjacent primes.
");
        else printf("%d,%d are closest, %d,%d are most distant.
",x2,y2,x1,y1);
    }
    return 0;
}

Mahmoud and a Dictionary

Mahmoud wants to write a new dictionary that contains n words and relations between them. There are two types of relations: synonymy (i. e. the two words mean the same) and antonymy (i. e. the two words mean the opposite). From time to time he discovers a new relation between two words.

He know that if two words have a relation between them, then each of them has relations with the words that has relations with the other. For example, if like means love and love is the opposite of hate, then like is also the opposite of hate. One more example: if love is the opposite of hate and hate is the opposite of like, then love means like, and so on.

Sometimes Mahmoud discovers a wrong relation. A wrong relation is a relation that makes two words equal and opposite at the same time. For example if he knows that love means like and like is the opposite of hate, and then he figures out that hate means like, the last relation is absolutely wrong because it makes hate and like opposite and have the same meaning at the same time.

After Mahmoud figured out many relations, he was worried that some of them were wrong so that they will make other relations also wrong, so he decided to tell every relation he figured out to his coder friend Ehab and for every relation he wanted to know is it correct or wrong, basing on the previously discovered relations. If it is wrong he ignores it, and doesn't check with following relations.

After adding all relations, Mahmoud asked Ehab about relations between some words based on the information he had given to him. Ehab is busy making a Codeforces round so he asked you for help.

Input

The first line of input contains three integers n, m and q (2 ≤ n ≤ 10⁵, 1 ≤ m, q ≤ 10⁵) where n is the number of words in the dictionary, m is the number of relations Mahmoud figured out and q is the number of questions Mahmoud asked after telling all relations.

The second line contains n distinct words a₁, a₂, ..., a_n consisting of small English letters with length not exceeding 20, which are the words in the dictionary.

Then m lines follow, each of them contains an integer t (1 ≤ t ≤ 2) followed by two different words x_i and y_i which has appeared in the dictionary words. If t = 1, that means x_i has a synonymy relation with y_i, otherwise x_i has an antonymy relation with y_i.

Then q lines follow, each of them contains two different words which has appeared in the dictionary. That are the pairs of words Mahmoud wants to know the relation between basing on the relations he had discovered.

All words in input contain only lowercase English letters and their lengths don't exceed 20 characters. In all relations and in all questions the two words are different.

Output

First, print m lines, one per each relation. If some relation is wrong (makes two words opposite and have the same meaning at the same time) you should print "NO" (without quotes) and ignore it, otherwise print "YES" (without quotes).

After that print q lines, one per each question. If the two words have the same meaning, output 1. If they are opposites, output 2. If there is no relation between them, output 3.

See the samples for better understanding.

Examples

Input

3 3 4
hate love like
1 love like
2 love hate
1 hate like
love like
love hate
like hate
hate like

Output

YES
YES
NO
1
2
2
2

Input

8 6 5
hi welcome hello ihateyou goaway dog cat rat
1 hi welcome
1 ihateyou goaway
2 hello ihateyou
2 hi goaway
2 hi hello
1 hi hello
dog cat
dog hi
hi hello
ihateyou goaway
welcome ihateyou

Output

YES
YES
YES
YES
NO
YES
3
3
1
1
2

带权并查集的运算，最后赛后补题一次没过就放一边了，过一段时间重写下就过了，好无语。细节问题没有考虑清楚。
同义词就让mp[s]和mp[ss]一个集合,mp[s]+N和mp[ss]+N一个集合，反义词就让mp[s]+N和mp[ss]一个集合，mp[s]和mp[ss]+N一个集合。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
const int N = 2e5+10;
int fa[N*2];
int find(int x){
    return fa[x] = fa[x]==x?x:find(fa[x]);
}
int unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x > y) fa[x] = y;
    else fa[y] = x;
}
int main(){
    int n,m,q;
    string s, ss;
    for(int i = 1; i <= N*2-1; i ++) fa[i] = i;
    scanf("%d%d%d",&n,&m,&q);
    map<string,int> mp;
    for(int i = 1; i <= n; i ++) {
        cin>>s;
        mp[s] = i;
    }
    int num;
    for(int i = 1; i <= m; i ++) {
        cin>>num>>s>>ss;
        if(num == 1){
            int x = find(mp[s]);
            int y = find(mp[ss]+N);
            if(x == y) printf("NO
");
            else {
                printf("YES
");
                unite(mp[s],mp[ss]);
                unite(mp[s]+N,mp[ss]+N);
            }
        } else {
            int x = find(mp[s]);
            int y = find(mp[ss]);
            if(x == y) printf("NO
");
            else{
                printf("YES
");
                unite(mp[s],mp[ss]+N);
                unite(mp[s]+N,mp[ss]);
            }
        }
    }
    while(q--) {
        cin>>s>>ss;
        if(find(mp[s]) == find(mp[ss]))printf("1
");
        else if(find(mp[s]) == find(mp[ss]+N)) printf("2
");
        else printf("3
");
    }
    return 0;
}

Mashmokh and Tokens

Bimokh is Mashmokh's boss. For the following n days he decided to pay to his workers in a new way. At the beginning of each day he will give each worker a certain amount of tokens. Then at the end of each day each worker can give some of his tokens back to get a certain amount of money. The worker can save the rest of tokens but he can't use it in any other day to get more money. If a worker gives back w tokens then he'll get dollars.

Mashmokh likes the tokens however he likes money more. That's why he wants to save as many tokens as possible so that the amount of money he gets is maximal possible each day. He has n numbers x₁, x₂, ..., x_n. Number x_i is the number of tokens given to each worker on the i-th day. Help him calculate for each of n days the number of tokens he can save.

Input

The first line of input contains three space-separated integers n, a, b (1 ≤ n ≤ 10⁵; 1 ≤ a, b ≤ 10⁹). The second line of input contains n space-separated integers x₁, x₂, ..., x_n (1 ≤ x_i ≤ 10⁹).

Output

Output n space-separated integers. The i-th of them is the number of tokens Mashmokh can save on the i-th day.

Examples

Input

5 1 4
12 6 11 9 1

Output

0 2 3 1 1 

Input

3 1 2
1 2 3

Output

1 0 1 

Input

1 1 1
1

Output

0 

注意整除情况就行。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define ll long long
using namespace std;

int main(){
    ll a, n, b, x, y, t;
    cin>>n>>a>>b;
    for(int i = 0;i < n;i ++){
       int x;
       cin >> x;
       t = x*a/b;
       if(t*b%a == 0)y = t*b/a;
       else y = t*b/a+1;
       cout << x-y << " ";
   }
   cout<<endl;
   return 0;