akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;

long long h, n, a, b;
long long d[10001];

int main()
{
	cin >> h >> n >> a >> b;

	for (long long j = 1; j <= h; j++)
		d[j] = ((j - 1) / a + 1) * b;

	for (int i = 1; i < n; i++) {
		cin >> a >> b;

		for (int j = 1; j <= h; j++)
			if(j <= a)
				d[j] = min(d[j], b);
			else
				d[j] = min(d[j], d[j - a] + b);
	}

	cout << d[h] << endl;

	return 0;
}

Measured memory_bytes: 384
a,b=map(int,input().split())
l=list(map(int,input().split()))
import itertools
b=min(b,50)
def ku(l):
    y=[0]*a
    for j,x in enumerate(l):
      y[max(0,j-x)]+=1
      r=min(j+x,a-1)
      if r<a-1:
        y[r+1]-=1
    return itertools.accumulate(y)

  
for _ in range(b):
  l=ku(l)
print(*l)

Measured memory_bytes: 173148
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define int long long

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int n, q;
    cin >> n >> q;
    vector<set<tuple<int, int, int> > > st(3);
    st[1].insert(make_tuple(2, n-1, n));
    st[2].insert(make_tuple(2, n-1, n));
    int ans = (n-2)*(n-2);
    for(int qq=0; qq<q; qq++){
        int num, x;
        cin >> num >> x;

        auto itr = st[num].lower_bound(make_tuple(x+1, 0, 0));
        itr--;
        int l = get<0>(*itr);
        int r = get<1>(*itr);
        int fw = get<2>(*itr);
        assert(l <= x && x <= r);
        ans -= fw - 2;
        st[num].erase(*itr);
        st[num].insert(make_tuple(l, x-1, fw));
        st[num].insert(make_tuple(x+1, r, fw));

        // fw の更新
        auto itr2 = st[3-num].lower_bound(make_tuple(fw+1, 0, 0));
        itr2--;
        int ll = get<0>(*itr2);
        int rr = get<1>(*itr2);
        int ffw = min(get<2>(*itr2), x);
        assert(rr <= fw);
        st[3-num].erase(*itr2);
        st[3-num].insert(make_tuple(ll, rr, ffw));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 16092
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cmath>
#include<iomanip>

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n-1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(a, n) sort(a, a+n)
#define VSORT(v) sort(v.begin(), v.end())

using namespace std;

int main()
{
    int l;

    cin >> l;

    double a = double(l / 3.0);

    cout << fixed << setprecision(15) << pow(a, 3) << endl;

    return 0;
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main() {
  int N;
  cin >> N;
  vector<double> a(N);
  rep(i, N) cin >> a.at(i);

  double ans = 0;
  rep(i, N) {
    ans += 1 / a.at(i);
  }
  printf("%.5f", 1 / ans);
}

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

typedef long long LL;
#define dbg(x) cerr << #x"=" << x << endl;
const int MAX_N = 1e5+100;
int cnt[MAX_N], sum[MAX_N];

int main(){
   // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int x;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        cnt[x]++;
    }
    for(int i = 1; i < MAX_N; ++i){
        sum[i] = sum[i-1] + cnt[i];
    }
    int ans = 0;
    for(int i = 1; i < MAX_N; ++i){
        // < k
        if(sum[i-1] == n-sum[i-1]) {
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

/*
>= K
< K
 */

Measured memory_bytes: 1024
loop do
	n, m = gets.split.map(&:to_i)
	break if n == 0

	candidates = (1..20).to_a.repeated_permutation(3).to_a
	r = c = s = 0
	(1..n).each do
		line = gets.chomp
		line =~ /^(\.*)/
		indent = $1.size

		candidates.delete_if do |ir, ic, is|
			ir * r + ic * c + is * s != indent
		end
		
		line.scan(/[(){}\[\]]/) do |bracket|
			case bracket
				when ?(; r += 1
				when ?); r -= 1
				when ?{; c += 1
				when ?}; c -= 1
				when ?[; s += 1
				when ?]; s -= 1
			end
		end
	end

	indents = (1..m).map do
		line = gets.chomp
		a = candidates.map {|ir, ic, is| ir * r + ic * c + is * s}.uniq
		indent = (a.size == 1 ? a[0] : -1)

		line.scan(/[(){}\[\]]/) do |bracket|
			case bracket
				when ?(; r += 1
				when ?); r -= 1
				when ?{; c += 1
				when ?}; c -= 1
				when ?[; s += 1
				when ?]; s -= 1
			end
		end

		indent
	end

	puts indents * ' '
end

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

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

  int n;
  while (cin >> n && n) {
    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
      int c, d;
      cin >> c >> d;

      if (c > d) a += c + d;
      else if (c < d) b += c + d;
      else a += c, b += d;
    }
 
    cout << a << " " << b << '\n';
  }

  return (0);
}



Measured memory_bytes: 3120
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

#include <climits>
#include <cmath>
#include <cstring>

#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;
typedef unsigned long long int ull;


int main()
{
	FAST;
	int arr[200001];
	int n;

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

	int maxx = arr[0];
	int count = 0;
	for(int i=0 ; i<n ; i++)
	{
		if(maxx >= arr[i])
			count++;
		maxx = min(maxx , arr[i]);
	}

	cout << count;
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
int main() {
	long long N;
	cin >> N;
	vector<long long>A(N + 2);
	A.at(0) = 0, A.at(N + 1) = 0;
	vector<long long>Dis(N + 1);
	for (long long i = 1; i <= N; i++) {
		cin >> A.at(i);
	}
	long long sum = 0;
	for (long long i = 0; i <= N; i++) {
		Dis.at(i) = abs(A.at(i) - A.at(i + 1));
		sum += Dis.at(i);
	}
	for (long long i = 1; i <= N; i++) {
		cout << sum - Dis.at(i - 1) - Dis.at(i) + abs(A.at(i - 1) - A.at(i + 1)) << endl;
	}
}

Measured memory_bytes: 2816
#include <iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define loop(i,n) for(int i = 0; i < (n); i++)
#define loops(i,f,n) for(int i = (f); i < (n); i++)
#define INF 1e9
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        if(a+b)
        {
            cout<<min(a,b)<<" "<<max(a,b)<<endl;
        }
    }
}


Measured memory_bytes: 3040
from fractions import gcd
n,m = [int(x) for x in input().split()]
s = input()
t = input()

def f(n,m):
    return n*m // gcd(n,m)

ans = f(n,m)

if s[::ans//m] == t[::ans//n]:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 5432
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();

		int cnt = 0;
		for (int i = 0; i < S.length(); i++) {
			char c = S.charAt(i);
			if (c=='o') {
				cnt++;
			}
		}
		if (cnt + 15-S.length() >=8) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int main()
{
	int n;
	int d[101][101];
	REP(i, 101)REP(j, 101) d[i][j] = (i == j ? 0 : INF);
	cin >> n;
	REP(i, n)
	{
		int a, b;
		cin >> a >> b;
		a--;
		REP(j, b)
		{
			int k;
			cin >> k;
			k--;
			d[a][k] = 1;
		}
	}
	REP(k, 101)REP(i, 101)REP(j, 101) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	int q;
	cin >> q;
	while (q--)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		if (d[a][b] < c) cout << d[a][b]+1 << endl;
		else puts("NA");
	}
	return 0;
}

Measured memory_bytes: 1204
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int r = sc.nextInt();
			if (r == 0) {
				sc.close();
				break;
			}

			int n = sc.nextInt();

			int[] xl = new int[n];
			int[] xr = new int[n];
			int[] h = new int[n];
			for (int i = 0; i < n; i++) {
				xl[i] = sc.nextInt();
				xr[i] = sc.nextInt();
				h[i] = sc.nextInt();
			}

			int[] cover = new int[2 * r];
			for (int i = 0; i < n; i++) {
				int ll = Math.max(0, xl[i] + r);
				int rr = Math.min(r * 2, Math.max(0, xr[i] + r));

				for (int j = ll; j < rr; j++) {
					cover[j] = Math.max(cover[j], h[i]);
				}
			}

			double ans = 100000.0;
			for (int i = 0; i < cover.length; i++) {
				int x = Math.abs(r - i);
				int xx = Math.abs(r - i - 1);
				double o1 = cover[i] - Math.sqrt(r * r - x * x);
				double o2 = cover[i] - Math.sqrt(r * r - xx * xx);
				ans = Math.min(ans, Math.min(o1 + r, o2 + r));
			}

			System.out.println(String.format("%.4f", ans));
		}
	}
}

Measured memory_bytes: 26332
#include<iostream>
#include<functional>
#include<map>
#include<algorithm>

using namespace std;

int main(){
	while( true ){
		int n;
		int nmax = 0;
		int ans = -1;
		map<int,int> m;
		map<int,int>::iterator itm;

		cin >> n;
		if( n == 0 )
			break;

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

		itm = m.begin();
		while( itm != m.end() ){
			if( nmax < itm->second ){
				nmax = itm->second;
				ans = itm->first;
			}
			++itm;
		}

		if( nmax > (double)n/2.0 )
			cout << ans << endl;
		else
			cout << "NO COLOR\n";
	}
	return 0;
}

Measured memory_bytes: 1940
#include <iostream>
#include <cstdlib>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
    map<int, int> iData;
    int iBuff, maxCount = 0, maxElement[100];
    pair<map<int, int>::iterator, bool> flag;
    while(cin >> iBuff)
    {
        flag = iData.insert(map<int, int>::value_type(iBuff, 1));
        if(flag.second == false)
        {
            iData[iBuff]++;
            maxCount = max(maxCount, iData[iBuff]);
        }
    }
    for(map<int, int>::iterator it = iData.begin(); it != iData.end(); it++)
    {
        if(it->second == maxCount )
            cout << it->first << endl;
    }
    return EXIT_SUCCESS;
}

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

using namespace std;

const int N = 200000 + 7;

typedef long long ll;
int main() {
  ll r, g, b, n;
  cin >> r >> g >> b >> n;
  ll rr = n / r;
  ll gg = n / g;
  ll bb = n / b;
  ll ans = 0;
  for(ll i = 0; i <= rr; ++i) {
    ll cur = r * i;
    if(cur > n) break;
    for(ll j = 0; j <= gg; ++j) {
      ll ncur = cur + g * j;
      if(ncur > n) break;
      ll rem = n - ncur;
      //cout << ncur << rem << rem %b << endl;
      if(rem >= 0 && rem % b == 0) {
        //cout << i << j << rem / b << endl;
        ++ans;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}


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

using namespace std;

int main()
{
    char s1[101],s2[101];

    int n;

    cin>>n;

    int sum1=0;
    int sum2=0;

    while(n--)
    {
        cin>>s1>>s2;
        if(strcmp(s1,s2)>0)
        {
            sum2+=3;
        }else if(strcmp(s1,s2)==0)
        {
            sum1+=1;
            sum2+=1;
        }else
        {
            sum1+=3;
        }
    }

    cout<<sum2<<" "<<sum1<<endl;



    return 0;
}



Measured memory_bytes: 3096
#include <cstdio>

int main() {
  char s[10];
  scanf("%s", s);
  int i = 0;
  while (1) {
    if (s[i] == 'A' && s[i+1] == 'C') {
      printf("Yes");
      break;
    } else if (s[i+1] == '\0') {
      printf("No");
      break;
    }
    ++i;
  }
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,k;
	cin >> n >> k;
	vector<int> d(k);
	for(int i = 0; i < k; i++){
		cin >> d[i];
	}

	for(int x = n; x < 100000; x++){
		int tmp = x;
		set<int> s;
		while(tmp!=0){
			s.insert(tmp%10);
			tmp /= 10;
		}
		bool flag = true;
		
		for(int i = 0; i < k; i++){
			if(s.count(d[i])) flag = false;
		}
		if(flag){
			cout << x << endl;
			break;
		}
	}


	return 0;
}

Measured memory_bytes: 256
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0
        negative = [False for _ in range(self.num_v)]
        for i in range(self.num_v - 1):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    negative[dest] = True
                if negative[src]:
                    negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a-1, b-1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])


Measured memory_bytes: 3444
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

int ans = 0;
vector<int>powers;
int restp[41];
bool check(const vector<vector<int>>&tonari,const vector<bool>&oks, const int next, int pow) {
	for (int c = next; c < powers.size(); ++c) {
		if (oks[c]) {
			pow += powers[c];
		}
	}
	return pow > ans;
}
int getans(const vector<vector<int>>&tonari,vector<bool>oks,const int next,const int pow) {
	if (!check(tonari,oks,next,pow))return pow;
	else {
		if (next == powers.size())return pow;
		int nans = 0;
		if(oks[next]){
			vector<bool>noks(oks);
			for (int c = next + 1; c < powers.size(); ++c) {
				if (tonari[next][c])noks[c] = false;
			}
			nans = max(nans, getans(tonari,noks, next + 1, pow + powers[next]));
		}
		nans = max(nans,getans(tonari, oks, next + 1, pow));
		ans = max(ans, nans);
		return nans;
	}

}

struct country {

};

int main() {
	while (1) {
		int N; cin >> N;
		ans = 0;
		memset(restp, 0, sizeof(restp));
		powers.clear();
		if (!N)break;
		vector<string>names;
		vector<vector<string>>rins(N);
		for (int i = 0; i < N; ++i) {
			string a; int  b, c; cin >> a >> b >> c;
			names.push_back(a);
			powers.push_back(b);
			for (int j = 0; j < c; ++j) {
				string st; cin >> st;
				rins[i].push_back(st);
			}
		}
		vector<vector<int>>tonari(N, vector<int>(N));
		for (int i = 0; i < N; ++i) {
			for (auto n : rins[i]) {
				int r = find(names.begin(), names.end(), n) - names.begin();
				tonari[i][r] = true;
			}
		}
		vector<bool>oks(N,true);
		for (int c = 1; c < powers.size(); ++c) {
			if (tonari[0][c])oks[c] = false;
		}
		for (int c = 0; c < N; ++c) {
			restp[c] = accumulate(powers.begin() + c, powers.end(), 0);
		}
		int ans = getans(tonari, oks, 1, powers[0]);
		cout << ans << endl;
	}
	return 0;
}

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

/*
*/

int main() {
  ll N;
  cin >> N;
  vector<ll> h(N);
  rep(i,N){
    cin >> h[i];
  }
  vector<ll> dp(100010,INF);
  dp[0] = 0;
  for(int i = 1;i<N;i++){
    dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]) , dp[i]);
    if(i>=2) dp[i] = min(dp[i-2] + abs(h[i]-h[i-2]) , dp[i]);
  }
  cout << dp[N-1] << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  string s;
  cin >> s;

  bool dp[N+1][4][1000];
  memset(dp, false, sizeof(dp));
  dp[0][0][0] = true;

  REP(i, N) REP(j, 4) REP(k, 1000){
    dp[i+1][j][k] |= dp[i][j][k];
    if(j <= 2 && k*10+(s[i]-'0') < 1000)
      dp[i+1][j+1][k*10+(int)(s[i]-'0')] |= dp[i][j][k];
  }

  int ans = 0;
  REP(k, 1000){
    if(dp[N][3][k]) ans++;
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 117504
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

int main(){
    list<ll> lst;
    ll n;
    cin >> n;

    char com[20];
    ll key;

    REP(i, n){
        scanf("%s%lld", com, &key);
        if(com[0] == 'i'){
            lst.push_front(key);
        }else if(com[0] == 'd' && strlen(com) <= 6){
            auto it = find(lst.begin(), lst.end(), key);
            if(it != lst.end()){
                lst.erase(it);
            }
        }else if(com[6] == 'F'){
            lst.pop_front();
        }else{
            lst.pop_back();
        }
    }

    const ll size = lst.size();
    ll i = 0;
    for(auto it = lst.begin(); it != lst.end(); ++it, ++i){
        printf("%lld", *it);
        if(i + 1 < size){
            printf(" ");
        }else{
            printf("\n");
        }
    }
    return 0;
}



Measured memory_bytes: 34372
/*
Author: CNYALI_LK
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
	int s=0,base=1;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=-base;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
	int cnt=0,fu=1;
	if(a<0){putchar('-');fu=-1;}
	do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
	while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
	putchar(end);
}
int main(){
#ifdef cnyali_lk
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
#endif
	int n,t,x,y,lt=0,lx=0,ly=0;
	n=read();
	for(int i=1;i<=n;++i){
		t=read();x=read();y=read();
		if(((t-lt)<abs(x-lx)+abs(y-ly))||(((t-lt)&1)!=((abs(x-lx)+abs(y-ly))&1))){
			printf("No\n");
			return 0;
		}
		lt=t;lx=x;ly=y;
	}
	printf("Yes\n");
	return 0;
}



Measured memory_bytes: 256
mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1) 
for i in range(k,0,-1): 
   cnt[i]+=pow(k//i,n,mod)
   for j in range(2,k//i+1):
     cnt[i]-=cnt[i*j]
ans=0
for i in range(1,k+1):
   ans+=i*(cnt[i])%mod 
   ans%=mod
print(ans)

Measured memory_bytes: 15204
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(void){
    int n; cin >> n;
    vector<vector<int>>x(n,vector<int>(2));
    for(int i=0;i<n;i++){
        int a,b; cin >>a >> b;
        x[i] = {a+b,a-b};
    }
    sort(x.begin(),x.end());
    // for(int i=0;i<n;i++){
    //     cout << x[i][1] << ' ' << x[i][0] << endl;
    // }cout << endl;
    int ans = 0,start=-1*1e10;
    for(int i=0;i<n;i++){
        if(start <= x[i][1]){
            ans++;
            start = x[i][0];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5888
#

import sys
input=sys.stdin.readline

def main():
    A,B,C=map(int,input().split())
    if (A==B or B==C or C==A) and not A==B==C:
        print("Yes")
    else:
        print("No")
    
    
    
if __name__=="__main__":
    main()


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

namespace Competitive
{
    internal class Solution
    {
        private long[] count;
        
        public void Run()
        {
            int N = int.Parse(Console.ReadLine());
            string march = "MARCH";
            count = Enumerable.Range(0, 5).Select(i => (long)0).ToArray();

            for (int i = 0; i < N; i++)
            {
                string line = Console.ReadLine();
                for (int j = 0; j < 5; j++)
                {
                    if (line[0] == march[j]) count[j]++;
                }
            }

            long ret = dfs0();
            
            Console.WriteLine(ret);
        }

        public long dfs0()
        {
            int[] flags = new int[] {0, 0, 0, 0, 0};
            return dfs(flags, 0);
        }

        // need yield combination
        public long dfs(int[] flags, int current)
        {
            if (flags.Sum() == 3)
            {
                long ret = 1;
                for (int i = 0; i < 5; i++)
                    if(flags[i] == 1)
                       ret *= count[i];
                return ret;
            }
            else
            {
                long ret = 0;
                for (int i = current; i < 5; i++)
                {
                    if (flags[i] == 0)
                    {
                        flags[i] = 1;
                        ret += dfs(flags, i);
                        flags[i] = 0;
                    }
                }

                return ret;
            }
            
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

struct Perm{
    std::vector<int> perm;

    Perm(std::initializer_list<int> p) : perm(p.begin(), p.end()) { }

    static Perm identity(){
        return {0, 1, 2, 3, 4, 5};
    }

    Perm& operator*=(const Perm &rhs){
        std::vector<int> p(6);
        for(int i=0;i<6;++i){
            p[i] = perm[rhs.perm[i]];
        }

        perm = std::move(p);

        return *this;
    }
};

const Perm r1 = {5, 3, 4, 1, 2, 0}, // 表裏をひっくり返す
    r2 = {0, 3, 1, 4, 2, 5}, // 水平面に垂直な軸に関して回転
    r3 = {2, 0, 1, 4, 5, 3}; // 見えている面を変えない回転
std::vector<Perm> perms;

struct Cube{
    std::vector<std::string> surface;

    Cube() = default;
    Cube(std::vector<std::string> v) : surface(std::move(v)) { }

    friend bool operator==(const Cube &lhs, const Cube &rhs){
        for(auto &p : perms){
            bool eq = true;

            for(int i=0;i<6;++i){
                if(lhs.surface[i] != rhs.surface[p.perm[i]]){
                    eq = false;
                    break;
                }
            }

            if(eq){
                return true;
            }
        }

        return false;
    }
};

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

    std::queue<Perm> que;
    que.emplace(Perm::identity());
    que.emplace(r1);
    
    for(int i=0;i<2;++i){
        Perm p = que.front();
        que.pop();

        for(int j=0;j<4;++j){
            que.emplace(p);
            p *= r2;
        }
    }

    for(int i=0;i<8;++i){
        Perm p = que.front();
        que.pop();

        for(int j=0;j<3;++j){
            que.emplace(p);
            p *= r3;
        }
    }

    until(que.empty()){
        perms.emplace_back(que.front());
        que.pop();
    }

    while(true){
        int N;
        std::cin >> N;

        if(N == 0){
            break;
        }

        std::vector<Cube> cubes(N);
    
        for(int i=0;i<N;++i){
            std::vector<std::string> v(6);

            for(int j=0;j<6;++j){
                std::cin >> v[j];
            }

            cubes[i] = std::move(Cube(v));
        }

        ll used = 0;
        int cnt = 0;
        
        for(int i=0;i<N;++i){
            if(used >> i & 1){
                continue;
            }

            cnt += 1;

            for(int j=i+1;j<N;++j){
                if(cubes[j] == cubes[i]){
                    used |= 1ll << j;
                }
            }
        }

        int left = N - cnt;
        std::cout << left << std::endl;
    }
}



Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 333;
string b[N];
int n;

int main() {
    ios::sync_with_stdio(false);
    cout.precision(10);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    int ans = 0;
    for(int o = 0; o < n; o++) {
        bool ok = true;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(b[i][(j + o) % n] != b[j][(i + o) % n]) {
                    ok = false;
                    break;
                }
            }
        }
        ans += ok;
    }
    cout << ans * n << endl;
    return 0;
}

Measured memory_bytes: 384
S = input()
s = S.replace('RL', 'RxL')
s = s.split('x')
ans = []
for i in range(len(s)-1):
    r = s[i].count('R')
    l = s[i+1].count('L')
    rl = r+l
    ans += ['0'] * (r-1)
    if rl % 2 == 0:
        rl = rl//2
        ans += [str(rl),str(rl)]
    else:
        rl =  rl//2
        if r%2 != 0:
            ans += [str(rl+1),str(rl)]
        else:
            ans += [str(rl),str(rl+1)]
    ans += ['0'] * (l-1)
print(' '.join(ans))

Measured memory_bytes: 13316
#include <stdio.h>
#include <vector>
 
using namespace std;
 
struct Node{
    Node(){
        parent = -1;
        depth = num_of_children = 0;
    }
    int parent;
    int depth;
    vector<int> children;
    int num_of_children;
};
 
void calcDepth(Node nodes[],int root_id){
    for(int i = 0;i < nodes[root_id].num_of_children;i++){
        nodes[nodes[root_id].children[i]].depth = nodes[root_id].depth+1;
        calcDepth(nodes,nodes[root_id].children[i]);
    }
}
 
int main(){
    int n,id,k,child_id,root_id;
    scanf("%d",&n);
    Node nodes[n];
 
    for(int i = 0; i < n; i++){
        scanf("%d %d",&id,&k);
        for(int j = 0; j < k; j++){
            scanf("%d",&child_id);
            nodes[id].children.push_back(child_id);
            nodes[id].num_of_children++;
            nodes[child_id].parent = id;
        }
    }
 
    for(root_id = 0; root_id < n; root_id++){
        if(nodes[root_id].parent == -1) break;
    }
 
    calcDepth(nodes,root_id);
 
    for(int i = 0; i < n; i++){
        if(nodes[i].parent == -1){
            printf("node %d: parent = -1, depth = 0, root, ",i);
        }else if(nodes[i].num_of_children == 0){
            printf("node %d: parent = %d, depth = %d, leaf, ",i,nodes[i].parent,nodes[i].depth);
        }else{
            printf("node %d: parent = %d, depth = %d, internal node, ",i,nodes[i].parent,nodes[i].depth);
        }
        printf("[");
        for(int j = 0; j < nodes[i].num_of_children-1; j++){
            printf("%d, ",nodes[i].children[j]);
        }
        if(nodes[i].num_of_children > 0){
            printf("%d",nodes[i].children[nodes[i].num_of_children-1]);
        }
        printf("]\n");
    }
}


Measured memory_bytes: 7280
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

VI g[100010];
int d1[100010], d2[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[x].PB(y);
    g[y].PB(x);
  }

  queue<int> que;
  REP(i, n) d1[i] = INF;
  que.push(0);
  d1[0] = 0;

  while(que.size()) {
    int p = que.front(); que.pop();
    REP(i, g[p].size()) {
      if(d1[g[p][i]] == INF) {
        que.push(g[p][i]);
        d1[g[p][i]] = d1[p] + 1;
      }
    }
  }

  queue<int> que2;
  REP(i, n) d2[i] = INF;
  que2.push(n-1);
  d2[n-1] = 0;

  while(que2.size()) {
    int p = que2.front(); que2.pop();
    REP(i, g[p].size()) {
      if(d2[g[p][i]] == INF) {
        que2.push(g[p][i]);
        d2[g[p][i]] = d2[p] + 1;
      }
    }
  }

  ll f = 0, s = 0;
  REP(i, n) {
    if(d1[i] <= d2[i]) f++;
    else s++;
  }
  //cout << f << " " << s << endl;
  if(f > s) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;

  return 0;
}


Measured memory_bytes: 6656
#![allow(unused_imports)]
#![allow(dead_code)]

use std::io::{ self, BufRead };
use std::iter::Iterator;
use std::cmp::*;
use std::collections::*;

fn sum(mut x: i64) -> i64 {
    let mut y = 0;
    while x > 0 {
        y += x % 10;
        x /= 10;
    }
    y
}

fn main() {
    let stdin = io::stdin();
    let mut cin = stdin.lock();

    let mut it = cin.lines()
    .map(|s| s.unwrap().parse::<i64>().unwrap());
    let n = it.next().unwrap();

    let mut d = it.take(n as usize).collect::<Vec<_>>();
    d.sort();
    let mut ans = 1;
    for i in 1..d.len() {
        if d[i-1] != d[i] { ans += 1; }
    }    

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

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    bool ans = true;
    rep(i,s.length()) {
       if(s[i]!=t[i]) ans = false;

    }

    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 3636
// Package main provides
//
// File:  c.go
// Author: ymiyamoto
//
// Created on Sat Dec  1 15:43:49 2018
//
package main

import "fmt"

var n int

func max(xs []int, exception int) (int, int) {
	count := 0
	val := 0

	for v, c := range xs {
		if v != exception && count < c {
			val = v
			count = c
		}
	}

	return val, count
}

func main() {
	fmt.Scan(&n)

	count1 := make([]int, 1e5+1)
	count2 := make([]int, 1e5+1)

	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)
		if i%2 == 0 {
			count1[v]++
		} else {
			count2[v]++
		}
	}

	val1, c1 := max(count1, 0)
	_, c2 := max(count2, val1)

	val3, c3 := max(count2, 0)
	_, c4 := max(count1, val3)

	if c3+c4 < c1+c2 {
		fmt.Println(n - c1 - c2)
	} else {
		fmt.Println(n - c3 - c4)
	}
}


Measured memory_bytes: 7424
n = int(input())
a = list(map(int, input().split(" ")))
deta = set()
error = False

for i in range(n):
    if n == 0:
        pass
    elif error:
        break
    elif a[i] in deta:
        error = True
        break
    deta.add(a[i])
if error:
    print("NO")
else:
    print("YES")

Measured memory_bytes: 25932
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<=n;++i)
int main(){
  ll n;
  cin>>n;
  ll h,k,w;
  ll p,q;
  rep1(i,3500){
    rep1(j,3500){
      p=n*i*j;
      q=4*i*j-n*i-j*n;
      if(q>0&&p%q==0){
	h=i;
	k=j;
	w=p/q;
	goto FINE;
      }
    }
  }
 FINE:
  if(n%2==0){
    h=n/2;
    w=n;
    k=n;
  }
  cout<<h<<" "<<w<<" "<<k<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
template <class T>
void inputV(vector<T> &x, int n){
  for(int i=0; i<n; i++) cin >> x[i];
}

int main() {
  int n; cin >> n;
  string ans = "Three";
  for(int i=0; i<n; i++) {
    string s; cin >> s;
    if(s == "Y") ans = "Four";
  }

  cout << ans << endl;

  return 0;
}

//


Measured memory_bytes: 256
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
MOD = 10 ** 9 + 7
xx = 0
yy = 0
for i, xi in enumerate(x):
    xx += (2 * i + 1 - n) * xi
for i, yi in enumerate(y):
    yy += (2 * i + 1 - m) * yi
print(xx * yy % MOD)


Measured memory_bytes: 18576
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt() * sc.nextInt();
        int b = sc.nextInt();
        if(a <= b){
            System.out.println(a);
            return;
        }
        System.out.println(b);
    }
}


Measured memory_bytes: 22612
#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 };
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }


ll mod_mul(ll x, ll n, ll mod)
{
	if (n == 0)
		return 0;
	if (x < 0)
		x = (x + mod) % mod;
	if (n < 0)
		n = (n + mod) % mod;
	if ((double)x * n + 1000 < LLONG_MAX)
		return (x * n) % mod;

	ll res = 0;
	while (n > 0)
	{
		if (n & 1)
			res = (res + x) % mod;
		x = x * 2 % mod;
		n /= 2;
	}

	return res;
}
ll ext_gcd(ll a, ll b, ll &x, ll &y)
{
	if (b)
	{
		ll g = ext_gcd(b, a % b, y, x);
		y -= (a / b) * x;
		return g;
	}
	else
	{
		x = 1, y = 0;
		return a;
	}
}
ll mod_inverse(ll a, ll mod)
{
	ll x, y;
	if (ext_gcd((a + mod) % mod, mod, x, y) == 1)
		return (mod + x % mod) % mod;
	else
		return 0;
}
int main()
{
	ios::sync_with_stdio(false);

	const ll mod = 9999999967LL;

	int n;
	cin >> n;
	ll x = 0;
	while (n--)
	{
		int o, y;
		cin >> o >> y;
		if (o == 1)
			x += y;
		else if (o == 2)
			x -= y;
		else if (o == 3)
			x = mod_mul(x, y, mod);
		else
			x = mod_mul(x, mod_inverse(y, mod), mod);

		x = (x + mod) % mod;
	}
	if (x >= 1LL << 31)
		x -= mod;
	cout << x << endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	while (cin >> n, n) {
		vector<int> p(n + 2), t(n + 2);
		vector<vector<int>> dp(n + 2, vector<int>(4, INF));
		for (int i = 1; i <= n; i++) {
			cin >> p[i] >> t[i];
		}
		p[n + 1] = 0;
		t[n + 1] = INF;
		dp[0][0] = 0;
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < 4; j++) {
				if (dp[i][j] == INF) continue;
				if (j < 3 && abs(p[i] - p[i + 1]) * (j + 1) <= t[i + 1] - t[i]) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(p[i] - p[i + 1]));
				if (p[i] * (j + 1) + p[i + 1] <= t[i + 1] - t[i]) dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + p[i] + p[i + 1]);
			}
		}
		int res = INF, last = 0;
		for (int i = 1; i < n + 2; i++) {
			bool ng = true;
			res = INF;
			for (int j = 0; j < 4; j++) {
				if (dp[i][j] != INF) {
					ng = false;
					res = min(res, dp[i][j]);
				}
			}
			if (ng) {
				last = i;
				break;
			}
		}
		if (res != INF) {
			cout << "OK " << res << endl;
		}
		else {
			cout << "NG " << last << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3052
#include <iostream>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main(void)
{
	int N,M; cin >> N>>M;
	vector<int>arr(N, 0);
	int saisyo = 1100000,count= 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		M -= arr[i];
		if (arr[i]<saisyo)
		{
			saisyo = arr[i];
		}
	}
	for (int i = 0; i < 11451419; i++)
	{
		if (M-saisyo>=0)
		{
			M -= saisyo;
			count++;
		}
	}
	cout << count + N << "\n";
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <fstream>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007LL
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pll Dir[4] = {
	{ -1 ,0 },{ 0 , 1 },{ 1 ,0 },{ 0 ,-1 }
};

//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)

struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}

};
typedef vector<vector<Edge>> Graph;

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

ll facmemo[200000] = {};

ll factorial(ll n) {//階乗
	if (facmemo[n] != 0) return facmemo[n];
	if (n == 0) return 1;
	ll ret = n * factorial(n-1);
	ret %= MODU;
	return facmemo[n] = ret;
}

ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x %mod;
		x = x * x%mod;
		n >>= 1;
	}
	return res;
}
ll divmod(ll a, ll b, ll m) { // a/b(mod m)
								  // a/b (mod m)
								  // a*b^-1
								  // b^-1 * b = 1
								  // b^(m-1) = 1 
								  // b^(m-2) * b = 1
								  // b^-1 = b^(m-2)

								  // a/b = a * b^(m-2)

	return (a * 1LL * mod_pow(b, m - 2, m)) % m;
}
ll ncr(ll n, ll r) {
	if (r == 0) return 1;
	if (n < r) return 1;
	return divmod(factorial(n), (factorial(r) * (factorial(n - r))) % MODU, MODU);
}

signed main() {
	int n;
	cin >> n;

	vector<int> a(n), cou(n + 2);
	
	REP(i, n) {
		cin >> a[i];
	}
	sort(ALL(a));

	int sen = 1, cur = 1;
	REP(i, n) {
		if (sen > a[i]) {
			cou[cur]++;
			cur++;
		}
		else {
			sen += 2;
			cou[cur]++;
		}
	}

	ll ans = 1, rest = 0;

	for (int i = n; 1 <= i; i--) {
		rest++;

		ans *= ncr(rest, cou[i]);
		ans %= MODU;
		ans *= factorial(cou[i]);
		ans %= MODU;

		rest -= cou[i];
	}

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


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

int main(){
  int n;
  cin >> n;
  
  cout << 0 << endl;
  int l = 0, r = n-1;
  vector<string> seet(n);
  string start;
  cin >> start;
  if(start == "Vacant") return 0;
  for(int i = 0; i < 20; i++){
    int next = (l + r + 1) / 2;
    cout << next << endl;
    string s;
    cin >> s;
    if(s == "Vacant") return 0;
    bool ok = true;
    if(s == start && next%2) ok = false;
    if(s != start && next%2 == 0) ok = false;
    if(ok) l = next;
    else r = next;
  }
}

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


bool CanGo(int y, int x, int R, int C) {
	return y >= 0 && y < R&& x >= 0 && x < C;
}

int TraceMaze(queue<vector<int>>& Queue, vector<vector<char>>& Map) {
	vector<int> nowstate = Queue.front();
	Queue.pop();
	int R = Map.size();
	int C = Map[0].size();
	int ny = nowstate[0];
	int nx = nowstate[1];
	int step = nowstate[2];

	if (Map[ny][nx] == '.') {
		if (CanGo(ny + 1, nx, R, C))Queue.push({ ny + 1,nx,step + 1 });
		if (CanGo(ny - 1, nx, R, C))Queue.push({ ny - 1,nx,step + 1 });
		if (CanGo(ny, nx + 1, R, C))Queue.push({ ny ,nx + 1,step + 1 });
		if (CanGo(ny, nx - 1, R, C))Queue.push({ ny ,nx - 1,step + 1 });
		Map[ny][nx] = '#';
		return step;
	}
	else {
		return step-1;
	}
}

int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<char>> map(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> map[i][j];
		}
	}
	int Max = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (map[i][j] == '#') continue;
			queue<vector<int>> Queue;
			vector<vector<char>> map2 = map;
			Queue.push({ i,j,0 });
			int ans = 0;
			while (!Queue.empty()) ans = TraceMaze(Queue, map2);
			//cout << i << "," << j << ":" << ans << endl;
			Max = max(ans, Max);
		}
	}
	cout << Max << endl;
}


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

cdy=0
for i in range(n-1):
    ai=a[i]
    aip=a[i+1]
    if a[i]>x:
        a[i]=x
        cdy=cdy+ai-x
    ai=a[i]
    if a[i]+a[i+1]>x:
        a[i+1]=x-a[i]
        cdy=cdy+ai+aip-x

print(cdy)        
        

Measured memory_bytes: 14152
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
//#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	long long int ans = -1;
	long long int c = 1;
	long long int k;
	cin >> k;
	long long int a = 7;
	long long int b;
	if (k % 2 == 0 || k % 5 == 0)
	{
		ans=-1;
		cout << ans << endl;
	}
	else
	{
		for (int i = 0; i < 100*k; i++)
		{
			if (a == 0)
			{
				ans = c;
				break;
			}
			else if (a < k)
			{
				c++;
				a = a * 10 + 7;
			}
			else
			{
				b = a / k;
				//cout << b << "=" << a <<"/"<<k<< endl;
				a = a - (b * k);
			}

			//cout << ans << ":" << a<<endl;
		}
		cout << ans << endl;
	}

}


	
	

	
	
/**/
/*#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.141592653589793

int main(void) {
	return 0;
}
*/

Measured memory_bytes: 3636
package main

import (
	"fmt"
)

func main() {
	var N, M int
	fmt.Scanf("%d%d", &N, &M)
	np := make(map[int]int)
	mnp := 0
	p := 2
	for M > 1 {
		if M%p != 0 {
			p++
			continue
		} else {
			M /= p
			np[p]++
			if mnp < np[p] {
				mnp = np[p]
			}
		}
	}
	b := make([]int, mnp+1)
	b[0] = 1
	for i := 1; i <= mnp; i++ {
		bb := b[i-1] * (N + i - 1)
		for bb%i > 0 {
			bb += 1000000007
		}
		b[i] = (bb / i) % 1000000007
	}
	ans := 1
	for _, n := range np {
		ans *= b[n]
		ans %= 1000000007
	}
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 512
# frozen_string_literal: true

H, W, K = gets.chomp.split.map(&:to_i)
board = H.times.map do
  gets.chomp.split('')
end

def copy(board)
  board.map(&:dup)
end

def count_black(board)
  ans = 0
  board.each do |line|
    line.each do |block|
      ans += 1 if block == '#'
    end
  end
  ans
end

def paint(board, yoko_count, tate_count)
  ans = 0
  (0..(W - 1)).to_a.combination(tate_count) do |gyo|
    (0..(H - 1)).to_a.combination(yoko_count) do |retu|
      copied = copy board
      gyo.each do |x|
        (0..H - 1).each do |y|
          copied[y][x] = 'r'
        end
      end
      retu.each do |y|
        copied[y].each_with_index do |_, x|
          copied[y][x] = 'r'
        end
      end
      ans += 1 if (count_black copied) == K
    end
  end
  ans
end

count = 0

(0..H).each do |yoko_count|
  (0..W).each do |tate_count|
    count += paint(board, yoko_count, tate_count)
  end
end

puts count


Measured memory_bytes: 14368
#include <bits/stdc++.h>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()



using namespace std;



int main() {
 ll N,K; cin>>N>>K;
 N = N % K;
 ll ans = min(N,K - N % K);
 cout<<ans<<endl;





  

  return 0;
}

Measured memory_bytes: 256
H=[]
W=[]
while 1:
    h,w=map(int,raw_input().split())
    if h==w==0:
        break
    H.append(h)
    W.append("#"*w)
for i in xrange(len(W)):
    for j in xrange(H[i]):
        print(W[i])
    print

Measured memory_bytes: 6364