akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class UnionFind {
private:
  vector<int> par;
public:
  UnionFind(int N) {
    par.resize(N);
    for (int i = 0; i < N; i++) par[i] = i;
  }
  int root(int x) { return (x == par[x])? x: (par[x] = root(par[x])); }
  void unite(int x, int y) { par[root(y)] = root(x); }
  bool same(int x, int y) { return (root(x) == root(y)); }
};

int main() {
  int N, M;
  cin >> N >> M;
  UnionFind UF(N);

  vector<ll> P(N); for (ll i = 0; i < N; i++) cin >> P[i];

  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y; x--; y--;
    UF.unite(x, y);
  }

  ll ans = 0;
  for (ll i = 0; i < N; i++) {
    ll p = P[i] - 1;
    if (UF.same(i, p)) ans++;
  }
  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, s, z,a[100005];
int main()
{
	int i, t;
	cin >> n;
	for (i = 0; i < n; i++) {
		scanf ("%d", &a[i]);
	}
	sort(a, a + n);
	t = z = 0;
	for (i = 0; i < n; i++) {
		if (a[i] != t) {
			s += z;
			z = 0;
		}
		t = a[i];
		z = 1 - z;
	}
	s += z;
	cout << s;
    return 0;
}


Measured memory_bytes: 640
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int N,M;
	int[][] connect;
	public void solve() {
		N = nextInt();
		M = nextInt();

		connect = new int[N][N];

		for(int i = 0;i < M;i++){
			int a = nextInt()-1;
			int b = nextInt()-1;

			connect[a][b]++;
			connect[b][a]++;
		}

		for(int i = 0;i < N;i++){
			int sum = 0;
			for(int j = 0;j < N;j++){
				sum += connect[i][j];
			}

			out.println(sum);
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 20692
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,w[101],sum;
int main(void){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> w[i];
        sum+=w[i];
    }
    int ans=10001,cur=0;
    for(int i=1;i<=n;i++){
        cur+=w[i];
        ans=min(ans, abs(sum-2*cur));
    }
    cout << ans << endl;
}

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

int main(){
	int n,k,x,y;
	cin>>n>>k>>x>>y;
	if(n<=k){
		cout<<x*n<<endl;
	}else{
		cout<<(k*x)+y*(n-k)<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int N = 1e5+10;
int a[N];
int main(){
    int n,k;
    cin >> n >> k;
    n = (n-1)/2;
    int l = 1,r = n*2+1,f = 1;
    for(int i=k;i>=1;--i){
        if(f){
            cout << l << ' ' << l+n << '\n';
            l++;
            n--;
        }else{
            cout << r << ' ' << r-n << '\n';
            r--;
            n--;
        }
        f ^= 1;
    }
    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
 

int main(){
	long long ans=0,r=0,b=0;
	string S;
	cin >> S;
	for(int i=0; i<S.size(); i++){
	if(S[i]=='0') r+=1;
	if(S[i]=='1') b+=1;
	}
	ans=min(r,b);
	cout << ans*2 << endl;
}

Measured memory_bytes: 512
import java.util.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int items[] = new int[N];
        for (int i = 0; i < N; i ++) {
            items[i] = sc.nextInt();
        }
        int total = Arrays.stream(items).sum();
        double min = 1.0 * total / (4 * M);
        int cnt = Arrays.stream(items).filter(i -> i >= min).map(i -> 1).sum();
        if (cnt >= M) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


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

int main (void){
    int k, n;
    int cont = 0;
    cin >> k;
    n = k * k;
    for(int i = 1; i <= n; i++){
        if(i % 2 == 1){
            cont += 1;
        }
    }
    cout << cont / 2 << endl;
    return 0;
}


Measured memory_bytes: 3524
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var M = line[1];
            var A = consoleReader.SplitInt();
            Array.Sort(A, (a, b) => b - a);
            var operations = consoleReader.RepeatSplitInt(M).Select(l => new Op { count = l[0], num = l[1] }).OrderByDescending(o => o.num).ToArray();

            long sum = 0;

            for (int i = 0, j = 0; i < N; i++)
            {
                if (j < M && A[i] < operations[j].num)
                {
                    if (N - i > operations[j].count)
                    {
                        N -= operations[j].count;
                        sum += (long)operations[j].num * operations[j].count;
                        --i;
                    }
                    else
                    {
                        sum += (long)operations[j].num * (N - i);
                        break;
                    }
                    ++j;
                }
                else sum += A[i];
            }

            return sum;
        }

        struct Op
        {
            public int count;
            public int num;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc()); static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Measured memory_bytes: 31556
#include<bits/stdc++.h>
using namespace std;
string s;
int a[1000010],ans=0,num;
int main()
{
	cin>>s;
	num=s.size();
	for(int i=1;i<=num;++i) a[i]=s[num-i]-'0';
	for(int i=1;i<=num+1;++i) {
		if(a[i]<=5) {
			int x=min(a[i+1],10-a[i+1])+a[i];
			int y=min(a[i+1]+1,10-a[i+1]-1)+(10-a[i]);
			if(x<=y) ans+=a[i];
			else {
				ans+=10-a[i];
				a[i+1]++;
			}
		}
		else if(a[i]>5){
			a[i+1]++;
			ans+=(10-a[i]);
		}
	}
	printf("%d",ans);
	return 0;
}

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

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

  N %= 100;
  N %= 10;

  switch(N){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      cout << "hon" << endl;
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      cout << "pon" << endl;
      break;
    case 3:
      cout << "bon" << endl;
      break;
  }
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int v[20100];
int t[100];
int mxvv[100];
int mxv[20100];
int n;
int total = 0;
int main(){
    cin >> n;

    for (int i = 0; i < n; ++i) cin >> t[i];
    for (int i = 0; i < n; ++i) cin >> mxvv[i];

    int tt = 0;
    for (int i = 0; i < n; ++i) {
        total += t[i];
        for (; tt < total; ++tt) {
            mxv[tt] = mxvv[i];
            v[tt] = 0;
        }
    }
    mxv[total] = mxvv[n - 1];
    while (1) {
        bool update = false;
        for (int t = 1; t < total; ++t) {
            if (v[t] <= v[t + 1] && v[t] <= v[t - 1] && v[t] < mxv[t] && v[t] < mxv[t - 1]) {
                v[t]++;
                update = true;
            }
        }
        if (!update) break;
    }
    double ans = 0;
    for (int t = 1; t <= total; ++t) {
        ans += (v[t - 1] + v[t]) / 2.;
        if (v[t - 1] == v[t] && v[t] < mxv[t - 1]) ans += 0.25;
    }
    cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 384
// 2020-09-27 19:19:21
// clang-format off
#include <bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
// #include <atcoder/convolution>
// #include <atcoder/dsu>
// #include <atcoder/fenwicktree>
// #include <atcoder/lazysegtree>
// #include <atcoder/math>
// #include <atcoder/maxflow>
// #include <atcoder/mincostflow>
// #include <atcoder/modint>
// #include <atcoder/scc>
// #include <atcoder/segtree>
// #include <atcoder/string>
// #include <atcoder/twosat>
// #include <atcoder/all>
// using namespace atcoder;

// clang-format on
void answer() {
  int n;
  cin >> n;
  vector<ll> a(n + 1);
  rep(i, n) cin >> a[i];
  a[n] = 0;
  ll m = 1000, s = 0;
  rep(i, n) {
    if (a[i] < a[i + 1]) {
      s += m / a[i];
      m %= a[i];
    } else if (a[i] > a[i + 1]) {
      m += s * a[i];
      s = 0;
    }
  }
  cout << m << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3628
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A = [LIST() for _ in range(3)]
N = INT()
b = [INT() for _ in range(N)]

check = [[0]*3 for _ in range(3)]

for n in b:
  for i in range(3):
    for j in range(3):
      if A[i][j] == n:
        check[i][j] = 1

for i in range(3):
  if sum(check[i]) == 3:
    print("Yes")
    exit()

for i in range(3):
  if check[0][i] and check[1][i] and check[2][i]:
    print("Yes")
    exit()
    
if check[0][0] and check[1][1] and check[2][2]:
  print("Yes")
  exit()
  
if check[0][2] and check[1][1] and check[2][0]:
  print("Yes")
  exit()
  
print("No")

Measured memory_bytes: 5204
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;
int main(){
  int a,b; cin >> a >> b;
  cout << max(a-2*b,0) << endl;
}


Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int maxk = 1e5 + 10;
vector<pair<int,int> >G[maxk];
queue<int>q;
int dis[maxk];
bool inq[maxk];
int main() {
	int k; scanf("%d", &k);
	for(int i = 0; i < k; i++) {
		G[i].push_back(make_pair((i + 1) % k, 1));
		G[i].push_back(make_pair(i * 10 % k, 0));
	}
	memset(dis, 63, sizeof(dis));
	q.push(1); dis[1] = 1;
	while(q.size()) {
		int u = q.front(); q.pop(); inq[u] = false;
		for(int i = G[u].size() - 1; i >= 0; i--) {
			int v = G[u][i].first;
			if(dis[v] > dis[u] + G[u][i].second) {
				dis[v] = dis[u] + G[u][i].second;
				if(!inq[v]) {
					q.push(v);
					inq[v] = true;
				}
			}
		}
	}
	printf("%d\n", dis[0]);
}

Measured memory_bytes: 6400
n = int(input())
x = list(map(int, input().split()))

y = sorted(x)

cost = 0
for i in x:
    cost += (i-1)*(i-1)
mini = cost
for p in range(y[0], y[-1]+1):
    cost = 0
    for i in x:
        cost += (i-p)*(i-p)
    if cost < mini:
        mini = cost

print(mini)


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

using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL<<60;

int main()
{
  int N, T;
  cin >> N >> T;
  vector<int> list(N);
  for (int i = 0; i < N; i++) {
    cin >> list[i];
  }

  vector<int> his(N - 1);
  int minv = list[0];
  int max_diff = 0;

  for (int i = 1; i < N; i++) {
    his[i - 1] = max(0, list[i] - minv);
    max_diff = max(max_diff, his[i - 1]);
    minv = min(minv, list[i]);
  }

  int ans = 0;
  for (int i = 0; i < N - 1; i++) {
    if (his[i] == max_diff) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long int a, b, n, ans;
    cin >> a >> b >> n;
    if (n < b - 1)
    {
        ans = a * n / b;
    }
    else
    {
        ans = a * (b - 1) / b;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"

using namespace std;

#define FOR(n) for(int i=0;i<n;i++)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]

int main()
{
	int a;
	string s;
	cin >> a >> s;

	if (a < 3200)cout << "red" << endl;
	else cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long a,b;cin >> a>>b;
  if (a>0) cout <<"Positive"<<endl;
  else if (a<=0 && b>=0) cout << "Zero" << endl;
  else if (((b-a)*(-1))%2==0) cout << "Negative" << endl;
  else cout << "Positive" << endl;
}

Measured memory_bytes: 256
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final int n = Integer.parseInt(br.readLine());
        final Card[] A = new Card[n];
        
        for(int i = 0; i < n; i++){
            A[i] = new Card(br.readLine(), i);
        }

        quickSort(A, 0, n-1);
        System.out.println(isStable(A)?"Stable":"Not stable");
        for(Card c : A){
            System.out.println(c.toString());
        }
    }

    static boolean isStable(Card[] A){
        for(int i=1; i<A.length; i++){
            if(A[i].getNum()==A[i-1].getNum() && A[i].getId()<A[i-1].getId()) return false;
        }
        return true;
    }

    static void quickSort(Card[] A, int p, int r){
        if(p<r){
            int q = partition(A, p, r);
            quickSort(A, p, q-1);
            quickSort(A, q+1, r);
        }
    }

    static int partition(Card[] A, int p, int r){
        final int x = A[r].getNum();
        int i = p-1;
        for(int j=p; j<r; j++){
            if(A[j].getNum()<=x){
                i++;
                swap(A,i,j);
            }
        }
        swap(A,i+1,r);
        return i+1;
    }

    public static void swap(Card[] A, int a, int b){
        Card t = A[a];
        A[a] = A[b];
        A[b] = t;
    }

}

class Card{
    final String str;
    final int num;
    final int id;

    Card(String s, int id){
        this.str = s;
        this.num = Integer.parseInt(s.substring(2));
        this.id = id;
    }

    final public int getNum(){
        return num;
    }

    final public int getId(){
        return id;
    }

    final public String toString(){
        return str;
    }
}



Measured memory_bytes: 57680
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        String ans;
        int x2 = x;
        int fx = 0;
        
        while (x2 > 0) {
            fx += x2 % 10;
            x2 /= 10;
        }
        
        if (x % fx == 0) ans = "Yes";
        else ans = "No";
        System.out.println(ans);
    }
}


Measured memory_bytes: 23380
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
#include<numeric>
#include<regex>
using namespace std;

typedef long long ll;
#define modulo 1000000007 // 10^9 + 7
#define MAX 1000000000 // 10^9

// 全部偶数なら後攻勝ち

int main() {
	int N; cin >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		ans += (a % 2);
	}

	if (ans) cout << "first" << endl;
	else cout << "second" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int L = 1e6;
int main()
  {int N; cin >> N;
  vector<int> A(N); map<int, int> m; for (auto &a : A) {cin >> a; ++m[a];}
  vector<bool> bs(L + 1, true);
  for (auto [i, c] : m) for (int j = i + (c < 2) * i; j <= L; j += i) bs[j] = false;
  int ans = 0; for (auto a: A) ans += bs[a];
  cout << ans << endl;}

Measured memory_bytes: 13560
N, Y = map(int, input().split())

total = 0
for a in range(N+1):
    
    for b in range(N+1-a):
        
        c = N -a -b
            
        total = a*10000 + b*5000 + c*1000 
        if (total == Y) and (a+b+c==N) and (c>=0):
            print(a, b, c)
            exit()
        
print(-1,-1,-1)

Measured memory_bytes: 9192
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] d = new int[n];
		for (int i = 0; i < n; i++) {
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		int m = sc.nextInt();
		int[] t = new int[m];
		for (int i = 0; i < m; i++) {
			t[i] = sc.nextInt();
		}
		Arrays.sort(t);
		sc.close();

		System.out.println(solve(n, d, m, t));
	}

	public static String solve(int n, int[] d, int m, int[] t) {
		int cur = 0;
		for (int i = 0; i < m; i++) {
			if (t[i] > d[cur]) {
				cur++;
				i--;
			} else if (t[i] == d[cur]) {
				cur++;
			} else if (t[i] < d[cur]) {
				return "NO";
			}
		}
		return "YES";
	}

	public static int[] arrayInt(Scanner sc, int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static long[] arrayLong(Scanner sc, int n) {
		long[] array = new long[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextLong();
		}
		return array;
	}

	public static double[] arrayDouble(Scanner sc, int n) {
		double[] array = new double[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextDouble();
		}
		return array;
	}
}


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

#define rep(i, n, s) for(long long (i) = 0; (i) < (n); (i) += (s))

using namespace std;

template <class T>
void printv(vector<T> v)
{
  cout << '[';
  for (auto vec: v)
  {
    cout << vec << ' ';
  }
  cout << ']' << endl;
}

int main()
{
  string s;
  cin >> s;
  long long sss = s.length();

  for (long long i = 0; i < sss; i++)
  {
    if (s.length() == 2)
    {
      cout << 1 << endl;
      exit(0);
    }
    s.pop_back();
    if (s.length() % 2 == 0)
    {
      string check1 = s.substr(0, (s.length() / 2));
      string check2 = s.substr((s.length() / 2), (s.length() / 2));

      if (check1 == check2)
      {
        cout << s.length() << endl;
        exit(0);
      }
    }
  }

}


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

using namespace std;

bool my_f(int x, int y) {
    while (x % y == 0) {
        x /= y;
    }
    return (x % y) == 1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    if (n == 2) {
        cout << 1;
        return 0;
    }
    int cnt = 0;
    for (int i = 2; i * i <= (n - 1); ++i) {
        if ((n - 1) % i == 0) {++cnt;
        if (n / i != i) ++cnt;}
    }
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0){ cnt += my_f(n, i);
        if (n / i != i) cnt += my_f(n, n / i);}
    }
    cout << cnt + 2;
    return 0;
}


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

typedef long long ll;
typedef unsigned long long int ull;
#define endl "\n"
#define pb push_back
#define sq(a) (a)*(a)
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define MOD 1000000007
#define PI 3.141592653589793238
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll exp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n)
    {
        if(n & 1)
            result=(result * x)%mod;
        x=(x*x)%mod;
        n=n>>1;
    }
    return result;
}



int32_t main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    IOS

    char c;
    cin>>c;
    if(c>=65&&c<=91)
    	cout<<"A"<<endl;
    else
    	cout<<"a"<<endl;
    
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)


ll r[200001];

int main(void){
    int n,maxi;
    ll max,min;

    scanf("%d",&n);

    REP(i,n)
        scanf("%lld",&r[i]);

    min = r[0];max = -10000000000;
    FOR(i,1,n){
        if(max < r[i] - min)
            max = r[i] - min;
        if(min > r[i])
            min = r[i];
    }

    printf("%lld\n",max);
    return 0;
}

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

#define ll long long
#define fore(i, n) for(i=0;i<n;i++)

template<typename T>
void output_vector(const vector<T>&v, int start=-1, int end=-1)
{
	if(start<0)start=0;
	if(end<0)end=v.size();
	
	for (int i = start; i < end; i++)
        cout << v[i]<<"\n";
}

int main() {
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, x, t;
    cin>>n>>x>>t;
    int d=ceil(n/double(x));
    cout<<d*t<<endl;
	return 0;
}

Measured memory_bytes: 3636
# AOJ 0609: Christmas Party
# Python3 2018.7.2 bal4u

import sys
from sys import stdin
input = stdin.readline

n, m = [int(input()) for i in range(2)]
a = list(map(int, input().split()))
s = [0]*n
for i in range(m):
	k = list(map(int, input().split()))
	x = 0
	for j in range(n):
		if k[j] == a[i]: s[j] += 1
		else: x += 1
	s[a[i]-1] += x
print(*s, sep='\n')	


Measured memory_bytes: 5632
k = int(input())
a, b = [int(elem) for elem in input().split()]


if a % k == 0 or b % k == 0:
    print('OK')
else:
    if k == 1:
        print('OK')
    elif a // k < b // k:
        print('OK')
    else:
        print('NG')



Measured memory_bytes: 9168
def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = defaultdict(lambda : defaultdict(lambda : 10**20))
    
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        if b<a:
            a,b = b,a
        length[a][b] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[min(t,v)][max(t,v)]:
                heappush(targets,(cost[t] + length[min(t,v)][max(t,v)],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

    print('\n'.join(map(str,out)))







main()

Measured memory_bytes: 98900
#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;
int a[N], b[N], n;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	cin >> n;
	Foz(i, n) cin >> a[i];
	Foz(i, n) b[i] = a[i];
	sort(b, b + n);
	if (b[n - 1] == b[n - 2]) {
		Foz(i, n) cout << b[n - 1] << '\n';
	}
	else {
		Foz(i, n) cout << (a[i] == b[n - 1] ? b[n - 2] : b[n - 1]) << '\n';
	}
}


Measured memory_bytes: 3200
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    int n, k, maxi=0;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i=0; i<n; i++) cin >> arr[i];
    for (int i=0; i<min(n, k); i++) {  // (number of things we're taking)-1
        for (int j=0; j<=i+1; j++) { // n.o.t.w.t from the left side
            multiset<int> ms;
            int kk = k-i-1, temp=0;
            for (int x=0; x<j; x++) {
                ms.insert(arr[x]);
                temp += arr[x];
            }
            for (int x=n-i+j-1; x<n; x++) {
                ms.insert(arr[x]);
                temp += arr[x];
            }
            for (auto x : ms) {
                if (x >= 0) break;
                if (!kk--) break;
                temp -= x;
            }
            maxi = max(maxi, temp);
        }
    }
    cout << maxi;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int now = 0;
  for (int i = 0; i < B; i++) {
    if (now == C) {
      cout << "YES" << endl;
      return 0;
    }
    now += A % B;
    now %= B;
  }
  if (now == C) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#[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()
}

//use lazy_static::lazy_static;

//lazy_static! {
//    static ref MOD :usize = 10usize.pow(9) + 7;
//}

use std::collections::HashMap;

static MOD: usize = 1000_000_007;

fn main() {
    let l: Vec<char> = read::<String>().chars().collect::<Vec<char>>();
    let n = l.len();

    let mut pow3 : Vec<usize> = vec![0; n];
    prepare(n, &l, &mut pow3);
    let answer = solve(n, &l, &pow3);
    println!("{}", answer);
}


fn prepare(n: usize, l: &[char], m3: &mut[usize]) {
    let mut x3 = 1;
    for i in 0..n { 
        m3[i] = x3;
        x3 = x3 * 3 % MOD;
    }
}


fn solve(n: usize, l: &[char], m3: &[usize]) -> usize {
    let mut count = 0;
    let mut c1 = 1;
    for i in 0..n {
        if l[i] == '0' {
            continue;
        }
        let remaining = n - i - 1; 
        let c2 = m3[remaining];
        let c3 = c1 * c2 % MOD;
        count = (count + c3) % MOD;
        
        c1 = c1 * 2 % MOD;
    }
    count = (count + c1) % MOD;
    return count;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,p,a[55],c=0;

int main(){
	cin >> n >> p;
	REP(i,0,n) cin >> a[i];
	REP(i,0,n) c+=a[i]%2;
	
	if(c) cout << (1L<<n-1) << endl;
	else cout << (p?0:(1L<<n)) << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <functional>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <array>
#include <memory>
#include <set>

using namespace std;

#define Get(ty,...) ty __VA_ARGS__;cins(__VA_ARGS__);
#define GetArray(ty,v,n) vector<ty> v(n);cin_arr(v,n);
#define ci cin
#define co cout
#define en endl;
#define Arr(f, arr,pred) f(arr.begin(),arr.end(),pred)
#define Arr2(f, arr) f(arr.begin(),arr.end())
#define ArrExpr(f, arr,expr) f(arr.begin(),arr.end(),[](auto x){return expr;})
#define Acc(init,arr,pred) accumulate(arr.begin(),arr.end(),init,pred)

void cins(){}

template<class Head,class... Tail>
void cins(Head& head,Tail&... tail) {
	cin >> head;
	cins(tail...);
}

template<class Arr>
void cin_arr(Arr& v,int n) {
	for (int i = 0; i < n; i++)
		cin >> v[i];
}


int main() {
	Get(int, n,m);
	int sum=0;
	int mi = 99999999;
	for (int i = 1; i <= n; i++) {
		sum += m+i-1;
		mi = min({ abs(m + i-1),abs(mi) })!=mi?m+i-1:mi;
	}
	co<<sum - mi<<en;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <iterator>
#include <utility>
#include <iomanip>
#include <stack>
#include<bitset>
#include <cmath>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
ll gcd(ll x,ll y){
	if(y==0)return x;
	return gcd(y,x%y);
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >pq;
ll expo(ll b,ll n,ll m)
{
 ll r,p;
	p=1;
	 b=b%m;
	while(n>0)
	{ 
		r=n%2;
		if(r==1)
		   p=((p%m)*(b%m))%m;
		b=((b%m)*(b%m))%m; 
		n=n/2;		
	}
 return (p%m);
}
ll divide1(ll a,ll b,ll m)
	{ ll r,p,n;
			p=a%m;
				n=m-2;
				while(n>0){
						 r=n%2;
						if(r==1)
							p=((p%m)*(b%m))%m;
						b=((b%m)*(b%m))%m; 
						n=n/2;	
					}
	return (p%m); }
ll absol(ll x)
{
	if (x<0)
	{
		return -x;
	}
	return x;
}
ll h[100012];
ll dp[100012];
int main(int argc, char const *argv[])
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	ll n,k;
	cin>>n>>k;
	for (int i = 0; i < n; ++i)
	{
		cin>>h[i];
	}
	for(int i=n-1;i>=0;--i)
	{
		dp[i]=1e17;
		for (int j = i+1; j <= i+k&&j<n; ++j)
		{
			dp[i]=min(dp[i],dp[j]+absol(h[j]-h[i]));
		}
		if (dp[i]==1e17)
		{
			dp[i]=0;
		}
	}
	cout<<dp[0]<<"\n";
	return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    std::ios::sync_with_stdio(false);

    char S[5];
    int ans = 700;
    FOR(i,0,5) {
        cin >> S[i];
        if (S[i] == 'o')
            ans += 100;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=60,MOD=1000000007;

int n;
char a[maxn],b[maxn];
ll ans;
int main()
{
    scanf("%d%s%s",&n,a+1,b+1);
    bool x=0;
    int pre=0;
    if(a[1]==b[1])ans=3,pre=0;else ans=6,pre=1;
    for(int i=pre+2;i<=n;i++){
    	if(a[i]==b[i]){
    		if(pre==0)ans=(ans*2)%MOD;
    		//else ans*=1;
    		pre=0;
    	}
    	else if(x==0)x=1;else{
    		if(pre==0)ans=(ans*2)%MOD;
    		else ans=(ans*3)%MOD;
    		x=0;
    		pre=1;
    	}
    }
    printf("%lld",ans);
    return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

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

    string Y;
    REP(i,0,SZ(X)) {
        if(SZ(Y) > 0 && Y.back() == 'S' && X[i] == 'T') Y.pop_back();
        else Y.pb(X[i]);
    }
    PR(SZ(Y));

    return 0;
}

/*



*/

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

int main(){
                                                                     

    int n, a, b, i;

    int t = 0;

    int kt = 0;

    string s;

    
    cin >> n >> a >> b >> s;


    for( i = 0 ; i < n ; i = i + 1 ){

         if( s.at(i) == 'a' ){

             if( t < a + b ){

                 cout << "Yes" << endl;

                 t += 1;

                 }

             else cout << "No" << endl;

             }

         if( s.at(i) == 'b' ){

             if( t < a + b && kt < b ){

                 cout << "Yes" << endl;

                 t += 1;

                 kt += 1;

                 }

             else cout << "No" << endl;

             }

         if( s.at(i) == 'c' ){

             cout << "No" << endl;

             }         

         }


    return 0;

    }

Measured memory_bytes: 896
use std::io::*;
use std::str::FromStr;
 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//main function
fn main() {
    let s: String = read();
    let ch: Vec<char> = s.chars().collect();
    let mut sum = 0;
    for i in 0..ch.len()/2{
	if ch[i as usize]!= ch[ch.len() as usize - i as usize -1] {
	    sum += 1;
	}
    }
    println!("{}",sum);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int h[n];
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	int c[n]={0};
	c[1]=abs(h[1]-h[0]);
	for(int i=2;i<n;i++)
	{
		c[i]=min(c[i-1]+abs(h[i]-h[i-1]),c[i-2]+abs(h[i]-h[i-2]));	
	}
	cout<<c[n-1]<<endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

static	int		l[100002], r[100002];
static	bool	x[100002];
static	int		y[100002];

bool isPrime(int v)
{
	if (v <= 1)
		return false;
	if (v == 2)
		return true;
	if (!(v & 1))
		return false;
	return !x[v];
}

void MakePrime(int mp)
{
	for(int i = 3;i <= mp; i += 2)
	{
		if(x[i])
			continue;
		x[i] = false;
		for(int j = i * 3;j <= mp;j += i * 2)
		{
			x[j] = true;
		}
	}
}

int main()
{
	int	q = 0;
	int	mp = 0;

	(void)fscanf(stdin, "%d", &q);
	for(int i = 0;i < q;i++)
	{
		(void)fscanf(stdin, "%d %d", &l[i], &r[i]);
		if(mp < r[i])
			mp = r[i];
	}
	MakePrime(mp);

	int	u = 0;
	for(int i = 0;i <= mp;i++)
	{
		if (isPrime(i) && isPrime((i + 1)/2))
			u ++;
		y[i] = u;
	}

	for(int i = 0;i < q;i++)
	{
		int	ls = l[i];
		int	rs = r[i];
		int	t	=	y[rs] - y[ls - 1];
		printf("%d\n",t);
	}

	return 0;
}


Measured memory_bytes: 1792
N = int(raw_input())
health = map(int, raw_input().strip().split())
 
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
if len(health) == 1:
	print health[0]
else:
	g = gcd(health[0], health[1])
	for i in range(2, len(health)):
		g = gcd(g, health[i])
print g

Measured memory_bytes: 11296
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < n; i++)
 
typedef long long ll;
 
ll mod=1000000007;
 
ll po(ll x, int a)
{
	if(x==0) return 0;
	if(a==0) return 1;
	if(a==1) return x;
	ll tmp=po(x, a/2);
	if(a%2==0) return tmp*tmp%mod;
	return tmp*tmp%mod*x%mod;
}
 
ll inv(ll x)
{
	return po(x, (int)mod-2);
}
 
ll beki[2010];
 
ll cb(int a, int b)
{
 	if(a<b) return 0;
	return beki[a]*inv(beki[b])%mod*inv(beki[a-b])%mod;
}
 
int main() {
	int n, k;
	cin >> n >> k;
	beki[0]=1;
	rep(i, n) beki[i+1]=beki[i]*(i+1)%mod;
	rep(j, k)
	{
		int i=j+1;
		cout << cb(k-1,i-1)*cb(n-k+1,i)%mod << endl;
	}
}

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

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  
  if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdio>//C的输入输出
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <bitset>//bitset可按位定义串
//比如：bitset <1000> all;定义一个1000位的串
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
#include <numeric>//常用数字操作 一般和algorithm搭配使用
#include <functional>//STL定义运算函数（代替运算符）
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define LOCAL
#define zeros(a,n) memset(a,0,(n)*sizeof(a[0]))
const int modn = 1e9+7;
int mod(int x) { return x<0?x+modn:x<modn?x:x-modn; }
const int N = 200005;
vector<int>g[N];
int n;
LL f[N],invf[N],ans[N],sz[N],dp[N],f2[N];
void dfs1(int u=1, int fa=-1){
    dp[u]=1;
    sz[u]=1;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa) continue;
        dfs1(v, u);
        dp[u]=dp[u]*dp[v]%modn*f[sz[u]+sz[v]-1]%modn*f2[sz[u]-1]%modn*f2[sz[v]]%modn;
        sz[u]+=sz[v];
        //cout << u<<" " <<v <<" " << sz[u] << " " <<sz[v]<<" "<< dp[u]<<endl;
    }
}
void exgcd(int a, int b, LL& x, LL& y){
    if(b == 0){
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b, a%b, x, y);
    LL t = x;
    x = y; y = t-a/b*y;
}
int inv(int a, int b){
    LL x, y;
    exgcd(a, b, x, y);
    return (x%b+b)%b;
}
void dfs2(int u=1, int fa=-1, int pd = 1){
    ans[u]=dp[u]*pd%modn*f[n-1]%modn*f2[sz[u]-1]%modn*f2[n-sz[u]]%modn;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa) continue;
        dfs2(v, u, ans[u]*f[sz[v]]%modn*inv(dp[v], modn)%modn*f[n-sz[v]-1]%modn*f2[n-1]%modn);
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    f[0]=1,invf[0]=1;
    f[1]=1, invf[1]=1;
    f2[0]=1;f2[1]=1;
    for(int i=2;i<=n;++i){
        f[i]=f[i-1]*i%modn;
        //inv [ i ] = (mod - mod/i)*inv[ mod%i ] %mod;
        invf[i]=(modn-modn/i)*invf[modn%i] % modn;
        f2[i]=f2[i-1]*invf[i]%modn;
    }
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1();
    dfs2();
    for(int i = 1; i <=n;++i) cout<<ans[i]<<"\n";
    return 0;
}



Measured memory_bytes: 23284
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
A.sort(reverse=True)
"""
kaijou = [1 for _ in range(N+1)]
for k in range(1, N):
  kaijou[k+1] = kaijou[k]*(k+1)%mod



b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res
"""
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)




def combination(n, k):
  #foo = kaijou[n]*modinv(kaijou[k]*kaijou[n-k]%mod)%mod
  foo = fact[n]*factinv[k]*factinv[n-k]%mod
  return foo

ans = 0

for k in range(N-K+1):
  ans += A[k]*combination(N-k-1, K-1)
  ans %= mod

for k in range(N-K+1):
  ans -= A[-k-1]*combination(N-k-1, K-1)
  ans %= mod

print(ans)

Measured memory_bytes: 25128