akhauriyash/Code-Regression huggingface dataset:
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define x 1e18
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
    ll n;
    cin>>n;
    ll a[n],mul=1;
    for(ll i=0;i<n;i++)
    {
      cin>>a[i];
      if(a[i]==0)
      {
          mul = 0;
      }
    }
    sort(a,a+n);
    for(ll i=0;i<n;i++)
    {
      if( mul == 0)
      {
        break;
      }
      if(a[i]>(ll)x/mul)
      {
          mul = -1;
          break;
      }
       mul = mul*a[i];
    }
    if(mul<0 || mul>x)
    {
        cout<<"-1";
    }
    else
    {
        cout<<mul;
    }

	return 0;
}


Measured memory_bytes: 4440
package main

import (
  "bufio"
  "os"
  "strconv"
  "fmt"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}

func Solve() {
  N := NextInt()
  V := make([]bool, N)
  H := make([]int, N)
  W := make([]int, N)
  for i := range H {
    A := NextLine()
    for j, a := range A {
      if a == '#' {
        V[j] = true
        H[j]++
      } else {
        W[i]++
      }
    }
  }
  C := N + 1
  for i, v := range V {
    if v {
      C = MinInt(W[i], C)
    } else {
      C = MinInt(W[i] + 1, C)
    }
  }
  if N < C {
    Write(-1)
    return
  }
  for _, h := range H {
    if h < N { C++ }
  }
  Write(C)
  return
}

func main() {
  Solve()
  Output()
}

Measured memory_bytes: 1408
#[allow(unused_imports)]
use std::collections::HashSet;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let xa = read_vec::<i32>();
    let x = xa[0];
    let a = xa[1];
    
    let answer = solve(x, a);
    println!("{}", answer);
}

fn solve(x: i32, a: i32) -> i32 {
    if x < a {
        return 0;
    }
    
    return 10;
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using ll = unsigned long long;
using namespace std;

ll cnt = 0;
int n,m;
int* a;
int* s;
ll* dp;

int main(void) {

    cin >> n >> m;
    
    a = new int[m];
    s = new int[n+10];
    dp = new ll[n+10];

    for(int i = 0; i < m; ++i) {
        cin >> a[i];
        s[a[i]] = -1;
    }

    dp[0] = 1;

    for(int i = 0; i < n; ++i) {
        for(int d = 1; d < 3; ++d) {
            if(s[i+d] != -1) {
                dp[i+d] += dp[i];
                dp[i+d] %= 1000000007;
            }
        }
    }

    cout << dp[n]%1000000007 << endl;

    return 0;
}

Measured memory_bytes: 1664
N = int(input())
n = 1<<N.bit_length()-1
if N == n:
    print("No")
else:
    print("Yes")
    # print(n)
    ANS = []
    if N % 2:
        for i in range(1, n-1):
            ANS.append((i, i+1))
        ANS.append((n-1, N+1))
        for i in range(1, n-1):
            ANS.append((i+N, i+N+1))
        for i in range(0, N-n, 2):
            ANS.append((1+N, i+n))
            ANS.append((i+n, i+n+1))
            ANS.append((1+N, i+n+1+N))
            ANS.append((i+n+1+N, i+n+N))
    else:
        a, b, c = N-2, N-1, N
        X = [i for i in range(1, n) if i != a^c] + [c, a]
        # print("X =", X)
        for i in range(n-1):
            ANS.append((X[i], X[i+1]))
        ANS.append((X[n-1], X[0]+N))
        for i in range(n-1):
            ANS.append((X[i]+N, X[i+1]+N))
        for i in range(0, N-n-3, 2):
            ANS.append((1+N, i+n))
            ANS.append((i+n, i+n+1))
            ANS.append((1+N, i+n+1+N))
            ANS.append((i+n+1+N, i+n+N))
        ANS.append((a, a^c))
        ANS.append((c, (a^c)+N))
        ANS.append((1+N, b))
        ANS.append((a, b+N))
    # print(len(ANS))
    # print(ANS)
    if N == 3:
        ANS = [(1,2),(2,3),(3,4),(4,5),(5,6)]
    for ans in ANS:
        print(*ans)
    # print("len =", len(ANS))

Measured memory_bytes: 61576
N = int(input())
S = input()

ret = 0
for x in range(10):
    for y in range(10):
        for z in range(10):
            a = S.find(str(x))
            if a != -1:
                b = S.find(str(y), a + 1)
                if b != -1:
                    c = S.find(str(z), b + 1)
                    if c != -1:
                        ret += 1
print(ret)

Measured memory_bytes: 9228
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin>>a;
	int temp=a/100;
	if(temp*111>=a)
	{
		cout<<temp*111<<endl;
	}
	else
	{
		cout<<(temp+1)*111<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

n = int(input())
li = []
for i in range(n):
    li.append(input())

dic = defaultdict(int)
for each in li:
    dic[each] += 1

res = sorted(dic.items(), key=lambda x:x[1], reverse=True)
max_val = 0
res_li = []
for name, val in res:
    if val >= max_val:
        max_val = val
    if max_val == val:
        res_li.append(name)

res_li.sort()
for each in res_li:
    print(each)


Measured memory_bytes: 47660
import sys
input = sys.stdin.readline


class Input():
    def __init__(self):
        self.line = input()

    def number(self):
        return int(self.line)

    def numbers(self):
        array = self.line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strings(self):
        return self.line.split(' ')


def main():
    ipt = Input()
    ab = ipt.numbers()
    a = ab[0]
    b = ab[1]

    if a < 10 and b < 10:
        print(a*b)
    else:
        print('-1')


main()


Measured memory_bytes: 38384
#include <iostream>

using namespace std;

int main()
{
    string N;
    cin>>N;

    if(N=="0")
        cout<<"Yes"<<endl;
    else{
        int n=0;
        int n1;
        for(int i=0;i<N.length();i++){
            n1= N[i]-'0';
            n=n+n1;
        }
        if(n%9==0)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3376
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jaynil
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABiscuitGenerator solver = new ABiscuitGenerator();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABiscuitGenerator {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            out.println(b * (c / a));
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21460
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  int s = 0;
  for(int i = 0;i < b;i++) {
    int c;
    cin >> c;
    s += c;
  }
  if(a > s)cout << "No" << endl;
  else cout << "Yes" << endl;
}


Measured memory_bytes: 256
//@author yash2040
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define pb push_back
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define deb(X) std::cerr << ">>> deb(" << __LINE__ << \") " << #X << " = " << (X) << std::endl
//#undef deb
//#define deb(X) (void)0
int32_t main()
{
	fast();
	int t=1;
//	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int arr[n+1];
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			cin>>arr[i];
			if(i%2==1 and arr[i]%2==1)
			cnt++;
		}
		cout<<cnt<<endl;
	}
}







Measured memory_bytes: 3636
S = input()
S = S.split()
A = S[0]
B = S[1]
K = S[2]

calcList = list()

a = 1
while a <= int(B):
    if int(A) % a == 0:
        if int(B) % a == 0:
            calcList.append(a)

    a += 1

print(calcList[len(calcList) - int(K)])

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<char,int>;

const ll MOD = INF + 7;


int main(){
   int a = INF;
   rep(i, 5){
      cin >> a;
      if(a == 0){
         cout << i + 1 << endl;
         return 0;
      }
   }
}

Measured memory_bytes: 3192
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine().replaceAll("\\s", ""));

		int result = num % 4;
		if (result == 0) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 22996
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    int x;
    cin >> x;
    int mon = 100;
    int ans = 0;
    while(mon < x){
        ans++;
        mon = mon*1.01;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N = getint();
	int A[100000];
	ll ans = (A[0] = getint());

	rep1(i, N - 1) {
		A[i] = getint();
		if (i & 1) ans = ans - A[i];
		else ans = ans + A[i];
	}

	cosp(ans);
	rep(i, N - 1) {
		cosp(ans = 2 * A[i] - ans);
	}

	Would you please return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 1000000007;
using ll = int64_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    ll x; int n;
    cin >> x >> n;
    vector<int> v(n+1);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &v[i+1]);
    }
    v.emplace_back(INF<int>);
    int q;
    cin >> q;
    int cur = 1, c = 0;
    ll l = 0, r = x, lv = 0, rv = x;
    for (int i = 0; i < q; ++i) {
        int t, a;
        scanf("%d %d", &t, &a);
        while(v[cur] <= t){
            int dt = v[cur] - v[cur-1];
            if(c){
                l += dt, r += dt;
                if(x <= l) lv = rv = 0, l = r = x;
                else if(x <= r) rv -= r-x, r = x;
            }else {
                l -= dt, r -= dt;
                if(r <= 0) lv = rv = 0, l = r = 0;
                else if(l <= 0) lv -= l, l = 0;
            }
            c ^= 1;
            cur++;
        }
        int dt = t-v[cur-1];
        {
            ll l2 = l, r2 = r, lv2 = lv, rv2 = rv;
            if(c){
                l2 += dt, r2 += dt;
                if(x <= l2) lv2 = rv2 = 0, l2 = r2 = x;
                else if(x <= r2) rv2 -= r2-x, r2 = x;
            }else {
                l2 -= dt, r2 -= dt;
                if(r2 <= 0) lv2 = rv2 = 0, l2 = r2 = 0;
                else if(l2 <= 0) lv2 -= l2, l2 = 0;
            }
            if(a <= lv2) printf("%li\n", l2);
            else if(a <= rv2) printf("%li\n", l2+(a-lv2));
            else printf("%li\n", r2);
        }
    }
    return 0;
}


Measured memory_bytes: 1656
#include <bits/stdc++.h>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
    int n;
    string s;
    int len[5] = {5,7,5,7,7};
    int count;
    int now;
    int ans;
    while(1){
        cin >> n;
        if(n==0) return 0;
        vector<int> w(n);
        for(int i=0;i<n;i++){
            cin >> s;
            w[i]=s.length();
        }
        ans=-1;
        for(int i=0;i<n;i++){
            count = 0;
            now = 0;
            for(int j=i;j<n;j++){
                count+=w[j];
                if(count==len[now]){
                    now++;
                    count=0;
                    if(now==5){
                        ans=i;
                    }
                }else if(count>len[now]){
                    break;
                }
            }
            if(ans != -1){
                break;
            }
        }
        cout << ans+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3160
#include<stdio.h>
int main(){
	int a,b;
	char op;
	while(1){
		scanf("%d %c %d",&a,&op,&b);
		if(op=='+') printf("%d\n",a+b);
		else if(op=='-') printf("%d\n",a-b);
		else if(op=='*') printf("%d\n",a*b);
		else if(op=='/') printf("%d\n",a/b);
		else if(op=='?') break;
	}
	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type_a,class Type_b> bool chmax(Type_a &a,const Type_b &b){if(a<b){a=b;return true;}return false;}
template<class Type_a,class Type_b> bool chmin(Type_a &a,const Type_b &b){if(a>b){a=b;return true;}return false;}
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int n,m;
	cin>>n>>m;
	
	int diff=abs(n-m);
	if(diff>1){
		cout<<0<<endl;
		return 0;
	}
	
	if(diff==0){
		llong ans=1;
		for(int i=n;i>0;--i) ans=ans*i%MOD;
		ans=ans*ans%MOD;
		ans=ans*2%MOD;
		
		cout<<ans<<endl;
		return 0;
	}
	
	if(n>m) swap(n,m);
	llong ans=1;
	for(int i=n;i>0;--i) ans=ans*i%MOD;
	ans=ans*(ans*m%MOD)%MOD;
	
	cout<<ans<<endl;
}

Measured memory_bytes: 256
n, q = gets.split.map(&:to_i)
s = gets.chomp
lr = q.times.map { gets.split.map(&:to_i) }
arr = Array.new(n, 0)
(1..n-1).each { |i| arr[i] = arr[i-1] + (s[i-1..i] == "AC" ? 1 : 0) }
puts lr.map{ |m| arr[m[1]-1] - arr[m[0]-1] }

Measured memory_bytes: 11772
import java.util.*;
public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X[]=new int[N+1];
		for(int i=1;i<=N;i++){
			X[i]=sc.nextInt();
		}
		int Max = Integer.MIN_VALUE;
		int Low = Integer.MAX_VALUE;
		int HP = 0;
		for(int i=1;i<=100;i++){
			HP=0;
			for(int j=1;j<=N;j++){
				HP=HP+(i-X[j])*(i-X[j]);
			}
			if (Max < HP) {Max=HP;
			}
			if (Low > HP) {Low=HP;
			}
		}
		System.out.println(Low);
        }
    }

Measured memory_bytes: 21716
from functools import reduce

n, m = list(map(lambda x: int(x), input().split()))

matrix_strings = []

for _ in range(n):
    matrix_strings.append(input())

vector_strings = []

for _ in range(m):
    vector_strings.append(input())

matrix = list(map(
    lambda matrix_string: list(map(
        lambda num_str: int(num_str),
        matrix_string.split())),
    matrix_strings))

vector = list(map(lambda num_str: int(num_str), vector_strings))

dot_product = []

for matrix_row in matrix:
    dot_product.append(
        reduce(
            lambda acc, m_ij_and_v_i: acc + (m_ij_and_v_i[0] * m_ij_and_v_i[1]),
            zip(matrix_row, vector),
            0)
    )

for dot_product_i in dot_product:
    print(dot_product_i)



Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;

#define LEN 100005

typedef struct pp {
    string name;
    int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x) {
    Q[tail] = x;
    tail = (tail + 1) % LEN;
}

P dequeue() {
    P x = Q[head];
    head = (head + 1) % LEN;
    return x;
}

int min(int a, int b) { return a < b ? a : b; }

int main() {
    int elaps = 0, c, q;
    P u;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> Q[i].name;
        cin >> Q[i].t;
    }
    head = 1;
    tail = n + 1;

    while (head != tail){
        u = dequeue();
        c = min(q, u.t);
        u.t -= c;
        elaps += c;
        if (u.t > 0)    enqueue(u);
        else    cout << u.name << " " << elaps << endl;
    }

    return 0;
}



Measured memory_bytes: 7032
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)

#define BITREP(BIT, NUM) REP(BIT, 1 << (NUM))
#define ISBIT(BIT, INDEX) ((BIT) & (1 << (INDEX)))


int main()
{
	ull n, m; cin>>n>>m;
	vector<ll> k( m, 0 );
	vector<vector<ll>> s( m, vector<ll>( n, 0 ) );
	vector<ll> p( m, 0 );

	REP( k_, m )
	{
		cin >> k[k_];
		REP( s_, k[k_] ) { cin>>s[k_][s_]; s[k_][s_]--; }
	}
	REP(p_,m) cin>>p[p_];
	
	ll ans = 0;
	BITREP( i, n )
	{
		bool ok = true;
		REP(k_, m)
		{
			int b = 0;
			REP( s_, k[k_] )
			{
				if( ISBIT( i, s[k_][s_] ) ) b = b == 0 ? 1 : 0;
			}
			if( b != p[k_] ) { ok = false; break; }
		}
		if( ok ) ++ans;
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int x;
	cin >> x;
	vector <bool > expo(x+1);
	expo[1] = 1;
	for(int b=2;b<=x;b++){
		int v = b*b;
		while(v<=x){
			expo[v] = 1;
			v *= b;
		}
	}
	for(int i=x;i>=1;i--) if(expo[i]){
		cout << i << endl;
		return 0;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,K;
  cin >> N >> K;
  cout << N-K+1 << endl;
  return 0;
}


Measured memory_bytes: 3600
using System;
using System.Collections.Generic;
using System.Linq;

public static partial class Program
{
    public static void Main()
    {
        var nk = CRL().ArrayInts();
        var n = nk[0];
        var k = nk[1];

        var ans = 0.0;
        for (int dice = 1; dice <= n; dice++)
        {
            var cnt = 0;
            var val = dice;
            while (val < k)
            {
                val *= 2;
                cnt++;
            }
            ans += Math.Pow(0.5, cnt) / n;    //確率を足す
        }
        
        CWL(ans);
    }
}

public static partial class Program
{
    //テンプレここから
    public static int Sigma(int n, int next = 1, int val = 0) => next > n ? val : Sigma(n, next + 1, val + next);  
    public static long GCD(long a, long b) => b == 0 ? a : GCD(b, a % b);
    public static int GCD(int a, int b) => b == 0 ? a : GCD(b, a % b);
    public static long LCM(long a, long b) => a * b / GCD(a, b);
    public static int LCM(int a, int b) => a * b / GCD(a, b);
    public static string CRL() => Console.ReadLine();
    public static void CWL(object obj) => Console.WriteLine(obj);
    public static int ToInt(this double d) => (int) d;
    public static long ToLong(this double d) => (long) d;
    public static int ToInt(this string str) => int.Parse(str);
    public static long ToLong(this string str) => long.Parse(str);
    public static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
    public static int[] ToInt(this IEnumerable<string> strs) => strs.Select(x => x.ToInt()).ToArray();
    public static long[] ArrayLongs(this string str, char opr = ' ') => str.Split(opr).ToLong();
    public static int[] ArrayInts(this string str, char opr = ' ') => str.Split(opr).ToInt();
    public static long Diff(long a, long b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static int Diff(int a, int b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static long Sign(this long i) => Math.Sign(i);
    public static bool IsEven(this long i) => i % 2 == 0;
    public static bool IsEven(this int i) => i % 2 == 0;
    public static readonly int[] Dx = new[] {0, -1, 0, 1};
    public static readonly int[] Dy = new[] {-1, 0, 1, 0};
    public const int Mod = 1000000007;
    public static string alphabet = "abcdefghijklmnopqrstuvwxyz";
    public static long ToLong(this char c) => c.ToString().ToInt();
    public static long[] Sort(this long[] array) => array.OrderBy(x => x).ToArray();
    public static int[] Sort(this int[] array) => array.OrderBy(x => x).ToArray();
    public static long[] DSort(this long[] array) => array.OrderByDescending(x => x).ToArray();
    public static int[] DSort(this int[] array) => array.OrderByDescending(x => x).ToArray();
    public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
    public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);

    public static string JoinToStr(this IEnumerable<int> array, string sep = "")
        => array.Select(x => x.ToString()).Join(sep);

    //テンプレここまで
}

Measured memory_bytes: 11348
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
typedef long long ll;
int main() {
   int N; cin >> N;
   if(N%2!=0) cout << N/2 << endl;
   else  cout << N/2 - 1 << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	a, b := intScanner(), intScanner()
	if a <= 8 && b <= 8 {
		fmt.Println("Yay!")
	} else {
		fmt.Println(":(")
	}
}


Measured memory_bytes: 1772
#python3
from collections import Counter
def main():
    s = input()
    ans = 0
    cnt = 0
    for i in range(len(s)):
        if (s[i] == "A") | (s[i] == "T") | (s[i] == "C") | (s[i] == "G"):
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, cnt)
    print(ans)
main()


Measured memory_bytes: 3316
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeMap;
class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力

		

		int n = sc.nextInt();
	
		String[] strs = new String[n];
		int[] p = new int[n];
		
//		for(int i= 0;i < n;i++){
//			strs[i] = sc.next();
//			p[i] = sc.nextInt();
//		}
		
		TreeMap<String, TreeMap<Integer,Integer>> map = new TreeMap<String,TreeMap<Integer,Integer>>();
		for(int i = 0;i < n;i++){
			String str = sc.next();
			int num = sc.nextInt();		
			TreeMap<Integer,Integer> submap = map.getOrDefault(str,new TreeMap<>(Comparator.reverseOrder()));
			submap.put(num, i);
			map.put(str, submap);
		}
		
		for(String ss:map.keySet()){
			for(int ans:map.get(ss).values()){
				System.out.println(ans+1);
			}
		}
		
		
		

		
		
	}
	
	static void allsum(int[] A){
		long ans = 0;
		for(int i = 0;i < A.length;i++){
//			System.out.println(A[i]);
			ans += A[i];
		}
		System.out.print(ans);
	}


	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}





}



class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return  otherpair.end - end;
	}
}




Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define spc " "
#define oi "oi\n"
#define ll long long 
#define pi pair<int,int>
#define vi vector<int>
#define pl pair<ll,ll>
#define vl vector<ll>
#define vii vector<pi>
#define vll vector<pl>
#define ft first
#define sd second

string s,t;
int dp[3005][3005],n,m;

int solve(int i,int j){
    if(i==n || j==m)return -100000;
    // cout<<i<<spc<<j<<endl;

    int &ans=dp[i][j];
    if(ans!=-1)
        return ans;
    ans=max(solve(i+1,j),solve(i,j+1));
    if(s[i]==t[j]) {
        ans=max(ans,1);
        ans=max(ans,1+solve(i+1,j+1));
    }
    return ans;
}

string back(int i,int j){
    string tmp;
    if(dp[i][j]==dp[i+1][j]){
        tmp=back(i+1,j);
    }
    else if(dp[i][j]==dp[i][j+1]){
        tmp=back(i,j+1);
    }
    else if(dp[i][j]==(dp[i+1][j+1]+1) && s[i]==t[j]){
        // cout<<oi;
        tmp=s[i]+back(i+1,j+1);
    }
    else if(s[i]==t[j]){    
        // cout<<oi;
        tmp=s[i];
    }
    // cout<<dp[i][j]<<spc<<dp[i+1][j+1]<<endl;    

    return tmp;

}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>s>>t;
    n=s.size();
    m=t.size();
    memset(dp,-1,sizeof(dp));
    solve(0,0);
    cout<<back(0,0)<<endl;   

    return 0;
    
}


Measured memory_bytes: 36352
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(it,it):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)


Measured memory_bytes: 64648
n = int(input())
x = list(input())
y = x.count("1")
s, t = y - 1, y + 1
p = [1] * 20
for i in range(1, 20):
    p[i] = p[i - 1] * 2
p.sort(reverse = True)
a, b, u, v = 1 / 2, 1 / 2, 0, 0
m1, m2 = [0] * n, [0] * n
if not s == 0:
    for i in range(1, n + 1):
        a += a
        a %= s
        b += b
        b %= t
        m1[i - 1] = a
        m2[i - 1] = b
        if x[-i] == "1":
            u += a
            v += b
else:
    for i in range(1, n + 1):
        b += b
        b %= t
        m2[i - 1] = b
        if x[-i] == "1":
            v += b
ans = [1] * n
if not s == 0:
    for i in range(1, n + 1):
        if x[-i] == "1":
            j = (u - m1[i - 1]) % s
        else:
            j = (v + m2[i - 1]) % t
        if not j == 0:
            while not j == 0:
                ans[-i] += 1
                l = j
                cnt = 0
                for k in p:
                    if l == 0:
                        break
                    if k <= l:
                        cnt += 1
                        l -= k
                j = j % cnt
else:
    for i in range(1, n + 1):
        if x[-i] == "1":
            ans[-i] = 0
        else:
            j = (v + m2[i - 1]) % t
            if not j == 0:
                while not j == 0:
                    ans[-i] += 1
                    l = j
                    cnt = 0
                    for k in p:
                        if l == 0:
                            break
                        if k <= l:
                            cnt += 1
                            l -= k
                    j = j % cnt
for i in ans:
    print(i)

Measured memory_bytes: 88244
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
#define for1(i,n) for (ll i=0;i<(n);(i)++)
#define for2(i,m,n) for (ll (i)=(m);(i)<(n);(i)++)
#define for3(i,m,n,d) for (ll (i)=(m);(i)<(n);(i)+=(d))
#define INF (1LL << 60)
#define STRING(str) #str
#define DEBUG 0
#if DEBUG
    #define trace(var) dump(STRING(var), var)
#else
    #define trace(var)
#endif

void dump(const string& name, const ll value)
{
    cerr << name << ": " << value << endl;
}

void solve()
{
    ll N,P;
    cin >> N >> P;
    ll odd = 0;
    ll ans = 0;
    for1(i,N) {
        ll a;
        cin >> a;
        if (a % 2 != 0) {
            odd++;
        }
    }
    if (odd > 0) {
        ans = 1LL << (N - 1);
    } else {
        if (P == 0) {
            ans = 1LL << N;
        } else {
            ans = 0;
        }
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
const int N = 200010;
ll a[N], n, pref[N];

ll sum (int i, int j) { return pref[j] - pref[i - 1]; }

ll calc (int k) {
	return sum(1, k) - k * a[k] + (n - k) * a[k] - sum(k + 1, n);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	cin >> n;
	For(i, 1, n + 1) cin >> a[i];
	For(i, 1, n + 1) a[i] -= i;
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	pref[0] = 0;
	For(i, 1, n + 1) pref[i] = a[i] + pref[i - 1];
	ll ans = calc(1);
	For(i, 1, n + 1) ckmin(ans, calc(i));
	cout << ans << '\n';
}



Measured memory_bytes: 3456
import java.util.Scanner;


public class Main {


//	final int MOD = 1000000007;


	public static void main(String[] args) {

		int ans = 0;
		Scanner sc = new Scanner(System.in);
		boolean f = false;

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();


		//-------------------------------------------------------------------------------------

		while(!f) {
			c -= b;
			if(c <= 0) {
				System.out.println("Yes");
				break;
			}
			a -= d;
			if(a <= 0) {
				System.out.println("No");
				break;
			}
		}

		//-------------------------------------------------------------------------------------

//		for(int i = 0; i < n; i++) {
//			System.out.println(ans[i]);
//		}

//		if(f) {
//			System.out.println("Yes");
//		} else {
//			System.out.println("No");
//		}

//		System.out.println(ans);

		sc.close();
	}
}

Measured memory_bytes: 35824
#include <bits/stdc++.h>
using namespace std;

int main() {
  char c;
  cin >> c;

  string ans = "consonant";
  if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
    ans = "vowel";

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int64_t INF = 1LL << 60;


int main() {
 char N1,N2,N3,N4;
 cin>>N1>>N2>>N3>>N4;
 string t="";
 t+=N1;t+=N2;t+=N3;t+=N4;
 string d="1479";
 sort(t.begin(),t.end());
 if(t==d){
     cout<<"YES"<<endl;
 }
 else{cout<<"NO"<<endl;}
 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long llong;
typedef pair<int, int> pii;

void solve(){

	string s;
	cin >> s;

	int n = (int)s.size();
	vector<int> cnt(256);

	for(int l = 0, h = 0; h < (int)s.size(); h++){

		cnt[ s[h] ]++;

		int len;

		while( (h - l + 1) > 2 && cnt[ s[l] ] <= ( (h - l + 1) / 2) ){

			cnt[ s[l] ]--;
			l++;

		}

		if( (h - l + 1) >= 2 && cnt[ s[h] ] > ((h - l + 1) / 2) ){

			cout << l + 1 << ' ' << h + 1 << endl;
			return;

		}

	}

	cout << "-1 -1";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(50) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int q;
  cin >> q;
  rep(qi, q)
  {
    int k;
    cin >> k;
    cout << (k == *lower_bound(all(a), k)) << endl;
  }
  return 0;
}



Measured memory_bytes: 3404
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
    

int main(void){
    char s[3],t[3];
    int c=0;
    cin>>s[0]>>s[1]>>s[2];
    cin>>t[0]>>t[1]>>t[2];
    for(int i=0;i<3;i++){
        if(s[i]==t[i]){
            c++;
        }
    }
    cout<<c;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<ll, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a.begin(), a.end(), [](const auto& a1, const auto& a2) {
        return a1.first> a2.first;
    });

    vector<vector<ll>> dp(n, vector<ll>(n, 0));

    for (int l = 0; l < n - 1; ++l) {
        for (int r = n - 1; r >= l; --r) {
            int i = n - 1 - r + l;
            dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a[i].first*abs(l - a[i].second));
            if (r - 1 >= 0)
                dp[l][r - 1] = max(dp[l][r - 1], dp[l][r] + a[i].first*abs(r - a[i].second));
        }
    }

    ll ans;

    for (int l = 0; l < n; ++l)
        for (int r = 0; r < n; ++r)
            ans = max(ans, dp[l][r]);

    cout << ans << endl;
}


Measured memory_bytes: 34600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.next();
		//String t = sc.next();
		long n = sc.nextLong();
		long m = sc.nextLong();
		//long k = sc.nextLong();
		//long l = sc.nextLong();
		long count=0;

		for(int i=1;i<10000;i++) {
			if(n<500*(i+1)) {
				count=i;
				break;
			}
		}
		if(500*count+m>=n) {
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		//System.out.println((int)Math.ceil((n+m)/2.0));
		//System.out.println(n-m-k*x);
	}
}




Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

///////////////////////////////
// Union Find
class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  VI ps(N+1);
  REP(i,N) cin >> ps[i+1];

  UnionFind uf(N+1);
  REP(i,M){
	int x, y;
	cin >> x >> y;
	uf.unite(x, y);
  }

  int ans = 0;
  FOR(i,1,N+1)
	if(uf.same(ps[i], i))
	  ++ans;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a, b;

ll solve(ll a, ll b) {
	return a + (b - a - 1) / 2;
}

int main() {
	cin >> n >> a >> b;
	if ((a + b) & 1) cout << min(solve(a, b), solve(n + 1 - b, n + 1 - a));
	else cout << (b - a) / 2;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif*/

    int N; cin >> N; N++;
    int M; cin >> M;
    bool valid[N]; F0R(i, N) valid[i] = true;
    F0R(i, M) {
        int cur; cin >> cur; valid[cur] = false;
    }

    ll dp[N]; dp[0] = 1; 
    if (valid[1]) {
        dp[1] = 1;
    } else dp[1] = 0;
    FOR(i, 2, N) {
        if (valid[i]) {
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] = dp[i] % MOD;
        } else dp[i] = 0;
    }

    cout << dp[N-1] << endl;


    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 1152
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double dd;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

#define FOR(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define DOW(i,b,a) for (int i = (b); i >= (a); i--)
#define pb(a) push_back(a)
#define ALL(a) (a).begin(),(a).end()
#define fi first
#define se second

template<typename T>
void print_array(T* arr, int num) {
   FOR(i, 0, num) cout << arr[i] << ' ';
   cout << endl;
}

template<typename T> 
void print_vector(vector<T> vec) {
   FOR(i,0,vec.size()) cout << vec[i] << ' ';
   cout << endl;
}

int n,t,pre,x;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
   // freopen("test.txt", "r", stdin);
    cin >> n >> t >> pre;
    int ans = 0;
    FOR(i,1,n) {
        cin >> x;
        ans += (x - pre > t) ? t : x - pre;
        pre = x;
    }
    ans += t;
    cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

signed main(){
	int x=read();
	int y=read();
	const int inf=LLONG_MAX/2;
	int res=inf;
	if(y>x)
		chmin(res,y-x);
	if(x*y<=0)
		chmin(res,abs(abs(x)-abs(y))+1);
	else
		chmin(res,abs(abs(x)-abs(y))+2);
	cout<<res<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long int o,val,cnt=0;
	cin>>o>>val;
	while(o--)
	{
		long long int x,y;
		cin>>x>>y;
		if(sqrt(pow(x,2)+pow(y,2))<=val) cnt++;
	}
	cout<<cnt<<'\n';
}

Measured memory_bytes: 3648