akhauriyash/Code-Regression huggingface dataset:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()

    cnt, q1 = 0, 0
    ism = False
    for a in A:
        cnt += a
        if ism and cnt >= 0:
            q1 += abs(cnt) + 1
            cnt = -1
        elif not ism and cnt <= 0:
            q1 += abs(cnt) + 1
            cnt = 1
        if ism:
            ism = False
        else:
            ism = True

    cnt , q2 = 0, 0
    ism = True
    for a in A:
        cnt += a
        if ism and cnt >= 0:
            q2 += abs(cnt) + 1
            cnt = -1
        elif not ism and cnt <= 0:
            q2 += abs(cnt) + 1
            cnt = 1
        if ism:
            ism = False
        else:
            ism = True
    print(min(q1,q2))


if __name__ == '__main__':
    main()


Measured memory_bytes: 19736
#include<iostream>
#include<string>
using namespace std;
int main (){
    string a,b;
    cin>>a>>b;
    for(int c=0;c<b.size();c++){
        cout<<a[c]<<b[c];
    }
    if(a.size()!=b.size()){
        cout<<a[a.size()-1];
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,m;
int A[maxn];
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        int c=(max(a,b)-min(a,b))/2;
        if(min(a,b)+c==max(a,b)-c)
            cout<<min(a,b)+c<<endl;
        else
            cout<<"IMPOSSIBLE"<<endl;
    }
}

Measured memory_bytes: 256
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		String inputString, phrase;
		InputStreamReader reader = new InputStreamReader(System.in);
		BufferedReader bufferdReader = new BufferedReader(reader);
		
		inputString = bufferdReader.readLine();
		inputString = inputString + inputString;
		phrase = bufferdReader.readLine();
		if (inputString.indexOf(phrase) != -1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 100000000

vector<vector<ll> > dp(100002, vector<ll> (3,-1));
ll ara[100005][4];
ll n;
ll f(ll i , ll j){

    if(i==n-1) return dp[i][j] = ara[i][j];
    if(dp[i][j]!=-1) return dp[i][j];

    ll m=0;

    if(j==2)
    m= max(f(i+1,0),f(i+1,1))+ara[i][2];

    else if(j==1)
    m= max(f(i+1,0),f(i+1,2))+ara[i][1];

    else m= max(f(i+1,2),f(i+1,1))+ara[i][0];


    dp[i][j] = m;

    return dp[i][j];
}



int main(){
    cin>>n;
    for(ll i=0;i<n;i++){
            for(ll j=0;j<3;j++)
        scanf("%lld",&ara[i][j]);
    }
    f(0,0);
    f(0,1);
    f(0,2);

    ll m=max(dp[0][0],dp[0][1]);
    cout<<max(dp[0][2],m);
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  long int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  int b = 0;
  for(int i = 0; i < n - 1; i++) {
    if(a[i] == a[i + 1]) {
      b = 1;
      break;
    }
  }
  if(b == 0) {
    cout << "YES";
  } else {
    cout << "NO";
  }
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <cmath>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <set>
using ll = long long;
using namespace std;
#define INF 999999999

int main()
{
    int N, H, W;
    cin >> N >> H >> W;
    cout << (N - H + 1) * (N - W + 1) << endl;

    return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  long long n, m;
  cin >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int j = n - i + 1;
    if (n % 2 == 0 && i > n / 4) {
      j--;
    }

    cout << i << ' ' << j << '\n';
  }
  return 0;
}

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

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

    int n, m;
    cin>>n;

    m = (n&1)?(n/2)+1:n/2;

    cout<<fixed<<setprecision(10)<<(double)((double)m/(double)n);
}


Measured memory_bytes: 256
import java.io.*;
public class Main{

    public static int[] sort(String s[]){
        int[] sides = new int[s.length];
        for(int i = 0;i < s.length; i++){
            sides[i] = Integer.parseInt(s[i]);
        }
        for(int j = 1;j < sides.length; j++){
            if(sides[0] < sides[j]){
                int n = sides[0];
                sides[0] = sides[j];
                sides[j] = n;
            }
        }
        return sides;
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int num = Integer.parseInt(str);
        while(num <= 0 || num > 1000){
            str = br.readLine();
            num = Integer.parseInt(str);
        }
        String str1;
        String side[][];
        side = new String[num][];
        int sides[][];
        sides = new int[num][];
        int a = 0;
        while(a != num){
            str1 = br.readLine();
            side[a] = str1.split(" ", 3);
            sides[a] = sort(side[a]);
            a++;
        }
        for(int k = 0;k < num;k++){
             if(sides[k][0]*sides[k][0] == sides[k][2]*sides[k][2] +sides[k][1]*sides[k][1]){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
}

Measured memory_bytes: 26612
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
bool minimize(T)(ref T x, T y) { if (x > y) { x = y; return true; } else { return false; } }
bool maximize(T)(ref T x, T y) { if (x < y) { x = y; return true; } else { return false; } }

long mod = 10^^9 + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto X = RD;
	auto Y = RD;
	auto Z = RD;
	auto K = RD;
	auto A = RDR.ARR;
	auto B = RDR.ARR;
	auto C = RDR.ARR;
	A.sort!"a > b"();
	B.sort!"a > b"();
	C.sort!"a > b"();

	auto dp = new long[](X*Y);
	foreach (i; 0..X)
	{
		foreach (j; 0..Y)
		{
			dp[i*Y+j] = A[i] + B[j];
			//debug writeln(i, ":", j, " ", dp[i*Y+j]);
		}
	}
	dp.sort!"a > b"();
	
	/*auto dpd = new long[](X*Y-1);
	foreach (i; 0..X*Y-1)
	{
		dpd[i] = dp[i] - dp[i+1];
	}
	auto cd = new long[](Z-1);
	foreach (i; 0..Z-1)
	{
		cd[i] = C[i] - C[i+1];
	}*/

	auto dp2 = new long[](min(K, X*Y)*Z+1);
	foreach (i; 0..min(K, X*Y))
	{
		foreach (j; 0..Z)
		{
			dp2[i*Z+j] = dp[i] + C[j];
			//debug writeln(i, ":", j, " ", dp2[i*Z+j]);
		}
	}
	dp2.sort!"a > b"();
	
	foreach (e; dp2[0..K])
		writeln(e);
	stdout.flush();
	debug readln();
}

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

int main() {
    int N;
    cin >> N;
    vector<int> V(100005);
    V[0]++;
    for (int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        V[a]++;
        V[b+1]--;
    }

    int res = 0;
    for (int i = 0; i <= 100001; i++) {
        V[i + 1] += V[i];
        if (i <= V[i]) res = i;
    }

    cout << res - 1 << endl;

    return 0;
}

Measured memory_bytes: 1536
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int N;
int main(){
  cin>>N;
  ll a[N],b[N];
  FOR(i,0,N)cin>>a[i];
  FOR(i,0,N)cin>>b[i];
  ll ans=0;
  FOR(i,0,30){
    ll T=1<<i;
    ll cnt=0;
    vector<int> v(N);
    FOR(j,0,N)v[j]=b[j]%(2*T);
    sort(v.begin(),v.end());
    FOR(j,0,N){
      ll aa=a[j]%(2*T);
      cnt+=lower_bound(v.begin(),v.end(),2*T-aa)-lower_bound(v.begin(),v.end(),T-aa);
      cnt+=lower_bound(v.begin(),v.end(),4*T-aa)-lower_bound(v.begin(),v.end(),3*T-aa);
    }
    if(cnt%2)ans+=T;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4208
import sys

n = int(raw_input())
A = map(int, sys.stdin.readline().split())

cnt = 0

for i in xrange(len(A)-1):
    for j in xrange(len(A)-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            cnt += 1

for x in A:
	print x,
print 
print cnt

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

using namespace std;

void rwFile() {
    freopen("INP.inp", "r", stdin);
    freopen("OUT.out", "w", stdout);
}

void solveA() {
    int k, x;
    cin >> k >> x;
    if (k * 500 >= x) cout << "Yes";
    else cout << "No";
}

void solveB() {
    int n; cin >> n;
    string s; cin >> s;
    int res = 0;
    for (int i = 0; i + 2 < n; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') res++;
    }
    cout << res;
}

void solveC() {
    int n; cin >> n;
    int p[n], q[n];
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n;i ++) cin >> q[i];
    int arr[n];
    int lim = 1;
    for (int i = 1; i <= n; i++) lim *= i;
    for (int i = 0; i < n; i++) arr[i] = i + 1;
    int a = 0, b = 0;
    for (int i = 0; i < lim; i++) {
        int isA = 1, isB = 1;
        for (int j = 0; j < n; j++) {
            if (arr[j] != q[j]) isB = 0;
            if (arr[j] != p[j]) isA = 0;
        }
        if (isA) a = i;
        if (isB) b = i;
        next_permutation(arr, arr + n);
    }
    cout << abs(a - b);
}

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

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

int find2(long long x) {
    int res = 0;
    while (x % 2 == 0) {
        res++;
        x /= 2;
    }
    return res;
}

void solveD() {
    long long n, m; cin >> n >> m;
    long long arr[n];
    if (n == 1) {
        int x; cin >> x;
        if (x % 2 == 1) cout << 0;
        else {
            x /= 2;
            int res = m / x - m / (2 * x); //(m - x) / (2 * x) + 1;
            cout << ((res < 0) ? 0 : res);
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        arr[i] /= 2;
    }
    int two = find2(arr[0]);
    for (int i = 1; i < n; i++) {
        if (find2(arr[i]) != two) {
            cout << 0;
            return;
        }
    }
    long long arrLcm = 1LL;
    for (int i = 0; i < n; i++) arrLcm = lcm(arrLcm, arr[i]);
    long long res = m / arrLcm - m / (2 * arrLcm); //(m - arrLcm) / (2 * arrLcm) + 1;
    cout << ((res < 0) ? 0 : res);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    //rwFile();
    ///solveA();
    ///solveB();
    ///solveC();
    solveD();
}


Measured memory_bytes: 1024
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:
  cnt[val]+=1
sums=sum(arr)
q=int(input())
for a in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]
  cnt[b]=0


Measured memory_bytes: 24196
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n;
  cin>>n;
  int a[100001] = {};
  int b[100001] = {};
  int c,d;
  for(int i = 0; i < n / 2; i++)
  {
    cin>>c>>d;
    a[c]++;
    b[d]++;
  }
  int ma = 0,mb = 0;
  int ia,ib;
  for(int i = 0; i < 100001; i++)
  {
    if(ma < a[i]) {
      ia = i;
    }
    if(mb < b[i]) {
      ib = i;
    }
    ma = max(ma, a[i]);
    mb = max(mb, b[i]);
  }
  sort(a, a + 100001, greater<int>());
  sort(b, b + 100001, greater<int>());
  

  int ans = 0;
  if(ia == ib) {
    ans = min(n - a[0] - b[1], n - a[1] - b[0]);
  } else {
    ans = n - a[0] - b[0];
  }
  
  cout << ans << endl;
  
  
  return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n;
	cin >> k >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	sort(v.begin(), v.end());
	int Max = k + v[0] - v[n - 1];
	for (int i = 0; i < n - 1; i++) {
		Max = max(Max, v[i + 1] - v[i]);
	}
	cout << k - Max << "\n";
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <iomanip>
using ll = long long;
using uint = unsigned int;
using graph = std::vector<std::vector<ll>>;
using wGraph = std::vector<std::vector<std::pair<ll,ll>>>;
#define rep(i,n) for (int i=0; i < int(n); i++)

using namespace std;
ll MOD7 = 1000000007;
ll MOD9 = 1000000009;
vector<ll> InputVec(ll N){
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    return A;
}
void OutputVec(vector<ll> A){
    for (int i = 0; i < A.size(); ++i) {
        cout << A[i] << ",";
    }
    cout << endl;
}
vector<vector<ll>> InputVec2d(ll H,ll W){
    vector<vector<ll>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<ll>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        for (int xi = 0; xi < W; ++xi) {
            cin >> A[yi][xi];
        }
    }
    return A;
}
vector<vector<char>> InputVec2dStr(ll H,ll W){
    vector<vector<char>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<char>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        string S;
        cin >> S;
        for (int xi = 0; xi < W; ++xi) {
            A[yi][xi] = S[xi];
        }
    }
    return A;
}
void OutputVec2d(vector<vector<ll>> A){
    for (int yi = 0; yi < A.size(); ++yi) {
        for (int xi = 0; xi < A[yi].size(); ++xi) {
            cout << A[yi][xi] << ",";
        }
        cout << endl;
    }
}
graph InputGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    return G;
}
graph InputDGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
    }
    return G;
}
void OutputGraph(graph G){
    for (int i = 0; i < G.size(); ++i) {
        cout << i << ":";
        for (int j = 0; j < G[i].size(); ++j) {
            cout << G[i][j]<< ",";
        }
        cout << endl;
    }
}
void OutputAnswerBool(bool b,bool isUpperCase = false){
    if(b){
        if(isUpperCase){
            cout << "YES" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }else{
        if(isUpperCase){
            cout << "NO" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}

int main() {
    ll S,W;
    cin >> S >> W;
    if(S > W){
        cout << "safe" << endl;
    }else{
        cout << "unsafe" << endl;
    }
}


Measured memory_bytes: 3600
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<ll, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

int f(int a){
    int sum = 0;
    while(a > 0){
        sum += a % 10;
        a /= 10;
    }
    return sum;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int mx = (int)1e9;
    for(int i = 1; i < n ; i ++ ){
        mx=min(mx,f(i)+f(n-i));
    }
    cout << mx;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;

#define INF 100000000
int N, A, B, C;

int dfs(int *L, int a, int b, int c, int i) {
  int ret0, ret1, ret2, ret3;
  if (i >= N) {
    if (min({a, b, c}) > 0) {
      return abs(a-A) + abs(b-B) + abs(c-C) - 30;
    } else {
      return INF;
    }
  }
  ret0 = dfs(L, a + L[i], b, c, i+1) + 10;
  ret1 = dfs(L, a, b + L[i], c, i+1) + 10;
  ret2 = dfs(L, a, b, c + L[i], i+1) + 10;
  ret3 = dfs(L, a, b, c, i+1);
  return min({ret0, ret1, ret2, ret3});
}

int main() {
  scanf("%d %d %d %d", &N, &A, &B, &C);
  int ans;
  int L[N];
  for (int i=0; i<N; i++) {
    scanf("%d", &L[i]);
  }
  ans = dfs(L, 0, 0, 0, 0);
  printf("%d\n", ans);
}


Measured memory_bytes: 128
n, m, c = map(int, input().split())

b = list(map(int, input().split()))

count = 0

for _ in range(n):
  a = list(map(int, input().split()))
  score = c
  for i in range(m):
    score += a[i] * b[i]
  if score > 0:
    count += 1
    
print(count)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod=1000000007;
const double PI = 3.14159265359;
#define pb  push_back
#define FOR(i,n) for(int i=0;i<(n);i++)
#define FORA(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define count_1(n)  __builtin_popcountll(n)
#define parity(n)   __builtin_parityll(n)   //Even parity 0 as output
void show    (int a[], int arraysize) { for (int i = 0; i < arraysize; ++i)  {cout << a[i] << " ";}	cout<<endl;}
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
void sieve(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}
int main()
{FAST
int a,b,c,d;
cin>>a>>b>>c>>d;

while(a>0&&c>0)
{
	c-=b;
	if(c<=0)
	{
		cout<<"Yes\n";
		break;
	}
	a-=d;
	if(a<=0)
	{
		cout<<"No\n";
		break;
	}
}

return  0;
}




Measured memory_bytes: 3644
N, Q = map(int, input().split())
S = input()
dp = [0] * N
for i in range(N-2, -1, -1):
    dp[i] = dp[i+1]
    if S[i:i+2] == 'AC':
        dp[i] += 1
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[l-1] - dp[r-1])

Measured memory_bytes: 6060
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{ min, max };

macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

#[allow(dead_code)]
const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let m: usize = sc.cin();
    let mut dp: Vec<i64> = vec![0; n + 1];
    let mut broken: Vec<bool> = vec![false; n + 1];

    for _ in 0..m {
        let a: usize = sc.cin();
        broken[a] = true;
    }

    dp[0] = 1;
    for i in 1..n+1 {
        if broken[i] { continue }
        dp[i] = if broken[i-1] { 0 } else { dp[i-1] } + if i<2 || broken[i-2] { 0 } else { dp[i-2] };
        dp[i] %= M;
    }

    // trace!(&dp);
    put!(dp[n]);

}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


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

using namespace std;
typedef long long ll;

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

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

    int odd = (n + 1) / 2;

    cout << 1.0 * odd / n << '\n';
    return 0;
}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI arccos(-1)
#define rep(i, N) for (int i = 0; i < (N); i++)
#define REP(i, a, N) for (int i = a; i < (N); i++)
#define rrep(i, N, k) for (int i = (N); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - (int)1e8;
const ll INFLL = numeric_limits<ll>::max() - (ll)1e17;

int main() {
    int N;
    cin >> N;
    map<int, int> count;
    for (int i = 2; i <= N; i++) {
        int temp;
        cin >> temp;
        count[temp]++;
    }
    for (int i = 1; i <= N; i++) {
        cout << count[i] << endl;
    }
}


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

int main()
{
  int L, M, N;
  while( cin >> L, L ) {
    bool flag = false;
    for(int i=0; i<12; i++) {
      cin >> M >> N;
      L -= M - N;
      if( L <= 0 && !flag ) {
	cout << i+1 << endl;
	flag = true;
      }
    }

    if( !flag ) cout << "NA" << endl;
  }
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <tr1/unordered_set>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long P;

P enc(int x, int y) { return P(x)<<32|y; }

int n;
P ps[200000];
tr1::unordered_set<P> vis;

void rec(const P& p) {
    if (vis.count(p)) return ;
    vis.insert(p);
    int x = p>>32;
    int y = p;
    rep (i, 3) rep (j, 3) {
        const P np = enc(x+i-1, y+j-1);
        if (binary_search(ps, ps+n, np)) rec(np);
    }
}

int main() {
    double R;
    scanf("%d%lf", &n, &R);
    R *= 1.05;
    rep (i, n) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        x += 1e7, y += 1e7;
        ps[i] = enc(int(x/R), int(y/R));
    }
    sort(ps, ps+n);
    n = unique(ps, ps+n) - ps;
    int ans = 0;
    rep (i, n) if (!vis.count(ps[i])) rec(ps[i]), ans++;
    printf("%d\n", ans);
    return 0;
}

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

int main(void) {
  int n;
  cin >> n;
  
  int res = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    while(a%2==0){
      a/=2;
      res++;
    }
  }

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


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

using namespace std;

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

#define ll long long int

int ctoi(char c) {return c-'0';}
int ord(char c) {return c-'a';}
int len(string s) {return s.length();}
int itoc(int i) {return i+'a';}

int main(){
int x,y,z;
cin>>x>>y>>z;
swap(x,y);
swap(x,z);
cout<<x<<" "<<y<<" "<<z<<endl;
return 0;
}




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

int main(){
    int n,x,y;
    cin >> n >> x >> y;
    vector<int> ans(n+1,0);
    int temp=n;

    for(int i=1;i<=n; ++i){
        for(int j=i+1; j<=n; ++j){
            temp = n;
            temp = min(temp,j-i);
            temp = min(temp,abs(x-i)+abs(y-j)+1);
            temp = min(temp,abs(x-j)+abs(y-i)+1);

            //cout <<"i,j" << i << ":" << j << "temp" << temp << endl;

            ans[temp]++;
        }
    }

    for(int i=1; i<n; ++i){
        cout << ans[i] << endl;
    }
}


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

int main(void){
  int *team,*rank,i,j,k,n;
  int t1,t2,p1,p2;
  int maxv,maxi,pflg=-1,rflg=-1;

  scanf("%d",&n);
  k=n*(n-1)/2;
  team=(int *)calloc(n,sizeof(int));
  rank=(int *)calloc(n,sizeof(int));
  team--;
  rank--;
  for(i=0;i<k;i++){
    scanf("%d %d %d %d",&t1,&t2,&p1,&p2);
    if(p1<p2) team[t2]+=3;
    else if(p1>p2) team[t1]+=3;
    else team[t1]++,team[t2]++;
  }
  
  for(i=1;i<=n;i++){
    maxv=-1;
    for(j=1;j<=n;j++){
      if(team[j]>maxv){
	maxv=team[j];
	maxi=j;
      }
    }
    if(pflg!=maxv){
      pflg=maxv;
      rflg=i;
    }
    rank[maxi]=rflg;
    team[maxi]=-1;
  }
  for(i=1;i<=n;i++) printf("%d\n",rank[i]);
  free(rank+1);
  free(team+1);
  return 0;
}
    

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int N,K;
    cin>>N>>K;
    vi A(N);
    for(int i=0;i<N;i++) cin>>A[i];

    for(int j=0;j<K;j++){
        vi B(N,0);
        for(int i=0;i<N;i++){
            B[max(0,i-A[i])]++;
            if(i+A[i]+1<N)B[i+A[i]+1]--;
        }
        bool all_N=true;
        A[0]=B[0];
        if(A[0]<N)all_N=false;
        for(int i=1;i<N;i++){
            A[i]=A[i-1]+B[i];
            if(A[i]<N)all_N=false;
        }
        if(all_N)break;
    }

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


Measured memory_bytes: 4852
h, w = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
dic_color = {}
for i, num in enumerate(A):
    color = i + 1
    dic_color[color] = num

if h <= w:
    yokonaga = True
else:
    yokonaga = False
    h, w = w, h

board = [[0 for i in range(w)] for j in range(h)]
#print(bord)
longer_side = max(h, w)

pointer_h = 0
pointer_w = 0

for color in dic_color.keys():
    num = dic_color[color]
    for i in range(num):
        board[pointer_h][pointer_w] = color
        #print(pointer_h, pointer_w, color, num)
        if pointer_h % 2 == 0 and pointer_w < w - 1:
            pointer_w += 1
            #print(1)
        elif pointer_h % 2 == 0 and pointer_w == w - 1:
            pointer_h += 1
            #print(2)
        elif pointer_h % 2 == 1 and pointer_w > 0:
            pointer_w -= 1
            #print(3)
        elif pointer_h % 2 == 1 and pointer_w == 0:
            pointer_h += 1
            #print(4)

if yokonaga:
    for i in range(h):
        print(*board[i], sep=" ")
else:
    board = [[board[i][j] for i in range(h)] for j in range(w)]
    for i in range(w):
        print(*board[i], sep=" ")


Measured memory_bytes: 43760
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i=a; i<n; i++)
#define RREP(i, a, n) for(ll i=n-1; i>=a; i--)
typedef long long ll;
const ll mod =1e9+7;
const ll inf =1e18;
using namespace std;

double h, w, n;
int main(){
    cin>>h>>w>>n;
    cout<<min(ceil(n/h), ceil(n/w))<<endl;
    return 0;
}

Measured memory_bytes: 256
while true
    h, w = gets.split
    h = h.to_i;w = w.to_i;
    if h == 0 && w == 0
        break
    end
    for i in 1..h
        for j in 1..w
        print "#"
        end
        print "\n"
    end
    print "\n"
end


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

typedef struct {
  char name[100];
  int t;
}A;

A Q[1000000];
A P[1000000];
int head, tail, n;

int isEmpty(){
  if(head == tail)return 1;
  else return 0;
}

void queue(A x){
  Q[tail] = x;
  tail++;
}

void initialize(){
  head = 0;
  tail = n+1;
}


int main(){
  int i, q, count=1, tmp=0, c;
  
  scanf("%d%d",&n,&q);
  int a[n+1];
  
  for(i=1; i<=n; i++)
    P[i].t = 0;

  for(i=1; i<=n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  initialize();

  i=1;

  while(count != n+1){
    if(Q[i].t > q){
      Q[i].t=Q[i].t-q;
      tmp += q;
      queue(Q[i]);
      i++;
    }
    else if(Q[i].t<=q){
      tmp += Q[i].t;
      P[count].t=tmp;
      strcpy(P[count].name, Q[i].name);
      i++;
      count++;
    }
  }

  for(i=1; i<=n; i++)
    printf("%s %d\n",P[i].name,P[i].t);
    
  return 0;
}
  



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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)
int main() {
    int n, k;
    cin >> n >> k;
    if (n > k) {
        cout << 0 << endl;
        return 0;
    }
    long long sum = 1;
    for (int i = k; i >= k - n + 1; i--) {
        sum *= i;
        sum = sum % mod;
        // cout << sum << endl;
    }
    cout << sum << endl;
}


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

int main() {
  int N;
  cin >> N;
  int T[N+1];
  for (int i=1; i<=N; i++) cin >> T[i];
  int M;
  cin >> M;
  int P[M], X[M];
  for (int i=0; i<M; i++) cin >> P[i] >> X[i];

  int sum[M]={0};
  for (int i=0; i<M; i++) {
    for (int j=1; j<=N; j++) {
      if (j == P[i]) {
        sum[i] += X[i];
      } else {
        sum[i] += T[j];
      }
    }
  }

  for (int i=0; i<M; i++) {
    cout << sum[i] << endl;
  }

  return 0;
}


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

int main(){
   int a;
   while(cin>>a,a){
       vector<unordered_set<string>>V(50);
       for(int b=0;b<a;b++){
	   string c;cin>>c;
	   string d="a";d[0]=c[0];
	   for(int e=1;e<c.length();e++){
	       if(c[e-1]=='a'||c[e-1]=='i'||c[e-1]=='u'||c[e-1]=='e'||c[e-1]=='o'){
		     d+=c[e];
		   }
	       }
	    for(int e=1;e<=50;e++){
		V[e-1].insert(d.substr(0,e));
		}
	   }
	   for(int f=1;f<=50;f++){
	       if(V[f-1].size()==a){
		   cout<<f<<endl;
		   goto l;
		   }
	       }
	       puts("-1");
	       l:;
       }
    }

Measured memory_bytes: 3240
#include <stdio.h>

int main(void) {
	int N,K;
	scanf("%d%d",&N,&K);
	int a[100010];
	int dp[100010] = {};
	for(int i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	
	for(int i=0;i<=K;i++){
		for(int j=0;j<N;j++){
			if(i-a[j]>=0&&dp[i-a[j]]==2){
				dp[i] = 1;
				break;
			}
			dp[i] = 2;
		}
	}
	if(dp[K]==1) printf("First");
	else printf("Second");
	
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void) {
  int H;
  int N;

  scanf("%d", &H);
  scanf("%d", &N);
  int A[N];
  int sum = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    sum += A[i];
  }
  if (sum >= H) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


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

int main() {
  int n,m; cin>>n>>m;
  int x=0;
  if (m<10) x=10*n+m;
  else if (m<100) x=100*n+m;
  else x=1000*n+m;

  bool frag=false;
  rep(i, 1000) {
    int tmp=i*i;
    if (i == 0) continue;
    if (frag) break;
    if (tmp>x) break;
    if (tmp==x) frag = true;
  }
  if (frag) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main() {

    int n;
    cin >> n;

    int dp[50];
    dp[0] = 1, dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    cout << dp[n] << endl;
    
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int maxval = -1000001;
  int minval = 1000001;
  long long all_sum = 0;
  for (int i=0; i<n; i++){
    int a;
    cin >> a;
    if (a>maxval){
      maxval = a;
    }
    if (a<minval){
      minval = a;
    }
    all_sum += a;
  }
  cout << minval << ' ' << maxval << ' ' << all_sum << endl;
  
}



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

 int main (){
     char a[1001];
     
     
     while (1){
         int sum=0;
         string x;
         cin >> x;
         if(x=="0"){
             break;
         }
         for (int i=0; i<x.size(); i++){
             sum+= x[i]-'0';
         }
         cout << sum << endl;


     }
 }



Measured memory_bytes: 3132
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int a,b,n;
int main()
{
  while(cin>>a>>b>>n){
    int ans = 0;
    a %=b;
    for(int i =0;i <n;i++){
      a*=10;
      ans +=a/b;
      a %=b;
    }
   cout <<ans<<endl;
  }
  return 0;
}

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

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

int main() {
  ll n, ans = 0;
  string s;
  cin >> n >> s;
  ll r = 0, g = 0, b = 0;
  vector<ll> R, G, B;
  unordered_set<ll> Bs;
  rep(i, n) {
    if (s[i] == 'R') {
      r++;
      R.push_back(i);
    } else if (s[i] == 'G') {
      g++;
      G.push_back(i);
    } else {
      b++;
      B.push_back(i);
      Bs.insert(i);
    }
  }
  R.resize(r);
  G.resize(g);
  B.resize(b);

  if (r == 0 || b == 0 || g == 0) {
    cout << 0 << endl;
    return 0;
  }

  ans = r * g * b;
  vector<int> N(3);
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < g; ++j) {
      if (R[i] < G[j]) {
        int diff = G[j] - R[i];
        if (Bs.count(R[i] - diff)) ans--;
        if (Bs.count(G[j] + diff)) ans--;
      } else {
        int diff = R[i] - G[j];
        if (Bs.count(G[j] - diff)) ans--;
        if (Bs.count(R[i] + diff)) ans--;
      }
      if ((R[i] + G[j]) % 2 == 0) {
        int id = (R[i] + G[j]) / 2;
        if (Bs.count(id)) ans--;
      }
    }
  }

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


Measured memory_bytes: 3740
<?php
  fscanf(STDIN, "%d %d", $a, $b);
  $a_str = "";
  $b_str = "";

  if ($a < $b) {
    for ($i=1; $i<=$b; $i++) {
      $a_str .= $a;
    }
    echo $a_str;
  } else {
    for ($i=1; $i<=$a; $i++) {
      $b_str .= $b;
    }
    echo $b_str;
  }

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int N; cin >> N;
  int ans = N / 111;
  if (N % 111 != 0) ans++;
  cout << ans * 111 << endl;

  return 0;
}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
#define ll long long

//const int mxn = 3000;

using namespace std;

//double p[mxn+1], dp[mxn+1][mxn+1];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    //memset(dp, 0, sizeof(dp)/sizeof(double));
    int n; 
    cin>>n;
    double p[n+1], dp[n+1][n+1];
    for(int i=1; i<=n; i++){
        cin>>p[i];
    }
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            dp[i][j] = 0;
        }
    }
    dp[1][0] = 1.0-p[1];
    for(int i=2; i<=n; i++){
        dp[i][0] = dp[i-1][0]*(1.0-p[i]);
    }
    dp[1][1] = p[1];
    for(int i=2; i<=n; i++){
        dp[i][i] = dp[i-1][i-1]*p[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            dp[i][j] = dp[i-1][j]*(1.0-p[i]) + dp[i-1][j-1]*p[i];
        }
    }
    double res = 0;
    for(int i=n/2+1; i<=n; i++){
        res += dp[n][i];
    }
    cout<<fixed<<setprecision(10)<<res;
    return 0;
}

Measured memory_bytes: 70656
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new MyInputStream(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(MyInputStream cin)
        {
            var N = cin.ReadInt();
            WriteLine(N / 3);
        }
    }

    public class MyInputStream
    {
        private readonly System.IO.TextReader _stream;
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(System.IO.TextReader s, char separator = ' ')
        {
            this.separator = separator;
            this._stream = s;
            inputStream = new Queue<string>();
        }
        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = _stream.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
        public string ReadLine() { return _stream.ReadLine(); }
        public int ReadInt() { return int.Parse(Read()); }
        public long ReadLong() { return long.Parse(Read()); }
        public double ReadDouble() { return double.Parse(Read()); }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read(); return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt(); return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong(); return ret;}
        public void ReadIntArrays(long N, out int[] A, out int[] B) { A = new int[N]; B = new int[N]; for (long i = 0; i < N; ++i) { A[i] = ReadInt(); B[i] = ReadInt(); }}
    }
}


Measured memory_bytes: 11220
#include <stdlib.h>
typedef long long LL;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
int acs(const void*a,const void*b){return*(int*)a-*(int*)b;}
int des(const void*a,const void*b){return*(int*)b-*(int*)a;}
#define N 100009
int n,a[N],b[N],c[N];LL ans=0;
int compA(int x,int y){return a[y]>=x?1:0;}
int compC(int x,int y){return c[y]<=x?1:0;}
LL BS(int x,int n,int c){
	int O=n,X=-1,mid=n/2;
	while(O-X>1){
		mid=(O+X)/2;
		if(c)compA(x,mid)?(O=mid):(X=mid);else compC(x,mid)?(O=mid):(X=mid);
	}
	return O;
}

int main(){
	scanf("%d",&n);
	rep(i,n)scanf("%d",a+i);
	qsort(a,n,sizeof(int),acs);
	rep(i,n)scanf("%d",b+i);
	qsort(b,n,sizeof(int),acs);
	rep(i,n)scanf("%d",c+i);
	qsort(c,n,sizeof(int),des);
	rep(i,n)ans+=BS(b[i],n,1)*BS(b[i],n,0);
	printf("%lld",ans);
}

Measured memory_bytes: 3304
///A drunk man will find his way home, but a drunk bird may get lost forever...
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define int long long
#define sz(x) (int)x.size()
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int a;
	cin >> a;
	cout << 3 * (a * a) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
 
using namespace std;
 
 int main(void){
     int N,M,min,check,a;
     cin >> N >> M;
     int A[N+10],B[N+10],C[M+10],D[M+10];
     for(int i=0; i<N; i++){
         cin >> A[i] >> B[i];
     }for(int i=0; i<M; i++){
         cin >> C[i] >> D[i];
     }
     for(int i=0; i<N; i++){
        min=abs(A[i]-C[0])+abs(B[i]-D[0]);
        check=1;
        for(int j=1; j<M; j++){
            a=abs(A[i]-C[j])+abs(B[i]-D[j]);
            if(min>a){
                min=a;
                check=j+1;
            }
        }

        cout << check << endl;
     }

     return 0;
 }


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    char X, Y;
    int x, y;

    scanf("%c %c", &X, &Y);

    switch(X){
        case 'A': x = 10; break;
        case 'B': x = 11; break;
        case 'C': x = 12; break;
        case 'D': x = 13; break;
        case 'E': x = 14; break;
        default:x = 15;
    }

    switch(Y){
        case 'A': y = 10; break;
        case 'B': y = 11; break;
        case 'C': y = 12; break;
        case 'D': y = 13; break;
        case 'E': y = 14; break;
        default:y = 15;
    }

    if(x < y)
        printf("<\n");
    else if(x > y)
        printf(">\n");
    else
        printf("=\n");

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n,m,i,a[51],b[51],c[51],k,j;
	float sum,mx,s;
	while(1){
		mx=0.0;
		cin>>n;
		if(n==0) break;
		cin>>m;
		for(i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
		for(i=0;i<n;i++){
			if(c[i]==1){
				sum=10000+m*b[i]*100;
				//printf("A %f\n",sum);
				if(mx<sum) mx=sum,k=a[i];
			}
			else {
				sum=1.0;
				s=1+(float)b[i]/100;
				for(j=0;j<m;j++){
					sum*=s;
				}
				sum=sum*10000;
					//printf("B %f\n",sum);
				if(mx<sum) mx=sum,k=a[i];
			}
		}
		printf("%d\n",k);
	}
	return 0;
}


Measured memory_bytes: 3060
import copy

D = int(input())
c = list(map(int,input().split()))
s = []
for i in range(D):
    s.append(list(map(int,input().split())))
last = [0]*26
    
ans = 0
md = [0]*26
cand = []
tl = []

for day in range(D):
    for j in range(26):
        last[j] += 1
    
    for k in range(26):
        #k番目を選ぶことによる
        merit = s[day][k]
        merit += last[k] * c[k]
        demerit = 0
        for j in range(26):
            if j != k:
                demerit += c[j] * last[j]
        md[k] = merit - demerit

    #日程の確定
    md2 = sorted(md)
    t = md.index(md2[-1])
    last[t] = 0
    tl.append(t+1)
    
    can = md.index(md2[-2])
    cand.append(can+1)
    #print(t+1)
 
#得点計算

def calcans(tl):
    last = [0]*26
    ans = 0
    for day in range(D):
        #満足度プラス計算
        ans += s[day][tl[day]-1]
        for j in range(26):
            last[j] += 1
        last[tl[day]-1] = 0
        #満足度マイナス計算
        minus = 0
        for j in range(26):
            minus += c[j] * last[j]
        ans -= minus
    return ans

normal = calcans(tl)
change = -1
for ii in range(D):
    tl2 = copy.deepcopy(tl)
    tl2[ii] = cand[ii]
    
    challenge = calcans(tl2)
    if normal < challenge:
        normal = challenge
        change = ii
        
if change >= 0:
    tl[change] = cand[change]
    
for tlc in tl:
    print(tlc)

Measured memory_bytes: 9516
#include <bits/stdc++.h>
#define int_inf 1000000000 //1e9
#define ll_inf  1000000000000000000 //1e18

using namespace std;






int main(){
	int c[3][3];
	for(int i=0; i<3; i++){
	for(int j=0; j<3; j++){
		cin>>c[i][j];
	}}
	
	int a;
	a=c[0][0]-c[0][1];
	if(c[1][0]-c[1][1]==a && c[2][0]-c[2][1]==a){}
	else{ cout<<"No"<<endl; return 0; }

	a=c[0][2]-c[0][1];
	if(c[1][2]-c[1][1]==a && c[2][2]-c[2][1]==a){}
	else{ cout<<"No"<<endl; return 0; }
	
	a=c[0][0]-c[1][0];
	if(c[0][1]-c[1][1]==a && c[0][2]-c[1][2]==a){}
	else{ cout<<"No"<<endl; return 0; }
	
	a=c[2][0]-c[1][0];
	if(c[2][1]-c[1][1]==a && c[2][2]-c[1][2]==a){}
	else{ cout<<"No"<<endl; return 0; }
	
	cout<<"Yes"<<endl;
	
	return 0;
}




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

int main() {
  string S;
  cin >> S;
  
  if (S[0] == S[1] && S[1] == S[2] || S[1] == S[2] && S[2] == S[3] || S[0] == S[1] == S[2] == S[3]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
il = [int(k) for k in input().split()]

H = il[0]
W = il[1]
# H : 縦
#  W : 横

import math

a = math.ceil(W/2)
b = math.floor(W/2)
c = math.ceil(H/2)
d = math.floor(H/2)

if H == 1 or W == 1:
    print("1")
else:
    print(a*c + b*d)


Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
#define RI int
#define CI const int&
using namespace std;
const int N=105;
int n,m,s,mod,ans,C[N][N],f[N][N][N][2],coef[N][N][N][2];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int sum(CI x,CI y)
{
	int t=x+y; return t>=mod?t-mod:t;
}
inline int sub(CI x,CI y)
{
	int t=x-y; return t<0?t+mod:t;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	RI i,j,k,l; scanf("%d%d%d%d",&n,&m,&s,&mod);
	for (C[0][0]=i=1;i<=max(n,m);++i) for (C[i][0]=j=1;j<=i;++j)
	C[i][j]=sum(C[i-1][j],C[i-1][j-1]);
	for (k=1;k<=s;++k) for (i=0;i<=m;++i)
	{
		int cur=1LL*quick_pow(s-k+1,i)*sub(quick_pow(k,m-i),quick_pow(k-1,m-i))%mod;
		for (coef[k][i][0][0]=j=1;j<=n;++j) coef[k][i][j][0]=1LL*coef[k][i][j-1][0]*cur%mod;
	}
	//for (k=1;k<=s;++k) for (i=0;i<=m;++i) for (j=0;j<=n;++j)
	//printf("%d ",coef[k][i][j][0]); putchar('\n');
	for (k=1;k<=s;++k) for (i=0;i<=n;++i)
	{
		int cur=1LL*quick_pow(k,n-i)*sub(quick_pow(s-k+1,i),quick_pow(s-k,i))%mod;
		for (coef[k][i][0][1]=j=1;j<=m;++j) coef[k][i][j][1]=1LL*coef[k][i][j-1][1]*cur%mod;
	}
	//for (k=1;k<=s;++k) for (i=0;i<=m;++i) for (j=0;j<=n;++j)
	//printf("%d ",coef[k][i][j][1]); putchar('\n');
	for (f[1][0][0][0]=k=1;k<=s;++k) for (i=0;i<=n;++i) for (j=0;j<=m;++j)
	{
		for (l=0;l<=n-i;++l)
		inc(f[k][i+l][j][1],1LL*f[k][i][j][0]*C[n-i][l]%mod*coef[k][j][l][0]%mod);
		for (l=0;l<=m-j;++l)
		inc(f[k+1][i][j+l][0],1LL*f[k][i][j][1]*C[m-j][l]%mod*coef[k][i][l][1]%mod);
	}
	return printf("%d",f[s+1][n][m][0]),0;
}

Measured memory_bytes: 18048