CodeforcesRound#315（Div.2）（ABCD题解）
A. Music
time limit per test：2 conds
memory limit per test：256 megabytes
Little Lesha loves listening to music via his smartphone. But the smartphone doesn't have much memory, so Lesha listens to his favorite songs in a well-known social network InTalk.
Unfortunately, internet is not that fast in the city of Ekaterinozavodsk and the song takes a lot of time to download. But Lesha is quite impatient. The song's duration is T conds. Lesha downloads the first S conds of the song and plays it. When the playback reaches the point that has not yet been downloaded, Lesha immediately plays the song from the start (the loaded part of the song stays in his phone, and the download is continued from the same place), and it happens until the song is downloaded completely and Lesha listens to it to
the end. For q conds of real time the Internet allows you to download q - 1 conds of the track.
Tell Lesha, for how many times he will start the song, including the very first start.
Input
The single line contains three integers T, S, q (2 ≤ q ≤ 104,1 ≤ S < T ≤ 105).
Output
Print a single integer — the number of times the song will be restarted.
Sample test(s)
Input
5 2 2
Output
2
Input
5 4 7
Output
1
Input
6 2 3
Output
1
Note
In the first test, the song is played twice faster than it is downloaded, which means that during four first conds Lesha reaches the moment that has not been downloaded, and starts the song again. After another two conds, the song is downloaded completely, and thus, Lesha starts the song twice.
线条画简单In the cond test, the song is almost downloaded, and Lesha will start it only once.
In the third sample test the download finishes and Lesha finishes listening at the same moment. Note that song isn't restarted in this ca.
志愿服务制度
题⽬⼤意：⼀个⼈下载歌，每q个时间单位能下载q－1个时间单位的歌，歌的长度为T。下到S的时候開始播放，假设歌还没下完且放到了还未下载的地⽅。则重头開始放，问⼀共要放多少次
题⽬分析：⼀開始从s開始。设下了cur秒后听和下的进度同样，则 s + (q - 1) / q * cur = cur，解得cur = q * s，然后从头開始。设t'秒后进度同样，则(q -1) / q * t' + cur = t'。解得t' = cur * q，可见直接拿第⼀次进度同样的时间乘q就是接下来每次进度同样的时间
1#include <cstdio>
2
3int main()
4{
高明的反义词是什么
5 int T, S, q, ans = 1, cur;
6 scanf("%d %d %d", &T, &S, &q);
7 cur = q * S;
冲刺口号
8 while(cur < T)
9 {
10 cur = q * cur;
11 ans ++;
12 }
13 printf("%d\n", ans);
14}
B. Inventory
time limit per test：1 cond
memory limit per test：256 megabytes
Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a databa by using tho numbers and keep the track of everything.
During an audit, you were surprid to find out that the items are not numbered quentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chon to make the numbers of the items quential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum u of the current numbering.
You have been given information on current inventory numbers for n items in the company. Renumber items so that their inventory numbers form apermutation of numbers from 1 to n by changing the number of as few items as possible. Let us remind you that a t
of n numbers forms a permutation if all the numbers are in the range from 1 to n, and no two numbers are equal.
Input
The first line contains a single integer n — the number of items (1 ≤ n ≤ 105).
The cond line contains n numbers a1, a2, ..., a n (1 ≤ a i ≤ 105) — the initial inventory numbers of the items.
Output
Print n numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.
Sample test(s)
Input
3
1 3 2
Output
1 3 2
Input
4
2 2
3 3
Output
2 1
3 4
Input
1
2胰岛a细胞分泌什么激素
Output
1
Note
In the first test the numeration is already a permutation, so there is no need to change anything.
In the cond test there are two pairs of equal numbers, in each pair you need to replace one number.
In the third test you need to replace 2 by 1, as the numbering should start from one.
题⽬⼤意：给n个数，能够改变随意个数字的⼤⼩⽬标是将其改成1-n的⼀个排列，要求改变次数最⼩，输出排列
题⽬分析：记录原始序列已经在1-n位置的数，凡是⼤于n的或者反复出现的数字下标 标记⼀下。枚举⼀下1-n中还有哪些数字没出现。然后按顺序改动
1#include <cstdio>
2#include <cstring>
3int const MAX = 1e5 + 5;
4int a[MAX], need[MAX];
5bool has[MAX], pos[MAX];
6
7int main()
8{
9 int n, num = 0;
10 scanf("%d", &n);
11 memt(has, fal, sizeof(has));
12 memt(pos, fal, sizeof(pos));
13 for(int i = 0; i < n; i++)
历届世界杯冠军14 {
15 scanf("%d", &a[i]);
16 if(!has[a[i]] && a[i] <= n)
17 has[a[i]] = true;
18 el
19 pos[i] = true;
20 }
21 int cnt = 0;
22 for(int i = 1; i <= n; i++)
23 if(!has[i])
24 need[cnt ++] = i;
25 int idx = 0;
26 for(int i = 0; i < n; i++)
27 if(pos[i])
28 a[i] = need[idx ++];
29 for(int i = 0; i < n - 1; i++)
30 printf("%d ", a[i]);
31 printf("%d\n", a[n - 1]);
32}
C. Primes or Palindromes?
time limit per test：3 conds
memory limit per test：256 megabytes
Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too co
mplex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!
Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itlf and one.
Rikhail calls a number a palindromic if it is integer, positive, and its decimal reprentation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
One problem with prime numbers is that there are too many of them. Let's introduce the following notation:π(n) — the number of primes no larger than n, rub(n) — the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.
He asked you to solve the following problem: for a given value of the coefficient A find the maximum n, such that π(n) ≤ A·rub(n).
Input
The input consists of two positive integers p, q, the numerator and denominator of the fraction that is the value of A (,
).
Output
If such maximum number exists, then print it. Otherwi, print"Palindromic tree is better than splay tree" (without the quotes).
Sample test(s)
Input
1 1
Output
40
Input
1 42
Output
1
Input
6 4
Output
172
题⽬⼤意：π(n) 为不⼤于n的素数个数，rub(n)为不⼤于n的回⽂数个数，A=p/q，如今要求最⼤的n，使得π(n) ≤ A·rub(n)
题⽬分析：预处理这两类数的个数，数组尽量往⼤了开吧，1e7过了
1#include <cstdio>
2#include <cstring>
3#include <algorithm>
4#define ll long long
遗忘的心
5using namespace std;
6int const MAX = 1e7 + 5;
7int cntpr[MAX], cntpa[MAX], p[MAX];
8bool prime[MAX];
9
10void get_prime()
11{
12 int pnum = 1;
13 memt(cntpr, 0, sizeof(cntpr));
14 memt(prime, true, sizeof(prime));
15 for(int i = 2; i <= MAX; i++)
16 {
17 cntpr[i] = cntpr[i - 1];
18 if(prime[i])
19 {
20 cntpr[i] ++;
21 p[pnum ++] = i;
22 }
23 for(int j = 1; j <= pnum && i * p[j] < MAX; j++)
24 {
25 prime[i * p[j]] = fal;
26 if(i % p[j] == 0)
出云大社27 break;
28 }
29 }
30}
31
32bool judge(int x)
