akhauriyash/Code-Regression huggingface dataset:
function myout(text){console.log(text);}//standard output
function Main(input) {
	//input = parseInt(input);
	//input = input.split(" ");
	input = input.split("\n");
	//input = input.split(" ").map((a)=>Number(a));
	//input = input.split("\n").map((a)=>Number(a));
  input.shift();
  input.sort(function(a,b){
  	var aList = a.split("");
    var bList = b.split("");
    for(var i = 0; i < aList.length; i++){
      if(aList[i] != bList[i]){
         return aList[i].charCodeAt() - bList[i].charCodeAt();
      }
    }
  });
  myout(input.join(""));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

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

int main() {
  int n;
  cin >> n;
  vector<int> as(n);
  for (auto &a : as) {
    cin >> a;
  }
  {
    bool f = true;
    for (auto &a : as) {
      f &= a == as[0];
    }
    if (f) {
      cout << n / 2 << endl;
      return 0;
    }
  }
  map<int, int> puni, muni;
  for (int i = 0; i < n; i += 2) {
    puni[as[i]]++;
  }
  for (int i = 1; i < n; i += 2) {
    muni[as[i]]++;
  }
  vector<pair<int, int>> bs, cs;
  for (auto &p : puni) {
    bs.push_back({p.second, p.first});
  }
  for (auto &p : muni) {
    cs.push_back({p.second, p.first});
  }
  sort(bs.begin(), bs.end());
  reverse(bs.begin(), bs.end());
  sort(cs.begin(), cs.end());
  reverse(cs.begin(), cs.end());
  int ans = n - bs[0].first - cs[0].first;
  if (bs[0].second == cs[0].second) {
    ans = n - max(bs[0].first + cs[1].first, bs[1].first + cs[0].first);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6520
n,m=gets.split.map(&:to_i)
aNs=gets.split.map(&:to_i)
aNsValueSum = aNs.inject(:+)
limitValue = (aNsValueSum.to_f / (4.0 * m.to_f)).ceil
count = 0
aNs.each do |value|
  count +=1 if value >= limitValue
end
puts count >= m ? "Yes" : "No"

Measured memory_bytes: 1788
# frozen_string_literal: true

a, b, x = gets.split.map(&:to_f)

h = x / (a * a)

theta = Math.atan(2 / a * (b - h))

l = b - a * Math.tan(theta)

if l < 0
  theta = Math.atan(b * b / (2 * a * h))
end
puts theta / Math::PI * 180


Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long long N,M;
    cin>>N>>M;
    long long ans=0;
    std::vector<long long>A(M) ;
    for(long long i=0;i<M;i++){
        cin>>A[i];
        ans+=A[i];
    }
    if(N>=ans){
        cout<<N-ans<<endl;
    }
    else{
        cout<<-1<<endl;
    }
    return 0;
}


Measured memory_bytes: 3684
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef unsigned long Key;

struct List {
	Key key;
	List* pre;
	List* next;
};

List* head;

void insert(Key k) {
	List* list = new List();
	head->next->pre = list;
	list->next = head->next;
	head->next = list;
	list->pre = head;
	list->key = k;
}

void ldelete(Key k) {
	List* iter = head->next;
	while (iter != head) {
		if (iter->key == k)break;
		iter = iter->next;
	}
	if (iter != head) {
		iter->pre->next = iter->next;
		iter->next->pre = iter->pre;
		delete iter;
	}
}

void deleteFirst() {
	if (head->next != head) {
		List* list = head->next;
		head->next = list->next;
		list->next->pre = head;
		delete list;
	}
}

void deleteLast() {
	if (head->pre != head) {
		List* list = head->pre;
		head->pre = list->pre;
		list->pre->next = head;
		delete list;
	}
}

void initialize() {
	head = new List;
	head->pre = head;;
	head->next = head;
	head->key = 0;
}

int main() {
	initialize();
	int n;
	scanf("%d", &n);
	for (int i{ 0 }; i < n; i++) {
		char com[20];
		scanf("%s", com);
		if (strcmp(com,"delete")==0) {
			Key key;
			scanf("%d", &key);
			ldelete(key);
		}
		else if (strcmp(com,"insert")==0) {
			Key key;
			scanf("%d", &key);
			insert(key);
		}
		else if (strcmp(com,"deleteFirst")==0) {
			deleteFirst();
		}
		else {
			deleteLast();
		}
	}

	List* list = head->next;
	while (list != head) {
		if (list != head->next)cout << " ";
		cout << list->key;
		list = list->next;
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 34484
n,k,q = map(int, input().split())
 
scores = []
 
for i in range(n):
  scores.append(k-q)
 
for i in range(q):
  a = int(input()) #Ai
  scores[a-1] = scores[a-1]+1
  
for i in range(n):
  if(scores[i] > 0):
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 7848
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  vector<vl> table(51, vl(51));
  rep(i, 51) table[i][0] = 1;
  rep(i, 50) {
    rep(j, 50) {
      table[i+1][j+1] += table[i][j] + table[i][j+1];
    }
  }

  rep(i, 10) {
    rep(j, 10) {
      cerr << table[i][j] << " ";
    }
    cerr << endl;
  }
  int n, a, b;
  cin >> n >> a >> b;
  vector<ll> v(n);
  map<ll, int> cnt;
  rep(i, n) {
    cin >> v[i];
    cnt[v[i]]++;
  }

  for (auto&& i : cnt) {
    cerr << i.first << " " << i.second << endl;
  }
  sort(v.begin(), v.end(), greater<ll>());

  double ave = 0;
  rep(i, a) {
    ave += v[i];
  }
  ave /= a;

  ll ans = 0;
  ll border = v[a-1];
  if (v[0] == border) {
    for (int i = a; i <= b; i++) {
      ans += table[cnt[border]][i];
    }
  } else {
    int border_cnt = 0;
    rep(i, n) {
      if (v[i] == border) {
        border_cnt++;
        if (i+1 == a) {
          ans = table[cnt[border]][border_cnt];
          break;
        }
      }
    }
  }

  printf("%.8lf\n", ave);
  printf("%lld\n", ans);
}





Measured memory_bytes: 256
#include <bits/stdc++.h>  // include all standard C++ libraries

using namespace std;

// Loops
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define _rrep(i,n) rrepi(i,n,0)
#define rrepi(i,a,b) for(int i=int(a)-1;i>=int(b);--i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(xi, x) for (auto&& xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)


// typedef
template <class T> using vec = vector<T>;
using ll = long long;
using vi   = vec<int>;
using vvi  = vec<vi>;
using vvvi = vec<vvi>;
using pii  = pair<int, int>;


// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second


// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase( unique(all(v)), v.end() )
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<class T> pair<T, size_t> max(vector<T> &x){ auto it = max_element(all(x)); return mp(*it, it-x.begin()); }
template<class T> pair<T, size_t> min(vector<T> &x){ auto it = min_element(all(x)); return mp(*it, it-x.begin()); }

template<class T> inline bool chmax(T &maxval, const T &newval) { if (maxval<newval) { maxval=newval; return 1; } return 0; }
template<class T> inline bool chmin(T &minval, const T &newval) { if (minval>newval) { minval=newval; return 1; } return 0; }

// Utilities
// Grid world utilities
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define inside(H,W,y,x) 0<=(x) && (x)<(W) && 0<=(y) && (y)<(H)

inline int in() {int x; cin >> x; return x;} // read int from cin
inline  ll IN() {ll x; cin >> x; return x;}  // read ll from cin



// Debug
#ifdef LOCAL
  #include "dump.hpp"
  #define debug(x) cerr << #x << ": " << x << '\n'
#else
  #define dump(...)
  #define debug(x)
#endif

// Paste snippets here!!

// 

int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  int x, y; cin>>x>>y;
  rep(i,x+1){  // #turtle
    if(4*i+2*(x-i)==y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3640
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

int main() {
  //
  int a, b, c;
  cin >> a >> b >> c;
  if (b + c >= a) {
    cout << b + c - a << endl;
  } else {
    cout << 0 << endl;
  }
  return 0;
}


Measured memory_bytes: 888
#include<iostream>

using namespace std;

void solve(int n)
{
    int i=1;
    do
    {
        int x=i;
        if(x%3==0)
        {
            cout<<" "<<i;
            continue;
        }
        while(x)
        {
            if(x%10==3)
            {
                cout<<" "<<i;
                break;

            }
            x/=10;
        }
    }while(++i<=n);
    cout<<endl;
}

int main()
{
    int n;

    cin>>n;

    solve(n);

    return 0;
}



Measured memory_bytes: 3104
<?php
# get a integer
fscanf(STDIN, "%s", $s);
# get two integers separated with half-width break
fscanf(STDIN, "%d", $k);

$parts = [];
$n = strlen($s);

$part = '';
$new = true;
for ($i=0; $i < $n ; $i++) { 
	if($i==0){
		$part = $s[$i];
	}else{
		if($s[$i]==$s[$i-1]){
			$part .= $s[$i];
		}else{
			$parts[] = $part;	
			$part = $s[$i]; 
		}
	}
}
if($part !='')
	$parts[] = $part;

$ans = 0;

$p = count($parts);


if($p>1)
{
	if($s[0]!=$s[$n-1]){
		foreach ($parts as $i => $part) {
			$ans += $k*onePiece(strlen($part));
		}

	}else{
		foreach ($parts as $i => $part) {
			if($i!=0 && $i!=$p-1){
				$ans += $k*onePiece(strlen($part));
			}
		}
		$ss = $parts[$p-1].$parts[0];
		$ans += onePiece(strlen($ss),$k-1);

		$ans+=onePiece(strlen($parts[0]));
		$ans+=onePiece(strlen($parts[$p-1]));

	}
}else{
	$ans = onePiece(strlen($parts[0])*$k);
	//$ans += strlen($parts[0])==1?($k-1):($k*(intval((strlen($parts[0])+1)/2)));
}

function onePiece($n,$k=1){
	$ans =0 ;
	switch ($n) {
		case 0:
		case 1:
			$ans = 0;
		break;
		default:
			$ans = intval($n/2)*$k;
	}
	return  $ans;
}

# output
echo $ans;

Measured memory_bytes: 4604
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define pb push_back 
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	vector<int> df;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		df.pb(x);
	}
	double maxi = 0, cur = 0;
	for(int i = 0; i < k; i++)
		cur += 1.0 * (df[i] + 1) / 2;
	int low = 0, high = k - 1;
	while(high < n){
		maxi = max(maxi, cur);
		cur -= 1.0 * (df[low] + 1) / 2;
		if(high + 1 < n){
			cur += 1.0 * (df[high + 1] + 1) / 2;
			low++;
			high++;
		}
		else break;
	}
	printf("%.17lf\n", maxi);

}

Measured memory_bytes: 1400
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

int main()
{
    int n;
    while(cin >> n && n)
    {
        int mmin = 100 * 5, mmax = 0;
        int t, now;

        REP(n)
        {
            now = 0;
            rep(j,5) { cin >> t; now += t;}

            mmin = min(mmin, now);
            mmax = max(mmax, now);
        }
        cout << mmax << " " << mmin << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
from collections import deque
N = int(input())
stack = deque(["0"])
cnt = 0
while len(stack)>0:
    c = stack.pop()
    for s in "357":
        cs = c + s
        # print(cs)
        if int(cs)<=N:
            stack.append(cs)
            if cs.count("3")*cs.count("5")*cs.count("7")>0:
                cnt += 1
print(cnt)

Measured memory_bytes: 3316
#include <iostream>
using namespace std;
typedef long long LL;
const int N=200000+10;
int n,a[N],b[N];
int main() {
    scanf("%d",&n);
    int mn=1e9+7;
    LL s=0,tmp=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if(a[i]==b[i]){
            tmp+=a[i];
            continue;
        }
        if(a[i]>b[i])mn=min(mn,b[i]);
        s+=a[i]+b[i];
    }
    if(mn==1e9+7) return !printf("0\n");
    cout<<(s-2*mn)/2+tmp<<endl;
}



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

using namespace std;

using ll = long long;

int main(void){
    ll n;
    ll ans = 0;

    cin >> n;

    for(ll i=1; i<=n; i++)
        if(i%3 != 0 && i%5 != 0)
            ans += i;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3636
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;

struct Frac {
  int64 p, q;
};

Frac operator -(const Frac& a, const Frac& b) {
  int64 p = a.p * b.q - a.q * b.p;
  int64 q = a.q * b.q;
  int64 d = abs(__gcd(p, q));
  p /= d; q /= d;
  return Frac{p, q};
}

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= 3500; ++i) {
    for (int j = 1; j <= 3500; ++j) {
      auto cur = Frac{4, n} - Frac{1, i} - Frac{1, j};
      if (cur.p == 1) {
        cout << i << " " << j << " " << cur.q << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    
    x3 = x2 - y2 + y1;
    y3 = y2 + x2 - x1;
    x4 = x1 - y2 + y1;
    y4 = y1 + x2 - x1;
    
    printf("%d %d %d %d\n",x3,y3,x4,y4);
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int main()
{
  int a, b, c;
  int t[60]; memset(t, 0, sizeof(t));
  cin >> a >> b >> c;
  int n = 0;
  while(1){
    //    cout << n%60 << " " << (n%60) + a << endl;
    if(((n%60) <= c && c <= ((n%60)+a) || (n%60)+a > 60 && 0 <= c && c <= ((n+a)%60))){
      cout << n  + (c-(n%60)) << endl;
      break;
    }
    n += a;
    if(t[n%60]){
      cout << -1 << endl;
      break;
    }
    t[n%60] = 1;
    n += b;
  }
  return 0;
}

Measured memory_bytes: 1164
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = tuple(map(int,input().split()))
    mod = 998244353

    v = max(a)
    inv = [0]*(v+1)
    inv[1] = 1
    for i in range(2,v+1):
        inv[i] = mod - (mod//i)*inv[mod%i]%mod
    #w
    w = [1]*(v+1)
    for i in range(2,v+1):
        w[i] = (inv[i]-w[i])%mod
        for j in range(i*2,v+1,i):
            w[j] = (w[j] + w[i])%mod


    #res
    res = 0
    num = [0]*(v+1)
    for e in a:
        num[e] += 1


    for d in range(1,v+1):
        s = 0
        t = 0
        for j in range(d,v+1,d):
            s += num[j]*(j//d)
            t += (num[j]*(j//d)*(j//d))
        AA = ((((s**2-t)//2)%mod*d)%mod)*d%mod
        res = (res + w[d]*AA%mod)%mod

    print(res%mod)

if __name__ == '__main__':
    main()

Measured memory_bytes: 101196
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> b;
    rep(i,n)cin>>a[i];
    if((n-1)%2){
        for(int i=n-1;i>0;i--){
            if(i%2)cout<<a[i]<<" ";
            else b.push_back(a[i]);
        }
        cout<<a[0]<<" ";
        rep(j,b.size())cout<<b[b.size()-1-j]<<" ";
    }
    else {
        for(int i=n-1;i>0;i--){
            if(!(i%2))cout<<a[i]<<" ";
            else b.push_back(a[i]);
        }
        cout<<a[0]<<" ";
        rep(j,b.size())cout<<b[b.size()-1-j]<<" ";
    }
    return 0;
}




Measured memory_bytes: 3448
#include <iostream>
#include <stdexcept>
#include <cassert>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;


void dfs(
    int i, int N, int K,
    vector<long long>& minS, vector<int>& railsX, vector<int>& railsY,
    vector<int>& X, vector<int>& Y, vector<int>& P
) {
  if (i == N) {
    // update minS
    long long S = 0;
    for (int i = 0; i < N; i++) {
      int distance = 1000000;
      for (int x : railsX) distance = min(distance, abs(x - X[i]));
      for (int y : railsY) distance = min(distance, abs(y - Y[i]));
      S += (long long) distance * P[i];
    }
    minS[K] = min(S, minS[K]);
    return;
  }

  dfs(i+1, N, K, minS, railsX, railsY, X, Y, P);
  railsX.push_back(X[i]);
  dfs(i+1, N, K+1, minS, railsX, railsY, X, Y, P);
  railsX.pop_back();
  railsY.push_back(Y[i]);
  dfs(i+1, N, K+1, minS, railsX, railsY, X, Y, P);
  railsY.pop_back();
}


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

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

  vector<long long> minS(N+1, 100000000002);
  vector<int> railsX = {0}, railsY = {0};
  dfs(0, N, 0, minS, railsX, railsY, X, Y, P);
  for (int i = 0; i <= N; i++) cout << minS[i] << endl;
  return 0;
}


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

using namespace std;

int f(int n){
	if(n % 2 == 0){
		return n / 2;
	}else{
		return 3 * n + 1;
	}
}

int main(){
	int s;
	int a[1000000];
	cin >> s;
	a[0] = s;
	for(int i = 1;; i++){
		a[i] = f(a[i - 1]);
		for(int j = 0; j < i; j++){
			if(a[j] == a[i]){
				cout << i + 1;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//2文字以上の怪文が含まれない
//偶数文字の時、中心に2文字の回文あり
//奇数文字の回文には中心に3文字の回文あり
//同じ文字を２文字以上離れて置ければ良い
//3文字周期の文字列
//各文字の出現回数の差が1以下
int main() {
    string S;
    cin >> S;
    int ca = 0;
    int cb = 0;
    int cc = 0;
    for(int i = 0;i<S.size();i++){
        if(S[i] == 'a') ca++;
        else if(S[i] == 'b') cb++;
        else if(S[i] == 'c') cc++;
    }
    if(abs(ca-cb) <= 1 && abs(cb-cc) <= 1 && abs(cc-ca) <= 1){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;

}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int ll;
const ll MOD = 1e9 + 7;

int main(){
	ll n, t, a, l, r = 0, ans = 1;
	vector<int> v;
	cin >> n >> t;
	for(int i = 0;i < n;++i){
		cin >> a;
		v.emplace_back(a);
	}
	sort(v.begin(), v.end());
	for(l = 0;l < n;++l){
		for(;r < n && v[r] <= v[l] + t;) r++;
		if(r >= n || v[r] > v[l] + t) --r;
		ans *= ((r - l + 1) % MOD);
		ans = ans % MOD;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3516
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int VMAX = 610;
const int EMAX = VMAX*(VMAX-1)/2;
int V,E;
vector<vector<int> > G(VMAX);
vector<PII> path(EMAX);

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V >> E;
  rep(i,E){
    cin >> path[i].first >> path[i].second;
    G[path[i].first].push_back(path[i].second);
  }
  //地点xからゴールまでの通路数の期待値
  //0はそこまでで塞ぐ作業を行わなかった時の最小の期待値
  //1はそこまでで塞ぐ作業を行った時の最小の期待値
  //到達できない時INF
  const int INF = 1e5;

  double Exp[V+1];

  double ans = INF;
  repp(w,1,V){
    rep(i,V+1) Exp[i] = INF;
    Exp[V] = 0;
    perr(v,1,V){
      double sum = 0.0;
      double sz = G[v].size();
      double ma = 0;
      for(const int& u : G[v]){
        sum += Exp[u];
        ma = max(ma,Exp[u]);
      }
      if(v==w&&G[v].size()!=1){
        sz-=1.0;
        sum -= ma;
      }
      sum += sz;
      Exp[v] = sum/sz;
    }
    ans = min(ans,Exp[1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2944
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B
// BFS algorithm
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(int argc, char **argv)
{
        int V, E;
        cin >> V >> E;
        vector<vector<int>> A(V);
        vector<int> B(V);
        for (int i = 0; i < E; i++) {
                int s, t;
                cin >> s >> t;
                A[s].push_back(t);
                B[t]++;
        }
        vector<bool> U(V);
        vector<int> L;
        queue<int> S;
        for (int i = 0; i < V; i++) {
                if (B[i] || U[i])
                        continue;
                S.push(i);
                U[i] = true;
                while (!S.empty()) {
                        auto c = S.front();
                        S.pop();
                        L.push_back(c);
                        for (auto a: A[c]) {
                                if (--B[a] == 0 && !U[a]) {
                                        S.push(a);
                                        U[a] = true;
                                }
                        }
                }
        }
        for (auto l: L)
                cout << l << endl;
        return 0;
}

Measured memory_bytes: 3728
#include <cstdio>
#include <cstring>

int main(){
  char s[300], p[300], t[300];

  scanf("%s", s);
  scanf("%s", p);

  strcpy(t, s);
  strcat(s, t);
  if (strstr(s, p)) {
    printf("Yes\n");
  }
  else {
    printf("No\n");
  }

  return 0;
}



Measured memory_bytes: 2756
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String s1 = s.substring(0, 2);
    String s2 = s.substring(2);
    int t1 = Integer.parseInt(s1);
    int t2 = Integer.parseInt(s2);
    int p1 = 0;
    int p2 = 0;
    if((t2 > 0) && (t2 <= 12)) p1++;
    if((t1 > 0) && (t1 <= 12)) p2++;
    String ans = "NA";
    if(p1 == 1) {
      if(p2 == 1) {
        ans = "AMBIGUOUS";
      } else {
        ans = "YYMM";
      }
    } else {
      if(p2 == 1) ans = "MMYY";
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <stdio.h>

int main(void) {
    char ch;

    while(1) {
      scanf("%c", &ch);
      if('a' <= ch && ch <= 'z') {
        printf("%c", ch-32);
      }
      else if('A' <= ch && ch <= 'Z') {
        printf("%c", ch+32);
      }
      else if(ch == ' ') {
        printf(" ");
      }
      else printf("%c", ch);

      if(ch == '\n') break;
    }

    return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int x, y, ans = 0;
    cin >> x >> y;
    if (x == 3) ans += 100000;
    if (x == 2) ans += 200000;
    if (x == 1) ans += 300000;
    if (y == 3) ans += 100000;
    if (y == 2) ans += 200000;
    if (y == 1) ans += 300000;
    if (x == 1 && y == 1) ans += 400000;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <regex>
#include <chrono>
#include <sstream>
#include <iomanip>

//#include <
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()

typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
//#define int long long


inline void solve(){
    int n;
    cin >> n;
    vector<int> c;
    c.bash(1);
    int t = 6;
    while(t<=n){
        c.bash(t);
        t *= 6;
    }
    t = 9;
    while(t<=n){
        c.bash(t);
        t*=9;
    }
    sort(ALL(c));
    auto x = unique(ALL(c));
    c.erase(x,c.end());
    vector<int > dp(n+5,INF);
    dp[0] = 0;
    for(int i = 0; i < c.size(); i++) {
        for(int j = 1; j <= n; j++) {
            if(j >= c[i]){
                chmin(dp[j],dp[j-c[i]]+1);
            }
        }
    }
    cout <<  dp[n] << endl;
}

struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;signed main(){solve();return 0;}



Measured memory_bytes: 640
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    bin_k = bin(k)[2:]

    len_bin_k = len(bin_k)

    doubling = [[0] * n for i in range(len_bin_k)]

    for i in range(len_bin_k):
        for j in range(n):
            if i == 0:
                doubling[i][j] = num_list[j]
                continue
            doubling[i][j] = doubling[i-1][doubling[i-1][j]-1]

    current_town = 1
    for i, s in enumerate(bin_k):
        if s == '0':
            continue
        current_town = doubling[len_bin_k-i-1][current_town-1]

    print(current_town)

if __name__ == '__main__':
    main()


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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    rrep (i, s.size() - 1) {
        string tmp = s.substr(0, i);
        int len = tmp.size();
        int l = (len + 1) / 2;
        string t = tmp.substr(0, l);
        string u = tmp.substr(l);
        if (t == u) {
            cout << tmp.size() << endl;
            return 0;
        }
    }
    
    return 0;
}



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

#define is_uruu leapyear
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(a);i>(b);--i)
#define REP(i,a) for(int i=0;i<(a);++i)

int partition(int A[], int p, int r){
	int x = A[r];
	int i = p;
	FOR(j, p, r){
		if(A[j] <= x){
			swap(A[j], A[i]);
			i++;
		}
	}
	swap(A[i], A[r]);
	return i;
}
	
int main(){
	
	int i, n, A[100005];
	cin >> n;
	FOR(j, 0, n){
		cin >> A[j];
	}
	
	i = partition(A, 0, n-1);
	
	FOR(j, 0, i) cout << A[j] << " ";
	cout << "[" << A[i] << "] " ;
	FOR(j, i+1, n-1) cout << A[j] << " ";
	cout << A[n-1] << endl;
	
	return 0;
}


Measured memory_bytes: 3440
let print_list l =
  List.map string_of_int l |> String.concat " " |> print_endline;;

let insertion_sort a n g count=
  let ct = (ref count) in
  for i = g to n-1 do
    let v = a.(i) in
    let rec loop j =
      if j < 0 || a.(j) <= v then (j+g)
      else
        begin
          a.(j+g) <- a.(j);incr ct;loop (j-g)
        end
    in a.(loop (i-g)) <-v;
  done;
  !ct
;;

let () =
  let n = read_int () in
  let n' = float_of_int n in
  let rec gen g b =
    let b2 = b *. 2.25 +. 1. in
    if b2 > n' then g
    else gen ((int_of_float (ceil b2))::g) b2
  in
  let a = Array.init n (fun x -> read_int ()) and
      g = gen [] 0. in
  let m = List.length g in
  let rec loop ct = function
      [] -> print_int m;print_newline ();
            print_list g;
            print_int ct;print_newline ();
            Array.iter (fun x -> print_int x;print_newline ()) a
    | h::t -> loop (insertion_sort a n h ct) t
  in loop 0 g
;;

Measured memory_bytes: 12324
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
    char ch;
    char ring[200],search[100],change[100];
    scanf("%s %s",ring , search);
    strcpy(change, ring);
    strcat(ring, change);
    //printf("%s",ring);
    if ( strstr(ring, search) == NULL ) printf("No\n");
    else printf("Yes\n");
    return 0;
}
    


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

using namespace std;

int main() {
    int N, X;
    cin >> N >> X;

    vector<int> vt(N);
    for (int i = 0; i < N; ++i) {
        long long t;
        cin >> t;
        t -= X;
        vt[i] = abs(t);
    }

    sort(vt.begin(), vt.end());
    int ans = vt[0];
    for (int i = 0; i < N; ++i) {
        ans = __gcd(ans, vt[i]);
    }

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


Measured memory_bytes: 640
import itertools
import copy

h,w,k=map(int,input().split(' '))
data=[input() for _ in range(h)]


def count_s(s):
    cnt = 0
    for ss in s:
        cnt += ss.count('.')
    return h*w-cnt

out=0
xx=h+w
if count_s(data) == k:
    out = 1

for kk in range(1,xx+1):
    lst = list(itertools.combinations([x for x in range(xx)], kk))
    for ll in lst:
        dd = copy.deepcopy(data)
        for l in ll:
            if l >= h:
                for i in range(h):
                    buf = dd[i]
                    dd[i]=buf[:l-h]+'.'+buf[l-h+1:]
            else:
                dd[l]='.'*w
        if count_s(dd) == k:
            out += 1

print(out)

Measured memory_bytes: 9352
def exit_No():
  print("No")
  exit()

def isNotNum(s):
  return not (ord('0') <= ord(s) <= ord('9'))

# Input
A, B = map(int, input().split())
S = input()

# Main
for i in range(A):
  if isNotNum(S[i]):
    exit_No()
    
if S[A] != '-':
  exit_No()

for i in range(B):
  if isNotNum(S[A+1+i]):
    exit_No()
    
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ;i++)

using namespace std;
using p=pair<int,int>;
typedef long long ll;
const double pi=3.14159265;

int main() {
  int r;
  cin >> r ;
  double ans=2*r*pi;
  cout << ans << endl;

}

Measured memory_bytes: 3684
function Main(input) {
    input = input.split("\n");
    input[0] = Number(input[0]);
    input[1] = Number(input[1]);
    input[2] = Number(input[2]);
    console.log((input[0] + input[1]) * input[2] / 2);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dbl;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<long long> vl;
typedef vector< pair<int, int> > vii;
#define mp make_pair
#define pb push_back
#define invec(a, n) for(ll i = 0; i < n; i++) {cin >> a[i];}
#define rep(n) for(ll i = 0; i < n; i++)
#define fr(i,j,k) for(ll i = j; i < k; i++)
#define FR(i,j,k) for(ll i = j; i >= 0; i--)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define INF 1000000
#define xx first
#define yy second
#define pl cout<<endl;
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
		return os<<"("<< p.first << "," << p.second<<")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
os << "{";
typename vector< T > :: const_iterator it;
for( it = v.begin(); it != v.end(); it++ ) {
		if( it != v.begin() ) os << ", ";
		os << *it;
}
return os << "}";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
os << "[";
typename set< T > :: const_iterator it;
for ( it = v.begin(); it != v.end(); it++ ) {
		if( it != v.begin() ) os << ", ";
os << *it;
}
return os << "]";
}
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
		os << "[";
		typename map< F , S >::const_iterator it;
for( it = v.begin(); it != v.end(); it++ ) {
if( it != v.begin() ) os << ", ";
os << it -> first << " = " << it -> second ;
}
return os << "]";
}
#define deb(x) cout << #x << " = " << x << endl;
 
#define er(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}
 
void fast()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}

void Longestdecrseq(ll segment[],ll length[],ll n)
{
	
	ll maxStart = 0;
    ll maxEnd = 0;

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

        if(segment[i] <= segment[i-1]){

            length[i] = length[i-1]+1;

            if(length[i] > length[maxEnd]){

                maxEnd = i;
                maxStart = maxEnd - length[maxEnd];

            }

        }else{

            length[i] = 0;

        }

    }

    string buff="";

    for(int i = maxStart; i <= maxEnd; i++){
        buff+=segment[i];
    }

	cout<<buff.size()-1<<endl;
}

 
int main()
{															
	ll n;
	cin>>n;
	ll h[n];

	
	for(ll i=0;i<n;i++)
	{
		cin>>h[i]; 
	}

	ll a[n];

	
	for(ll i=0;i<n;i++)
	{
		a[i]=0; 
	}


	Longestdecrseq(h,a,n);

}

Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

using ll = long long int;
using pll = pair<ll, ll>;

int main()
{
    ll N, K;
    cin >> N >> K;

    vector<ll> cs(N, 0);

    rep (i, K)
    {
        ll d;
        cin >> d;

        rep (j, d)
        {
            ll a;
            cin >> a;

            --a;

            ++cs[a];
        }
    }

    ll ans = 0;

    rep (i, N)
    {
        if (cs[i] == 0) { ++ans; }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
N = input()


def check(n, ln):
    if ln == 0:
        if int(N) >= int(n) and set(list(n)) == {'3', '5', '7'}:
            return [n]
        else:
            return []
    nums = []
    for i in ['3', '5', '7']:
        nums.extend(check(n + i, ln - 1))
    return nums


def main():
    cnt = 0
    for l in range(3, len(N) + 1):
        cnt += len(check('', l))
    print(cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4464
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();

		int[] b = new int[n];
		for (int i = 0; i < n; i++)
			b[i] = sc.nextInt();

		int[] c = new int[n];
		for (int i = 0; i < n - 1; i++)
			c[i] = sc.nextInt();

		sc.close();
		int s = 0;

		for (int i = 0; i < n; i++)
			s = s + b[a[i] - 1];

		for (int i = 1; i < n; i++) {
			if (a[i] - a[i - 1] == 1)
				s = s + c[a[i - 1] - 1];
		}

		System.out.println(s);

	}
}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;cin >> N;
  int minimum = MAX_I;
  int x;
  rep(i,N){
    cin >> x;
    int count = 0;
    while((x&1)==0&&x!=0){
      ++count;
      x>>=1;
    }
    minimum = min(minimum,count);
  }
  cout << minimum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
bool isp[1<<20];
int cnt[1<<20];
main()
{
	for(int i=2;i<=1e6;i++)isp[i]=true;
	for(int i=2;i<=1e6;i++)
	{
		if(isp[i])
		{
			for(int j=i+i;j<=1e6;j+=i)isp[j]=false;
		}
	}
	for(int i=1;i<1<<20;i++)cnt[i]=cnt[i-1]+isp[i];
	int N;
	while(cin>>N,N)
	{
		int sum=0;
		for(;N--;)
		{
			int p,m;cin>>p>>m;
			int L=p-m-1,R=p+m;
			if(L<0)L=0;
			if(R>=1<<20)R=(1<<20)-1;
			int X=cnt[R]-cnt[L];
			sum+=X-1;
		}
		cout<<sum<<endl;
	}
}


Measured memory_bytes: 8152
#include<stdio.h>
void trace(int A[],int N)
{
  int i;
  for(i = 0; i<N;i++){
    if(i>0)
      printf(" ");
  printf("%d",A[i]);
}
printf("\n");
}

void insertionSort(int A[],int N)
{
  int j,i,v;
  for(i=1;i<N;i++){
    v = A[i];
    j = i-1;
    while(j>=0 && A[j]>v){
      A[j+1] = A[j];
      j--;
    }
    A[j + 1] = v;
    trace(A,N);
  }
}
    
int main(){
  int i,j,N;
  int A[100];
  scanf("%d",&N);
  for(i = 0;i<N;i++)
    scanf("%d",&A[i]);
  trace(A,N);
  insertionSort(A,N);

    return 0;
}



Measured memory_bytes: 2064
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())


int main(){
  string s;
  ll q;
  cin>>s>>q;
  ll a=0;
  REP(i,q){
    int t;
    cin>>t;
    if(t==1){
      a++;
    }
    else{
      int f;char c;
      cin>>f>>c;
      if((f==1&&a%2==0)||(f==2&&a%2==1)){
        s.insert(s.begin(),c);
      }
      else{
        s.push_back(c);
      }
    }
  }
  if(a%2==1){
    reverse(s.begin(),s.end());
  }
  cout<<s<<endl;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n;
  cin >> n;
  int v[100005] = {};
  rep(i, 0, n) cin >> v[i];
  map<int, int> mp1, mp2;
  rep(i, 0, n) {
    if(i % 2) {
      mp1[v[i]]++;
    }else {
      mp2[v[i]]++;
    }
  }
  int mx1 = 0, mx12 = 0, mx2 = 0, mx22 = 0;
  int id1, id2;
  rep(i, 0, 100001) {
    if(mx1 <= mp1[i]) {
      mx12 = mx1;
      mx1 = mp1[i];
      id1 = i;
    }else {
      mx12 = max(mx12, mp1[i]);
    }
    if(mx2 <= mp2[i]) {
      mx22 = mx2;
      mx2 = mp2[i];
      id2 = i;
    }else {
      mx22 = max(mx22, mp2[i]);
    }
  }
  if(id1 == id2) {
    cout << n - max(mx1 + mx22, mx2 + mx12) << endl;
  }else {
    cout << n - mx1 - mx2 << endl;
  }
}


Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int N;
    cin >> N;
    vector<queue<int>> A(N);
    REP(i, N) {
        REP(j, N - 1) {
            int a;
            cin >> a;
            A[i].emplace(--a);
        }
    }
    int res = -1;
    vector<int> cnt(N);
    while (true) {
        bool end = true;
        bool impossible = true;
        REP(i, N) {
            if (A[i].empty()) continue;
            end = false;
            int j = A[i].front();
            if (A[j].front() == i) {
                A[i].pop();
                A[j].pop();
                cnt[i] = cnt[j] = max(cnt[i], cnt[j]) + 1;
                impossible = false;
            }
        }
        if (end) {
            REP(i, N) res = max(res, cnt[i]);
            break;
        }
        if (impossible) break;
    }
    cout << res << endl;

    return 0;
}

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

int main() {
    int n, m, ac = 0, wa = 0;
    cin >> n >> m;
    int p;
    string s;
    map<int, int> mp;
    for(int i = 0; i < m; ++i) {
        cin >> p >> s;
        if(s == "WA") {
            if(mp[p] != -1) {
                mp[p]++;
            }
        } else {
            if(mp[p] != -1) {
                ac++;
                wa += mp[p];
                mp[p] = -1;
            } 
        }
    }

    cout << ac << " " << wa << '\n';
}


Measured memory_bytes: 4992
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (ll i = begin; i < n; i++)
#define repe(i, begin, n) for (ll i = begin; i <= n; i++)
#define repr(i, begin, n) for (ll i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (ll i = begin; i >= end; i--)

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 ll inf = 1000000007;
// const ll MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
const ll MOD = 998244353;
ll dp[3030][3030];
ll N;
ll S;
ll A[3030];

int main() {
  cin >> N >> S;
  repe(i, 1, N) { cin >> A[i]; }

  dp[0][0] = 1;
  repe(i, 1, N) {
    ll a = A[i];
    repe(j, 0, S) {
      if (j < a) {
        dp[i][j] = dp[i - 1][j] * 2;
        dp[i][j] %= MOD;
      } else {
        dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a];
        dp[i][j] %= MOD;
      }
    }
  }
  cout << dp[N][S] << endl;
}


Measured memory_bytes: 74680
from bisect import bisect_right as br
n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for x in range(n):
	for y in range(x+1,n):
		i=l[x]
		j=l[y]
		cnt+=br(l,i+j-1)-1-y
print(cnt)

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define ld long double
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
#define dbg2(a,b) cerr << #a << " = " << a << " " << #b << " = " << b << '\n';              

typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

int main(){

	IOS
	int n,i,j;
	cin >> n;
	vi a(n);
	int sum = 0;
	forn(0,n,i){
		cin >> a[i];
		sum += a[i];
	}
	int ans = INT_MAX;

	int s = 0;

	forn(0,n - 1,i){
		s += a[i];
		ans = min(ans,abs(sum - 2*s));
	}

	cout << ans << '\n';
}

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

// int/long:            -2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define MOD 1000000007

#define Rep0(i, n)      for (auto i=0; i<n; i++)
#define Rep1(i, n)      for (auto i=1; i<=n; i++)
#define Sort(P) sort(P.begin(), P.end())
#define Rev(P)  reverse(P.begin(), P.end())

int     main() {
        int N;
        cin >>N;
        vector<ll> A(N, 0);
        Rep0(i, N)
                cin >>A.at(i);
        Sort(A);
        Rev(A);
        int IX=1;
        ll S=0;
        Rep0(i, N-1) {
                S+=A.at(IX/2);
                IX++;
        }
        cout <<S <<endl;
        return 0;
}

Measured memory_bytes: 4836