akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static final int NUM=1000;

	private static int[][] graph= {
			{0},							// A
			{1, 0},							// B
			{0, 1, 0},						// C
			{1, 0, 0, 0},					// D
			{0, 1, 0, 1, 0},				// E
			{0, 0, 1, 0, 1, 0},				// F
			{0, 0, 0, 1, 0, 0, 0},			// G
			{0, 0, 0, 0, 1, 0, 1, 0},		// H
			{0, 0, 0, 0, 0, 1, 0, 1, 0},	// I
		//	 A  B  C  D  E  F  G  H  I
	};

	private static boolean check(String str) {
		char[] array=str.toCharArray();
		for(int i=0; i<array.length-1; i++)
			if(!neighbor(array[i], array[i+1]))
				return false;
		return true;
	}

	private static boolean neighbor(char p, char n) {
		if(p<n)
			return graph[n-'A'][p-'A']==1;
		else
			return graph[p-'A'][n-'A']==1;
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in), 1);

		for(int i=0; i<NUM; i++) {

			String s=br.readLine();

			if(check(s))
				System.out.println(s);
		}
	}

}

Measured memory_bytes: 23800
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a;
    cin >> a;
    int ret = 0;
    for (int i = 0; i < n - 1; i++) {
        int x;
        cin >> x;
        if (a < x)ret++;
        a = x;
    }
    cout << ret << endl;
    return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MAXN = 310;
const int MAXM = 8010;
int n, A, dp[MAXN][MAXM];
inline void work() {
  scanf("%lld%lld", &n, &A), dp[0][0] = 1;
  for(reg int i = 1; i <= n; ++i) {
    int x;
    scanf("%lld", &x);
    for(reg int j = i; j > 0; j--) for(reg int k = A * n; k >= x; k--) dp[j][k] += dp[j - 1][k - x];
  }
  int ans = 0;
  for(reg int i = 1; i <= n; ++i) ans += dp[i][i * A];
  printf("%lld\n", ans);
}
signed main() {
  int _ = 1;
  // scanf("%d", &_);
  while(_--) work();
  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

struct Edge{
    // 始点, 終点, 重み, 最大量
    long long src, dst, weight, capacity;
    Edge(): src(0), dst(0), weight(0), capacity(0) {}
    Edge(long long s, long long d, long long w): src(s), dst(d), weight(w) {}
    Edge(long long s, long long d, long long w, long long c): src(s), dst(d), weight(w), capacity(c) {}
};

class Graph{
public:
    long long size;
    vector<vector<Edge>> node;
    Graph(long long n): size(n), node(n) {}
    // 無向辺の追加
    void addEdge(long long s, long long d, long long w = 1){
        node[s].emplace_back(s, d, w);
        node[d].emplace_back(d, s, w);
    }
    // 有向辺の追加
    void addArc(long long s, long long d, long long w = 1){
        node[s].emplace_back(s, d, w);
    }
    // ノードの追加
    void addNode(){
        size++;
        node.emplace_back();
    }
};

// TopologicalSort; トポロジカルソート
// ：有向非巡回グラフ（DAG）の全ての辺が右向きになるように整列する。[O(E+V)]
vector<long long> TopologicalSort(const Graph &g){
    vector<long long> indegree(g.size), sorted;
    for(long long v=0; v<g.size; v++) for(auto &edge: g.node[v]) indegree[edge.dst]++;
    queue<long long> que;
    for(long long i=0; i<g.size; i++) if(indegree[i] == 0) que.push(i);
    while(!que.empty()){
        long long v = que.front();
        que.pop();
        sorted.emplace_back(v);
        for(auto &edge: g.node[v]) if (--indegree[edge.dst] == 0) que.push(edge.dst);
    }
    return *max_element(indegree.begin(), indegree.end()) == 0LL ? sorted : vector<long long>();
}

// DAGMaxDistance; DAGにおける最大距離の計算
// ：TopologicalSortによる整列順でDAGを巡回し最大距離を計算する。
long long DAGMaxDistance(const Graph &g, const vector<long long> &sorted){
    vector<long long> dp(g.size, 0);
    long long maxDist = 0;
    for(auto &v: sorted){
        for(auto &edge: g.node[v]){
            dp[edge.dst] = max(dp[edge.dst], dp[v]+1);
            maxDist = max(maxDist, dp[edge.dst]);
        }
    }
    return maxDist;
}

int main(){
    Init();
    ll n, m; cin >> n >> m;
    Graph g(n);
    rep(i, m){
        ll x, y; cin >> x >> y; x--; y--;
        g.addArc(x, y, 1);
    }
    auto sorted = TopologicalSort(g);
    cout << DAGMaxDistance(g, sorted) << endl;
}

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

int main() {
  int k, a, b;
  cin >> k >> a >> b;

  if ((b/k - a/k >= 1) || (a%k == 0)) {
    cout << "OK";
  }
  else {
    cout << "NG";
  }
  cout << endl;
}


Measured memory_bytes: 3572
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);

   int N = sc.nextInt();
   int L = sc.nextInt();
   String[] sl = new String[N];
   for(int i =0;i<N;i++) sl[i] = sc.next();
   
   Arrays.sort(sl);
   StringBuilder sb = new StringBuilder();
   for(int i=0;i<N;i++) sb.append(sl[i]);
   System.out.println(sb.toString());
 }
}

Measured memory_bytes: 22996
mod = 10**9+7
n,k = [int(x) for x in input().strip().split()]
res=0
for j in range(k,n+2):
    mn = (j-1)*j//2
    mx = j*(2*n-j+1)//2
    res = (res%mod+(mx-mn+1)%mod)%mod

print(res%mod)

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

using namespace std;

class Dice
{
  public:
    vector<int> diceNum;
    Dice(vector<int>& inputs);
    void toW();
    void toS();
    void ParallelRotation();
};

Dice::Dice(vector<int>& inputs)
{
  diceNum=inputs;
}

void Dice::toW()
{
  swap(diceNum[0],diceNum[3]);
  swap(diceNum[0],diceNum[5]);
  swap(diceNum[0],diceNum[2]);
}

void Dice::toS()
{
  swap(diceNum[0],diceNum[1]);
  swap(diceNum[0],diceNum[5]);
  swap(diceNum[0],diceNum[4]);
}

void Dice::ParallelRotation()
{
  swap(diceNum[1],diceNum[2]);
  swap(diceNum[2],diceNum[4]);
  swap(diceNum[4],diceNum[3]);
}

bool Judge(Dice& dice1,Dice& dice2)
{
  int count=0;
  for(int i=0;i<6;i++)
  {
    if(dice1.diceNum[i]==dice2.diceNum[i]) count++;
  }
  if(count==6)return true;
  else return false;
    
}

int main(int argc,char* argv[])
{
  vector<int> inputs(6);
  int count = 0;
  bool flag=false;
  for(int i=0;i<6;i++){cin >> inputs[i];}
  Dice dice1(inputs);
  for(int i=0;i<6;i++){cin >> inputs[i];}
  Dice dice2(inputs);

  while(1)
  {
    dice2.toS();
    for(int j=0;j<4;j++)
    {
      dice2.ParallelRotation();
      flag=Judge(dice1,dice2);
      if(flag==true) break;
    }
    if(flag==true) break;
    dice2.toW();
    for(int j=0;j<4;j++)
    {
      dice2.ParallelRotation();
      flag=Judge(dice1,dice2);
      if(flag==true) break;
    }
    count++;
    if(flag==true) break;
    if(count==3)break;
  }
  if(flag==true) cout << "Yes" << endl;
  else if(flag==false) cout << "No" << endl;
}

Measured memory_bytes: 3120
#include <stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	long long int arr[n], max = 1e18, prod = 1, flag = 0, zero = 0;
	
	for (int i = 0; i < n; i++){
		scanf("%lld", &arr[i]);
		flag = (arr[i] > max) ? 1 : flag;
		prod *= arr[i];
		(arr[i]) ? max /= arr[i] : zero = 1;
	}
	(zero) ? puts("0") : ((flag) ? puts("-1") : printf("%lld\n", prod));
	
	return 0;
}

Measured memory_bytes: 2464
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($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)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
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, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        h: usize,
        w: usize,
    }

    let ans = (n-h+1)*(n-w+1);

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    ll sum = 0;
    vector<int> vec(N);
    for(int i = 0; i < N; i++){
        cin >> vec[i];
    }
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            sum += vec[i] * vec[j];
        }
    }
    cout << sum <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
 
int main()
{
    int N;
    long int A[201];
    int min=1000000000;
    int temp=0;
    int i;
  
 // 整数の入力
    scanf("%d", &N);
 // printf("%d\n",N);
  for(i=0;i<N;i++){
    scanf("%ld", &A[i]);
//     printf("%ld\n",A[i]);
    temp = 0;
    while(1){
      if(A[i]%2 == 0){
        A[i]=A[i]/2;
        temp = temp +1;
//        printf("temp %d\n",temp);
      } else {
        break;
      }
    }
    if(min>temp)
    {
//      printf("temp %d ,%d\n",temp,min);
      min = temp;
    }
  }
  
    printf("%d\n",min);
/*
  for(i=0;i < 3 ;i++ ){
//    printf("%c\n",s[i]);
    if(49 == s[i]){ 
     cnt = cnt + 1;
//     printf("%d\n",cnt);
              }
  }
     printf("%d\n", cnt);
*/ 
    return 0;
}

Measured memory_bytes: 128
def multi_input():
    return map(int, input().split())

s = input()
l = []
l.append(s[0])

for si in s[1:]:
    t = []
    for li in l:
        t.append(li+'+'+si)
        t.append(li+'-'+si)
    l = t
    
for li in l:
    if eval(li) == 7:
        print(li+'=7')
        break

Measured memory_bytes: 3064
/*
 * 0308.cc: Deadlock
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int UN = 100;
const int DN = 100;
const int GN = UN + DN;

/* typedef */

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

/* global variables */

vi nbrs[GN];
bool used[GN];

/* subroutines */

bool rec(int u) {
  if (used[u]) return true;
  used[u] = true;
  vi &nbru = nbrs[u];
  for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++)
    if (rec(*vit)) return true;
  used[u] = false;
  return false;
}

/* main */

int main() {
  int n;
  cin >> n;
  while (n--) {
    int ui, di;
    string op;
    cin >> ui >> op >> di;
    ui--, di--;

    if (op == "lock") nbrs[UN + di].push_back(ui);
    else if (op == "wait") nbrs[ui].push_back(UN + di);
  }

  for (int i = 0; i < GN; i++) {
    if (nbrs[i].size() == 0) continue;

    memset(used, false, sizeof(used));
    if (rec(i)) {
      puts("1");
      return 0;
    }
  }

  puts("0");
  return 0;
}

Measured memory_bytes: 1228
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, D = LI()
    A = [LI_() for _ in range(H)]
    Q = I()

    c = [[] for _ in range((H * W))]
    for i, j in itertools.product(range(H), range(W)):
        c[A[i][j]] = [i, j]

    c_cum = [0] * (H * W)
    for i in range(H * W - D):
        c_cum[i+D] = (abs(c[i+D][0] - c[i][0]) + abs(c[i+D][1] - c[i][1])) + c_cum[i]

    for _ in range(Q):
        L, R = LI_()
        ans = c_cum[R] - c_cum[L]
        print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 25116
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,c[6]={500,100,50,10,5,1},ans;
	while(true){
		cin>>n;
		if(!n)break;
		n=1000-n,ans=0;
		for(int i=0;i<6;i++)ans+=n/c[i],n%=c[i];
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 2960
/* Sort I - Stable Sort */

#include <stdio.h>

void swap( char* a, char* b )
{
  char tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main( void )
{
  int n, i, j;
  scanf( "%d\n", &n );

  char bE[n], bA[n];
  for ( i = 0; i < n; i++ )
    scanf( " %c%c", &bE[i], &bA[i] );

  char sE[n], sA[n];
  for ( i = 0; i < n; i++ ) {
    sE[i] = bE[i];
    sA[i] = bA[i];
  }

  /* BubbleSort */
  for ( i = 0; i < n; i++ ) {
    for ( j = n - 1; j > i; j-- ) {
      if ( bA[j] < bA[j-1] ) {
        swap( &bA[j], &bA[j-1] );
        swap( &bE[j], &bE[j-1] );
      }
    }
  }

  /* SelectionSort */
  for ( i = 0; i < n; i++ ) {
    int minj = i;
    for ( j = i; j < n; j++ ) {
      if ( sA[j] < sA[minj] )
        minj = j;
    }
    swap( &sA[i], &sA[minj] );
    swap( &sE[i], &sE[minj] );
  }


  for ( i = 0; i < n - 1; i++ )
    printf( "%c%c ", bE[i], bA[i] );
  printf( "%c%c\n", bE[n-1], bA[n-1] );
  printf( "Stable\n" );

  for ( i = 0; i < n - 1; i++ )
    printf( "%c%c ", sE[i], sA[i] );
  printf( "%c%c\n", sE[n-1], sA[n-1] );


  int stablep = 1;
  for ( i = 0; i < n; i++ ) {
    if ( bE[i] != sE[i] ) {
      stablep = 0;
      break;
    }
  }

  if ( stablep )
    printf( "Stable\n" );
  else
    printf( "Not stable\n" );

  return 0;
}

Measured memory_bytes: 608
// AtCoder Beginner Contest 057
// D - Maximum Average Sets

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#define MAX_N 50
#define EPS 1e-10
using namespace std;
typedef long long int ll;


ll N, A, B;
map<ll, ll> count;
ll c[MAX_N + 1][MAX_N + 1];
ll ans;

int main() {

  ll v, sum, p_count, used, diff;

  scanf("%lld%lld%lld", &N, &A, &B);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &v);
    count[v] = count[v] + 1;
  }

  memset(c, 0, sizeof(c));
  for (int i = 0; i <= N; i++) {
    c[i][0] = 1;
    c[i][i] = 1;
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j < i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }

  sum = 0;
  used = 0;
  auto itr = count.rbegin();
  for (; itr != count.rend(); itr++) {
    p_count = itr->second;
    if (used < A) {
      diff = min(itr->second, A - used);
      sum += itr->first * diff;
      used += diff;
      itr->second -= diff;
    }
    if (A <= used && used < B && (itr->first - ((double)sum / used)) >= EPS) {
      diff = min(itr->second, B - used);
      sum += itr->first * diff;
      used += diff;
      itr->second -= diff;
    }
    if (A <= used && used <= B && itr->first - ((double)sum / used) < EPS) {
      break;
    }
  }

  if (abs(itr->first - ((double)sum / used)) < EPS) {
    diff = min(itr->second, B - used);
    ans = 0;
    for (int i = 0; i <= diff; i++) {
      ans += c[p_count][itr->second - i];
    }
    sum += itr->first * diff;
    used += diff;
    itr->second -= diff;
  } else {
    ans = c[p_count][itr->second];
  }

  printf("%lf\n", (double)sum / used);
  printf("%lld\n", ans);

  return 0;

}




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

using namespace std;
using ll = long long;
using ld = long double;

const string YES = "APPROVED";
const string NO = "DENIED";

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  bool pred = true;
  for (auto x : a) {
    cin >> x;
    if (x % 2 == 0 && x % 3 && x % 5) {
      pred = false;
    }
  }

  cout << (pred ? YES : NO) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,x,y,c[100];
long long f[20][20],ans;
char a[100],d[100],e[100];
void dfs(int t)
{
		if (t>n)
		{
				x=y=0;
				for (int i=1;i<=n;++i)
						if (c[i]==0)
								d[++x]=a[i];
						else	e[++y]=a[i];
				memset(f,0,sizeof(f));
				f[0][0]=1;
				for (int i=1;i<=n;++i)
						for (int j=0;j<=min(i,x);++j)
						{
								if (j && a[n+n-i+1]==d[j])
										f[i][j]+=f[i-1][j-1];
								if (i>j && i-j<=y && a[n+n-i+1]==e[i-j])
										f[i][j]+=f[i-1][j];
						}
				ans+=f[n][x];
				return;
		}
		c[t]=0;	dfs(t+1);
		c[t]=1;	dfs(t+1);
}
int main()
{
		scanf("%d",&n);
		scanf("%s",a+1);
		dfs(1);
		printf("%lld\n",ans);
		return 0;
}


Measured memory_bytes: 256
import math
ans = 0
X = int(input())
if X<4:
    print(1)
else:
    for i in range(2,math.ceil(math.sqrt(X))):
        for j in range(math.ceil(math.log(X)/math.log(i))+1):
            if i**j <= X:
                ans = max(i**j,ans)
    print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> c(N);
  for(int i=0;i<N;i++)cin >> c[i];
  sort(c.begin(), c.end());

  for(int i=0;i<Q;i++){
    int q;
    cin >> q;
    int maxi = 0;
    for(int t=0;t<=c.back();t+=q){
      int p = lower_bound(c.begin(), c.end(), t + q) - c.begin();
      if(p >= 1){
        maxi = max(maxi, c[p-1] % q);
      }
    }
    cout << maxi << endl;
  }
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    int ans  = 0;

    if(s == "RRR"){
        cout << 3 << endl;
    }else if (s == "RRS"){
        cout << 2 << endl;
    }else if(s == "RSS"){
        cout <<  1 << endl;
    }else if(s == "RSR"){
        cout <<  1 << endl;
    }else if(s == "SSR"){
        cout << 1 << endl;
    }else if(s == "SRS"){
        cout << 1 << endl;
    }else if(s == "SRR"){
        cout << 2 << endl;
    }else{
        cout << 0 << endl;
    }
}

Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll a,n;
	cin>>a>>n;
	ll sum=0;
	for(int i=1;i<=n;i++){
		ll t;
		cin>>t;
		sum+=t;
	}
	cout<<((sum>=a)?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 256
unittest
{
	assert( [ "5", "2 2 3 5 5" ].solve == 2 );
	assert( [ "9", "1 2 3 4 5 6 7 8 9" ].solve == 0 );
	assert( [ "6", "6 5 4 3 2 1" ].solve == 18 );
	assert( [ "7", "1 1 1 1 2 3 4" ].solve == 6 );
}



import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	
	foreach( i, ref a; as )
	{
		a -= 1 + i.signed;
	}
	as.sort();
	
	auto ans = 0L;
	auto b = as[ $ / 2 ];
	foreach( ref a; as )
	{
		ans += abs( a - b );
	}
	return ans;
}


Measured memory_bytes: 11776
#include<iostream>
#include<string>

using namespace std;

int main(){
	string s, p;
	cin >> s >> p;
	s += s;
	if(s.find(p) != -1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}
	


Measured memory_bytes: 3212
H, W, N = map(int, input().split())
Sr, Sc = map(int, input().split())
S = input()
T = input()

# 左か上に移動させたい
now = [Sr, Sc]
for s, t in zip(S, T):
  # 高橋くんのターン
  if s == 'L':
    now[1] -= 1
  if s == 'U':
    now[0] -= 1
  # 駒を取り除けたかチェック
  if now[0] <= 0 or now[1] <= 0:
    print('NO')
    quit()
  
  # 青木くんのターン
  if t == 'R':
    now[1] = min(now[1] + 1, W)
  if t == 'D':
    now[0] = min(now[0] + 1, H)

# 右か下に移動させたい
now = [Sr, Sc]
for s, t in zip(S, T):
  # 高橋くんのターン
  if s == 'R':
    now[1] += 1
  if s == 'D':
    now[0] += 1
  # 駒を取り除けたかチェック
  if H < now[0] or W < now[1]:
    print('NO')
    quit()
  
  # 青木くんのターン
  if t == 'L':
    now[1] = max(now[1] - 1, 1)
  if t == 'U':
    now[0] = max(now[0] - 1, 1)

print('YES')

Measured memory_bytes: 3888
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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; }

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string n;
  cin >> n;
  int m = int(n.size());
  if(n[m-1] == '3') cout << "bon" << endl;
  else if(n[m-1] == '0' || n[m-1] == '1' || n[m-1] == '6' || n[m-1] == '8') cout << "pon" << endl;
  else cout << "hon" << endl;

}


Measured memory_bytes: 3640
#include <iostream>

int main(){
  int n;
  int p[10];
  int max = 0, sum = 0;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::cin >> p[i];
    max = std::max(max, p[i]);
    sum += p[i];
  }
  sum -= max / 2;
  std::cout << sum << std::endl;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    char ch;
    while(cin>>ch)
    {
        if(ch=='A')
        {
            cout<<"T"<<endl;
        }
        else if(ch=='T')
        {
            cout<<"A"<<endl;
        }
        else if(ch=='G')
        {
            cout<<"C"<<endl;
        }
        else
        {
            cout<<"G"<<endl;
        }

    }



    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;cin>>n;
  vector<ll> c;
  c.clear();
  ll i,j,k;
  map<ll,ll> m;
  for(i=0;i<n;i++) {
    cin >> j;
    if(i%2) m[j]=1;
    else    m[j]=0;
    c.push_back(j);
  }
  sort(c.begin(),c.end());
  
  ll ans=0;
  for(i=0;i<n;i++){
    if((m[c[i]]+i)%2) ans++;
  }
  cout << ans/2 << endl;
  return 0;
}


Measured memory_bytes: 7284
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

const ll mod = 1e9 + 7;

ll sub1(ll H, ll W) {
  ll ret;
  if (W % 3 == 0) {
    ret = 0;
  } else {
    ret = H;
  }
  return ret;
}

ll sub2(ll H, ll W) {
  ll ret = LONG_LONG_MAX;
  ll maxv, minv;
  for (ll i = 1; i <= H - 1; ++i) {
    ll a = i * W;
    ll b = (H - i) * (W/2);
    ll c = (H - i) * ((W+1)/2);
    maxv = max(a, max(b, c));
    minv = min(a, min(b, c));
    ret = min(ret, maxv - minv);
  }

  return ret;
}

int main() {
  ll H, W;

  cin >> H >> W;

  ll ans, ans1, ans2;
  ans1 = min(sub1(H, W), sub1(W, H));
  ans2 = min(sub2(H, W), sub2(W, H));
  ans = min(ans1, ans2);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String... args) {
		Scanner scan = new Scanner(System.in);
		long h = scan.nextLong();

		System.out.println(calc(h));
		scan.close();
	}

	private static long calc(long count) {
		return count <= 1 ? 1 : calc(count / 2) * 2 + 1;
	}
}

Measured memory_bytes: 23636
#include <iostream>
#include <string>
#include <map>
#include <deque>
#include <vector>
typedef unsigned int UINT;
using namespace std;

int main() 
{
    string mas;
    cin >> mas;
    int count = 0;
    for (char a : mas) {
        if (a == '1')
            count++;
    }
        cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
ls = list(map(int,input().split()))
import collections
c = collections.Counter(ls)
unique_ls = list(reversed(sorted(([i[0] for i in c.items() if i[1] >= 2]))))

if len(unique_ls) >=2:
  if ls.count(unique_ls[0]) >=4:
    print(unique_ls[0]**2)
  else:
    print(unique_ls[0]*unique_ls[1])
elif len(unique_ls) ==1:
  if ls.count(unique_ls[0]) >=4:
    print(unique_ls[0]**2)
  else:
    print(0)
else:
  print(0)

Measured memory_bytes: 18444
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
	const int maxn=55;
	int a[maxn][maxn];
	int n;
	int main(){
		IOS
		bool ans=1;
		string s;
		cin>>s;
		if(s[0]=='7'||s[1]=='7'||s[2]=='7')
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
		return 0;
	} 

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

void sort(int *num, int size) {
	int v = 0, j = 0;
	for (int i = 1; i < size; i++) {
		v = num[i];
		j = i - 1;
		while (j >= 0 && num[j] > v) {
			num[j + 1] = num[j];
			j--;
		}
		num[j + 1] = v;
		
	}
}

int main() {
	int num[3];
	cin >> num[0] >> num[1] >> num[2];

	sort(num, 3);

	cout << num[0] << " " << num[1] << " " << num[2] << endl;

	return 0;
}

Measured memory_bytes: 3064
#include<stdio.h>
using namespace std;

int main(){
    int r, D, x[11];
    scanf("%d %d %d", &r, &D, &x[0]);
    for(int i=1; i<11;i++){
        x[i]= r*x[i-1] - D;
        printf("%d\n", x[i]);
    }
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public 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 cnt = 0, tmp = 0;
		
		for(int i = 0; i < N - 1; i++) {
			for(int j = N - 1; j > i; j--) {
				if(A[j] < A[j - 1]) {
					tmp = A[j];
					A[j] = A[j - 1];
					A[j - 1] = tmp;
					
					cnt++;
				}
			}
		}
		
		for(int i = 0; i < N; i++) {
			if(i == N - 1) {
				System.out.print(A[i]);
			} else {
				System.out.print(A[i] + " ");
			}
		}
		System.out.println();
		
		System.out.println(cnt);
	}
}

Measured memory_bytes: 26264
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n;
        cin >> n;
        int a[n];
        for(int &it : a){
            cin >> it;
        }
        int ans = a[0];
        for(int i = 1; i < n; i++){
            ans = (ans / __gcd(ans, a[i])) * a[i];
        }
        cout << ans << '\n';
    }
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
     string s;
     cin >> s;
     rep(i, s.size())cout << "x";
     cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	//pwg or pwgy
	int N;
	cin>>N;
	for(int i=0; i<N; i++){
		string P;
		cin>>P;
		if(P=="Y"){
			cout<<"Four"<<endl;
			break;}
		if((N-1)==i) {cout<<"Three"<<endl;}
	
		
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int a, b, angle;
    double PI = acos(-1);

    cin >> a >> b >> angle;

    double angleA = angle * PI / 180;

    double S = a*b/2 *sin(angleA);

    double L = a + b + sqrt(a*a+b*b-2*a*b*cos(angleA));

    double h = 2 * S / a;

    printf("%lf\n", S);

    printf("%lf\n", L);

    printf("%lf\n", h);

    return 0;
}


Measured memory_bytes: 3416
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 3e5 + 200;
const long long MNN = 1e5;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong n, m, s, t;
vector<int> q[MXN];
llong cnt[MXN];
bool used[MXN];

int main () {
    ios;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        q[u].pb(v + MNN);
        q[u + MNN].pb(v + 2 * MNN);
        q[u + MNN + MNN].pb(v);
    }
    cin >> s >> t;
    queue<llong> lol;
    lol.push(s);
    cnt[s] = 0;
    while(!lol.empty()){
        llong x = lol.front();
        lol.pop();
        for(int i = 0; i < q[x].size(); i++){
            int to = q[x][i];
            if(!used[to]){
                cnt[to] = cnt[x] + 1;
                lol.push(to);
                used[to] = 1;
            }
        }
    }
    if(cnt[t] == 0) cout << -1;
    else cout << cnt[t] / 3;
    
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    int a[n] , b[n], c[n]; 
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) cin >> b[i];
    for(int i=0; i<n; i++) cin >> c[i];
    sort(a, a+n);
    sort(b, b+n);
    sort(c, c+n);
    int x=0;
    int z=0;
    long ans =0;
    for(int i=0; i<n; i++){
        while(x<n && a[x] < b[i]) x++;
        while(z<n && c[z] <= b[i]) z++;
        ans += (long)x*(n-z);
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x, y;
  cin >> x >> y;
  if(y % 2 != 0){
    cout << "No" << endl;
    return 0;
  }
  if(2*x <= y && y <= 4*x){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 3596
a, b = map(int, input().split())

def xor(n):
    m = n % 4
    if m == 0:
        return n
    elif m == 1:
        return 1
    elif m == 2:
        return n+1
    else:
        return 0

print(xor(a-1)^xor(b))

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int main() {
    lint N, H;
    cin >> N >> H;
    vector<pair<lint, lint>> sord(N);
    rep(i, N) cin >> sord[i].first >> sord[i].second;
    sort(sord.rbegin(), sord.rend());

    // rep(i, sord.size()) {
    //     cout << sord[i].first << ' ' << sord[i].second << endl;
    // }

    pair<lint, lint> sordSP = sord.front();
    sord.erase(sord.begin());

    vector<lint> th(0);

    for (int i = 0; i < sord.size(); i++) {
        if (sord[i].second <= sordSP.first) {
            continue;
        } else {
            th.push_back(sord[i].second);
        }
    }
    sort(th.rbegin(), th.rend());

    lint cnt = 0;
    for (int i = 0; i < th.size(); i++) {
        if (H <= sordSP.second) {
            cnt++;
            cout << cnt << endl;
            return 0;
        } else {
            H -= th[i];
            cnt++;
        }
    }

    H -= sordSP.second;
    cnt++;

    cnt += (H + sordSP.first - 1) / sordSP.first;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 5868
fun main(arg: Array<String>) {
    val n = readLine()!!.toInt()
    for (i in 1..n) {
        if (i % 3 == 0 || include3(i)) print(" " + i)
    }
    println("")
}

fun include3(x: Int): Boolean {
    if (x % 10 == 3) { return true }
    else if (x / 10 > 0) {
        if (include3(x / 10)) {
            return true
        }
    }
    return false
}


Measured memory_bytes: 24216
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc =  new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    int N = Integer.parseInt(S[0]);
    int K = Integer.parseInt(S[1]);
    
    long ans1 = 0;
    long ans2 = 0;
    for(int i = 1; i <= N; i++){
      if(K%2 == 0){
        if(i%K == 0){
          ans1++;
        }else if(i%K == K/2){
          ans2++;
        }
      }else if(K%2 != 0 && i%K == 0){
        ans2++;
      }
    }
    ans1 = ans1*ans1*ans1;
    ans2 = ans2*ans2*ans2;
    System.out.println(ans1+ans2);
  }
}

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

using namespace std;

int first(int n){
    while(n){
        if(n < 10)
            return n;
        n /= 10;
    }
    return n;
}

int last(int n){
    return n%10;
}

int a[10][10];

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    
    for(int i=1;i<=n;++i)
        a[first(i)][last(i)]++;
    
    // for(int i=1;i<=9;++i){

    //     for(int j=1;j<=9;++j)
    //         cout << a[i][j] << ' ';
    //     cout << '\n';
    // }
    
    long long counter = 0;
    for(int i=1;i<=9;++i)
        for(int j=1;j<=9;++j)
            counter += a[i][j] * a[j][i];
    
    cout << counter << '\n';

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long int ll;
const ll MOD (1e9+7);
const ll INF (2e9);
const int MAX_N (200001);

int main(void) {
    char *s=new char[15];
    cin>>s;
    // int len=strlen(s);
    int len;
    for(len=0;s[len]!='\0';len++){};
    reverse(s,s+len);
    ll ans=0;
    for(int i=0;i<len;i++){
        for(int j=0;j<=i;j++){//下からi番目の数が10^jの桁とみなされるパターン
            ans+=(s[i]-'0')*pow(10,j)*pow(2,len-i-1)*pow(2,((i-j-1)>=0?(i-j-1):0));//値,left,right
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main (){
	
	int N;
	long long int count=0;
	scanf("%d", &N);
	
	for (int i = 1;i<=N;i++) {
		count; 
		if (i%3==0 || i%5==0) {	
		}
	 else {
			count=count+i ;
		
		}
}
	printf("%lld", count);
	return 0;
	
	
	
}

Measured memory_bytes: 1704
#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

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

typedef pair<int, int> pii;

struct SegmentTree {
	pii init_val;
	int n;
	vector<pii> dat;
	
	SegmentTree(int _n) {
		init_val = pii(-INF, -INF);
		n = 1;
		while (n < _n) n *= 2;
		dat.clear();
		dat.resize(2 * n - 1, init_val);
	}
	
	void update(int k, pii a) {
		k += n - 1;
		dat[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);
		}
	}
	
	pii query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return init_val;
		if (a <= l && r <= b) return dat[k];
		return max(query(a, b, k * 2 + 1, l, (l + r) / 2),
			query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	
	pii query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
};

typedef SegmentTree Seg;

int main() {
	int n, r, l;
	cin >> n >> r >> l;
	
	vector<pii> ans(n, pii(0, 0)); // time, -ID
	REP(i, n) ans[i].second = -i;
	Seg seg(n); // score, -ID
	REP(i, n) seg.update(i, pii(0, -i));
	
	int beft = 0; //??\????????????
	
	while (r--) {
		int d, t, x;
		scanf("%d %d %d", &d, &t, &x);
		d--;
		
		pii tmp = seg.query(0, n); // ?????§????????????????????????score, -ID
		
		ans[-tmp.second].first += t - beft;
		
		seg.update(d, pii(seg.query(d, d + 1).first + x, -d)); 

		beft = t;
	}
	ans[-seg.query(0, n).second].first += l- beft;
	
	sort(ans.rbegin(), ans.rend());
	cout << -ans[0].second + 1 << endl;
	
	return 0;
}

Measured memory_bytes: 3908
N = int(input())
W = list(map(int,input().split()))
sum_all = sum(W)
ans = float("INF")
for t in range(N):
  sum = 0
  for i in range(N):
    if t >= i:
      sum += W[i]
    else:
      break
  ans = min(ans, abs(sum - (sum_all - sum)))
print(ans)

Measured memory_bytes: 3060
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/16
Solved on 2019/2/16
@author: shinjisu
"""


# ABC 118
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


def dmp(x):
    global debug
    if debug:
        print(x)
    return x


def probB():
    N, M = getIntList()
    A = getIntMat(N)
    dmp((N, M))
    dmp(A)
    food = set([])
    food = set(A[0][1:])
    dmp(food)
    for i in range(N):
        food2 = set(A[i][1:])
        food = food & food2
        dmp(food)
    return len(food)


debug = False  # True False
print(probB())


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    return 123


def probD():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    return 123


def probA():
    A, B = getIntList()
    dmp((A, B))
    if B % A == 0:
        return A+B
    else:
        return B-A




Measured memory_bytes: 3064
using static System.Math;
using System;

class M
{
    private const int MOD = 1000000007;
    private readonly int[] _f;
    public int Mul(int a, int b) => (int)(BigMul(a, b) % MOD);
    public M(int n)
    {
        _f = new int[n + 1];
        _f[0] = 1;
        for (int i = 1; i <= n; ++i)
            _f[i] = Mul(_f[i - 1], i);
    }
    public int Fac(int n) => _f[n];
    public int Pow(int a, int m)
    {
        if (m == 0) return 1;
        else if (m == 1) return a;
        var p1 = Pow(a, m / 2);
        var p2 = Mul(p1, p1);
        return ((m % 2) == 0) ? p2 : Mul(p2, a);
    }
    public int Div(int a, int b) => Mul(a, Pow(b, MOD - 2));
    public int Ncr(int n, int r)
    {
        if (n < r) return 0;
        if (n == r) return 1;
        var res = Fac(n);
        res = Div(res, Fac(r));
        res = Div(res, Fac(n - r));
        return res;
    }
}

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var k = int.Parse(line[1]);
        var md = new M(n + k);
        var ans = md.Ncr(n - 1, k - 1);
        Console.WriteLine(ans);
    }
}



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

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const int MAX_A = 100;

int sort(const int N, int (*a)[MAX_A]) {
    int count = 0;

    for (int i = 0; i < N; i++) {
        int min_ind = i;
        for (int j = i + 1; j < N; j++) {
            if ((*a)[j] < (*a)[min_ind]) {
                min_ind = j;
            }
        }
        if (i != min_ind) {
            count++;
            swap((*a)[i], (*a)[min_ind]);
        }
    }

    return count;
}

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

    int A[MAX_A];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int count = sort(N, &A);

    cout << A[0];
    for (int i = 1; i < N; i++) {
        cout << " " << A[i];
    }
    cout << endl;

    cout << count << endl;

    return 0;
}



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

const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const int MOD=1000000007;

int main(){
	ll n;cin>>n;
	if(n%2==1){
		puts("0");
	}
	else{
		ll a=5;
		ll sum=0;
		while(a<=n){
			sum+=n/(a*2);
			a*=5;
		}
		cout<<sum<<endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long int
#define rep(i,a,b)	for(i=a;i<b;i++)
#define M 1000000007
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
int main()
{
	string s1,s2,s3;
	lli i,a,b=0,l,j;
	cin >> a >> b;
	l=max(a+b,a-b);
	l=max(l,a*b);
	cout << l << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
                       ///****   Hasebul Hassan Chowdhury ***////
#define ms(a,v)        memset(a,v,sizeof a)
#define lll            long long
#define FOR(i,a,b)     for(int i=a;i<=b;i++)
#define fast           ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Read           freopen("READ.txt", "r", stdin)
#define Write          freopen("OUTPUT.txt", "w", stdout)
#define INF            1000000007

vector<int>adj[200005];
int visited[200005]={0};
int ans=0,Max=0;;

void Dfs(int i)
{
	if(visited[i]==1) return;
	visited[i]=1;
	ans++;
	Max=max(ans,Max);
	for(int j=0;j<adj[i].size();j++)
	{
		Dfs(adj[i][j]);
	}
}

void solve()
{
    string s,t;
    cin>>s>>t;
    int Min=INT_MAX;
    for(int i=0;i<=s.size()-t.size();i++)
    {
    	int cnt=0;
    	for(int j=0,k=i;j<t.size();j++,k++)
    	{
           if(s[k]!=t[j]) cnt++;
    	}
    	Min=min(Min,cnt);
    }
    cout<<Min<<endl;
}

int main()
{
    fast
    #ifndef ONLINE_JUDGE
    Read;
    Write;
    #endif
    //sieve();
    //int cnt=1;
    //int t; cin>>t; while(t--) solve();
    solve();
}

Measured memory_bytes: 8316
#!/usr/bin/env python3
import sys


def solve(S: str):
    bAC = True

    if S[0] != "A":
        bAC = False

    if S[2:-1].count("C") != 1:
        bAC = False

    if not S.replace("A","").replace("C","").islower():
        bAC = False

    print("AC" if bAC  else "WA")

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

int main() {
    int N; cin >> N;
    int id = 0, a = 0;
    while(N > a) {
        id++;
        a += id;
    }
    if(N == a) {
        rep(i, 1, id + 1) cout << i << '\n';
    } else {
        a -= id;
        id--;
        int n = id - N + a;
        rep(i, 1, id + 1) {
            if(i <= n) cout << i << '\n';
            else cout << i + 1 << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 256
class node:
    def __init__(self,parent, left, right):
        self.parent=parent
        self.left=left
        self.right=right

class binaryTree:

    def __init__(self, datas):
        #format of datas
        #id, left, right
        self.T=[]
        for d in datas:
            self.T.append(node(-1, -1, -1))

        for d in datas:
            self.T[d[0]].left=d[1]
            self.T[d[0]].right=d[2]

        for d in datas:

            id=d[0]
            if(self.T[id].left != -1):
                self.T[self.T[id].left].parent = id
            if (self.T[id].right != -1):
                self.T[self.T[id].right].parent = id

        rootid=-1
        for d in datas:
            if(self.T[d[0]].parent == -1):
                rootid = d[0]
                #print(rootid)

        self.Depth=[-1 for _ in range(len(datas))]
        self.Height=[-1 for _ in range(len(datas))]

        self.setDepth(rootid,0)

        for i in range(len(datas)):
            self.setHeight(i)


    def setDepth(self,id,depth):
        if(id!=-1):
            self.Depth[id]=depth
            self.setDepth(self.T[id].left, depth+1)
            self.setDepth(self.T[id].right, depth + 1)
            return
        return

    def setHeight(self, id):
        h1=0
        h2=0

        if(self.T[id].left != -1):
            h1=self.setHeight(self.T[id].left)+1
        if(self.T[id].right !=-1):
            h2=self.setHeight(self.T[id].right)+1
        self.Height[id]=max(h1,h2)
        return max(h1,h2)

    def getSibring(self,id):
        p=self.T[id].parent
        right=-1
        left=-1

        if(p!=-1):
            right=int(self.T[p].right)
        if(p!=-1):
            left=int(self.T[p].left)

        #print("id="+str(id)+"r="+ str(right) +" l="+str(left))

        if(p == -1):
            return -1
        elif id != left and left != -1 :
            return left
        elif id != right and right != -1 :
            return right
        else:
            return -1


    def printNode(self,id):
        p=self.T[id].parent
        r=self.T[id].right
        l=self.T[id].left

        strs=""
        strs = strs+"node "+ str(id)+":"

        if(p==-1):
            strs=strs+" parent = -1"
        else:
            strs = strs + " parent = " + str(self.T[id].parent)
        strs=strs+", sibling = "+str(self.getSibring(id))

        deg=0
        if(r!=-1):
            deg=deg+1
        if(l!=-1):
            deg=deg+1
        strs=strs+", degree = "+str(deg)
        strs=strs+", depth = "+str(self.Depth[id])
        strs=strs+", height = "+str(self.Height[id])

        if(self.T[id].parent == -1):
            strs=strs+", root"
        elif(self.T[id].right == -1 and self.T[id].left == -1):
            strs=strs+", leaf"
        else:
            strs=strs+", internal node"

        return strs

n=int(input())
dlist=[]
for i in range(n):
    dlist.append(list(map(int,(input().split()))))
t=binaryTree(dlist)
for i in range(n):
    print(t.printNode(i))




















Measured memory_bytes: 5632