Codeforces Round #193(이전 두 문제)
7574 단어 dpenglishcodeforces
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Everybody knows that the Berland citizens are keen on health, especially students. Berland students are so tough that all they drink is orange juice!
Yesterday one student, Vasya and his mates made some barbecue and they drank this healthy drink only. After they ran out of the first barrel of juice, they decided to play a simple game. All n people who came to the barbecue sat in a circle (thus each person received a unique index bi from 0 to n - 1). The person number 0 started the game (this time it was Vasya). All turns in the game were numbered by integers starting from 1. If the j-th turn was made by the person with index bi, then this person acted like that:
he pointed at the person with index (bi + 1) mod n either with an elbow or with a nod (x mod y is the remainder after dividing x byy);
if j ≥ 4 and the players who had turns number j - 1, j - 2, j - 3, made during their turns the same moves as player bi on the current turn, then he had drunk a glass of juice;
the turn went to person number (bi + 1) mod n.
The person who was pointed on the last turn did not make any actions.
The problem was, Vasya's drunk too much juice and can't remember the goal of the game. However, Vasya's got the recorded sequence of all the participants' actions (including himself). Now Vasya wants to find out the maximum amount of juice he could drink if he played optimally well (the other players' actions do not change). Help him.
You can assume that in any scenario, there is enough juice for everybody.
Input
The first line contains a single integer n (4 ≤ n ≤ 2000) — the number of participants in the game. The second line describes the actual game: the i-th character of this line equals 'a', if the participant who moved i-th pointed at the next person with his elbow, and 'b', if the participant pointed with a nod. The game continued for at least 1 and at most 2000 turns.
Output
Print a single integer — the number of glasses of juice Vasya could have drunk if he had played optimally well.
Sample test(s)
input
4
abbba
output
1
input
4
abbab
output
0
Note
In both samples Vasya has got two turns — 1 and 5. In the first sample, Vasya could have drunk a glass of juice during the fifth turn if he had pointed at the next person with a nod. In this case, the sequence of moves would look like "abbbb". In the second sample Vasya wouldn't drink a single glass of juice as the moves performed during turns 3 and 4 are different.
제목 주소: #193 A Down the Hatch!
제목 대의: n명에게 a나 b를 보고하기 시작하고 첫 번째 사람이 시작한 다음에 번갈아 숫자를 보고한다. 만약 네 앞에 세 사람이 연속으로 같은 알파벳을 보고한다면 술을 한 잔 마셔라.첫사람한테 술 몇 잔 마셨냐고...겨우 이 정도의 정보밖에 없었는데, 결과적으로 영어를 너무 헷갈려 죽겠는데, 뜻밖에도 40분이나 걸려서야 써냈다.그리고 마지막에 와까지 했어요.너무 어수선했어.
AC 코드:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int main()
{
int n,i;
char a[2002];
while(cin>>n)
{
cin>>a;
int len=strlen(a);
int res=0;
for(i=n;i<len;i+=n)
{
if((a[i-1]==a[i-2])&&(a[i-2]==a[i-3]))
// , n ,
// n-3 。。。
res++;
}
cout<<res<<endl;
}
return 0;
}
B. Maximum Absurdity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Reforms continue entering Berland. For example, during yesterday sitting the Berland Parliament approved as much as n laws (each law has been assigned a unique number from 1 to n). Today all these laws were put on the table of the President of Berland, G.W. Boosch, to be signed.
This time mr. Boosch plans to sign 2k laws. He decided to choose exactly two non-intersecting segments of integers from 1 to n of length k and sign all laws, whose numbers fall into these segments. More formally, mr. Boosch is going to choose two integers a, b (1 ≤ a ≤ b ≤ n - k + 1, b - a ≥ k) and sign all laws with numbers lying in the segments [a; a + k - 1] and [b; b + k - 1] (borders are included).
As mr. Boosch chooses the laws to sign, he of course considers the public opinion. Allberland Public Opinion Study Centre (APOSC) conducted opinion polls among the citizens, processed the results into a report and gave it to the president. The report contains the absurdity value for each law, in the public opinion. As mr. Boosch is a real patriot, he is keen on signing the laws with the maximum total absurdity. Help him.
Input
The first line contains two integers n and k (2 ≤ n ≤ 2·105, 0 < 2k ≤ n) — the number of laws accepted by the parliament and the length of one segment in the law list, correspondingly. The next line contains n integers x1, x2, ..., xn — the absurdity of each law (1 ≤ xi ≤ 109).
Output
Print two integers a, b — the beginning of segments that mr. Boosch should choose. That means that the president signs laws with numbers from segments [a; a + k - 1] and [b; b + k - 1]. If there are multiple solutions, print the one with the minimum number a. If there still are multiple solutions, print the one with the minimum b.
Sample test(s)
input
5 2
3 6 1 1 6
output
1 4
input
6 2
1 1 1 1 1 1
output
1 3
Note
In the first sample mr. Boosch signs laws with numbers from segments [1;2] and [4;5]. The total absurdity of the signed laws equals 3 + 6 + 1 + 6 = 16.
In the second sample mr. Boosch signs laws with numbers from segments [1;2] and [3;4]. The total absurdity of the signed laws equals 1 + 1 + 1 + 1 = 4.
제목 주소: #193 B. Maximum Absurdity
제목 대의:
n과 하나의 수조 a[n], 하나의 k를 주고 연속적으로 사귀고 싶지 않은 두 개의 구간을 찾아서 2k개의 원소와 가장 큰 두 개의 구간의 왼쪽 경계를 만든다.직접 시뮬레이션, 시간 초과...그리고 예처리를 했고 WA가 떨어졌고 결국 포기했어요. 그때 생각했던 머리가 아팠어요.
dp가 처리해야 한다. 직접 한 번 훑어보고 첫 번째 구간에서 가장 큰 것을 찾은 다음에 두 구간과 가장 큰 것을 한 걸음 한 걸음 밀어낸다.
AC 코드:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
__int64 aa[200005]; //
__int64 bb[200005]; //bb[i] i K
int main()
{
int n,k,i,p1,p2,pt;
while(cin>>n)
{
cin>>k;
for(i=1;i<=n;i++)
scanf("%I64d",&aa[i]);
memset(bb,0,sizeof(bb));
for(i=1;i<=k;i++)
bb[1]+=aa[i];
for(i=2;i<=n-k+1;i++)
bb[i]=bb[i-1]-aa[i-1]+aa[i+k-1];
p1=1; p2=k+1;
__int64 ma1=-1,ma2=-1;
//ma1 ma2
for(i=p2;i<=n-k+1;i++)
{
if(bb[i-k]>ma1)
{
p1=i-k;
ma1=bb[i-k];
}
if(ma1+bb[i]>ma2) //
{
pt=p1;
p2=i;
ma2=ma1+bb[i];
}
}
printf("%d %d
",pt,p2);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.