CodeForces 879A
Description
It seems that Borya is seriously sick. He is going visit n doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in the prescribed order (i.e. Borya should first visit doctor 1, then doctor 2, then doctor 3 and so on). Borya will get the information about his health from the last doctor.
Doctors have a strange working schedule. The doctor i goes to work on the si-th day and works every di day. So, he works on days si, si + di, si + 2di, ….
The doctor’s appointment takes quite a long time, so Borya can not see more than one doctor per day. What is the minimum time he needs to visit all doctors?
Input
First line contains an integer n — number of doctors (1 ≤ n ≤ 1000).
Next n lines contain two numbers si and di (1 ≤ si, di ≤ 1000).
Output
Output a single integer — the minimum day at which Borya can visit the last doctor.
Example
Input
3
2 2
1 2
2 2
Output
4
Input
2
10 1
6 5
Output
11
Note
In the first sample case, Borya can visit all doctors on days 2, 3 and 4.
In the second sample case, Borya can visit all doctors on days 10 and 11.
//codeforces 879a
// Round #443 Div.2
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int ans,b,flag,si,di;
int main(){
int n=0;
scanf("%d",&n);
ans=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&si,&di);
/*if(si>ans)
ans=si;
printf("aans=%d\n",ans);*/
flag=0;
b=0;
while(flag<1){
if(si+di*b>ans){
ans=si+di*b;
flag++;
//break;
}
else
b++;
//printf("ans=%d,b=%d\n",ans,b);
}
}
printf("%d",ans);
}
CodeForces 879B
Description
n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.
For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.
Input
The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) — the number of people and the number of wins after which a player leaves, respectively.
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ n) — powers of the player. It’s guaranteed that this line contains a valid permutation, i.e. all ai are distinct.
Output
Output a single integer — power of the winner.
Example
Input
2 2
1 2
Output
2
Input
4 2
3 1 2 4
Output
3
Input
6 2
6 5 3 1 2 4
Output
6
Input
2 10000000000
2 1
Output
2
Note
Games in the second sample:
3 plays with 1. 3 wins. 1 goes to the end of the line.
3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.
//codeforces 879b
// Round #443 Div.2
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
long long a[501];
long long vis[501];
int main(){
int n;
long long k;
//memset(a,0,sizeof(a));
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
long long ans=a[1];
for(int i=2;i<=n;i++){
if(a[i]>ans){
vis[a[i]]++;
if(vis[a[i]]==k) {
printf("%lld\n",a[i]);
return 0;
}
ans=a[i];
}else {
vis[ans]++;
if(vis[ans]==k) {
printf("%lld\n",ans);
return 0;
}
}
}
printf("%lld\n",ans);
return 0;
}
