akhauriyash/Code-Regression huggingface dataset:
/* AOJ 0060
 *
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0060
 *
 */

#include <stdio.h>
#define DEBUG 0


float odds(int* cards){
    int available[11];
    int i;
    int yes = 0;
    int no = 0;
    int sum;
    
    for(i=1;i<11;i++){
        available[i] = (
                (cards[0] != i)
                &&
                (cards[1] != i)
                &&
                (cards[2] != i)
                );
        if(DEBUG)
            printf("%d %d\n", i, available[i]);
    }
    sum = cards[0] + cards[1];

    for(i=1;i<11;i++){
        if(available[i]){
            if(sum + i < 21){
                yes += 1;
            }else{
                no += 1;
            }

        }
    }

    return yes/7.0;
}

int main(){
    int cards[3];

    while(scanf("%d %d %d", cards, cards+1, cards+2) == 3){

        if(DEBUG)
            printf("%d %d %d\n", cards[0], cards[1], cards[2]);
        if(odds(cards) < 0.50){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int main(){
    int a,b,c,ans;
    scanf("%d%d%d",&a,&b,&c);
    if(a==b&&b==c&&a==c) printf("1");
    else if(a==b||b==c||a==c) printf("2");
    else printf("3");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
   	
int main() {
	int counter = 0;
	int n, d;

	cin >> n >> d;
	double sum = 0;
	double x[n][d];

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < d; j++)
		{
			cin >> x[i][j];
		}
	}

	for (int i = 0; i < n-1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			sum = 0;
			for (int k = 0; k < d; k++)
			{
				sum = sum + (x[i][k] - x[j][k])*(x[i][k] - x[j][k]);
			} 
			sum = sqrt(sum);
			// cout << sum;
			if (ceil(sum) == floor(sum))
			{
				counter++;
			}
		}
	}

	cout << counter;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  ll x,a,b; cin >> x >> a >> b;
  if(b-a<=0) cout << "delicious" << endl;
  else if(b-a>=x+1) cout << "dangerous" << endl;
  else cout << "safe" << endl;
}


Measured memory_bytes: 256
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,M = [int(x) for x in input().split()]
xls = [int(x) for x in input().split()]
xls.sort()
dls = [xls[i+1]-xls[i] for i in range(M-1)]
if N >= M:
    ans = 0
else:
    dls.sort()
    ans = sum(dls[0:M-N])

print(ans)

Measured memory_bytes: 13840
#include <stdio.h>

int main (void){
  int n,a[1001],h,i,j,v;

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

  for(i=1;i<=n;i++){
    for(h=0;h<n;h++){
      printf("%d",a[h]);
      if(h!=n-1) printf(" ");
    }
    printf("\n");
    v=a[i];
    j=i-1;
    if(i!=n){
      while(j>=0 && a[j]>v){
	a[j+1]=a[j];
	j--;
      }
      a[j+1]=v;
    }
  }
  return(0);
}



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

int main() {
	int A, B;
	cin >> A >> B;
	for (int i = 0;; i++) {
		if ((A - 1) * i + 1 >= B) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int k,n,i,a[200000],b,min;
	cin>>k>>n;
	min=k;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(i=0;i<n;i++)
	{
		if(i==n-1)
		{
			b=k+a[0]-a[n-1];
			b=k-b;
			if(b<min)
			min=b;
		}
		else
		{
			b=k-(a[i+1]-a[i]);
			if(b<min)
			min=b;
		}
	}
	cout<<min;
}


Measured memory_bytes: 1024
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]
INF = float('inf')
for i in range(1, n):
  act = INF
  for j in range(k):
    if i-j > 0:
      act = min(act, dp[-1-j]+abs(h[i]-h[i-j-1]))
  dp.append(act)
print(dp[-1])

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

int n,m,x,a,b,c;
bool arr[10005][10005];
char y;
queue < pair < pair <int,int> , int> > q;

int main(){
	cin>>n>>m;
	x = n*m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>y;
			if(y == '#'){ 
				arr[i][j] = 1;
				q.push(make_pair(make_pair(i,j),0));
			}
		}
	}
	while(x>1){
		a = q.front().first.first;
		b = q.front().first.second;
		c = q.front().second;
		q.pop();
		x--;
		if(a>1 && arr[a-1][b] == 0){
			q.push(make_pair(make_pair(a-1,b),c+1));
			arr[a-1][b] = 1;
		}
		if(a<n && arr[a+1][b] == 0){
			q.push(make_pair(make_pair(a+1,b),c+1));
			arr[a+1][b] = 1;
		}
		if(b>1 && arr[a][b-1] == 0){
			q.push(make_pair(make_pair(a,b-1),c+1));
			arr[a][b-1] = 1;
		}
		if(b<m && arr[a][b+1] == 0){
			q.push(make_pair(make_pair(a,b+1),c+1));
			arr[a][b+1] = 1;
		}
	}
	c = q.front().second;
	q.pop();
	cout<<c<<endl;
}

Measured memory_bytes: 21520
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Template
{
    public class Scanner
    {
        public string NextLine => Console.ReadLine();
        public int NextInt => int.Parse(NextLine);
        public long NextLong => long.Parse(NextLine);
        public double NextDouble => double.Parse(NextLine);
 
        public string[] StrAry(char separator = ' ') => Console.ReadLine().Split(separator);
        public int[] IntAry(char separator = ' ') => Array.ConvertAll(StrAry(separator), int.Parse);
        public long[] LongAry(char separator = ' ') => Array.ConvertAll(StrAry(separator), long.Parse);
        public double[] DoubleAry(char separator = ' ') => Array.ConvertAll(StrAry(separator), double.Parse);
    }
 
    internal class Template
    {
        public static void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
        private static void Fill<T>(T[] src, T value, int len) { for (int i = 0; i < len; i++) { src[i] = value; } }
 
        static void Solve() 
        {
            var scan = new Scanner();
            var line = scan.IntAry();
            var tuple = Tuple.Create(line[0] * line[1], line[2] * line[3]);
            Console.WriteLine((tuple.Item1 > tuple.Item2) ? tuple.Item1 : tuple.Item2);            
        }
 
        private static void Main()
        {
            Console.SetOut(new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a,b); }
void Mul(int &a, int b){ a = mul(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
cs int N = 1e7 + 50;
int n, A, fc[N], ifc[N], iv[N];
int C(int n, int m){ return mul(fc[n],mul(ifc[n-m],ifc[m])); }
void fc_init(int n){
	fc[0]=fc[1]=ifc[0]=ifc[1]=iv[1]=1;
	for(int i=2;i<=n;i++)fc[i]=mul(fc[i-1],i);
	for(int i=2;i<=n;i++)iv[i]=mul(Mod-Mod/i,iv[Mod%i]);
	for(int i=2;i<=n;i++)ifc[i]=mul(ifc[i-1],iv[i]);
}
int calc(int a, int b, int c){ return mul(fc[a+b+c],mul(a,iv[a+b])); }
int main(){
	scanf("%d%d",&n,&A);
	fc_init(n); int ans=0;
	for(int i=1;i<=A;i++)
	for(int j=1,coe;j<=i;j++){
		coe=C(i,j);if((i-j)&1)coe=dec(0,coe);
		Mul(coe,calc(j,n-A,max(0,A-i-1)));
		Add(ans,coe);
	} cout<<ans; return 0;
}

Measured memory_bytes: 120924
// #define DEBUG_MODE
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;
typedef vector< int > vi;
typedef pair< int, int > ii;
typedef vector< ii > vii;
typedef vector< ll > vll;
#ifdef DEBUG_MODE
	#define errp(...) fprintf(stderr, __VA_ARGS__)
#else
	#define errp(...)
#endif
#define dbg(x) errp("[%s = %d]\n", #x, x)

int main () { 
#ifdef DEBUG_MODE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	ll x = b / c - (a - 1) / c;
	ll y = b / d - (a - 1) / d;
	ll g = (c * d) / __gcd(c, d);
	ll z = b / g - (a - 1) / g;

	// printf("x, y, z = %lld, %lld, %lld\n", x, y, z);
	printf("%lld\n", b - a + 1 - (x + y - z));
}

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

int main(){
  int N,K;
  cin >> N >> K;
  int ans = 0;
  for(int i = 0; i < N; ++i){
    int x;
    cin >> x;
    if(x < abs(K - x)) ans += x * 2;
    else ans += abs(K - x) * 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
import sys
from heapq import heappush, heappop
from collections import deque
from itertools import permutations
input = sys.stdin.readline

def dijkstra(N, start, adj_dict):
    distance = [float('inf')] * N
    distance[start] = 0
    priority_queue = []
    
    for i in range(N):
        heappush(priority_queue, (distance[i], i))
        
    while len(priority_queue) > 0:
        (current_dist, current_node) = heappop(priority_queue)
        if distance[current_node] < current_dist:
            continue
        for next_node, w in adj_dict[current_node]:
            if distance[next_node] >= distance[current_node] + w:
                distance[next_node] = distance[current_node] + w
                heappush(priority_queue, (distance[next_node], next_node))
    
    return distance

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj_dict = {i: deque([]) for i in range(N)}

for _ in range(M):
    a_i, b_i, c_i = map(int, input().split())
    adj_dict[a_i-1].append((b_i-1, c_i))
    adj_dict[b_i-1].append((a_i-1, c_i))

distance_map = [dijkstra(N, start, adj_dict) for start in range(N)]
ans = 1000000000

for route in permutations(r):
    ans_cand = 0
    
    for i in range(len(route)-1):
        ans_cand += distance_map[route[i]-1][route[i+1]-1]
    
    ans = min([ans, ans_cand])

print(ans)


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

long long N, M, done = 0;
vector<long long> A, B;
long long ans = 0;

bool judge(long long mid){
    long long count = 0;
    int j = 0;
    for(int i=N-1; i>=0; i--){        
        //符号をどうしたらいいのかわからないポイント１
        while(mid <= A[i]+A[j] && j<N) j++;
        count += j;
    }
    //符号をどうしたらいいのかわからないポイント２
    if(count >= M) return true;
    else return false;
}

int main(){
    cin >> N >> M;
    A.resize(N);
    B.resize(N+1);
    for(int i=0; i<N; i++) cin >> A[i];
    sort(A.rbegin(), A.rend());
    /*
    cout << "sorted_A : " << endl;
    for(int i=0; i<N; i++) cout << A[i] << " ";
    cout << endl;
    */
    for(int i=1; i<N+1; i++){
        B[i] = B[i-1] + A[i-1];
    }

    long long right = (A[0]*2 + 1)*M;
    long long left = 0;
    long long mid;
    while(left+1 < right){
        mid = (left + right)/2;
        if(judge(mid)) left = mid;
        else right = mid;
    }
    //cout << "left = " << left << endl << endl;

    int j = 0;
    for(int i=N-1; i>=0; i--){
        //符号をどうしたらいいのかわからないポイント３
        while(left <= A[i] + A[j] && j<N) j++;
        ans += B[j] + A[i]*j;
        /*
        cout << "i = " << i << " j = " << j << endl;
        cout << "A[i]+A[j] = " << A[i] + A[j] << endl;
        cout << "B[j] = " << B[j] << endl;
        cout << "ans = " << ans << endl << endl;
        */
        done += j;
    }
    //cout << "ans_before = " << ans << endl;
    ans -= left * (done-M);
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, std::vector<long long> P){
  set<ll> s;
  ll ans=0;
  REP(N){
    if(s.lower_bound(P[i])==s.begin()){
      ++ans;
    }
    s.insert(P[i]);
  }
  cout<<ans<<endl;
}

int main(){
  cout<<setprecision(1000);
  cin.tie(0);
  ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> P(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&P[i]);
    }
    solve(N, std::move(P));
    return 0;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> X(N);
    for(int i = 0; i < N; i++){
        cin >> X[i];
    }
    long long ans = 0;
    for(int i = 0; i < N; i++){
        ans += (X[i] - X[0])*(X[i] - X[0]);
    }
    for(int i = 1; i < 100; i++){
        int p = i;
        long long a = 0;
        for(int i = 0; i < N; i++){
            a += (X[i] - p)*(X[i] - p);
        }
        if(a < ans) ans = a;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	final long MOD = (long) 1e9 + 7;

	void run() {
		Scanner sc = new Scanner(System.in);
		long S = sc.nextLong();// 1e18
		long a = (long) Math.sqrt(S);
		while (a * a < S) {
			++a;
		}
		long X1 = a;
		long Y1 = 1;
		long X2 = a * a - S;
		long Y2 = a;
		long X3 = 0;
		long Y3 = 0;
		System.out.println(X1 + " " + Y1 + " " + X2 + " " + Y2 + " " + X3 + " " + Y3);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 23636
L, R = map(int, input().split())

ans = 2018
tmp = 0

for i in range(L, R):
	for j in range(i + 1, R + 1):
		tmp = (i * j) % 2019

		if tmp == 0:
			ans = tmp
			print(ans)
			exit()
		else:
			ans = min(tmp, ans)

print(ans)

Measured memory_bytes: 39024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> isUsed(n);
    sort(all(a));
    int cnt = 0;
    ll x, y;
    for(int i = n-1; i  > 0; i--){
        if (a[i] == a[i-1] && isUsed[i] == 0){
            isUsed[i-1] = 1;
            cnt++;
            if (cnt == 1) x = a[i];
            else {
                y = a[i];
                break;
            }
        }
    }
    ll ans = x * y;
    if (cnt == 2) cout << ans << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 3980
#include <iostream>
using namespace std;
int main(void){
    string S;
    cin >> S;
    
    if( S.at(0) == S.at(1) && S.at(2) == S.at(3) && S.at(1) != S.at(2))
    {std::cout << "Yes" << std::endl;}
    
    else if( S.at(0) == S.at(2) && S.at(1) == S.at(3) && S.at(0) != S.at(1) )
    {std::cout << "Yes" << std::endl;}
    
    else if( S.at(0) == S.at(3) && S.at(1) == S.at(2) && S.at(0) != S.at(1) )
    {std::cout << "Yes" << std::endl;}
    
    else {std::cout << "No" << std::endl;}
    }

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

int main(){
  int a=0,w=0,t=0,r=0;
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    if(s=="AC"){
      a++;
    }
    else if(s=="WA"){
      w++;
    }
    else if(s=="TLE"){
      t++;
    }
    else{
      r++;
    }
  }
  cout<<"AC x "<<a<<endl;
  cout<<"WA x "<<w<<endl;
  cout<<"TLE x "<<t<<endl;
  cout<<"RE x "<<r<<endl;
}

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

int N;
std::string S;
std::vector<int> Mtable;

int64_t solve();

int main()
{
	scanf("%d", &N);
	std::cin >> S;
	Mtable.resize(N + 1);
	for (int i{N - 1}; i >= 0; i--)
	{
		if (S[i] == 'M') Mtable[i]++;
		Mtable[i] += Mtable[i + 1];
	}
	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
		printf("%lld\n", solve());

	return 0;
}

int64_t solve()
{
	int k;
	scanf("%d", &k);

	int64_t ans{}, count{}, sum{};
	for (int i{N - 1}; i >= 0; i--)
	{
		if (i + k < N && S[i + k] == 'C')
		{
			count--;
			sum -= Mtable[i + 1] - Mtable[i + k];
		}
		if (S[i] == 'D')
			ans += sum;
		else if (S[i] == 'M')
			sum += count;
		else if (S[i] == 'C')
			count++;
	}
	return ans;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x)  (x).begin(),(x).end()

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> mp;

const int MOD = 1e9 + 7;


int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }
    int ans = __gcd(a[0], a[1]);
    for (int i = 2; i < n; ++i) {
        ans = __gcd(ans, a[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, k;
int a[110];

ll dp[110][100100];

ll solve() {
    dp[0][k] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][k] = 1;
        for (int j = k-1; j >= 0; j--) {
            dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % mod;
            if (j+a[i-1]+1 <= k) {
                dp[i][j] += mod - dp[i-1][j+a[i-1]+1];
                dp[i][j] %= mod;
            }
        }
    }
    return dp[n][0];
}

void input() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


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

using namespace std;

int main(void){
	while(1){
		int a,n;
		char str[10001];
		cin >> n;
		if(n==0)break;
		for(a=0;a<n;a++){
			int m,e,j;
			cin >> m >> e >> j;
			if(m==100 || e==100 || j==100)str[a]='A';
			else if(m+e>=180)str[a]='A';
			else if(m+e+j>=240)str[a]='A';
			else if(m+e+j>=210)str[a]='B';
			else if(m+e+j>=150 && m>=80 || e>=80)str[a]='B';
			else str[a]='C';
		}
		for(a=0;a<n;a++){
			cout << str[a] << endl;
		}

	}
}

Measured memory_bytes: 0
#include <stdio.h>

#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)

int main(void) {
	int a,b,c,d;
	
	scanf("%d %d %d %d", &a, &b, &c, &d);
	
	if (b < c || d < a) {
		puts("0");
	} else {
		printf("%d\n", MIN(b,d)-MAX(a,c));
	}
	
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  int a,b;
  a = N * 8 / 108;
  b = (N - a)*1.08;
  if(N == b){
    cout << N-a << endl;
  }else{
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0;i < N;i++)
int main(){
  int N;
  int size;
  string s;

  while(cin >> N,N){
    cin >> size >> s;
    
    char c = 'O';
    int cnt = 0;
    int sum = 0;
    
    Rep(i,size) {
      if(cnt >= N * 2 + 1 && cnt % 2 == 1){
	sum++;
      }
      if(s[i] == c)cnt = 0;
      if(cnt)cnt++;
      if(s[i] == 'I' && !cnt)cnt = 1;
      c = s[i];
    }    
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 3932
#include <iostream>
#include <map>
#include <utility>
using namespace std;

typedef long long lint;

int root(int *uni,int a){
    if(uni[a]<0) return a;
    else return uni[a]=root(uni, uni[a]);
}
bool connect(int *uni,int ia,int ib){
    int a=root(uni,ia),b=root(uni,ib);
    if(a==b) return false;

    if(uni[a]>uni[b]){
        uni[b]+=uni[a];
        uni[a]=b;
    }else{
        uni[a]+=uni[b];
        uni[b]=a;
    }
    return true;
}

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

    int *road,*train;
    road=new int[N+1];
    train=new int[N+1];
    for(int i=0;i<N;i++) road[i]=train[i]=(-1);

    int p,q,r,s;
    for(int i=0;i<K;i++){
        cin >> p >> q;
        connect(road,p-1,q-1);
    }
    for(int i=0;i<L;i++){
        cin >> r >> s;
        connect(train,r-1,s-1);
    }

    map<pair<int,int>,int> roots;

    for(int i=0;i<N;i++) roots[make_pair(root(road,i),root(train,i))]++;

    for(int i=0;i<N;i++){
        cout << roots[make_pair(root(road,i),root(train,i))];

        if(i==N-1) cout << endl;
        else cout << ' ';
    }
    
    delete[] road,train;
    return 0;
}//

Measured memory_bytes: 13568
// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 1e6 + 5;
const int MOD = 998244353;

int N, M;

void input()
{
    read(N); read(M);
}

LL fac[MAXN], ifac[MAXN];

LL fpm(LL base, LL exp)
{
    LL ret = 1;
    for (; exp; exp >>= 1) {
        if (exp & 1)
            (ret *= base) %= MOD;
        (base *= base) %= MOD;
    }
    return ret;
}

inline LL C(int n, int k)
{
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

void solve()
{
    if (N < M)
        std::swap(N, M);

    int rng = N + M;
    fac[0] = 1;
    for (int i = 1; i <= rng; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifac[rng] = fpm(fac[rng], MOD - 2);
    for (int i = rng; i >= 1; --i) {
        ifac[i - 1] = ifac[i] * i % MOD;
    }

    LL t = 0;
    for (int i = 1; i <= M; ++i) {
        (t += C(i * 2, i) * C(N + M - i * 2, N - i)) %= MOD;
    }
    LL ans = (t * fpm(C(N + M, N) * 2, MOD - 2) + N) % MOD;

    printf("%lld\n", ans);
}

int main()
{
#ifdef __DEBUG
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif

    input();
    solve();
}

// 柳如眉，云似发，鲛绡雾縠笼香雪。
//     -- 魏承班《渔歌子·柳如眉》


Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6+10;
bool boo[maxn];
int cnt[maxn];
int b[maxn];
int main(){
	LL n;
  	cin>>n;
  	for (int i=2;i<maxn;i++) if (!boo[i]){
      	while (n % i == 0) {
          	n /= i;
          	cnt[i]++;
        }
      	if (1LL * i * i >= 1LL * maxn) continue;
      	for (int j=i*i;j<maxn;j+=i) boo[i] = true;
      	if (n == 1) break;
    }
  	int nt = 1, ti = 1;
  	for (int i=1;i<maxn;i++) {
    	if (i == nt){
        	b[i] = ti;
          	ti++;
          	nt += ti;
        }else b[i] = b[i-1];
    }
   	LL ans = 0;
  	for (int i=2;i<maxn;i++) ans += b[cnt[i]];
  	if (n > 1) ans++;
  
  	cout<<ans<<endl;
  	return 0;
}


Measured memory_bytes: 7512
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
vector<vector<int>> G;
vector<int> vis;
vector<int> vert;
void dfs(int cur, int par = -1, int num = 1){
    if(vis[cur]) return;

    if(G[cur].size() == 0) return;
    vis[cur] = num;
    vert.pb(cur);
    for(int v: G[cur]){
        if(par == v) continue;
        dfs(v, cur, num + 1);
    }
}

template <typename T> inline void voutput(T &v){
    rep(i, v.size()){
        if (i) cout << " " << v[i];
        else cout << v[i];
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N, M;
    cin >> N >> M;
    G.resize(N);
    vis.assign(N, 0);
    

    rep(i, M){
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].pb(v), G[v].pb(u);
    }
    
    
    ll ans = 0;
    
    ll odd = 0;
    ll even = 0;
    
    rep(i, N){
        vert.clear();
        dfs(i);
        if(vert.size() < 2) continue;
        bool loop = false;
        for(int v: vert){
            for(int w: G[v]){
                if((vis[v] - vis[w]) % 2 == 0){
                    loop = true;
                }
            }
        }
//        cout << "vert:";
//        voutput(vert);
//        cout << i << ":" << loop << endl;
        if(loop) even++;
        else odd++;
    }
//    voutput(vis);
    ll rest = 0;
    rep(i, N) if(vis[i] > 0) rest++;
//    cout << odd << "," << even << "," << rest << endl;
    ans += (odd + even) * (odd + even) + odd * odd;
    ans += (N - rest) * (N - rest) + 2 * (N - rest) * rest;
    
    output(ans);
    
    return 0;
}

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

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

    vector<vector<vector<long double>>> ans(N + 1, vector<vector<long double>>(N + 1, vector<long double>(N + 1)));

    ans[0][0][0] = 0;

    for(auto i = 1; i <= N; ++i)ans[0][0][i] = ans[0][0][i - 1] + N / static_cast<long double>(i);

    for(auto i = 1; i <= N; ++i){
        ans[0][i][0] = ans[0][i - 1][1] + N / static_cast<long double>(i);
        for(auto j = 1; j <= N - i; ++j)
            ans[0][i][j] = (ans[0][i - 1][j + 1] * i + ans[0][i][j - 1] * j + N) / static_cast<long double>(i + j);
    }

    for(auto i = 1; i <= N; ++i){
        ans[i][0][0] = ans[i - 1][1][0] + N / static_cast<long double>(i);
        for(auto j = 1; j <= N - i; ++j)
            ans[i][0][j] = (ans[i - 1][1][j] * i + ans[i][0][j - 1] * j + N) / static_cast<long double>(i + j);
        for(auto j = 1; j <= N - i; ++j){
            ans[i][j][0] = (ans[i - 1][j + 1][0] * i + ans[i][j - 1][1] * j + N) / static_cast<long double>(i + j);
            for(auto k = 1; k <= N - i - j; ++k)
                ans[i][j][k] = (ans[i - 1][j + 1][k] * i + ans[i][j - 1][k + 1] * j + ans[i][j][k - 1] * k + N) / static_cast<long double>(i + j + k);
        }
    }

    uint_fast32_t x(0), y(0), z(0);

    for(auto i = 0, a = 0; i < N; ++i){
        scanf("%d", &a);
        ++(a == 1 ? x : a & 1 ? z : y);
    }

    printf("%.12Lf\n", ans[z][y][x]);

    return 0;
}

Measured memory_bytes: 431360
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair


void solve(){
 	
 	string s1,s2,s3;
 	cin>>s1>>s2>>s3;
 	queue<char> sa,sb,sc;
 	for(int i=0;i<s1.size();i++){
 		sa.push(s1[i]);
 	}
 	for(int i=0;i<s2.size();i++){
 		sb.push(s2[i]);
 	}
    for(int i=0;i<s3.size();i++){
 		sc.push(s3[i]);
 	}
 	char pop='a';
  int t=1;
 while(t ){
 	if(pop=='a'  ){
 		if(sa.empty()){ cout<<"A"<<endl; return ;}
 		 pop=sa.front();
 		 sa.pop();
 	}
 	else if(pop=='b'  ){
 		if(sb.empty()){ cout<<"B"<<endl; return ;}
 		 pop=sb.front();
 		 sb.pop();
 	}
 	else if(pop=='c'  ){
 		if(sc.empty()){ cout<<"C"<<endl; return ;}
 		 pop=sc.front();
 		 sc.pop();
 	}


}
 	
}



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

  fast
  ll t=1;
 
  while(t--){
  	solve();
  }

return 0;
  
}

Measured memory_bytes: 3592
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N, M = na[0], na[1]
    p = list(map(int, input().split()))
    x_list = [None] * (N + 1)
    y_list = [None] * (N + 1)
    for i in range(M):
        na = list(map(int, input().split()))
        x, y = na[0], na[1]
        if x_list[x] is None:
            x_list[x] = [y]
        else:
            x_list[x].append(y)
        if y_list[y] is None:
            y_list[y] = [x]
        else:
            y_list[y].append(x)

    visited = [False] * (N + 1)
    connections = [None] * (N + 1)
    for i in range(1, N + 1):
        if not visited[i]:
            q = []
            c = set()
            visited[i] = True
            q.append(i)
            while 0 < len(q):
                j = q.pop(0)
                c.add(j)
                if not x_list[j] is None:
                    for k in x_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
                if not y_list[j] is None:
                    for k in y_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
            if 1 < len(c):
                connections[i] = c

    cn = 0
    counted = [False] * (N + 1)
    for i in range(1, N + 1):
        if not connections[i] is None:
            c = connections[i]
            for j in c:
                if p[j - 1] in c:
                    cn += 1
                counted[j] = True
    for i in range(1, N + 1):
        if not counted[i]:
            if p[i - 1] == i:
                cn += 1

    print(cn)


if __name__ == '__main__':
    main()



Measured memory_bytes: 39376
N = input()
a = list(map(int, input().split()))
 
def f(x):
  cnt = 0
  cur = 0
  for ai in a:
    cur += ai
    cur *= x
    if cur <= 0:
      cnt += 1 - cur
      cur = 1
    cur *= x
    x *= -1
  return cnt
 
print(min(f(1), f(-1)))

Measured memory_bytes: 14332
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=(ll)1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> p(N,0);
    for(ll i=0;i<N;++i)cin>>p[i];
    vector<ll> a(N,0);
    vector<ll> b(N,0);
    for(ll i=0;i<N;++i)a[i]=20001*i+1;
    for(ll i=0;i<N;++i)b[i]=20001*(N-1-i)+1;
    for(ll i=0;i<N;++i)a[p[i]-1]+=i;
    for(auto p: a)cout<<p<<" ";
    cout<<endl;
    for(auto p: b)cout<<p<<" ";
    fl

    return 0;
}



Measured memory_bytes: 3760
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const bool debug=true;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n,m;
vector<ll> x;
int main(void) {
    cin >> n >> m;
    
    rep(i,m){
        ll tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    if(n>=m){
        cout << 0 << endl;
        return 0;
    }
    sort(x.begin(),x.end());
    vector<pair<ll,ll> > diff;
    ll cnt=m-n;
    rep(i,m-1){
       diff.push_back(make_pair(x[i+1]-x[i],i)); 
    }
    sort(diff.begin(),diff.end(),greater<pair<ll,ll> >());
    // DEBUG{
    //     rep(i,m){
    //         cout << diff[i].first << endl;
    //     }
    // }
    ll res=0;
    bool koma[m]={};
    koma[0]=true;
    rep(i,n-1){
        koma[diff[i].second+1]=true;
    }
    // DEBUG{
    //     rep(i,m){cout << koma[i] << endl;}
    // }
    for(int i=1;i<m;i++){
        if(!koma[i])res+=x[i]-x[i-1];
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main()
{
    string arr;
    cin >> arr;
    int l= arr.length();
    bool isCorrect = true;
    int half = l/2;
    for(int i = 0; i<half; i++)
    {
        int j = l-i-1;
        int i2= half+1+i;
        int j3 = half-i-1;
        if(arr.at(i)==arr.at(j)&&arr.at(i)==arr.at(j3)&&arr.at(i2)==arr.at(j)){
            continue;
        }
        isCorrect = false;
        printf("No\n");
        break;


    }
    if(isCorrect){
    printf("Yes\n");
    }
}

Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1137&lang=jp

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int convert_to_digit(string mcxi)
{
	int num=0;

	int k=1;
	rep(i, mcxi.length())
	{
		if(isdigit(mcxi[i])){
			k = mcxi[i] - '0';
		}
		else if(mcxi[i] == 'm'){
			num += k*1000; k=1;
		}
		else if(mcxi[i] == 'c'){
			num += k*100; k=1;
		}
		else if(mcxi[i] == 'x'){
			num += k*10; k=1;
		}
		else if(mcxi[i] == 'i'){
			num += k*1; k=1;
		}
	}
	return num;
}

string convert_to_mcxi(int value)
{
	string word[4] = {"i","x", "c", "m"};
	string mcxi("");
	int tmp;
	rep(i,4)
	{
		tmp = value % 10;
		
		if(tmp == 0){
			//Do Nothing...
		}
		else if(tmp == 1)
		{
			mcxi = word[i] + mcxi;
		}else
		{
			mcxi = to_string(tmp) + word[i] + mcxi;
		}

		value = value / 10;
	}

	return mcxi;
}

int main() {

	int N;

	cin >> N;

	rep(i,N)
	{
		string in1, in2;
		cin >> in1 >> in2;

		int out1 = convert_to_digit(in1);
		int out2 = convert_to_digit(in2);	

		string mcxi = convert_to_mcxi(out1+out2);
		cout << mcxi << endl;

	}
	return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

typedef long long ll;

constexpr int INF = 1e8;
constexpr int MOD = 1e9+7;

int a[100000];

int main(void) {
    int i, n, l;
    scanf("%d%d",&n,&l);
    int last = -1;
    REP (i,n) scanf("%d",&a[i]);
    REP (i,n-1) {
        if (a[i] + a[i+1] >= l)
            last = i;
    }
    if (last == -1)
        printf("Impossible\n");
    else {
        printf("Possible\n");
        REP (i,last) printf("%d\n",i+1);
        RREP (i,n-2,last+1) printf("%d\n",i+1);
        printf("%d\n",last+1);
    }
    return 0;
}


Measured memory_bytes: 1152
//By Ralif Rakhmatullin
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<math.h>
#include<cassert>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<bitset>
#include<valarray>
#include<iterator>
#include<list>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define S second
#define ld long double
#define F first
#define y1 LOL
#define ld long double
#define pb push_back
#define len length
#define sz size
#define beg begin
const ll INF = (ll)1e18 + 123;
const int inf=(int)2e9 + 123; 
const int mod=1e9+7;
using namespace std;
int n, a[100011];
int ev = 0, odd = 0;
void out(int x){
	if(x == 0)
		cout << "First";
	else
		cout << "Second";
	exit(0);
}
bool go(){
	int gcd = 0;
	for(int i = 1; i <= n; i ++){
		if(a[i] % 2 == 1){
			if(a[i] == 1)	
				return 0;
			a[i] --;
		}
		gcd = __gcd(gcd, a[i]);
	}
	odd = ev = 0;
	for(int i = 1; i <= n; i ++){
		a[i] /= gcd;
		if(a[i] % 2 == 1)
			odd ++;
	   	else
	   		ev ++;
	}
	return 1;
}
int main(){
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  	srand(FOR);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		if(a[i] % 2 == 1)
			odd ++;
	   	else
	   		ev ++;
	}
	if(n == 1){
		out(a[1] % 2);
	}
	int t = 0;
	while(1){
		if(ev % 2 == 1){
			out(t);
		}	
		if(odd == 1){
			if(!go()){
				out(t ^ 1);
			}
		}else{
			out(t ^ 1);
		}
		t ^= 1;
	}
	return 0;
}

Measured memory_bytes: 768
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 2;
double EPS = 1e-10;
 
void unko(bool x) {
	if (x) cout << "unko" << endl;
}
 
int main() {
    int N, M; cin >> N >> M;
    vector<int> K(N);
    vector<vector<int> > S(N), H(N);
	int sumK = 0;
    for (int i = 0; i < N; i++) {
        cin >> K[i];
		sumK += K[i];
        for (int k = 0; k < K[i]; k++) {
            int s, h; cin >> s >> h;
            S[i].push_back(s);
            H[i].push_back(h);
        }
    }
	unko(sumK == 4000 && M == 200);
    double maxi = 0;
    for (int t = 0; t < N; t++) {
        vector<int> dp(M + 1, -INF);
        dp[M] = 0;
        for (int i = 0; i < N - 1; i++) {
            vector<int> _dp = dp;
            for (int j = 0; j <= M; j++) {
                int h = 0, v = 0;
                for (int k = 0; k < K[i]; k++) {
                    h += H[i][k];
                    v += S[i][k] * H[i][k];
                    if (v > j) break;
                    _dp[j - v] = max(_dp[j - v], dp[j] + h);
                }
            }
            dp = _dp;
        }
        for (int j = 0; j <= M; j++) {
            double h = dp[j], v = j;
            for (int k = 0; k < K[N - 1]; k++) {
                double dh = min((double)H[N - 1][k], v / S[N - 1][k]);
                h += dh; v -= S[N - 1][k] * dh;
            }
            maxi = max(maxi, h);
        }
        rotate(K.begin(), K.begin() + 1, K.end());
        rotate(S.begin(), S.begin() + 1, S.end());
        rotate(H.begin(), H.begin() + 1, H.end());
    }
    printf("%.20f\n", maxi);
}

Measured memory_bytes: 1272
S=input()
count=0
start=0
for i in S:
    if count%2==0:
        if i=="0":
            start+=1
    else:
        if i=="1":
            start+=1
    count+=1
if (len(S)-start)>start:
    print(start)
else:
    print(len(S)-start)


Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
	int X;
	long long A5;
	long long B5;
	cin >> X;
	for(int i=1; i<=1000; i++){
		for(int j=-1000; j<=1000; j++){
			A5 = pow(i, 5);
			B5 = pow(j, 5);
			if(A5 == X+B5) {
				cout << i << " "<< j;	
				return 0;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 3516
from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())

for i in range(q):
    data = input().split()
    if len(data) == 1:
        header *= -1
    else:
        f = int(data[1])
        c = data[2]
        if header == 1:
            if f == 1:
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if f == 1:
                d.append(c)
            else:
                d.appendleft(c)

if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)

print(s)

Measured memory_bytes: 8564
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int f = sc.nextInt();
        int r = sc.nextInt();
        while(m!=-1||f!=-1||r!=-1){
            if(m==-1||f==-1) System.out.println("F");
            else{
                if(m+f>=65){
                    if(m+f>=80) System.out.println("A");
                    else        System.out.println("B");
                }else{
                    if(m+f>=30){
                        if(m+f>=50) System.out.println("C");
                        else{
                            if(r>=50) System.out.println("C");
                            else      System.out.println("D");
                        }
                    }else System.out.println("F");
                }
            }
            m = sc.nextInt();
            f = sc.nextInt();
            r = sc.nextInt();
        }
    }
}


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main()
{
    int N,Q;
    ll K;
    cin >> N >> K >> Q;
    vector<int>A(Q);
    vector<ll>cnt(N,K - Q);
    rep(i,Q)
    {
        cin >> A[i];
        cnt[A[i]-1]++;
    }
    rep(i,N)
    {
        if(cnt[i] > 0) cout <<"Yes" << endl;
        else cout << "No" << endl;
    }
    //cout << endl;
    //rep(i,N) cout << cnt[i] << endl; 
}


Measured memory_bytes: 1792
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 10 ** 9 + 7
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

bit = Bit(2020)
X = 0
for i, p in enumerate(A):
    bit.add(p, 1)
    X += i + 1 - bit.sum(p)

bit = Bit(2020)
Y = 0
for i, p in enumerate(A * 2):
    bit.add(p, 1)
    Y += i + 1 - bit.sum(p)
Y -= 2 * X

ans = (X * K + Y * K * (K - 1) // 2) % mod
print(ans)


Measured memory_bytes: 3188
import sys

chars = 'abcdefghijklmnopqrstuvwxyz'
counts = [0]*26

words = sys.stdin.read()
# words = 'This is a pen.'

for A in words:
    index = 0
    for B in chars:
        if A.lower() == B:
            counts[index] += 1
            break
        index += 1

for i in range(len(chars)):
    print(f'{chars[i]} : {counts[i]}')


Measured memory_bytes: 5576
#include<stdio.h>
#include<string.h>

int main(){
int a,b;
char aName[15], bName[15], cName[15];
scanf("%s%s", aName, bName);
scanf("%d%d", &a, &b);
getchar();
scanf("%s", cName);
if(strcmp(cName,aName)==0)printf("%d %d\n", a-1, b);
else printf("%d %d\n", a, b-1);
	return 0;
}

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

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

    int count = 0;
    int tap = 1;
    while (tap < b) {
        tap +=  a - 1;
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc166/tasks/abc166_f
// 
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define is_in(i, s) (s.find(i) != s.end())
#define all(x) (x).begin(),(x).end()
#define outl(x) cout<<x<<endl
#define outsp(x) cout<<x<<" "
typedef long long ll;
typedef pair<int,int> P;
#define AB 0
#define BC 1
#define AC 2


#define MAX_N 100005


int main() {
	int n,a,b,c;
	int op[MAX_N];
	string ans[MAX_N];
	cin >> n >> a >> b >> c;
	rep(i,n){
		string s;
		cin >> s;
		if(s=="AB")op[i]=AB;
		else if(s=="AC")op[i]=AC;
		else op[i]=BC;
	}

	rep(i,n){
		int *x,*y;
		string xs,ys;
		if(op[i]==AB){
			x=&a;y=&b;
			xs="A";ys="B";
		}else if(op[i]==AC){
			x=&a;y=&c;
			xs="A";ys="C";
		}else{
			x=&b;y=&c;
			xs="B";ys="C";
		}
		if(*x==0 && *y==0){
			outl("No");
			return 0;
		}
		bool add_x = *x<*y;
		if(*x==1 && *y==1 && a+b+c==2 && i<n-1 ){
			if(op[i]==AB) add_x = op[i+1]==AC;
			else if(op[i]==AC) add_x = op[i+1]==AB;
			else add_x = op[i+1]==AB;
		}
		if(add_x){
			*x += 1;
			*y -= 1;
			ans[i] = xs;
		}else{
			*x -= 1;
			*y += 1;
			ans[i] = ys;
		}
	}
	outl("Yes");
	rep(i,n)outl(ans[i]);

    return 0;
}



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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
// constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  REP(i, N){
    cin >> A[i] >> B[i];
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  int ans;
  if(N % 2){
    ans = B[N/2] - A[N/2] + 1;
  }
  else{
    ans = (2*B[N/2]+2*B[N/2-1])/2 - (2*A[N/2] + 2*A[N/2-1])/2 + 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6428