Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
#include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
struct PairHash {inline std::size_t operator()(const std::pair<int, int> &v) const { return v.first * 31 + v.second; }};
// speed
#define Code ios_base::sync_with_stdio(false);
#define By ios::sync_with_stdio(0);
#define Sumfi cout.tie(NULL);
// alias
using ll = long long;
using ld = long double;
using ull = unsigned long long;
// constants
const ld PI = 3.14159265358979323846; /* pi */
const ll INF = 1e18;
const ld EPS = 1e-9;
const ll MAX_N = 1010101;
const ll mod = 1e9 + 7;
// typedef
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef array<ll,3> all3;
typedef array<ll,5> all5;
typedef vector<all3> vall3;
typedef vector<all5> vall5;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef deque<ll> dqll;
typedef deque<pll> dqpll;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
typedef unordered_map<pll, ll, PairHash> umpll;
// macros
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,m,n) for(ll i=n;i>=m;i--)
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define INF(a) memset(a,0x3f3f3f3f3f3f3f3fLL,sizeof(a))
#define ASCEND(a) iota(all(a),0)
#define sz(x) ll((x).size())
#define BIT(a,i) (a & (1ll<<i))
#define BITSHIFT(a,i,n) (((a<<i) & ((1ll<<n) - 1)) | (a>>(n-i)))
#define pyes cout<<"Yes\n";
#define pno cout<<"No\n";
#define endl "\n"
#define pneg1 cout<<"-1\n";
#define ppossible cout<<"Possible\n";
#define pimpossible cout<<"Impossible\n";
#define TC(x) cout<<"Case #"<<x<<": ";
#define X first
#define Y second
// utility functions
template <typename T>
void print(T &&t) { cout << t << "\n"; }
template<typename T>
void printv(vector<T>v){ll n=v.size();rep(i,0,n){cout<<v[i];if(i+1!=n)cout<<' ';}cout<<endl;}
template<typename T>
void printvln(vector<T>v){ll n=v.size();rep(i,0,n)cout<<v[i]<<endl;}
void fileIO(string in = "input.txt", string out = "output.txt") {freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout);}
void readf() {freopen("", "rt", stdin);}
template<typename T>
void readv(vector<T>& v){rep(i,0,sz(v)) cin>>v[i];}
template<typename T, typename U>
void readp(pair<T,U>& A) {cin>>A.first>>A.second;}
template<typename T, typename U>
void readvp(vector<pair<T,U>>& A) {rep(i,0,sz(A)) readp(A[i]); }
void readvall3(vall3& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2];}
void readvall5(vall5& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2]>>A[i][3]>>A[i][4];}
void readvvll(vvll& A) {rep(i,0,sz(A)) readv(A[i]);}
struct Combination {
vll fac, inv;
ll n, MOD;
ll modpow(ll n, ll x, ll MOD = mod) { if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }
Combination(ll _n, ll MOD = mod): n(_n + 1), MOD(MOD) {
inv = fac = vll(n,1);
rep(i,1,n) fac[i] = fac[i-1] * i % MOD;
inv[n - 1] = modpow(fac[n - 1], MOD - 2, MOD);
rrep(i,1,n - 2) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll fact(ll n) {return fac[n];}
ll nCr(ll n, ll r) {
if(n < r or n < 0 or r < 0) return 0;
return fac[n] * inv[r] % MOD * inv[n-r] % MOD;
}
};
struct Matrix {
ll r,c;
vvll matrix;
Matrix(ll r, ll c, ll v = 0): r(r), c(c), matrix(vvll(r,vll(c,v))) {}
Matrix operator*(const Matrix& B) const {
Matrix res(r, B.c);
rep(i,0,r) rep(j,0,B.c) rep(k,0,B.r) {
res.matrix[i][j] = (res.matrix[i][j] + matrix[i][k] * B.matrix[k][j] % mod) % mod;
}
return res;
}
Matrix copy() {
Matrix copy(r,c);
copy.matrix = matrix;
return copy;
}
Matrix pow(ll n) {
assert(r == c);
Matrix res(r,r);
Matrix now = copy();
rep(i,0,r) res.matrix[i][i] = 1;
while(n) {
if(n & 1) res = res * now;
now = now * now;
n /= 2;
}
return res;
}
};
// geometry data structures
template <typename T>
struct Point {
T y,x;
Point(T y, T x) : y(y), x(x) {}
Point(pair<T,T> p) : y(p.first), x(p.second) {}
Point() {}
void input() {cin>>y>>x;}
friend ostream& operator<<(ostream& os, const Point<T>& p) { os<<p.y<<' '<<p.x<<'\n'; return os;}
Point<T> operator+(Point<T>& p) {return Point<T>(y + p.y, x + p.x);}
Point<T> operator-(Point<T>& p) {return Point<T>(y - p.y, x - p.x);}
Point<T> operator*(ll n) {return Point<T>(y*n,x*n); }
Point<T> operator/(ll n) {return Point<T>(y/n,x/n); }
bool operator<(const Point &other) const {if (x == other.x) return y < other.y;return x < other.x;}
Point<T> rotate(Point<T> center, ld angle) {
ld si = sin(angle * PI / 180.), co = cos(angle * PI / 180.);
ld y = this->y - center.y;
ld x = this->x - center.x;
return Point<T>(y * co - x * si + center.y, y * si + x * co + center.x);
}
ld distance(Point<T> other) {
T dy = abs(this->y - other.y);
T dx = abs(this->x - other.x);
return sqrt(dy * dy + dx * dx);
}
T norm() { return x * x + y * y; }
};
template<typename T>
struct Line {
Point<T> A, B;
Line(Point<T> A, Point<T> B) : A(A), B(B) {}
Line() {}
void input() {
A = Point<T>();
B = Point<T>();
A.input();
B.input();
}
T ccw(Point<T> &a, Point<T> &b, Point<T> &c) {
T res = a.x * b.y + b.x * c.y + c.x * a.y;
res -= (a.x * c.y + b.x * a.y + c.x * b.y);
return res;
}
bool isIntersect(Line<T> o) {
T p1p2 = ccw(A,B,o.A) * ccw(A,B,o.B);
T p3p4 = ccw(o.A,o.B,A) * ccw(o.A,o.B,B);
if (p1p2 == 0 && p3p4 == 0) {
pair<T,T> p1(A.y, A.x), p2(B.y,B.x), p3(o.A.y, o.A.x), p4(o.B.y, o.B.x);
if (p1 > p2) swap(p2, p1);
if (p3 > p4) swap(p3, p4);
return p3 <= p2 && p1 <= p4;
}
return p1p2 <= 0 && p3p4 <= 0;
}
pair<bool,Point<ld>> intersection(Line<T> o) {
if(!this->intersection(o)) return {false, {}};
ld det = 1. * (o.B.y-o.A.y)*(B.x-A.x) - 1.*(o.B.x-o.A.x)*(B.y-A.y);
ld t = ((o.B.x-o.A.x)*(A.y-o.A.y) - (o.B.y-o.A.y)*(A.x-o.A.x)) / det;
return {true, {A.y + 1. * t * (B.y - A.y), B.x + 1. * t * (B.x - A.x)}};
}
//@formula for : y = ax + b
//@return {a,b};
pair<ld, ld> formula() {
T y1 = A.y, y2 = B.y;
T x1 = A.x, x2 = B.x;
if(y1 == y2) return {1e9, 0};
if(x1 == x2) return {0, 1e9};
ld a = 1. * (y2 - y1) / (x2 - x1);
ld b = -x1 * a + y1;
return {a, b};
}
};
template<typename T>
struct Circle {
Point<T> center;
T radius;
Circle(T y, T x, T radius) : center(Point<T>(y,x)), radius(radius) {}
Circle(Point<T> center, T radius) : center(center), radius(radius) {}
Circle() {}
void input() {
center = Point<T>();
center.input();
cin>>radius;
}
bool circumference(Point<T> p) {
return (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y) == radius * radius;
}
bool intersect(Circle<T> c) {
T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
return (radius - c.radius) * (radius - c.radius) <= d and d <= (radius + c.radius) * (radius + c.radius);
}
bool include(Circle<T> c) {
T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
return d <= radius * radius;
}
};
ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }
all3 __exgcd(ll x, ll y) { if(!y) return {x,1,0}; auto [g,x1,y1] = __exgcd(y, x % y); return {g, y1, x1 - (x/y) * y1}; }
ll __lcm(ll x, ll y) { return x / __gcd(x,y) * y; }
ll modpow(ll n, ll x, ll MOD = mod) { n%=MOD; if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }
vll st;
vvll radj;
vll adj, vis1, vis2, rsz;
void dfs1(ll u) {
vis1[u] = true;
ll v = adj[u];
if(!vis1[v]) dfs1(v);
st.push_back(u);
}
void dfs2(ll u, ll& root) {
vis2[u] = true;
rsz[root] += 1;
for(auto& v : radj[u]) {
if(!vis2[v])
dfs2(v,root);
}
}
ll solve(vll& A) {
adj = vis1 = vis2 = rsz = vll(sz(A));
radj = vvll(sz(A));
st = {};
ll res = 0;
rep(i,0,sz(A)) {
ll v = (i + A[i] + 1) % sz(A);
if(v == i) res += 1;
adj[i] = v;
radj[v].push_back(i);
}
rep(i,0,sz(A)) {
if(!vis1[i])
dfs1(i);
}
while(sz(st)) {
auto u = st.back(); st.pop_back();
if(vis2[u]) continue;
dfs2(u,u);
}
rep(i,0,sz(A)) if(rsz[i] > 1) res += rsz[i];
return res;
}
int main() {
Code By Sumfi
cout.precision(12);
ll tc = 1;
cin>>tc;
rep(i,1,tc+1) {
ll n;
cin>>n;
vll A(n);
readv(A);
print(solve(A));
}
return 0;
}
# cook your dish here
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict
def dfs1(u):
visited[u] = True
v = (u + e[u] + 1) % n
if visited[v] is False:
dfs1(v)
order.append(u)
def dfs2(u):
visited[u] = True
for adjacent in transpose[u]:
if visited[adjacent] is False:
dfs2(adjacent)
scc.append(u)
t = int(input())
for i in range(t):
n = int(input())
e = [int(x) for x in input().split()]
transpose = defaultdict(list)
for index, value in enumerate(e):
transpose[(index + value + 1)% n].append(index)
ans = 0
visited = [False] * n
order = []
for i in range(n):
if visited[i] is False:
dfs1(i)
# print(order)
visited = [False] * n
for i in range(n):
node = order[n-1-i]
scc = []
if visited[node] is False:
dfs2(node)
# print(scc,(scc[0] + e[scc[0]] + 1) % n)
if len(scc) == 1 and scc[0] != (scc[0] + e[scc[0]] + 1) % n:
continue
ans += len(scc)
print(ans)
// CHEFRRUN
#include <stdio.h>
#define ll long long
#define gc getchar_unlocked
int getn(){
int n = 0, c = gc(), f = 1;
while(c != '-' && (c < '0' || c > '9')) c = gc();
if(c == '-') f = -1, c = gc();
while(c >= '0' && c <= '9') n = (n<<3) + (n<<1) + c - '0', c = gc();
return n * f;
}
int MOD;
int madd(int a, int b){ return ((a += b) >= MOD) ? a-MOD : a; }
char r[100000];
int a[100000], v[100000];
int main(){
int T,N, i,j,k, n;
T = getn();
while(T--){
N = MOD = getn();
for(i = 0; i < N; ++i) a[i] = getn()%N, v[i] = -1, r[i] = 0;
for(i = 0; i < N; ++i){
if(v[i] != -1) continue;
for(j = i; v[j] == -1; j = madd(j, a[j]+1)) v[j] = i;
if(v[j] == i){
k = j, r[j] = 1;
for(j = madd(j, a[j]+1); j != k; j = madd(j, a[j]+1)) r[j] = 1;
}
}
for(i = n = 0; i < N; ++i) if(r[i]) ++n;
printf("%d\n", n);
}
return 0;
}
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int test = Integer.parseInt(reader.readLine().trim());
while (test-- > 0) {
int n = Integer.parseInt(reader.readLine().trim());
String[] str = reader.readLine().trim().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(str[i]);
int[] adj = new int[n];
for (int i = 0; i < n; i++) {
adj[i] = (i + 1 + arr[i]) % n;
}
boolean[] vis = new boolean[n];
boolean[] recstack = new boolean[n];
int res = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
res += dfs(i, adj, vis, recstack);
}
}
System.out.println(res);
}
reader.close();
}
public static int cycle(int node, int[] adj) {
int temp = node;
int count = 1;
while (adj[temp] != node) {
count++;
temp = adj[temp];
}
return count;
}
public static int dfs(int node, int[] adj, boolean[] vis, boolean[] recstack) {
vis[node] = recstack[node] = true;
int i = 0;
if (node == adj[node]) i = 1;
if (!vis[adj[node]]) {
i = dfs(adj[node], adj, vis, recstack);
} else if (vis[adj[node]] && recstack[adj[node]]) {
i = cycle(adj[node], adj);
} else if (vis[adj[node]] && !recstack[adj[node]]) {
i = 0;
}
recstack[node] = false;
return i;
}
}
import os, sys
from io import BytesIO, IOBase
sys.setrecursionlimit(10**6+100)
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10 ** 9 + 7
from math import ceil
import heapq
from bisect import bisect_left
def dfs(i):
v[i]=1
if v[ad[i][0]]!=1:
dfs(ad[i][0])
arr.append(ad[i][0])
def dfs1(i):
v[i]=1
for j in tr[i]:
if v[j]==0:
dfs1(j)
ck.append(j)
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
v=[0]*n
ad=[[] for _ in range(n)]
tr=[[] for _ in range(n)]
for i in range(n):
ad[i].append((i+a[i]+1)%n)
tr[(i+a[i]+1)%n].append(i)
arr=[]
for i in range(n):
if not v[i]:
dfs(i)
arr.append(i)
# print(arr)
v=[0]*n
ans=0
# print(tr)
while arr:
t=arr.pop()
#print(t,v)
if not v[t]:
ck=[]
ck.append(t)
dfs1(t)
# print(ck)
if len(ck)>=2:
ans+=len(ck)
for i in range(n):
if i in ad[i]:
ans+=1
print(ans)
t = int(raw_input())
for i in range(t):
N = int(raw_input())
st = raw_input().split()
A = []
for x in st:
A.append(int(x))
# endfor x
V = [0 for x in range(N)]
tot = 0
for p in range(N):
if V[p] == 0:
L = []
q = p
while V[q] == 0:
V[q] = 1
L.append(q)
q = (q+1+A[q])%N
# endwhile
if q in L:
z = 0
while L[z] != q:
z += 1
# endwhile
tot += len(L) - z
# endif
# endif
# endfor p
print tot
# endfor i
using System;
public class Class1
{
public static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine());
for(int i=0;i<T;i++)
{
int N = Convert.ToInt32(Console.ReadLine());
string[] temp = new string[N];
temp = Console.ReadLine().Split();
int[,] taste = new int[3, N];
for(int j=0;j<N;j++)
{
taste[0, j] = Convert.ToInt32(temp[j]);
taste[1, j] = 0;
taste[2, j] = 0;
}
int loop = 0;
int step = 0;
int count = 0;
int k = 0;
for(int j=0;j<N;j++)
{
step = 0;
if (taste[1, j] == 0)
{
step += 1;
loop += 1;
k = j;
while (taste[1, k] == 0)
{
taste[1, k] = loop;
taste[2, k] = step;
step++;
k = (k + taste[0, k] + 1) % N;
}
if (loop == taste[1, k])
{
count += step - taste[2, k];
}
}
}
Console.WriteLine(count);
}
}
}
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)
func main() {
InitReader(os.Stdin, 1<<20)
InitWriter(os.Stdout)
defer Flush()
solve()
}
func solve() {
T := ReadInt()
for t := 0; t < T; t++ {
n := ReadInt()
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = ReadInt()
}
count := make([]int, n)
touched := make([]int, n)
pos := 0
for q := 1; q <= n; q++ {
for pos < n && count[pos] > 0 {
pos++
}
if pos == n {
break
}
node := pos
for {
if count[node] == 2 || (touched[node] > 0 && touched[node] < q) {
break
}
count[node]++
touched[node] = q
node = (node + a[node] + 1) % n
}
}
res := 0
for i := 0; i < n; i++ {
if count[i] == 2 {
res++
}
}
Println(fmt.Sprint(res))
}
}
// ========== To Use
var DefaultReader *Reader
var DefaultWriter *bufio.Writer
func Flush() {
DefaultWriter.Flush()
}
func InitReader(r io.Reader, size int) {
DefaultReader = newReader(r, size)
}
func InitWriter(w io.Writer) {
DefaultWriter = bufio.NewWriter(w)
}
func InitWriterSize(w io.Writer, size int) {
DefaultWriter = bufio.NewWriterSize(w, size)
}
func Print(s string) {
DefaultWriter.WriteString(s)
}
func Printf(format string, args ...interface{}) {
Print(fmt.Sprintf(format, args))
}
func Printfln(format string, args ...interface{}) {
Printf(format+"\n", args)
}
func Println(s string) {
Print(s + "\n")
}
func ReadInt() int {
value, _ := DefaultReader.readInt()
return value
}
func ReadInt64() int64 {
value, _ := DefaultReader.readInt64()
return value
}
// ========== Reader
type Reader struct {
buffered bufio.Reader
st StringTokenizer
}
func (reader *Reader) fill() (bool, error) {
if reader.st.hasMoreTokens() {
return false, nil
}
line, err := reader.buffered.ReadString("\n"[0])
if err != nil {
if err != io.EOF {
return false, fmt.Errorf("Reader failed to read to the end of the line")
}
} else {
line = line[:len(line)-1]
}
reader.st = *newStringTokenizer(line, " ")
return true, err
}
func newReader(r io.Reader, size int) *Reader {
buffer := *bufio.NewReaderSize(r, size)
st := *new(StringTokenizer)
return &Reader{buffer, st}
}
func (reader *Reader) readInt() (int, error) {
value, err := reader.readInt64()
return int(value), err
}
func (reader *Reader) readInt64() (int64, error) {
_, err := reader.fill()
if err != nil && err != io.EOF {
return 0, err
}
token, ok := reader.st.nextToken()
if !ok {
return 0, fmt.Errorf("Reader failed to get the next token")
}
value, err := strconv.ParseInt(token, 10, 64)
if err != nil {
return 0, fmt.Errorf("Reader failed to parse token while trying to read an int")
}
return value, err
}
// ========== StringTokenizer
type StringTokenizer struct {
tokens []string
index int
}
func (st *StringTokenizer) hasMoreTokens() bool {
return st.index < len(st.tokens)
}
func newStringTokenizer(str, sep string) *StringTokenizer {
tokens := strings.Split(str, sep)
return &StringTokenizer{tokens, 0}
}
func (st *StringTokenizer) nextToken() (string, bool) {
index := &st.index
tokens := st.tokens
if *index >= len(tokens) {
return "", false
}
res := tokens[*index]
*index++
return res, true
}
In our experience, we suggest you solve this Chef and Round Run CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and Round Run CodeChef Solution.
I hope this Chef and Round Run CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!