Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

A - Discount

Problem Statement

A product originally priced at $A$ yen is now sold for $B$ yen. What percentage discount is applied?

$1\le B < A\le 10^5$

Input Format

$A~B$

Output Format

Output the answer (without %). Absolute or relative error up to $10^{-2}$ is allowed.

Samples

$A$	$B$	Output
$100$	$80$	$20.0$
$7$	$6$	$14.285714$
$99999$	$99998$	$0.0010000100001$

Analysis

The answer can be directly calculated using $\frac{A-B}{A}$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#include <cstdio>
#include <tuple>
using namespace std;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%.6lf", (a - b) * 100.0 / a);
    return 0;
}

B - Play Snuke

Problem Statement

Takahashi wants to buy a product called Play Snuke.
There are $N$ stores selling Play Snuke. It takes $A_i$ minutes for Takahashi to reach the $i$-th store, which sells the product at $P_i$ yen with $X_i$ units in stock.
Takahashi will visit one of these stores to buy a Play Snuke.
However, each store sells one unit of Play Snuke at $0.5, 1.5, 2.5,\dots$ minutes after opening.
Determine if Takahashi can buy the product. If possible, output the minimum amount he needs to pay.

$1\le N\le 10^5$
$1\le A_i, P_i, X_i\le 10^9$

Input Format

$N$
$A_1~P_1~X_1$
$\vdots$
$A_N~P_N~X_N$

Output Format

If Takahashi can buy Play Snuke, output the minimum cost; otherwise, output -1.

Samples

Sample Input1

Sample Output1

1

8

Takahashi can choose store 2 and pay 8 yen.

Sample Input2

Sample Output2

1

-1

All stores will have sold out when Takahashi arrives.

Sample Input3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


10
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016

Sample Output3

1

861648772

Analysis

For store $i$, if $X_i > A_i$, the product is still available when Takahashi arrives. Among all valid stores, select the minimum $P_i$. If no store satisfies $X_i > A_i$, output -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <cstdio>
#define maxn 100005
#define INF 2147483647
using namespace std;

int main()
{
    int n, ans = INF;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        int a, p, x;
        scanf("%d%d%d", &a, &p, &x);
        if(x > a && p < ans)
            ans = p;
    }
    if(ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

C - Unexpressed

Problem Statement

Given an integer $N$, how many integers between $1$ and $N$ (inclusive) cannot be expressed as $a^b$ where $a$ and $b$ are integers greater than or equal to $2$?

$1\le N\le 10^{10}$

Input Format

$N$

Output Format

Output the answer.

Samples

$N$	Output
$8$	$6$
$100000$	$99634$

Analysis

There are relatively few numbers expressible as $a^b$. Enumerate all possible $a$ ($2\le a\le \sqrt N$), collect all $a^b$ values not exceeding $N$ in a set (for deduplication), then compute $N - \text{final set size}$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <cstdio>
#include <cmath>
#include <set>
using namespace std;

using LL = long long;
set<LL> s;

int main()
{
    LL n;
    scanf("%lld", &n);
    LL tmp = sqrt(n);
    for(LL a=2; a<=tmp; a++)
    {
        LL res = a; // res = a ^ b
        while((res *= a) <= n)
            s.insert(res);
    }
    printf("%lld\n", n - s.size());
    return 0;
}

D - Poker

Problem Statement

Refer to the original problem.

Input Format

$K$
$S$
$T$

Output Format

Output Takahashi’s winning probability as a decimal between $0$ and $1$. Absolute or relative error up to $10^{-5}$ is allowed.

Samples

$K$	$S$	$T$	Output
$2$	`1144#`	`2233#`	$0.4444444444444$
$2$	`9988#`	`1122#`	$1.0$
$6$	`1122#`	`2228#`	$0.0019323671498$
$10^5$	`3226#`	`3597#`	$0.6296297942426$

Analysis

$$\begin{cases} C_xC_y & (x \ne y)\\ C_x(C_x - 1) & (x = y)\\ \end{cases}$$

Enumerate all valid $(x, y)$ pairs and divide the result by $(9K - 8)(9K - 9)$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <cstdio>
using namespace std;

using LL = long long;

char s[7], t[7];

int score(const char* cards)
{
    int cnt[10];
    for(int i=0; i<10; i++) cnt[i] = i;
    for(int i=0; i<5; i++)
        cnt[cards[i] - '0'] *= 10;
    int res = 0;
    for(int x: cnt) res += x;
    return res;
}

int main()
{
    int k;
    scanf("%d%s%s", &k, s, t);
    int cnt[10];
    for(int i=1; i<10; i++) cnt[i] = k;
    for(int i=0; i<4; i++)
        cnt[s[i] - '0'] --,
        cnt[t[i] - '0'] --;
    LL win = 0LL;
    for(int x=1; x<10; x++)
        if(cnt[x])
        {
            s[4] = '0' + x;
            int sscore = score(s);
            for(int y=1; y<10; y++)
                if(cnt[y])
                {
                    t[4] = '0' + y;
                    if(sscore > score(t))
                        win += cnt[x] * LL(cnt[y] - (x == y));
                }
        }
    LL tmp = 9LL * k - 8LL;
    printf("%.8lf\n", double(win) / tmp / double(tmp - 1LL));
    return 0;
}