UOJ Logo DreamsChaser的博客

博客

Solution to ABC193(In English)

2021-02-28 16:57:04 By DreamsChaser

Contest URL：https://atcoder.jp/contests/abc193.

$\large \mathcal{A - Discount}$

$\mathsf{Description}$

A shop sells a product whose regular price is $A$ yen (Japanese currency) for $B$ yen. By what percentage of the regular price is this product discounted?

$\mathsf{Solution}$

We can easily know that the answer is $\dfrac{A-B}A$.Output the number and submit and $\color{green}\text{AC.}$

$\mathsf{Code\ In\ C^{++}}$

#include <bits/stdc++.h>

using namespace std;

int A,B;

int main() {
    scanf("%d%d",&A,&B);
    printf("%.12lf",(A-B)*100.0/A);
    return 0;
}

$\large \mathcal{B - Play\ Snuke}$

$\mathsf{Description}$

Takahashi wants to buy the popular video game console called Play Snuke.

There are $N$ shops that sell Play Snuke: Shop $1,2,…,N.$ Shop $i$ is $A_i$ minutes' walk from where Takahashi is now, sells Play Snuke for $P_i$ yen (Japanese currency), and currently has $X_i$ Play Snukes in stock.

Now, Takahashi will go to one of those shops on foot and buy Play Snuke if it is still in stock when he gets there.

However, Play Snuke is so popular that the number of consoles in stock (if any) in every shop will decrease by $1$ at the following moments: $0.5,1.5,2.5,…$ minutes from now.

Determine whether Takahashi can buy Play Snuke. If he can, find the minimum amount of money needed to buy one.

$\mathsf{Solution}$

Takahashi can buy Play Snuke If and only if $X_i>A_i$ ,then he can use $P_i$ yen to buy it.

So we let $i=1\rightarrow n$, if we find an $i$ that $X_i>A_i$,then answer will update.Then submit and $\color{green}\text{AC.}$

$\mathsf{Code\ In\ C^{++}}$

#include <bits/stdc++.h>

using namespace std;
const int N=100010;

int n,ans=0x7f7f7f7f;
int A[N],X[N],P[N];

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d%d%d",&A[i],&P[i],&X[i]);
    for(int i=1; i<=n; i++)
        if(X[i]>A[i]) ans=min(ans,P[i]);
    if(ans==0x7f7f7f7f) printf("-1");
    else printf("%d",ans);
    return 0;
}

$\large \mathcal{C - Unexpressed}$

$\mathsf{Description}$

Given is an integer $N$. How many integers between $1$ and $N$ (inclusive) are unrepresentable as $a^b$, where $a$ and $b$ are integers not less than $2$ ?

$\mathsf{Solution}$

We can easily find out the number of $i$ that:

  • $1\le i\le n$
  • $i$ is representable as $a^b$, where $a$ and $b$ are integers not less than 2.

We can set up a set.Let $i=1\rightarrow \sqrt{n}$ and throw $i^2,i^3,...$ into this set.Finally,the size of this set is the number of integers between $1$ and $N$ (inclusive) are representable as $a^b$, where $a$ and $b$ are integers not less than $2$.

Don't forget the correct answer is $n\ -\ $size of the set.

$\mathsf{Code\ In\ C^{++}}$

#include <bits/stdc++.h>

using namespace std;

long long N;
set<long long> xr;

int main() {
    scanf("%lld",&N);
    for(int i=sqrt(N); i>=2; i--) {
        long long tmp=1ll*i*i;
        while(tmp<=N) {
            xr.insert(tmp);
            tmp *= i;
        }
    }
    printf("%lld\n",N-xr.size());
    return 0;
}

$\large \mathcal{D - Poker}$

$\mathsf{Description}$

We have $9K$ cards. For each $i=1,2,…,9,$ there are $K$ cards with $i$ written on it.

We randomly shuffled these cards and handed out five cards - four face up and one face down - to each of Takahashi and Aoki.

You are given a string $S$ representing the cards handed out to Takahashi and a string $T$ representing the cards handed out to Aoki.

S and T are strings of five characters each. Each of the first four characters of each string is $1, 2, …,$ or $9,$ representing the number written on the face-up card. The last character of each string is #, representing that the card is face down.

Let us define the score of a five-card hand as $\sum\limits_{i=1}^9 i\times 10^{c_i}$, where $c_i$ is the number of cards with $i$ written on them.

Takahashi wins when the score of Takahashi's hand is higher than that of Aoki's hand.

Find the probability that Takahashi wins.

$\mathsf{Solution}$

How to calculate the number of the all possibilities?

We record the number of $i$ is $xr_i$.

We can enumerate what number is the # is.Let the nuber behind Takahashi's # is $i$, and the number behind Aoki's # is $j$.

  • if $i=j$，we add the number of the all possibilities with $P_{k-xr_i}^2$.
  • if $i≠j$, we add the number of the all possibilities with $(k-xr_i)(k-xr_j)$.

Don't forget to divide the probability with $P_{9K-8}^2$!

$\mathsf{Code\ In\ C^{++}}$

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int K,a1,a2;
int xr[10];
LL ans;

LL power(int x) {
    LL ans=1;
    while(x--) ans *= 10;
    return ans;
}

LL score(int x) {
    int sw[6]={0,x%10,(x/10)%10,(x/100)%10,(x/1000)%10,x/10000};
    int a[10]={0,0,0,0,0,0,0,0,0,0};
    LL ans=0;
    for(int i=1; i<=5; i++) a[sw[i]]++;
    for(int i=0; i<=9; i++) ans += i*power(a[i]);
    return ans;
}

int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main() {
    K=read();a1=read();a2=read();
    xr[a1%10]++;xr[(a1/10)%10]++;xr[(a1/100)%10]++;xr[(a1/1000)]++;
    xr[a2%10]++;xr[(a2/10)%10]++;xr[(a2/100)%10]++;xr[(a2/1000)]++;
    for(int i=1; i<=9; i++)
        for(int j=1; j<=9; j++) {
            if(xr[i]==K || xr[j]==K || (i==j && xr[i]==K-1)) continue;
            if(score(a1*10+i)<=score(a2*10+j)) continue;
//            cout<<i<<" "<<j<<endl;
            if(i==j) ans += 1ll*(K-xr[i])*(K-xr[i]-1);
            else ans += 1ll*(K-xr[i])*(K-xr[j]); 
        } 
//        cout<<ans<<endl;
    printf("%.12lf",ans*1.0/(1ll*(9*K-8)*(9*K-9)));
    return 0;
}

$\large \mathcal{E - Oversleeping}$

$\mathsf{Description}$

A train goes back and forth between Town $A$ and Town $B$. It departs Town $A$ at time $0$ and then repeats the following:

  • goes to Town $B$, taking $X$ seconds;
  • stops at Town $B$ for $Y$ seconds;
  • goes to Town $A$, taking $X$ seconds;
  • stops at Town $A$ for $Y$ seconds.

More formally, these intervals of time are half-open, that is, for each $n=0,1,2,…$:

  • at time $t$ such that $(2X+2Y)n≤t<(2X+2Y)n+X$, the train is going to Town $B$;
  • at time $t$ such that $(2X+2Y)n+X≤t<(2X+2Y)n+X+Y$, the train is stopping at Town $B$;
  • at time $t$ such that $(2X+2Y)n+X+Y≤t<(2X+2Y)n+2X+Y$, the train is going to Town $A$;
  • at time $t$ such that $(2X+2Y)n+2X+Y≤t<(2X+2Y)(n+1)$, the train is stopping at Town $A$.

Takahashi is thinking of taking this train to depart Town $A$ at time $0$ and getting off at Town $B$. After the departure, he will repeat the following:

  • be asleep for $P$ seconds;
  • be awake for $Q$ seconds.

Again, these intervals of time are half-open, that is, for each $n=0,1,2,…$:

  • at time $t$ such that $(P+Q)n≤t<(P+Q)n+P$, Takahashi is asleep;
  • at time $t$ such that $(P+Q)n+P≤t<(P+Q)(n+1)$, Takahashi is awake.

He can get off the train at Town $B$ if it is stopping at Town $B$ and he is awake.

Determine whether he can get off at Town $B$. If he can, find the earliest possible time to do so.

Under the constraints of this problem, it can be proved that the earliest time is an integer.

You are given $T$ cases. Solve each of them.

$\mathsf{Solution}$

Formally,we can retell this problem as:

to find the mininum of $n$:

  • $(2X+2Y)n+X≤t<(2X+2Y)n+X+Y$
  • $(P+Q)n+P≤t<(P+Q)(n+1)$

Noticed that $Y$ and $Q$ are small,so we enumerate $t\%(2X+2Y)$ and $t\%(P+Q).$

After that,use ExCRT then get $\color{green}\text{AC!}$

$\mathsf{Code\ In\ C^{++}}$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int T,X,Y,P,Q;
LL a[3],b[3];

LL mul(LL a,LL b,LL p){
    LL ans=0;
    for(; b; b>>=1){
        if(b&1) ans=(ans+a)%p;
        a=2*a%p;
    }
    return ans;
}

void Exgcd(LL a,LL b,LL &x,LL &y) {
    if(b==0) {
        x=1,y=0;
        return;
    }
    Exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return;
}

LL ExCRT() {
    LL ans=0,lcm=1;
    LL k1,k2,c;
    for(int i=1; i<=2; i++) {
        LL gcd=__gcd(lcm,a[i]),Mi=a[i]/gcd;
        Exgcd(lcm,a[i],k1,k2);
        c=((b[i]-ans)%a[i]+a[i])%a[i];
        if(c%gcd) return -1;
        k1=mul(k1,c/gcd,Mi);
        ans += k1*lcm;
        lcm *= Mi;
        ans=(ans%lcm+lcm)%lcm;
    }
    return (ans%lcm+lcm)%lcm;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        LL ans=9223372036854775807;
        scanf("%d%d%d%d",&X,&Y,&P,&Q);
        for(int i=X; i<X+Y; i++)
            for(int j=P; j<P+Q; j++) {
                a[1]=2*X+2*Y;
                a[2]=P+Q;
                b[1]=i;
                b[2]=j;
                LL k=ExCRT();
                if(k!=-1) ans=min(ans,k);
            }
        if(ans==9223372036854775807) printf("infinity\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

$\large \mathcal{F - Zebraness}$

I didn't accept this problem when I enjoy the contest.....

But it's a really wonderful graph problem!

评论

YuHaoXiang
s o l o t i o n

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-04-19 12:57:41