PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Vishesh Saraswat
Tester: Istvan Nagy
Editorialist: Harshikaa Agrawal
Difficulty:
Easy
Prerequisites:
Modular Arithmetic, Dynamic Programming (not necessary)
Problem:
There are N elements in a circle, 1 to N. The following operations are done N−1 times
- Start at the lowest index
- From there M−1 steps are taken.
- The index that’s reached is removed from the circle.
The last element remaining after N−1 operations is the winner. Given an M and X, Output the winner for 1 player, 2 players, 3 players, …, X players.
Explanation:
For N ≤ X, consider
f(N) = M \bmod N, if M \bmod N \neq 0
f(N) = N, if M \bmod N = 0
f(N) gives the position of the index that is reached (removed) after the operation occurs once out of the N-1 times. This means we can now compare it to when the game is played with N-1 players.
Consider winner from N players as g(N).
If g(N-1) < f(N), it means that g(N) would be the same as that of g(N-1). This is because if you remove a player that was ahead of g(N-1), the difference won’t affect the winner for a circle of N players.
However if g(N-1) \geq f(N), that means the circle has changed and g(N) will be g(N-1) + 1. We will take the base case as g(1) = 1 because 0 operations will be performed in this case.
Time complexity:
O(X) for each test case
Setter’s Solution
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
using ll = long long;
const int mod = 1e9+7;
void solve(int tc) {
int m, x;
cin >> m >> x;
vector<int> ans(x+1);
auto get = [=] (int num) {
if (m%num==0)
return num;
return m%num;
};
ans[1] = get(1);
for (int i = 2; i <= x; ++i)
ans[i] = (get(i) > ans[i-1] ? ans[i-1] : ans[i-1] + 1);
for (int i = 1; i <= x; ++i)
cout << ans[i] << " ";
cout << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1;
cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
Tester’s Solution
Tester's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <cassert>
#include <vector>
using namespace std;
#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
int main() {
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 1'000);
int sumX = 0;
for (int tc = 0; tc < T; ++tc)
{
int M = readIntSp(1, 1'000'000'000);
int X = readIntLn(1, 10'000);
sumX += X;
int lastWinner = 1;
printf("1 ");
for (int N = 2; N <= X; ++N)
{
int first = M%N;
if (first == 0)
first = N;
if (first <= lastWinner)
lastWinner++;
printf("%d ", lastWinner);
}
printf("\n");
}
assert(sumX <= 500'000);
assert(getchar() == -1);
}
Editorialist’s solution:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int m, x;
cin>>m>>x;
int ans[x+1];
ans[1] = 1;
if(x > 1)
{
for(int i = 2; i <= x; i++)
{
int temp;
if(m%i != 0)
{
temp = m%i;
}
else
{
temp = x;
}
if(temp > ans[i-1])
{
ans[i] = ans[i-1];
}
else
{
ans[i] = ans[i-1]+1;
}
}
}
for(int i = 1; i <= x; i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
}
return 0;
}
The event is a part of our annual tech symposium Exun 2021-22, powered by Athena Education.
,might be overkill.