akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 1000000007
int ara_t[100002][3], dp[100002][3];
int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d%d%d", &ara_t[i][0], &ara_t[i][1], &ara_t[i][2]);
    for(int i = 0; i < 100002; i++){dp[i][0] = 0, dp[i][1] = 0, dp[i][2] = 0;}
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = max(max(dp[i][0], dp[i-1][1]+ara_t[i][0]), dp[i-1][2]+ara_t[i][0]);
        dp[i][1] = max(max(dp[i][1], dp[i-1][0]+ara_t[i][1]), dp[i-1][2]+ara_t[i][1]);
        dp[i][2] = max(max(dp[i][2], dp[i-1][1]+ara_t[i][2]), dp[i-1][0]+ara_t[i][2]);
    }
    printf("%d", max(max(dp[n][0], dp[n][1]), dp[n][2]));
    //printf("\nTime: %lf", ((double)(clock() - z) / CLOCKS_PER_SEC)*1e-6);
    return 0;
}


Measured memory_bytes: 2560
///   ***   ---   |||		 In the name of ALLAH		|||   ---   ***   ///



#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(0); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {			cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

ll gcd ( ll a, ll b ) { return __gcd ( a, b ); }
ll lcm ( ll a, ll b ) { return a * ( b / gcd ( a, b ) ); }


int dx[] = { 0, 0, +1, -1, -1  +1, -1, +1 };
int dy[] = { +1, -1, 0, 0, -1, +1, +1, -1 };

int stoi ( char c ) {return c-'0';}

int main()
{
	optimize();

	ll a;
	cin >> a;

	string s;
	cin >> s;

	ll b = stoi ( s[0] ) * 10;
	b += stoi ( s[2] );
	b *= 10;
	b += ( stoi ( s[3] ) );

	a *= b;
	a /= 100;
	cout << a << endl;


	return 0;
}

















Measured memory_bytes: 3656
S = input()
while len(S) > 0:
    if S[-5:] == 'dream' or S[-5:] == 'erase':
        S = S[:-5]
    elif S[-7:] == 'dreamer':
        S = S[:-7]
    elif S[-6:] == 'eraser':
        S = S[:-6]
    else:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)
using namespace std;
using Weight = int;
using Array = vector<int>;
using Matrix = vector<Array>;
constexpr int INF = 1000000000;


pair<Weight, Array> hungarian(const Matrix &m) {
  int n = m.size();
  int p, q;
  Array fx(n, INF), fy(n, 0);
  vector<int> x(n, -1), y(n, -1);
  REP(i,n)REP(j,n) fx[i] = max(fx[i], m[i][j]);
  for (int i = 0; i < n; ) {
    vector<int> t(n, -1), s(n+1, i);
    for (p = q = 0; p <= q && x[i] < 0; ++p)
      for (int k = s[p], j = 0; j < n && x[i] < 0; ++j)
        if (fx[k] + fy[j] == m[k][j] && t[j] < 0) {
          s[++q] = y[j], t[j] = k;
          if (s[q] < 0)
            for (p = j; p >= 0; j = p)
              y[j] = k = t[j], p = x[k], x[k] = j;
        }
    if (x[i] < 0) {
      Weight d = INF;
      for (int k = 0; k <= q; ++k)
        for (int j = 0; j < n; ++j)
          if (t[j] < 0) d = min(d, fx[s[k]] + fy[j] - m[s[k]][j]);
      for (int j = 0; j < n; ++j) fy[j] += (t[j] < 0 ? 0 : d);
      for (int k = 0; k <= q; ++k) fx[s[k]] -= d;
    } else ++i;
  }
  Weight ret = 0;
  for (int i = 0; i < n; ++i) ret += m[i][x[i]];
  return make_pair(ret, x);
}

int main() {
  int n;
  cin>>n;
  Matrix w(n, Array(n));
  REP(i,n)REP(j,n) cin >> w[i][j];
  Matrix e(n, Array(n));
  REP(i,n)REP(j,n) cin >> e[i][j];
  vector<string> m(n);
  Matrix mat(n, Array(n));
  int cost = 0;
  REP(i,n) {
    cin>>m[i];
    REP(j,n) {
      if (m[i][j] == 'o') {
        mat[i][j] = 1000 + e[i][j];
        cost += e[i][j];
      } else {
        mat[i][j] = 1000 - w[i][j];
      }
    }
  }
  auto res = hungarian(mat);
  cout << (n*1000 - res.first + cost) << endl;
  int cnt = 0;
  stringstream ss;
  REP(i,n)REP(j,n) {
    if (m[i][j] == 'o') {
      if (res.second[i] != j) {
        ss << (i+1) << ' ' << (j+1) << " erase" << endl;
        ++cnt;
      }
    } else {
      if (res.second[i] == j) {
        ss << (i+1) << ' ' << (j+1) << " write" << endl;
        ++cnt;
      }
    }
  }
  cout << cnt << endl;
  cout << ss.str() << flush;
  return 0;
}

Measured memory_bytes: 3276
N,M = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
cd = [tuple(map(int,input().split())) for _ in range(M)]

for a,b in ab:
    tmp = []
    for c,d in cd:
        tmp.append(abs(a-c)+abs(b-d))
    
    print(tmp.index(min(tmp))+1)

Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<utility>

using namespace std;
typedef long long ll;
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 long long INF = 1LL << 60;
//以下変更可能領域

vector<int> G[300000];
typedef pair<int, int> P;
int E, V;
int d[300000];

void solve(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    for (int i = 0; i < V; i++) {
        d[i] = 1000000;
    }
    d[s] = 0;
    que.push(P(0,s));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i = 0; i < G[v].size(); i++) {
            int e = G[v][i];
            if (d[e] > d[v] + 1) {
                d[e] = d[v] + 1;
                que.push(P(d[e],e));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u,v;
        cin >> u >> v;
        G[u-1].push_back(v-1+N);
        G[u-1+N].push_back(v-1+2*N);
        G[u-1+2*N].push_back(v-1);
    }
    V = 3 * N; E = M;
    int s,t;
    cin >> s >> t; s--; t--;
    solve(s);
    if (d[t] == 1000000) {
        cout << -1 << "\n";
    } else {
        cout << d[t]/3 << "\n";
    }
}

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

using namespace std;

typedef struct task {
    int a;
    int b;
} task;

bool operator<(const task& task_i, const task& task_j) {
    return task_i.b < task_j.b;
}

int main(void) {
    int n;
    vector<task> tasks;
    int sum = 0;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        int b;
        cin >> a >> b;
        tasks.push_back({a, b});
    }

    sort(tasks.begin(), tasks.end());

    for (task t: tasks) {
        sum += t.a;
        if (sum > t.b) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int n,x;cin>>n;
  	vector<int> arr(n,0);
  	for(int i=0;i<n;i++) {
    	cin>>arr[i];
    }
  	for(int i=0;i<n;i++) {
    	cin>>x;
      	arr[i] -= x;
    }
  	sort(arr.begin(),arr.end(),greater<int>());
  	int sum = 0;
  	for(int i=0;i<n;i++) {
     	if(arr[i]>0) sum += arr[i];
      	else break;
    }
  	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    p=LIST()
    ct=0
    for i in range(1,n-1):
        if (p[i-1]<=p[i]<=p[i+1]) or (p[i-1]>=p[i]>=p[i+1]):
            ct+=1
    print(ct)
if __name__ == '__main__':
    do()

Measured memory_bytes: 3064
import sys
from bisect import bisect_right
n, k, *a = map(int, sys.stdin.read().split())

mod = 1000000007
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i] > a[j]:
            ans += 1
ans = k * ans % mod
a.sort()
cnt = 0
for ai in a:
    cnt += n - bisect_right(a, ai)
ans += (k * (k - 1) // 2) % mod * cnt
print(ans % mod)


Measured memory_bytes: 42332
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()
}

fn main() {
    let s: String = read();
    let n: Vec<char> = s.chars().collect();
    
    if n[2] == n[3] && n[4] == n[5] {
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
N = int(input())

a_list = list(map(int,input().split()))
a_n_list = []
for i in range(N):
    a_n_list.append([a_list[i],i+1])
a_n_list.sort()
ans = ""
for i in range(N):
    print(a_n_list[i][1], end=" ")

Measured memory_bytes: 21440
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n - 1):
    if d[i - 1][0] == d[i - 1][1] and d[i][0] == d[i][1] and d[i + 1][0] == d[i + 1][1]:
        print('Yes')
        exit()
print('No')

Measured memory_bytes: 9188
N = int(input())

dp = [N] * (N + 1)
dp[0] = 0

for i in range(1, N+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[N], dp[i-power] + 1)
        power *= 6

    power = 9
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9

print(dp[-1])


Measured memory_bytes: 9500
import itertools
 
H,W,K=map(int, input().split())
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)


Measured memory_bytes: 3188
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(D)]

ans_cnt = 10 ** 20
for i in range(2 ** (D)):
    def make_p(i):
        p = bin(i)[2::]
        while len(p) != D:
            p = "0" + p
        key = D
        for j in range(D - 1, -1, -1):
            if int(p[j]) == 0:
                key = j
                break
        return p, key
    
    p_and_key = make_p(i)
    p = p_and_key[0]
    key = p_and_key[1]
    cnt = 0
    ansP = 0
    for j in range(len(p)):
        if p[j] == "1":
            ansP += pc[j][0] * 100 * (j + 1) + pc[j][1]
            cnt += pc[j][0]
    j = 0
    if int(key) != int(D):
        key = int(key)
        while ansP < G:
            j = int(j)
            if pc[key][0] <= j:
                break
            ansP += 100 * (key + 1)
            cnt += 1
            j += 1
    if ansP >= G:
        ans_cnt = min(ans_cnt, cnt)

print(ans_cnt)


Measured memory_bytes: 3064
#[macro_use]
mod utils {
    macro_rules! input {
        ($($r:tt)*) => {
            let stdin = std::io::stdin();
            let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
            let mut next = move || -> String{
                bytes
                    .by_ref()
                    .map(|r|r.unwrap() as char)
                    .skip_while(|c|c.is_whitespace())
                    .take_while(|c|!c.is_whitespace())
                    .collect()
            };
            input_inner!{next, $($r)*}
        };
    }
    macro_rules! input_inner {
        ($next:expr) => {};
        ($iter:expr, ) => {};
 
        ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
        ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
    }
    macro_rules! read_value {
        ($next:expr, ( $($t:tt),* )) => {
            ( $(read_value!($next, $t)),* )
        };
        ($next:expr, [ $t:tt ; $len:expr ]) => {
            (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        };
        ($next:expr, chars) => {
            read_value!($next, String).chars().collect::<Vec<char>>()
        };
        ($next:expr, usize1) => {
            read_value!($next, usize) - 1
        };
        ($next:expr, $t:ty) => {
            $next().parse::<$t>().expect("Parse error")
        };
    }
}

fn main() {
    input! {
        x: u64,
        y: u64,
        z: u64
    }

    println!("{} {} {}", z, x, y);
    
}


Measured memory_bytes: 4352
def count(s):
    if not s:
        return 0
    c1 = sum(s)
    return sum(i for i,v in enumerate(s) if v) - c1*(c1-1)//2


S = list(input())
S.reverse()
score = 0

tmp = []
while S:
    a = S.pop()
    if a == 'A':
        tmp.append(0)
    elif a == 'B' and S and S[-1] == 'C':
        S.pop()
        tmp.append(1)
    else:
        score += count(tmp)
        tmp = []

score += count(tmp)
print(score)

Measured memory_bytes: 5540
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <ctime>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define Set(i, v) memset(i, v, sizeof i)

using namespace std;

typedef long long LL;

const int N = 100010;

LL X;
int n, m;
int rev[N], t[N], A[N], num[N];

int main(){
	scanf("%lld%d", &X, &n);
	For(i, 1, n) scanf("%d", &rev[i]);
	scanf("%d", &m);
	For(i, 1, m) scanf("%d%d", &t[i], &A[i]), num[i] = A[i];
	sort(num + 1, num + m + 1);
	LL ret = 0, Maxval = num[m], Minval = num[1], val = 0;
	int pr = m, pl = 1;
	int i = 1, j = 1, now = 0, sign = -1;
	rev[n + 1] = t[m + 1] = 2e9;
	while(j <= m){
		int nt = min(rev[i], t[j]) - now;
		val += sign * nt, ret += sign * nt;
		val = min(max(val, 0LL), LL(X));
		if(pl < pr){
			if(sign == -1){
				while(pl < pr && num[pl + 1] + ret <= 0) ++pl;
				if(pl >= pr) val = 0;
				Minval = max(0LL, Minval - nt), Maxval -= nt;
			}
			else{
				while(pl < pr && num[pr - 1] + ret >= X) --pr;
				if(pl >= pr) val = X;
				Maxval = min(LL(X), Maxval + nt), Minval += nt;
			}
		}
		now += nt;
		//printf("%d %d\n", pl, pr);
		if(now == rev[i]) sign = -sign, ++i;
		if(now == t[j]){
			if(pl >= pr) printf("%lld\n", val);
			else if(A[j] <= num[pl]) printf("%lld\n", Minval);
			else if(A[j] >= num[pr]) printf("%lld\n", Maxval);
			else printf("%lld\n", A[j] + ret);
			++j;
		}
	}
	return 0;
}

Measured memory_bytes: 2816
import numpy as np
a, b, x = map(int, input().split())
if a ** 2 * b / 2 >= x:
    print(np.rad2deg(np.arctan(a * b ** 2 / (2 * x))))
else:
    print(-np.rad2deg(np.arctan((2/a**3) * (x - (a ** 2) * b))))



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

int main() {
  int M,K,L;
  cin>>M>>K;
  L=exp2(M);
  if(M==1){
    if(K==0){
      cout<<"0 0 1 1"<<endl;
    }
    else{
      cout<<"-1"<<endl;
    }
  }
  else{
    if(K>=L){
      cout<<"-1"<<endl;
    }
    else{
      for(int i=0;i<L;i++){
        if(i!=K){
          cout<<i<<" ";
        }
      }
      cout<<K<<" ";
      for(int i=L-1;i>=0;i--){
        if(i!=K){
          cout<<i<<" ";
        }
      }
      cout<<K<<endl;
    }
  }
      
}


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

typedef long long ll ; 
typedef unsigned long long ull ; 
typedef vector<int> vi ; 
typedef vector<vi> vii ;
typedef vector<ll> vl ;
typedef vector<vl> vll ;
typedef set<int> si ; 
typedef map<int,int> mii ; 
typedef map<ll,ll>  mll ; 
typedef map<string,int> msi ;
typedef set<ll> sl ; 
typedef set<char> sc ; 
typedef pair<int,int> pii ;


#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
const int INF = 1 << 29 ; 
#define MOD (ll)(1e9+7)
#define eps 1e-6
#define pb push_back 
#define mp make_pair 
#define DEBUG(x)		cout << '>' << #x << ':' << x << endl;
#define F first 
#define S second 
#define all(s) s.begin,s.end() 

int main() 
{
	ios::sync_with_stdio(0) ;
	cin.tie(NULL) ; 
	//freopen("input.txt","r",stdin);

	int n , W;
	cin >> n >> W;
	int w[n] , v[n];
	REP(i,n) cin >> w[i] >> v[i];
	long long dp[n+1][W+1];
	REP(i,n+1) REP(j,W+1) dp[i][j] = 0;
	REP(i,n) {
		REP(j,W+1) {
			if(j >= w[i]) 
				dp[i+1][j] = max(dp[i][j] , v[i] +dp[i][j-w[i]]);
			else 
				dp[i+1][j] = dp[i][j];
		}
	}
	/*
	REP(i,n+1) {
		REP(j,W+1) {
			cout << dp[i][j] << " " ;
		}
		cout << endl;
	}
	*/
	cout << dp[n][W] << endl;
	return 0 ; 
}



Measured memory_bytes: 79104
using System;
public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var h1 = int.Parse(line[0]);
        var h2 = int.Parse(line[1]);
        string[] line2 = Console.ReadLine().Trim().Split(' ');
        var k1 = int.Parse(line2[0]);
        var k2 = int.Parse(line2[1]);
        string[] line3 = Console.ReadLine().Trim().Split(' ');
        var p = Array.ConvertAll(line3, int.Parse);
        var hp = h1 * p[0] + h1 / 10 * p[2] + h2 * p[1] + h2 / 20 * p[3];
        var kp = k1 * p[0] + k1 / 10 * p[2] + k2 * p[1] + k2 / 20 * p[3];
        if (hp > kp) Console.WriteLine("hiroshi");
        else if (hp == kp) Console.WriteLine("even");
        else Console.WriteLine("kenjiro");
    }
}

Measured memory_bytes: 8928
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

string s;

int check(int n){
	int l = (s.length() - n) / 2;
	for(int i = 0; i < l; i++){
		if(s.at(i) != s.at(l + i)) return 0;
	}
	return 1;
}

int main(){
	cin >> s;
	for(int n = 2; n < s.length(); n += 2){
		if(check(n) == 1){
			cout << s.length() - n << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int irekae(int);

int main(void){
	int a,b,c;
	int n;
	scanf("%d %d %d",&a,&b,&c);
	if(a>b){
		n=a;
		a=b;
		b=n;
	}
	if(b>c){
		n=c;
		c=b;
		b=n;
	}
	if(a>c){
		n=a;
		a=c;
		c=n;
	}
	if(a>b){
		n=a;
		a=b;
		b=n;
	}
	printf("%d %d %d\n",a,b,c);
	
	return 0;
}




Measured memory_bytes: 2132
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> a[100001];
int main(){
  int cnt=0;
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>a[i].f>>a[i].s;
    if(a[i].f>a[i].s)
      swap(a[i].f,a[i].s);
  }
  sort(a,a+m);
  int s=0,e=0;
  int go=0;
  while(go<m){
    s=a[go].f,e=a[go].s;
    go++;
    while(go<m){
      if(a[go].f>=e || a[go].s<=s)
        break;
      s=max(a[go].f,s);
      e=min(a[go].s,e);
      go++;
    }
    cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

def factrial(N):
    fc = [1, 1] + [None] * N
    inv = [0, 1] + [None] * N
    fcInv = [1, 1] + [None] * N
    for i in range(2, N+1):
        fc[i] = i*fc[i-1]%mod
        inv[i] = mod-(inv[mod%i]*(mod//i))%mod
        fcInv[i] = fcInv[i-1]*inv[i]%mod
    return fc, fcInv

def modCom(n, k):
    return 0 if n < k else fc[n] * fcInv[k] * fcInv[n-k] % mod

N, K = map(int, input().split())
fc, fcInv = factrial(N+1)
a = [int(x) for x in input().split()]
a.sort()
ans = 0
for i in range(N-K+1):
    ans -= a[i] * modCom(N-i-1, K-1) % mod
    ans %= mod
for i in range(K-1, N):
    ans += a[i] * modCom(i, K-1) % mod
    ans %= mod
print(ans)


Measured memory_bytes: 72236
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.ex=self.px/self.pd
		self.ey=self.py/self.pd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*cos(atan2(u.ey,u.ex)-atan2(neu.ey,neu.ex)) + sqrt(u.d**2-d**2) > R:
				#if u.pd*abs(neu.ex*u.ex+neu.ey*u.ey)+sqrt(u.d**2-d**2) > R: #nazeka kore ja dame
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Measured memory_bytes: 4668
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
#include <map>

#define FOR0(var, max) for (ul (var) = 0; (var) < (max); ++(var))
#define FORi(var, min, max) for (ul (var) = (min); (var) < (max); ++(var))
#define FORi_INV(var, min, max) for (ul (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

const static ul NMAX = 100000;
const static ul SEGNMAX = (1 << 17);
const static ul AiMAX = 1000000000;

static ul N;
static ul Ai[NMAX];

template <class T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}

/* (identity element, operation) */
template <class T>
using Monoid = pair<T, function<T(T, T)>>;

template <class T, ul K>
class SegmentTree {
  const Monoid<T> monoid;
  const ul N = (1 << K);
  T tree[2 * (1 << K) - 1];

  ui parent(ui i) {
    if (i == 0) {
      return 0;
    }
    return (i - 1) / 2;
  }

  ui child1(ui i) {
    return i * 2 + 1;
  }

  ui child2(ui i) {
    return i * 2 + 2;
  }

  bool is_leaf(ui i) {
    return (N - 1 <= i);
  }

  void propagate_from_leaf(ui i) {
    ui cur = N - 1 + i;
    while (cur != 0) {
      cur = parent(cur);
      auto x1 = tree[child1(cur)];
      auto x2 = tree[child2(cur)];
      tree[cur] = monoid.second(x1, x2);
    }
  }

  T query_impl(ui a, ui b, ui k, ui l, ui r) {
    if (r <= a || b <= l) {
      return monoid.first;
    } else if (a <= l && r <= b) {
      return tree[k];
    } else {
      auto ta = query_impl(a, b, child1(k), l, (l + r) / 2);
      auto tb = query_impl(a, b, child2(k), (l + r) / 2, r);
      return monoid.second(ta, tb);
    }
  }
public:
  /* Initialize Segment Tree with Monoid `_monoid` */
  SegmentTree(const Monoid<T>& _monoid) : monoid(_monoid) {
    FOR0(i, N) {
      tree[i] = monoid.first;
    }
  }

  void update(ui i, T x) {
    tree[N - 1 + i] = x;
    propagate_from_leaf(i);
  }

  // [a, b)
  T query(ui a, ui b) {
    return query_impl(a, b, 0, 0, N);
  }
};

void solve(void) {
  Monoid<ul> monoid = make_pair(0ULL, gcd<ul>);
  SegmentTree<ul, 17> tree(monoid);
  FOR0(i, N) {
    tree.update(i, Ai[i]);
  }
  ul res = 0;
  FOR0(i, N) {
    ul t = 0;
    if (0 != i) {
      t = tree.query(0, i);
    }
    if (i + 1 != N) {
      t = gcd(t, tree.query(i + 1, N));
    }
    // cout << t << endl;
    // cout << segtree_query(0, i) << ", " << segtree_query(i + 1, N) << endl;
    if (res < t) {
      res = t;
    }
  }
  cout << res << endl;
}

int main(void) {
  cin >> N;
  FOR0(i, N) {
    cin >> Ai[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 2816
#include "bits/stdc++.h"
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];

  int cnt = 0;
  rep(i, h) {
    rep(j, w) {
      if (s[i][j] == '#') {
        cnt++;
      }
    }
  }

  queue<pair<int, int>> que;
  que.emplace(0, 0);
  vector<vector<int>> d(h, vector<int>(w, inf));
  d[0][0] = 0;

  auto inside = [&](int x, int y){
    return 0 <= x && x < h && 0 <= y && y < w;
  };

  while (!que.empty()) {
      int x, y;
      tie(x, y) = que.front(); que.pop();
      if (x == h - 1 && y == w - 1)
          break;

      rep(k, 4) {
          int nx = x + dx[k], ny = y + dy[k];
          if (inside(nx, ny) && d[nx][ny] == inf && s[nx][ny] == '.') {
              d[nx][ny] = d[x][y] + 1;
              que.emplace(nx, ny);
          }
      }
  }

  cout << (d[h-1][w-1] == inf ? -1 : h * w - d[h-1][w-1] - 1 - cnt) << endl;
}


Measured memory_bytes: 256
#coding: utf-8
N = input()
N_list = list(map(int,N))
N_str = str(N)

if (N_list[0] + N_list[1] + N_list[2] + N_list[3]) ==7:
    print(N_str[0] +"+"+ N_str[1] +"+"+  N_str[2] + "+" + N_str[3]+"=7")

elif (N_list[0] - N_list[1] + N_list[2] + N_list[3]) ==7:
    print(N_str[0] +"-"+ N_str[1] +"+"+  N_str[2] + "+" + N_str[3]+"=7")

elif (N_list[0] - N_list[1] - N_list[2] + N_list[3]) ==7:
    print(N_str[0] +"-"+ N_str[1] +"-"+  N_str[2] + "+" + N_str[3]+"=7")

elif (N_list[0] - N_list[1] - N_list[2] - N_list[3]) ==7:
    print(N_str[0] +"-"+ N_str[1] +"-"+  N_str[2] + "-" + N_str[3]+"=7")

elif (N_list[0] + N_list[1] - N_list[2] + N_list[3]) ==7:
    print(N_str[0] +"+"+ N_str[1] +"-"+  N_str[2] + "+" + N_str[3]+"=7")

elif (N_list[0] + N_list[1] - N_list[2] - N_list[3]) ==7:
    print(N_str[0] +"+"+ N_str[1] +"-"+  N_str[2] + "-" + N_str[3]+"=7")

elif (N_list[0] + N_list[1] + N_list[2] - N_list[3]) ==7:
    print(N_str[0] +"+"+ N_str[1] +"+"+  N_str[2] + "-" + N_str[3]+"=7")

elif (N_list[0] - N_list[1] + N_list[2] - N_list[3]) ==7:
    print(N_str[0] +"-"+ N_str[1] +"+"+  N_str[2] + "-" + N_str[3]+"=7")

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


void solve() {
    ll i,j,k,l,r,x,y; string s;
    bool exit = false;
    ll A, B, C;
    cin >> A >> B >> C;
    ll ret;
    if(A+B+1<C){
        ret = B + (A+B+1);
    }else{
        ret = B + C;
    }
    cout<<ret<<endl;
    /*cin>>N;
    vector<ll> V((N+1)*(N+1));
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

ll mod = 1000000007;

ll solve(ll c)
{
    if (c == 1)
    {
        return 1;
    }
    else
    {
        for (ll i = 2; i * i <= c; i++)
        {
            if (c % i == 0)
            {
                while (c % i == 0)
                {
                    c /= i;
                }
                return 1 + solve(c);
            }
        }
    }
    return 2;
}

signed main()
{
    ll a, b;
    cin >> a >> b;
    ll c = __gcd(a, b);
    //    cerr << c << endl;
    ll ans = solve(c);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3652
import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {


    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        //
        int n=in.nextInt();
        String str=in.next();
        int r=0;
        int b=0;
        for(int i=0;i<str.length();i++){
            //
            int d=str.charAt(i)=='R'?r++:b++;
        }
        System.out.println(r>b?"Yes":"No");
    }

}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>

using namespace std;

int main() {
	long long n;
	cin >> n;
	int ans = 1e9;
	for (long long i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			long long j = n / i;
			int d = max(to_string(i).size(), to_string(j).size());
			ans = min(ans, d);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define sz(x) (int)(x.size())
#define lt(x) (int)(x.length())
#define MOD 1000000007 
#define mx 100003

int n, l, P[mx][20], q, a[mx], A, b;

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	cin >> l;
	for(int i = 1; i <= n; i++){
		int in = upper_bound(a + 1, a + n + 1, a[i] + l) - a;
		in -= 1;
		P[i][0] = in;
		// debug(i);
		// debug(in);
	}
	for(int j = 1; j <= 18; j++)
		for(int i = 1; i <= n; i++)
			P[i][j] = P[P[i][j - 1]][j - 1];
	cin >> q;
	while(q--){
		cin >> A >> b;
		if(A > b)
			swap(A, b);
		int jaw = 1;
		for(int i = 18; i >= 0; i--){
			if(P[A][i] < b){
				A = P[A][i];
				// debug(A);
				jaw += 1 << i;
			}
		}
		cout << jaw << '\n';
	}
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define gc getchar
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x1 uvuvwevwevwe
#define y1 onyetenyevwe
#define x2 ugwemubwem
#define y2 ossas
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
const LL INF=1000000000;
template <typename T> void scan(T &angka){
	angka=0;char input=gc();T kali=1;
	while(!(48<=input&&input<=57)){	if(input=='-')	kali=-1;input=gc();}
	while(48<=input&&input<=57)	angka=(angka<<3)+(angka<<1)+input-48,input=gc();angka*=kali;
}
template <typename T1,typename T2> void scan(T1 &angka1,T2 &angka2){
	scan(angka1);scan(angka2);
}
int matriks[20][20]={},nodes,edge,total[(1<<15)+5][20]={},harga[(1<<15)+5],temp[20],bentuk[(1<<15)+5];
LL dp[(1<<15)+5][20];
void setINF(){
	for(int i=0;i<(1<<nodes);i++)
	{
		for(int j=0;j<nodes;j++)
			dp[i][j]=INF;
	}
}
int lsone(int state){
	return state&-state;
}
void precomp(){
	for(int state=0;state<(1<<nodes);state++)
	{
		for(int i=0;i<nodes;i++)
		{
			if(state==0)
				total[state][i]=0;
			else
				total[state][i]=total[state-lsone(state)][i]+matriks[i][__builtin_popcount(lsone(state)-1)];
		}
	}
}
int main()
{
	scan(nodes,edge);
	for(int i=1;i<=edge;i++)
	{
		int u,v,weight;
		scan(u,v),scan(weight);
		u--;
		v--;
		matriks[u][v]=weight;
		matriks[v][u]=weight;
	}
	setINF();
	precomp();
	//basecase
	dp[(1<<0)][0]=0;
	for(int state=1;state<(1<<nodes);state++)
	{
		for(int i=0;i<nodes;i++)
		{
			if((state&(1<<i))==0)			//gak valid
			{
				assert(dp[state][i]==INF);
				continue;
			}
			for(int j=0;j<nodes;j++)
			{
				if(state&(1<<j))
					continue;
				if(matriks[i][j]==0)
					continue;
				dp[state|(1<<j)][j]=min(dp[state|(1<<j)][j],dp[state][i]+total[state^(1<<i)][j]);
			}
			int invers=state^((1<<nodes)-1),totalBit=__builtin_popcount(invers);
			for(int j=0;j<totalBit;j++)
			{
				temp[j]=__builtin_popcount(lsone(invers)-1);
				invers-=lsone(invers);
			}
			harga[0]=0;
			bentuk[0]=0;
			for(int mask=1;mask<(1<<totalBit);mask++)
			{
				harga[mask]=harga[mask-lsone(mask)]+total[state^(1<<i)][temp[__builtin_popcount(lsone(mask)-1)]];
				bentuk[mask]=bentuk[mask-lsone(mask)]^(1<<temp[__builtin_popcount(lsone(mask)-1)]);
				assert((state&bentuk[mask])==0);
				dp[state^bentuk[mask]][i]=min(dp[state^bentuk[mask]][i],dp[state][i]+harga[mask]);
			}
		}
	}
	cout<<dp[(1<<nodes)-1][nodes-1]<<endl;
}

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

int main() {
	string str;
	bool l,s,m;
	while(cin>>str){
	l=s=m=true;
	for(int i=0;i<str.size();i++){
		if(str.size()<6){
			break;
		}
		
		if(s)if('a'<=str[i]&&str[i]<='z')s=false;
		if(l)if('A'<=str[i]&&str[i]<='Z')l=false;
		if(m)if('0'<=str[i]&&str[i]<='9')m=false;
	}
	if(l+s+m)cout<<"INVALID"<<endl; else cout<<"VALID"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;
int main(void){
    ll d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3644
#include<stdio.h>
int main(){

  int n,m,l;
  scanf("%d %d %d", &n, &m, &l);

  int i,j,a[n][m];
  
  for ( i = 0 ; i < n ; i++ ){
    for ( j = 0 ; j < m ; j++ ){
      scanf("%d", &a[i][j]);
    }
  }

  int b[m][l];

  for ( i = 0 ; i < m ; i++ ){
    for( j = 0 ; j < l ; j++ ){
      scanf("%d", &b[i][j]);
    }    
  }

  long sum,c[n][l];
  int k;
  sum =0;

  for ( i = 0 ; i < n ; i++ ){
    for ( j = 0 ; j < l ; j++ ){
      for ( k = 0 ; k < m ; k++ ){

	sum = sum + a[i][k] * b[k][j];

      }

      c[i][j] = sum;
      sum = 0;

    }
  }

  for ( i = 0 ; i < n ; i++ ){
    for ( j = 0 ; j < l ; j++ ){

      printf("%ld", c[i][j]);

      if ( j == l - 1 ){
	printf("\n");
	break;
      }

      printf(" ");
      
    }
    
  }

  return 0;
  
}

Measured memory_bytes: 760
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    String[] T = sc.nextLine().split(" ");
    String U = sc.nextLine();
    int A = Integer.parseInt(T[0]);
    int B = Integer.parseInt(T[1]);
    if(U.equals(S[0])){
      A--;
    }else{
      B--;
    }
    System.out.println(A+" "+B);
  }
}

Measured memory_bytes: 22996
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> h(n);
  int cnt = 0, tmp = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> h[i];
  }
  for (int i = 0; i < n; i++)
  {
    if (h[i - 1] >= h[i])
    {
      cnt++;
      //cout << cnt << endl;
    }
    else
    {
      //cout << cnt << endl;
      tmp = max(cnt, tmp);
      cnt = 0;
    }
  }
  int ans = max(tmp, cnt);
  cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner Input = new Scanner(System.in);
        String A = Input.next();
        String B = Input.next();
        String C = Input.next();
        if (A.charAt(A.length() - 1) == B.charAt(0) && B.charAt(B.length() - 1) == C.charAt(0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");}
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> x(n), y(n);
  for (i64 i = 0; i < n; i++)
    cin >> x[i] >> y[i];
  map<pair<i64, i64>, i64> m;
  for (i64 i = 0; i < n; i++)
    for (i64 j = 0; j < n; j++)
      if (i != j && (x[i] != x[j] || y[i] != y[j]))
        m[{x[i] - x[j], y[i] - y[j]}]++;
  i64 ans = 0;
  for (pair<pair<i64, i64>, i64> i : m)
    ans = max(ans, i.second);
  cout << n - ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
bool a[300000]={0};
a[1]=1;
for(int i=2;i<150001;i++){
	if(a[i]==1) continue;
	int j=2*i;
	while(j<300000){
		a[j]=1;
		j=j+i;
	}
}
int n;
while(cin>>n && n!=0){
int ans=0;	
	for(int i=n+1;i<=2*n;i++){
	if(a[i]==0) ans++;	
	}

cout<<ans<<endl;
}

	return 0;
}

Measured memory_bytes: 3308
from functools import reduce
MOD = 10**9 + 7
primes = list(map(int, "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997".split(" ")))

N = int(input())
arr = []

for p in primes:
    if p <= N:
        pow_p = p
        s = 0
        while pow_p <= N:
            s += N // pow_p
            pow_p *= p
        arr.append(s+1)

if N == 1:
    print(1)
else:
    print(reduce(lambda a, b: (a * b) % MOD, arr))


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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 2e16;
const int MB = 20;
const int MOD = 998244353;
const int maxN = 1e7 + 1;

void solve() {
	int n;
	cin >> n;
	map<string, int> mp;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		mp[s]++;
	}
	cout << "AC x " << mp["AC"] << '\n';
	cout << "WA x " << mp["WA"] << '\n';
	cout << "TLE x " <<  mp["TLE"] << '\n';
	cout << "RE x " << mp["RE"];
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using str = string;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
const double PI = 3.141592653589793238;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define REP(i, m, n) for (int i = m; i < (int)n; i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greator<>()
#define d20 std::setprecision(20)
#define veci vector<int>
#define vecll vector<long long int>
#define vecb vector<bool>
#define vecd vector<double>
template <typename T>
T lcm(T a, T b)
{
	return a / __gcd(a, b) * b;
}

int main()
{
	int n;
	cin >> n;
	cout << n/2 + n%2 << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
char str[MAXN];
int num[1<<26];
int dp[MAXN];
int sum;
int main()
{
    scanf("%s", str);
    memset(num, 0x3f, sizeof(num));
    memset(dp, 0x3f, sizeof(dp));
    num[0]=0;
    sum=0;
    int len=strlen(str);
    for(int i=0;i<len;++i)
    {
        int x=1<<(str[i]-'a');
        sum^=x;
        dp[i]=min(dp[i], num[sum]+1);
        for(int j=0;j<26;++j)
            dp[i]=min(dp[i], num[sum^(1<<j)]+1);
        num[sum]=min(num[sum], dp[i]);
    }
    printf("%d\n", dp[len-1]);
    return 0;
}


Measured memory_bytes: 263424
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datK) = readLine.split(" ").map(_.toInt)
    val datS = readLine

    val ans =
      if (datS.length() <= datK) datS
      else datS.take(datK) + "..."
    println(ans)
  }
}


Measured memory_bytes: 54716
MAX = 2010
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

N, K = map(int, input().split())

for i in range(K):
    ans = C(N-K+1, i+1)*C(K-1, i)%MOD
    print(ans)

Measured memory_bytes: 43504
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(){
    int H, W;
    char c;
    cin >> H >> W;

    rep(i, H+2)
    {
        rep(j, W+2){
            if((i == 0) || (i == H+1)){
                cout << '#';
            }else{
                if ((j == 0) || (j == W+1)) {
                    cout << '#';
                }else{
                    cin >> c;
                    cout << c;
                }

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

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

class MainClass {
  public static void Main (string[] args) {
    //入力
    var N = long.Parse(Console.ReadLine());
    var list = Console.ReadLine().Split(' ').Select(long.Parse);

    //処理
    var delNum = N - list.Distinct().Count();
    var ans = N - (Convert.ToInt64(Math.Ceiling((double)delNum / 2))) * 2;
    //出力
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 23264
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n, c[128];
		cin >> n;
		for (int i = 0; i < n; ++i)
			cin >> c[i];

		int dp[128][128];
		clear(dp, 0);

		for (int bet = 1; bet < n; ++bet)
		{
			for (int i = 0; i < n; ++i)
			{
				int j = (i + bet + 1) % n;
				for (int k = 0; k < bet; ++k)
				{
					int p = (i + 1 + k) % n;
					max_swap(dp[i][j], dp[i][p] + dp[p][j] + abs(c[i] - c[p]));
				}
			}
		}
		int res = 0;
		for (int i = 0; i < n; ++i)
			max_swap(res, dp[i][i]);
		cout << res << endl;
	}
}

Measured memory_bytes: 0
import Data.Ord (comparing)
import Data.List (foldl',sortBy)
import Data.List.Split (splitOn)
import qualified Data.Map.Strict as Map
import System.IO (isEOF)

type Composition = [(Int,Int)]

main = do
    quit <- isEOF
    if quit then return () else do
        input >>= return . solve >>= output
        main

input :: IO [Int]
input = (map read . splitOn ",") `fmap` getLine

output :: String -> IO ()
output = putStrLn

solve :: [Int] -> String
solve ns = comp `seq` (snd $ head $ filter (\(pred,_) -> pred comp) preds)
    where
    comp = composition ns
    preds = [
        (isFourCard, "four card"),
        (isFullHouse, "full house"),
        (isStraight, "straight"),
        (isThreeCard, "three card"),
        (isTwoPair, "two pair"),
        (isOnePair, "one pair"),
        (const True, "null")]

composition :: [Int] -> Composition
composition ns = sortBy (flip (comparing snd)) $ filter (\(_,c) -> c > 0) $
                 Map.assocs $ foldl' countUp Map.empty ns
    where
    countUp map n = Map.insertWith (+) n 1 map

isFourCard :: Composition -> Bool
isFourCard [(_,4),(_,1)] = True
isFourCard _ = False

isFullHouse :: Composition -> Bool
isFullHouse [(_,3),(_,2)] = True
isFullHouse _ = False

isStraight :: Composition -> Bool
isStraight [(1,1),(10,1),(11,1),(12,1),(13,1)] = True
isStraight [(a,1),(b,1),(c,1),(d,1),(e,1)]
    | b-a==1 && c-b==1 && d-c==1 && e-d==1 = True
isStraight _ = False

isThreeCard :: Composition -> Bool
isThreeCard [(_,3),(_,1),(_,1)] = True
isThreeCard _ = False

isTwoPair :: Composition -> Bool
isTwoPair [(_,2),(_,2),(_,1)] = True
isTwoPair _ = False

isOnePair :: Composition -> Bool
isOnePair [(_,2),(_,1),(_,1),(_,1)] = True
isOnePair _ = False

Measured memory_bytes: 4164
S = input()
N = len(S)

end = (N-1)//2
stt = (N+3)//2

S1 = S[:end]
S2 = S[stt-1:]

if S == S[::-1] and S1 == S1[::-1] and S2 == S2[::-1]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
#include <iostream>

int main(int argc, char** argv)
{
	while (true)
	{
		int m, f, r;
		std::cin >> m >> f >> r;
		if (m == -1 && f == -1 && r == -1)
		{
			break;
		}

		char rank = 'F';
		if (m >= 0 && f >= 0)
		{
			int mf = m + f;
			if (mf >= 80) { rank = 'A'; }
			else if (mf >= 65) { rank = 'B'; }
			else if (mf >= 50 || r >= 50) { rank = 'C'; }
			else if (mf >= 30) { rank = 'D'; }
			else { rank = 'F'; }
		}

		std::cout << rank << std::endl;
	}

	return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

void solve() {
    int n; cin >> n;
    string a, b, c; cin >> a >> b >> c;
    int ans = 0;
    rep(i, 0, n){
        if(a[i] == b[i] && b[i] == c[i]) continue;
        else if(a[i] != b[i] && b[i] != c[i] && c[i] != a[i]) ans += 2;
        else ans++;
    }
    cout << ans << endl;
}

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

    solve();
    return 0;
}
 


Measured memory_bytes: 256