Codeforces Round #479 (Div. 3)

1. 문제 (http://codeforces.com/contest/977/problem/A)

A. Wrong Subtraction

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Little girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm:

• if the last digit of the number is non-zero, she decreases the number by one;
• if the last digit of the number is zero, she divides the number by 10 (i.e. removes the last digit).

You are given an integer number $n$. Tanya will subtract one from it $k$ times. Your task is to print the result after all $k$ subtractions.

It is guaranteed that the result will be positive integer number.

Input

The first line of the input contains two integer numbers $n$ and $k$ ($2\le n\le {10}^9$, $1\le k\le 50$) — the number from which Tanya will subtract and the number of subtractions correspondingly.

Output

Print one integer number — the result of the decreasing $n$ by one $k$ times.
It is guaranteed that the result will be positive integer number.

2. 알고리즘

키워드 - 구현

3. 코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>         // greater 사용 위해 필요  
#include <string>
#include <map>
#include <math.h>
using namespace std;
 
int main() {
 
    int n, t;
 
    cin >> n >> t;
 
    while(t--) {
 
        int cand = n % 10;
        if(cand == 0) {
            n = n / 10;
        } else {
            n--;
        }
    }
 
    cout << n << endl;
    return 0;
}

1. 문제 (http://codeforces.com/contest/977/problem/B)

B. Two-gram

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Two-gram is an ordered pair (i.e. string of length two) of capital Latin letters. For example, "AZ", "AA", "ZA" — three distinct two-grams.

You are given a string $s$ consisting of $n$ capital Latin letters. Your task is to find any two-gram contained in the given string as a substring(i.e. two consecutive characters of the string) maximal number of times. For example, for string $s$ = "BBAABBBA" the answer is two-gram "BB", which contained in $s$ three times. In other words, find any most frequent two-gram.

Note that occurrences of the two-gram can overlap with each other.

Input

The first line of the input contains integer number $n$ ($2\le n\le 100$) — the length of string $s$. The second line of the input contains the string $s$ consisting of $n$ capital Latin letters.

Output

Print the only line containing exactly two capital Latin letters — any two-gram contained in the given string $s$ as a substring (i.e. two consecutive characters of the string) maximal number of times.

2. 알고리즘

키워드 - 구현, 문자열 처리

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
 
/*
* @memory  - 1984 kb
* @time    - 0 ms
*/
 
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    int n; cin >> n;
 
    string s;
    cin >> s;
 
    map<string, int> m;
 
    int i=0;
    while(true) {
 
        string ss = s.substr(i, 2);
        m[ss]++;
        i++;
 
        if (i + 2 > s.size()) {
            break;
        }
    }
 
    map<string, int>::iterator iter;
 
    int sol = -1; 
    string sss; 
    for(iter = m.begin(); iter != m.end(); iter++) 
    { 
        if (sol < iter->second)  { 
            sol = iter->second; 
            sss.clear(); 
            sss.append(iter->first); 
        } 
    }
    
    cout << sss << endl;
 
    return 0;
}

1. 문제 (http://codeforces.com/contest/977/problem/C)

C. Less or Equal

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence of integers of length $n$ and integer number $k$. You should print any integer number $x$ in the range of $[1;{10}^9]$ (i.e. $1\le x\le {10}^9$) such that exactly $k$ elements of given sequence are less than or equal to $x$.

Note that the sequence can contain equal elements.

If there is no such $x$, print "-1" (without quotes).

Input

The first line of the input contains integer numbers $n$ and $k$ ($1\le n\le 2\cdot {10}^5$, $0\le k\le n$). The second line of the input contains $n$ integer numbers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$) — the sequence itself.

Output

Print any integer number $x$ from range $[1;{10}^9]$ such that exactly $k$ elements of given sequence is less or equal to $x$.

If there is no such $x$, print "-1" (without quotes).

2. 알고리즘

키워드 - 정렬

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
/*
* @memory  - 1984 kb
* @time    - 0 ms
*/
 
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    int n, k; cin >> n >> k;
 
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
 
    sort(arr.begin(), arr.end());
 
    int ans;
    if (k == 0) {
        ans = arr[0] - 1;
    } else {
        ans = arr[k - 1];
    }
 
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        if (arr[i] <= ans) ++cnt;
 
    if (cnt != k || !(1 <= ans && ans <= 1000 * 1000 * 1000)) {
        cout << -1 << CENDL;
        return 0;
    }
 
    cout << ans << CENDL;
 
    return 0;
}

1. 문제 (http://codeforces.com/contest/977/problem/D)

2. 알고리즘

키워드 - 정렬, 정수론

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
/*
* @memory  - 1984 kb
* @time    - 0 ms
*/
 
typedef long long LL;
int count3(LL x){
    int ret=0;
    while(x % 3 == 0){
        ret++;
        x /= 3;
    }
    return ret;
}
 
int n;
vector<pair<int,LL>> v;
 
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    cin>>n;
    v.resize(n);
    for(int i=0; i<n; i++){
        cin>>v[i].second;
        v[i].first=-count3(v[i].second);
    }
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++)
        cout << v[i].second << " ";
 
    return 0;
}

1. 문제 (http://codeforces.com/contest/977/problem/E)

E. Cyclic Components

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an undirected graph consisting of $n$ vertices and $m$ edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $a$ is connected with a vertex $b$, a vertex $b$ is also connected with a vertex $a$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices $u$ and $v$ belong to the same connected component if and only if there is at least one path along edges connecting $u$ and $v$.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

• the first vertex is connected with the second vertex by an edge,
• the second vertex is connected with the third vertex by an edge,
• ...
• the last vertex is connected with the first vertex by an edge,
• all the described edges of a cycle are distinct.

A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

There are $6$ connected components, $2$ of them are cycles: $[7,10,16]$ and $[5,11,9,15]$.

Input

The first line contains two integer numbers $n$ and $m$ ($1\le n\le 2\cdot {10}^5$, $0\le m\le 2\cdot {10}^5$) — number of vertices and edges.

The following $m$ lines contains edges: edge $i$ is given as a pair of vertices $v_i$, $u_i$ ($1\le v_i,u_i\le n$, $u_i\ne v_i$). There is no multiple edges in the given graph, i.e. for each pair ($v_i,u_i$) there no other pairs ($v_i,u_i$) and ($u_i,v_i$) in the list of edges.

Output

Print one integer — the number of connected components which are also cycles.

2. 알고리즘

키워드 - DFS, GRAPHS

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
/*
* @memory  - 1984 kb
* @time    - 0 ms
*/
 
const int N = 200 * 1000 + 11;
 
int n, m;
int deg[N];
bool used[N];
vector<int> comp;
vector<int> g[N];
 
void dfs(int v) {
    used[v] = true;
    comp.push_back(v);
 
    for (auto to : g[v])
        if (!used[to])
            dfs(to);
}
 
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y);
        g[y].push_back(x);
        ++deg[x];
        ++deg[y];
    }
 
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            comp.clear();
            dfs(i);
            bool ok = true;
            for (auto v : comp) ok &= deg[v] == 2;
            if (ok) ++ans;
        }
    }
 
    cout << ans << CENDL;
 
    return 0;
}