C:URAL - 2064

Young gardener didn’t visit his garden for a long time, and now it’s not very pleasant there: n caterpillars have appeared on the ground.

Kirill decided to use this opportunity to have some fun and organized a competition — "caterpillar crawl-race."
At Kirill’s command all caterpillars start crawling from the ground to the top of a tree. But they get tired pretty fast. After crawling t i cm i-th caterpillar needs to rest for t i minutes. During that time it slides down a bit. Crawling speed of a caterpillar is 1 cm/minute, sliding speed — also 1 cm/minute.
Kirill is very much interested to find out how high on the tree is the leading caterpillar at different moments in time.
Input
First line contains one integer n — the number of caterpillars (1 ≤ n ≤ 10 6).
Second line contains n integers t i — characteristics of caterpillars (1 ≤ t i ≤ 10 9).
In the third line there is a number q — number of moments in time, which Kirill finds interesting (1 ≤ q ≤ 10 6).
Remaining q lines contain one query from Kirill each. A query is described by x i — number of minutes since the start of the competition (1 ≤ x i ≤ 10 6).
Output
For every query print in a separate line one integer, that describes how high is the highest caterpillar at the given moment of time.
Example
input output
4
1 3 2 1
12
1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 2 1 2 1 2 3 2 1 0

#include <bits/stdc++.h>int MAX=1e6;//define MAX 1e6默認(rèn)的好像是double類(lèi)型 using namespace std; int a[1000010],ans[1000010]; int main() {int n;cin>>n;for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n);n=unique(a,a+n)-a;if(a[n-1]>=MAX){int q,x;scanf("%d",&q);for(int i=0;i<q;++i){scanf("%d",&x);printf("%d\n",x);}return 0;}for(int i=0;i<n;++i){int j;for( j=a[i];j<=MAX;j+=2*a[i])ans[j]=max(ans[j],a[i]);ans[MAX] = max(ans[MAX], a[i]-(j-MAX));}for(int i=0;i<=a[n-1];++i)ans[i]=i;for(int i=1;i<=MAX;++i)ans[i]=max(ans[i],ans[i-1]-1);for(int i=MAX;i>=0;--i)ans[i]=max(ans[i],ans[i+1]-1);int q;cin>>q;for(int i=0;i<q;++i){int x;scanf("%d",&x);printf("%d\n",ans[x]);}return 0; } #include <bits/stdc++.h> const int MAX=2*1e6+10;//define MAX 1e6默認(rèn)的好像是double類(lèi)型 using namespace std; int a[1000010],ans[MAX+5];//const int MAX=2*1e6+10; 不加const就不對(duì) int main() {int n;cin>>n;for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n);n=unique(a,a+n)-a;/* if(a[n-1]>=MAX){int q,x;scanf("%d",&q);for(int i=0;i<q;++i){scanf("%d",&x);printf("%d\n",x);}return 0;}*/for(int i=0;i<n;++i){int j;for( j=a[i];j<=MAX;j+=2*a[i])ans[j]=max(ans[j],a[i]);// ans[MAX] = max(ans[MAX], a[i]-(j-MAX));}// for(int i=0;i<=a[n-1];++i)// ans[i]=i;for(int i=1;i<=MAX;++i)ans[i]=max(ans[i],ans[i-1]-1);for(int i=MAX;i>=0;--i)ans[i]=max(ans[i],ans[i+1]-1);int q;cin>>q;for(int i=0;i<q;++i){int x;scanf("%d",&x);printf("%d\n",ans[x]);}return 0; }D: URAL - 2065
Alex is a very serious mathematician and he likes to solve serious problems. For example, this problem.
You are to construct an array of n integers in which the amount of different integers is not less than k. Among all such arrays you have to construct the one with the minimal amount of different sums on non-empty subarrays. In other words, lets compute the sums of every non-empty subarray and remove repeating sums. You have to minimize the number of remaining sums.
Input
In the only line of input there are two integers n, k (1 ≤ k ≤ n ≤ 500), separated by a space.
Output
Print n integers separated by spaces — the answer for the problem. All the numbers must not be greater than 10 6 by absolute value. It is guaranteed that there exists an optimal solution with numbers up to 10 5 by absolute value. If there are multiple possible answers, you may print any of them.
Example
input output
1 1? ? ? ?-987654
3 2? ? ? ? 0 7 0
Notes

Let’s take a closer look on the second sample. We will denote the sum on the segment [ l, r] by sum( l, r) (elements are numbered starting with 1). sum(1, 1) = sum(3, 3) = 0, sum(1, 2) = sum(1, 3) = sum(2, 2) = sum(2, 3) = 7, so there are only two different sums.

# include <iostream> # include <cstdio> using namespace std; int main() {int n, k, a[501],t=0;for(int i=0; i<=500; i++){if(i%2==0){t++;a[i]=t;}elsea[i]=-t;}while(~scanf("%d%d",&n,&k)){for(int i=0; i<k-1; ++i)printf("%d ",a[i]);for(int i=k-1; i<n; ++i)printf("0 ");printf("\n");}return 0; }

E:URAL - 2066

You probably know that Alex is a very serious mathematician and he likes to solve serious problems. This is another problem from Alex.
You are given three nonnegative integers a, b, c. You have to arrange them in some order and put +, ? or × signs between them to minimize the outcome of the resulting expression. You are not allowed to use unary minus and parentheses in the expression. There must be exactly one sign between every pair of neighbouring numbers. You should use standard order for performing operations (multiplication first, addition and subtraction then).
Input
There are three lines with one integer in each line. The numbers are arranged in non-decreasing order (0 ≤ a ≤ b ≤ c ≤ 100).
Output
Print one number — the minimal outcome.
Example
input output
1
2

3? ? ? ? ? ? ? ? ?-5

#include<iostream> #include<algorithm> using namespace std;int main() {int s[5];for(int i=0;i<3;i++)cin>>s[i];sort(s,s+3);int sum1=s[0]-s[1]-s[2];int sum2=s[0]-s[1]*s[2];if(sum1<sum2)cout<<sum1;elsecout<<sum2;return 0; }

F：URAL - 2067?

There is a group of n children. According to a proverb, every man to his own taste. So the children value strawberries and raspberries differently. Let’s say that i-th child rates his attachment to strawberry as s i and his attachment to raspberry as r i.
According to another proverb, opposites attract. Surprisingly, those children become friends whose tastes differ.
Let’s define friendliness between two children v, u as: p( v, u) = sqrt(( s v ? s u) 2 + ( r v ? r u) 2)
The friendliness between three children v, u, w is the half the sum of pairwise friendlinesses: p( v, u, w) = ( p( v, u) + p( v, w) + p( u, w)) / 2
The best friends are that pair of children v, u for which v ≠ u and p( v, u) ≥ p( v, u, w) for every child w. Your goal is to find all pairs of the best friends.
Input
In the first line there is one integer n — the amount of children (2 ≤ n ≤ 2 · 10 5).
In the next n lines there are two integers in each line — s i and r i (?10 8 ≤ s i, r i ≤ 10 8).
It is guaranteed that for every two children their tastes differ. In other words, if v ≠ u then s v ≠ s u or r v ≠ r u.
Output
Output the number of pairs of best friends in the first line.
Then output those pairs. Each pair should be printed on a separate line. One pair is two numbers — the indices of children in this pair. Children are numbered in the order of input starting from 1. You can output pairs in any order. You can output indices of the pair in any order.
It is guaranteed that the amount of pairs doesn’t exceed 10 5.
Example
input output
2
2 3? ? ?1
7 6? ? ?1 2
3
5 5
2 -4

-4 2? ? 0

#include<cstdio> #include<algorithm> using namespace std; struct node {int s;int r;int id; }p[200005]; int cmp(node p1,node p2) {if(p1.s==p2.s)return p1.r<p2.r;return p1.s<p2.s; } int main() {int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&p[i].s,&p[i].r);p[i].id=i+1;}sort(p,p+n,cmp);int flag=0;for(int i=1;i<=n-2;i++){ ///斜率相等求三點(diǎn)共線(xiàn)。if((p[0].s-p[i].s)*(p[n-1].r-p[i].r)!=(p[n-1].s-p[i].s)*(p[0].r-p[i].r)){flag=1;break;}}if(flag)printf("0\n");else{printf("1\n");printf("%d %d",p[0].id,p[n-1].id);}return 0; }

H:

Ilya is a frontman of the most famous rock band on Earth. Band decided to make the most awesome music video ever for their new single. In that music video Ilya will go through Manhattan standing on the top of a huge truck and playing amazing guitar solos. And during this show residents of the island will join in singing and shaking their heads. However, there is a problem. People on some streets hate rock. Recall that Manhattan consists of?n?vertical and?m?horizontal streets which form the grid of (?n?? 1)×(?m?? 1) squares. Band’s producer conducted a research and realized two things. First, band’s popularity is constant on each street. Second, a popularity can be denoted as an integer from 1 to 10?⁹. For example, if rockers go along the street with popularity equal to 10?⁹?then people will greet them with a hail of applause, fireworks, laser show and boxes with... let it be an orange juice. On the other hand, if rockers go along the street with popularity equal to 1 then people will throw rotten tomatoes and eggs to the musicians. And this will not help to make the most awesome music video! So, a route goes from the upper left corner to the bottom right corner. Let us define the route coolness as the minimal popularity over all streets in which rockers passed non-zero distance. As you have probably guessed, the musicians want to find the route with the maximal coolness. If you help them then Ilya will even give you his autograph! Input In the first line there are integers?n?and?m?(2 ≤?n,?m?≤ 10?⁵), separated by space. These are the numbers of vertical and horizontal streets, respectively. In the following?n?lines there are popularity values (one value on each line) on vertical streets in the order from left to right. In the following?m?lines there are popularity values (one value on each line) on horizontal streets in the order from top to bottom. It is guaranteed that all popularity values are integers from 1 to 10?⁹. Output Output a single integer which is a maximal possible route coolness. Example inputoutput

2 3 4 8 2 7 3	4
4 3 12 4 12 3 21 5 16	12

Notes

Explanation of the first sample (the "coolest" route is highlighted):

????

I: ural2070

Nikolay and Asya investigate integers together in their spare time. Nikolay thinks an integer is interesting if it is a prime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number (e.g., number 1 has one divisor and number 10 has four divisors).
Nikolay and Asya are happy when their tastes about some integer are common. On the other hand, they are really upset when their tastes differ. They call an integer satisfying if they both consider or do not consider this integer to be interesting. Nikolay and Asya are going to investigate numbers from segment [ L; R] this weekend. So they ask you to calculate the number of satisfying integers from this segment.
Input
In the only line there are two integers L and R (2 ≤ L ≤ R ≤ 10 12).
Output
In the only line output one integer — the number of satisfying integers from segment [ L; R].
Example
input output
3 7? ? ? ? ? 4
2 2? ? ? ? ? 1

77 1010? ? 924

滿(mǎn)足兩種條件的情況下比較復(fù)雜，可以用離散數(shù)學(xué)的p:數(shù)為素?cái)?shù)，q:為合數(shù)?r:因子數(shù)為素?cái)?shù)的個(gè)數(shù)，反向推倒出來(lái)把數(shù)為合數(shù)，且因字?jǐn)?shù)為質(zhì)數(shù)的個(gè)數(shù)刪除剩下的就是滿(mǎn)足要求的

還要知道一個(gè)因子個(gè)數(shù)分解定理 ：把一個(gè)數(shù)質(zhì)因子分解x=p1^a1*p2^a2*p3^a3...

x的因子的個(gè)數(shù)為 ?（a1+1）（a2+1）（a3+1）。。。。（）

上式中的每一項(xiàng)都是大于1的，而我們?nèi)绻笊鲜降慕Y(jié)果為一個(gè)質(zhì)數(shù)，很明顯只能留下一項(xiàng)，且這一項(xiàng)為一個(gè)質(zhì)數(shù)（即ai+1為一個(gè)質(zhì)數(shù)）

那么不滿(mǎn)意的數(shù)就是：p^q? 次方(p是質(zhì)素，q+1是質(zhì)數(shù)，這樣他的因子肯定是質(zhì)數(shù)個(gè)。

（上面推導(dǎo)出來(lái)的是刪除?合數(shù)且因子數(shù)為質(zhì)數(shù)的，起初想不通這樣會(huì)不會(huì)刪除一些本身是素?cái)?shù)的數(shù)，（不會(huì)，因?yàn)橐粋€(gè)素?cái)?shù)a的話(huà)a=p1^a1*.....，那么p1只能是a，a1也只能是1,只有這樣a1+1=2?這個(gè)素?cái)?shù)a的因子個(gè)數(shù)才為2）

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include <cstring> const int maxn = 1000005;// 1e6+10;改成這個(gè)就gg using namespace std; long long primer[1000005]; bool p[1000005]; long long total; void Primer() {total=0;memset(p,true,sizeof(p));for(long long i=2;i<=maxn;++i){if(p[i]){primer[total++]=i;for(long long k=i+i;k<=maxn;k+=i){p[k]=false;}}} } long long solve(long long n) {long long mul,ans=n,j;for(long long i=0;i<total&&primer[i]*primer[i]<=n;++i){mul=primer[i];for( j=2;j<n;++j){mul*=primer[i];if(mul>n) break;if(p[j+1])ans--;}}return ans; } int main() {long long R,L;Primer();scanf("%lld%lld",&L,&R);printf("%lld\n",solve(R)-solve(L-1));return 0; }

https://blog.csdn.net/jerans/article/details/68936810

L:URAL - 2073

Nikolay has decided to become the best programmer in the world! Now he regularly takes part in various programming contests, attentively listens to problems analysis and upsolves problems. But the point is that he had participated in such a number of contests that got totally confused, which problems had already been solved and which had not. So Nikolay conceived to make a program that could read contests’ logs and build beautiful summary table of the problems. Nikolay is busy participating in a new contest so he has entrusted this task to you!
Input
The first line contains an integer n (1 ≤ n ≤ 100). It‘s the number of contests‘ descriptions. Then descriptions are given. The first line of description consists of from 1 to 30 symbols — Latin letters, digits and spaces — and gives the name of contest. It‘s given that the name doesn‘t begin and doesn’t end with a space. In the second line of description the date of contest in DD.MM.YY format is given. It‘s also given that the date is correct and YY can be from 00 to 99 that means date from 2000 till 2099. In the third line of description there are numbers p and s separated by space (1 ≤ p ≤ 13, 0 ≤ s ≤ 100). It‘s amount of problems and Nikolay’s submits in the contest. Then s lines are given. These are submits’ descriptions. Description of each submit consists of the problem‘s letter and the judge verdict separated by space. The letter of the problem is the title Latin letter and all problems are numbered by first p letters of English alphabet. The judge verdict can be one of the following: Accepted, Wrong Answer, Runtime Error, Time Limit Exceeded, Memory Limit Exceeded, Compilation Error.
Output
Print the table, which consists of n+1 lines and 3 columns. Each line (except the first) gives the description of the contest. The first column gives the name of the contest, the second column gives the date of the contest (exactly as it was given in the input), the third column gives the description of the problems. Every description of problems is the line of 13 characters, where the i-th character correlate with the i-th problem. If the problem got verdict Accepted at least one time, this character is ’o’. If the problem was submitted at least once but wasn’t accepted, the character is ’x’. If the problem was just given at the contest but wasn’t submitted, the character is ’.’. Otherwise, the character is ’ ’ (space). Contests in the table must be placed in the same order as in input.
Column with the name of the contest consists of 30 symbols (shorter names must be extended by spaces added to the right to make this length). Columns with the date and description of problems consist of 8 and 13 characters accordingly.
The first line of the table gives the names of columns. The boundaries of the table are formatted by ’|’, ’-’ и ’+’ symbols. To get detailed understanding of the output format you can look at the example.
Example
input output
2
Codeforces Gamma Round 512
29.02.16
5 4
A Accepted
B Accepted
C Accepted
E Accepted
URKOP
17.10.15
12 11
A Accepted
B Wrong Answer
B Time Limit Exceeded
J Accepted
B Accepted
J Time Limit Exceeded
J Accepted
F Accepted
E Runtime Error
H Accepted
E Runtime Error
+------------------------------+--------+-------------+
|Contest name? ? ? ? ? ? ? ? ? |Date? ? |ABCDEFGHIJKLM|
+------------------------------+--------+-------------+
|Codeforces Gamma Round 512? ? |29.02.16|ooo.o? ? ? ? |
+------------------------------+--------+-------------+
|URKOP? ? ? ? ? ? ? ? ? ? ? ? ?|17.10.15|oo..xo.o.o.. |

+------------------------------+--------+-------------+

#include <bits/stdc++.h> using namespace std; struct node {string name;int nian,yue,ri;int m,s; }f[200]; struct del {int num[30]; }q[200]; int main() {int n;scanf("%d%*c",&n);memset(q,0,sizeof(q));for(int i=0;i<n;i++){getline(cin,f[i].name);scanf("%d",&f[i].nian);getchar();scanf("%d",&f[i].yue);getchar();scanf("%d",&f[i].ri);getchar();scanf("%d %d",&f[i].m,&f[i].s);getchar();for(int j=0;j<f[i].s;j++){char e;string e1;scanf("%c",&e);getchar();getline(cin,e1);//getchar();///cout<<"*/";// printf("e=%c\n",e);//printf("e1[0]=%c\n",e1[0]);if("Accepted"==e1)q[i].num[e-'A']=1;else if("Accepted"!=e1&&q[i].num[e-'A']!=1)q[i].num[e-'A']=2;elsecontinue;}}cout<<"+------------------------------+--------+-------------+"<<endl;cout<<"|Contest name |Date |ABCDEFGHIJKLM|"<<endl;for(int i=0;i<n;i++){cout<<"+------------------------------+--------+-------------+"<<endl;int len=f[i].name.length();cout<<"|"<<f[i].name;for(int k=1;k<=30-len;k++)cout<<" ";cout<<"|";printf("%02d.%02d.%02d",f[i].nian,f[i].yue,f[i].ri);cout<<"|";for(int h=0;h<f[i].m;h++){if(q[i].num[h]==0)cout<<".";else if(q[i].num[h]==1)cout<<"o";else if(q[i].num[h]==2)cout<<"x";}for(int r=1;r<=13-f[i].m;r++)cout<<" ";cout<<"|"<<endl;}printf("+------------------------------+--------+-------------+\n");return 0; }

總結(jié)

以上是生活随笔為你收集整理的2018 Spring Team Contest B的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。