Educational Codeforces Round 82 (Rated for Div. 2)

A. Erasing Zeroes

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes

You are given a string $s$. Each character is either $0$ or $1$.

You want all $1$’s in the string to form a contiguous subsegment. For example, if the string is $0$, $1$, $00111$ or $01111100$, then all 1’s form a contiguous subsegment, and if the string is $0101$, $100001$ or $11111111111101$, then this condition is not met.

You may erase some (possibly none) $0$’s from the string. What is the minimum number of $0$’s that you have to erase?

Input

The first line contains one integer $t$ ($1≤t≤100$) — the number of test cases.

Then $t$ lines follow, each representing a test case. Each line contains one string $s$ ($1≤|s|≤100$); each character of $s$ is either $0$ or $1$.

Output

Print $t$ integers, where the $i$-th integer is the answer to the $i$-th testcase (the minimum number of $0$’s that you have to erase from $s$).

Example

input

3
010011
0
1111000

output

2
0
0

Note

In the first test case you have to delete the third and forth symbols from string 010011 (it turns into $0111$).

Code

题意:给你一个字符串,你可以去掉其中的一些$0$。求最少去掉多少个$0$,使字符串中的$1$连续。
从前往后遍历,找到第一个$1$作为左边界,再从后往前遍历找到第一个$1$作为右边界,左右边界中间的$0$个数即为所求。
注意有不存在1的情况,我居然上来就WA了一发,还涨了分,可见我以前有多菜。

#include <bits/stdc++.h>
using namespace std;

char s[105];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%s", s);
        int n = strlen(s);
        int left = -1, right = -1;
        for(int i=0; i<n; i++) {
            if(s[i] == '1') {
                left = i;
                break;
            }
        }
        for(int i=n-1; i>=0; i--) {
            if(s[i] == '1') {
                right = i;
                break;
            }
        }
        if(left == -1 || right == -1) {
            printf("0\n");
            continue;
        }
        int ans = 0;
        for(int i=left+1; i<right; i++) {
            if(s[i] == '0') ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. National Project

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

Your company was appointed to lay new asphalt on the highway of length $n$. You know that every day you can either repair one unit of the highway (lay new asphalt over one unit of the highway) or skip repairing.

Skipping the repair is necessary because of the climate. The climate in your region is periodical: there are $g$ days when the weather is good and if you lay new asphalt these days it becomes high-quality pavement; after that, the weather during the next $b$ days is bad, and if you lay new asphalt these days it becomes low-quality pavement; again $g$ good days, $b$ bad days and so on.

You can be sure that you start repairing at the start of a good season, in other words, days $1,2,…,g$ are good.

You don’t really care about the quality of the highway, you just want to make sure that at least half of the highway will have high-quality pavement. For example, if the $n=5$ then at least $3$ units of the highway should have high quality; if $n=4$ then at least $2$ units should have high quality.

What is the minimum number of days is needed to finish the repair of the whole highway?

Input

The first line contains a single integer $T$ ($1≤T≤10^4$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains three integers $n$, $g$ and $b$ ($1≤n,g,b≤10^9$) — the length of the highway and the number of good and bad days respectively.

Output

Print $T$ integers — one per test case. For each test case, print the minimum number of days required to repair the whole highway if at least half of it should have high quality.

Example

input

3
5 1 1
8 10 10
1000000 1 1000000

output

5
8
499999500000

Note

In the first test case, you can just lay new asphalt each day, since days 1,3,5 are good.

In the second test case, you can also lay new asphalt each day, since days 1-8 are good.

Code

题意:有一条长度为$n$的路,每天可以选择修$1$单位长度或者不修。天气$g$天晴天,$b$天雨天周期往复,在晴天时修的路质量较高,雨天时修的路质量较低。问至少需要多少天才能修完全部的路并至少有一半长度的路达到高质量。
首先算出需要高质量的天数,然后分为两种情况。
第一种情况,高质量天数可以整除$g$,那么我们需要的总天数就是“高、低、……、高”这种形式。
第二种情况,高质量天数不可以整除$g$,那么我们需要的总天数就是“高、低、……、高、低、高(不完整)”。
两种情况分别计算,再和$n$比较取$max$,因为至少需要$n$天才能修完整个马路。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        LL n, g, b; scanf("%lld %lld %lld", &n, &g, &b);
        LL num = n / 2 + (n % 2);
        LL ans = 0;
        if(num / g == 0) ans = n;
        else {
            if(num % g == 0) ans = (num / g - 1) * (g + b) + g;
            else ans = (num / g) * (g + b) + (num % g);
            ans = max(ans, n);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. Perfect Keyboard

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes
    Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $26$ lowercase Latin letters will be arranged in some order.

Polycarp uses the same password $s$ on all websites where he is registered (it is bad, but he doesn’t care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn’t like to move his fingers while typing the password, so, for each pair of adjacent characters in $s$, they should be adjacent on the keyboard. For example, if the password is $abacaba$, then the layout $cabdefghi$… is perfect, since characters $a$ and $c$ are adjacent on the keyboard, and $a$ and $b$ are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $s$, so, for example, the password cannot be password (two characters $s$ are adjacent).

Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?

Input

The first line contains one integer $T$ ($1≤T≤1000$) — the number of test cases.

Then $T$ lines follow, each containing one string $s$ ($1≤|s|≤200$) representing the test case. $s$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $s$.

Output

For each test case, do the following:

  • if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);
  • otherwise, print YES (in upper case), and then a string consisting of $26$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them.

Example

input

5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

output

YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Code

题意:给你一串密码,让你设计一个$1×26$的键盘,要求密码中相邻位在键盘上也是相邻的。
直接暴力模拟了。遍历给定的密码的同时设计键盘。如果当前遍历到的字母不在键盘当前键位的左/右相邻位,且左/右相邻位有空位则填入空位,否则输出NO;如果如果当前遍历到的字母在键盘当前键位的左/右相邻位,则更新键盘当前状态。

#include <bits/stdc++.h>
using namespace std;

char s[205];
char ans[100];
bool vis[26];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%s", s); int n = strlen(s);
        memset(ans, '\0', sizeof(ans));
        memset(vis, false, sizeof(vis));

        int now = 50;
        bool NO = false;
        int mn = 200, mx = -1;
        for(int i=0; i<n; i++) {
            if(!vis[s[i]-'a']) {
                if(ans[now-1] == '\0') ans[--now] = s[i];
                else if(ans[now+1] == '\0') ans[++now] = s[i];
                else {
                    NO = true;
                    break;
                }
                vis[s[i]-'a'] = true;
            }
            else {
                if(ans[now-1] == s[i]) {
                    now--;
                }
                else if(ans[now+1] == s[i]){
                    now++;
                }
                else {
                    NO = true;
                    break;
                }
            }
            mn = min(mn, now);
            mx = max(mx, now);
        }
        if(NO) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for(int i=mn; i<=mx; i++) printf("%c", ans[i]);
        for(int i=0; i<26; i++) {
            if(!vis[i]) printf("%c", i+'a');
        }
        printf("\n");
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇