akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int k;
vector<int> a;

struct edge{
    int cost, from;
};

void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({1, 1});
    while(!q.empty()){
        pair<int, int> p = q.top();
        q.pop();
        edge e = {p.first, p.second};
        if(a[e.from] < a[(e.from * 10) % k]){
            a[(e.from * 10) % k] = e.cost;
            q.push({e.cost, (e.from * 10) % k});
        }
        if(a[e.from] + 1 < a[(e.from + 1) % k]){
            a[(e.from + 1) % k] = e.cost + 1;
            q.push({e.cost + 1, (e.from + 1) % k});
        }
    }
}

int main(){
    cin >> k;
    a = vector<int>(k, 999999);
    a[1] = 1;
    dijkstra();
    cout << a[0] << endl;
    return 0;
}


Measured memory_bytes: 1276
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
ans=0

if p==2:
  for i in range(n):
    if int(s[i])%2==0:
      ans+=n-i
  print(ans)
  sys.exit()

if p==5:
  for i in range(n):
    if int(s[i])%5==0:
      ans+=n-i
  print(ans)
  sys.exit()

l=[0,int(s[0])%p]
x=int(s[0])
y=1
for i in range(1,n):
  y*=10
  y%=p
  x+=(y*int(s[i]))%p
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=j*(j-1)//2
print(ans)

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

int main(){
  int N, K;
  cin >> N >> K;
  
  int d[K], A[K];

  int cnt = 0;

  int num[1000] ={0};
  for(int i=0; i<K; ++i){
    cin >> d[i];
    for(int j=0; j<d[i]; ++j){
      cin >> A[i];
      num[A[i]]++;
    }
  }


  for(int i=0; i<=N; ++i){
    if(num[i]) ++cnt;
  }
    cout << N-cnt;

  return 0;
}

Measured memory_bytes: 3596
#include <stdio.h>
#include <stdlib.h>
long long gcd(long long m,long long n)
{
    long long mod;
    while(n!=0)
    {
        mod=m%n;
        m=n;
        n=mod;
    }
    return m;
}
int main()
{
   long long A,B;
   scanf("%lld%lld",&A,&B);
   printf("%lld",A*B/gcd(A,B));
    return 0;
}


Measured memory_bytes: 128
#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> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int n;
  cin >> n;
  vector<ll> v(n);
  map<ll, int> mp;
  rep(i,n) {
    ll a;
    cin >> a;
    mp[a]++;
    if (mp[a] == 2) {
      mp[a] -= 2;
      v.push_back(a);
    }
  }
  sort(ALL(v), greater<>());
  if (v.size() <= 1) cout << 0 << endl;
  else cout << v[0] * v[1] << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 10236
import java.util.*;

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

        int num = sc.nextInt();

        int[] nums = new int[num];
        int max = 0;
        int second = 0;
        for(int i = 0; i < num; i++){
            nums[i] = sc.nextInt();
            if(nums[i] >= max){
                second = max;
                max = nums[i];
            }else if(nums[i] > second){
                second = nums[i];
            }
        }

        int ans;
        for(int i = 0; i < num; i++){
            if(nums[i] == max)ans = second;
            else ans = max;
            System.out.println(ans);
        }

    }
}

Measured memory_bytes: 85212
# ABC172 Making Triangle
N = int(input())
L = list(map(int,input().split()))
d = {i:L.count(i) for i in L}

L = sorted(L)
ans = 0
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            cnt += 1
            if L[k] < L[i] + L[j] and L[k] != L[i] and L[i] != L[j] and L[j] != L[k]:
                ans += 1
print(ans)

Measured memory_bytes: 9096
pos = int(input())
data = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"

data = data.split(', ')
print(data[pos-1])

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		int k =sc.nextInt();
		int ans = (int)(k*Math.pow(k-1,n-1));
		System.out.println(ans);

	}
}

Measured memory_bytes: 21844
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
typedef long long ll;
const int N=500005;
ll x,y,z;
using namespace std;

set<ll> S;
set<ll>::iterator it;
int main()
{
	#ifdef Kay
		freopen ("code.in","r",stdin);
		freopen ("code.out","w",stdout);
	#endif
	cin>>x>>y>>z;
	if (x>y) swap(x,y);
	if (y>z) swap(y,z);
	if (x>z) swap(x,z);
	if ((x&1) || (y&1) || (z&1)){printf ("0");return 0;}
	if (x==y && y==z){printf ("-1");return 0;}
	ll s=y-x,t=z-y,t1=0,t2=0;
	if (s==0) t1=10000000;
	else {while (s && s%2==0) s>>=1,t1++;}
	if (t==0) t2=10000000;
	else {while (t && t%2==0) t>>=1,t2++;}
	cout<<min(t1,t2);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		double masu[][]=new double[2][n];
		for(int i=0;i<n;i++) {
			masu[0][i]=sc.nextDouble();
			masu[1][i]=sc.nextDouble();
		}

		double g=0;
		int c=0;
		for(int i=0;i<n-1;i++) {
			for(int j=i+1;j<n;j++) {
				double b=Math.sqrt((Math.pow((double)masu[0][i]-masu[0][j],2))+(Math.pow((double)masu[1][i]-masu[1][j], 2)));
				g+=b;
				c++;
			}
		}
		double ans=g/c*(n-1);
		System.out.println(ans);
	}

}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rt return 0
#define endln "\n"
#define for1(i, a, b) for (long long int i = a; i < b; i++)
#define for2(i, a, b) for (long long int i = a; i > b; i--)
//  cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;typedef long long int i;
typedef long long int lli;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli t, n, x, y;
    cin >> n >> x >> y;
    // cin >> t;
    vector<lli> v;
    v.resize(n + 5, 0);

    for1(i, 1, n + 1)
    {
        for1(j, i + 1, n + 1)
        {
            lli a = j - i;
            lli b = abs(x - i) + 1 + abs(y - j);
            lli c = min(a, b);
            v[c] += 1;
        }
    }
    for1(i, 1, n)
    {
        cout << v[i] << endl;
    }
}

Measured memory_bytes: 256
N, M, X, Y = gets.split(' ').map(&:to_i)
s = gets.split(' ').map(&:to_i)
t = gets.split(' ').map(&:to_i)

w = s.max
z = t.min
if w < z && X < z && z <= Y 
  puts 'No War'
else
  puts 'War'
end

Measured memory_bytes: 1916
#include <bits/stdc++.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.end(),x.begin()
#define sz(x) ((int)x.size())
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pi;
int a, b, c, i, j, k;
long long ans = 0LL;
int main ()
{
	ll a,h,n,val = 0,k;
	scanf("%lld%lld",&n,&k);
    vl vec(n);
    for(int i = 0; i < n; ++ i){
        scanf("%lld",&a);
        vec[i] = a;
    }
    sort(all(vec));
    reverse(all(vec));
    for(int i = k; i < n; ++ i){
        ans += vec[i];
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
//Dijkstra
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int inf = 1001001001;

int main()
{
    /*
    std::priority_queue<
        int,              // 要素の型はint
        std::vector<int>, // 内部コンテナはstd::vector (デフォルトのまま)
        std::greater<int> // 昇順 (デフォルトはstd::less<T>)
        >
        que;
    */

    int n, m, r;
    cin >> n >> m >> r;
    int d[n];
    bool flag[n] = {};
    int confirmed = 0;
    //    priority_queue<pair<int, int>> q;
    std::priority_queue<
        pair<int, int>,              // 要素の型はint
        std::vector<pair<int, int>>, // 内部コンテナはstd::vector (デフォルトのまま)
        std::greater<pair<int, int>> // 昇順 (デフォルトはstd::less<T>)
        >
        q;
    //int S[m], T[m], D[m];
    vector<vector<pair<int, int>>> edge(n);
    for (int i = 0; i < m; i++)
    {
        int s, t, d;
        cin >> s >> t >> d;
        /*
        S[i] = s;
        T[i] = t;
        D[i] = d;
        */
        edge.at(s).push_back(make_pair(t, d));
    }
    for (int i = 0; i < n; i++)
    {
        d[i] = inf;
        //q.push(make_pair(inf, i));
    }
    d[r] = 0;
    q.push(make_pair(0, r));

    while (!q.empty() && confirmed != n)
    {
        pair<int, int> v = q.top();
        q.pop();

        if (!flag[v.second])
        {
            //cout << v.second << " " << v.first << endl;
            flag[v.second] = true;
            confirmed++;
            /*
            for (int i = 0; i < m; i++)
            {
                if (S[i] == v.second)
                {
                    if (d[T[i]] > d[S[i]] + D[i])
                    {
                        d[T[i]] = d[S[i]] + D[i];
                        q.push(make_pair(d[T[i]], T[i]);
                    }
                }
            }
            */
            for (int i = 0; i < edge.at(v.second).size(); i++)
            {
                if (d[edge.at(v.second).at(i).first] > d[v.second] + edge.at(v.second).at(i).second)
                {
                    d[edge.at(v.second).at(i).first] = d[v.second] + edge.at(v.second).at(i).second;
                    q.push(make_pair(d[edge.at(v.second).at(i).first], edge.at(v.second).at(i).first));
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (d[i] == inf)
        {
            cout << "INF" << endl;
        }
        else
        {
            cout << d[i] << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 13020
n, X = map(int, input().split())
x = list(map(int, input().split()))
for i in range(n-1):
    x[i+1] += x[i]
x.reverse()

c = [2 for _ in range(n)]
c[0] = 5
c[1] = 0

ans = 10**20
for k in range(1, n+1):
    tmp = sum(s * t for s, t in zip(x[::k], c[:(n-1)//k+1])) + X * (n+k)
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 25716
a_500 = int(input())
b_100 = int(input())
c_50 = int(input())
x = int(input())
count = 0
for a in range(a_500+1):
    for b in range(b_100+1):
        for c in range(c_50+1):
            if a*500+b*100+c*50 == x:
                count += 1
print(count)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a+b > c+d) cout << "Left" << endl;
  else if (a+b == c+d) cout << "Balanced" << endl;
  else cout << "Right" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
  static int Max = 1000;
  static int top;
  static int[] Stack = new int[Max];

  public static void main(final String[] args) {
    initialize();
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    String[] str = s.split(" ");
    for (int i = 0; i < str.length; i++) {
      if (Character.isDigit(str[i].charAt(0))) {
        push(Integer.parseInt(str[i]));
      }
      else if (String.valueOf(str[i]).equals("+")) {
        int a = pop();
        int b = pop();
        push(a + b);
      }
      else if (String.valueOf(str[i]).equals("-")) {
        int a = pop();
        int b = pop();
        push(b - a);
      }
      else if (String.valueOf(str[i]).equals("*")) {
        int a = pop();
        int b = pop();
        push(a * b);
      }
    }
    System.out.println(pop());
  }

  private static void initialize() {
    top = 0;
  }

  private static boolean isEmpty() {
    return top == 0;
  }

  private static boolean isFull() {
    return top >= Max - 1;
  }

  private static void push(int x) {
    if (isFull()) {
      throw new Error("Over Flow");
    }
    top++;
    Stack[top] = x;
  }

  private static int pop() {
    if (isEmpty()) {
      throw new Error("Under Flow");
    }
    top--;
    return Stack[top + 1];
  }

  private static void print(int[] A) {
    System.out.println(Arrays.toString(A));
  }
}


Measured memory_bytes: 26308
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
const ll INF=1<<27;
int n,a,b,c;
vector<int> l(10);
int ans=INF;
void dfs(int depth,vector<int> v){
    if(depth==n){
         map<ll, ll> mp;
        rep(i, n) {
            if (v[i] == 3) continue;
            mp[v[i]]++;
        }
        if (mp.size() != 3) return;
        else {
            vector<int> sum(3,0);
            vector<int> cnt(3,0);
            for(int i=0;i<n;i++){
            if(v[i]==0)sum[0]+=l[i],cnt[0]++;
            if(v[i]==1)sum[1]+=l[i],cnt[1]++;
            if(v[i]==2)sum[2]+=l[i],cnt[2]++;
            }
             int ret=0;
             int tmp=0;
             tmp=(cnt[0]-1)+(cnt[1]-1)+(cnt[2]-1);
               ret=abs(a-sum[0])+abs(b-sum[1])+abs(c-sum[2])+10*tmp;
               ans=min(ans,ret);
               return;
        }
    }
    for(int i=0;i<4;i++){
        v[depth]=i;
        dfs(depth+1,v);
    }
}
int main(){
 cin>>n>>a>>b>>c;
 l.resize(n);
 rep(i,n)cin>>l[i];
 vector<int> v(n,0);
 dfs(0,v);
 cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define lb(s,x) (lower_bound(all(s),x)-s.begin())
#define ub(s,x) (upper_bound(all(s),x)-s.begin())
#define uniq(a) a.erase(unique(all(a)),a.end())
#define bit(k) (1LL<<(k))
const int INF = 1e9;

#define debug(x) cerr<<(#x)<<": "<<(x)<<endl
template<class T,class U>
ostream& operator<<(ostream& o, const pair<T,U> &p){
    o<<"("<<p.first<<", "<<p.second<<")";
    return o;
}
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }

int mergecount(vector<int> &a) {
  int count = 0;
  int n = a.size();
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end());
    count += mergecount(b);
    count += mergecount(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i)
      if (k == (int)c.size())       a[i] = b[j++];
      else if (j == (int)b.size())  a[i] = c[k++];
      else if (b[j] <= c[k])   a[i] = b[j++];
      else                   { a[i] = c[k++]; count += n/2 - j; }
  }
  return count;
}

int main(void){
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    int res = INF;
    rep(mask, 1<<n){
        {
            int back_count = 0;
            rep(i,n){
                if(mask & bit(i)) back_count++;
            }
            if (back_count & 1) {
                continue;
            }
        }

        using P = pair<int,int>;
        vector<P> even, odd;
        rep(i,n){
            bool is_back = mask & bit(i);
            if ((i&1)^is_back) {
                odd.push_back({is_back ? b[i] : a[i], i});
            } else {
                even.push_back({is_back ? b[i] : a[i], i});
            }
        }
        sort(all(even));
        sort(all(odd));
        int E = even.size();
        int O = odd.size();
        if (n & 1) {
            if (E-O != 1) continue;
        } else {
            if (E != O) continue; 
        }

        bool ng = false;
        rep(i,n-1){
            if (i % 2 == 0) {
                if (even[i/2].first > odd[i/2].first) ng = true;
            } else {
                if (odd[i/2].first > even[(i+1)/2].first) ng = true;
            }
        }
        if (ng) continue;
        vector<int> v;
        rep(i,n){
            v.push_back((i % 2 == 0) ? even[i/2].second : odd[i/2].second);
        }
        res = min(mergecount(v), res);
    }
    cout << (res == INF ? -1 : res) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
#define rep(i,x,n) for(int i=x;i<n;i++)
using ll=long long;

int n;
string s;

ll gcl(ll x,ll y){
    if(x<y) swap(x,y);
    while(y>0){
        ll t=x%y;
        x=y;
        y=t;
    }
    return x;
}

ll fac(int n){
    if(n==0||n==1) return 1;
    return n*fac(n-1);
}

int main(){
    cin>>n;
    vector<vector<int> > S(n,vector<int>(26,0));
    rep(i,0,n){
        cin>>s;
        int m=s.size();
        rep(j,0,m) S[i][(int)(s[j]-'a')]++;
    }
    
    string ans;
    rep(i,0,26){
        int mina=51;
        rep(j,0,n){
            mina=min(mina,S[j][i]);
        }
        rep(j,0,mina){
            ans+=(char)(i+'a');
        }
    }
    cout<<ans<<endl;    
}

Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
edges = []
for i in range(M):
    a, b, c = getNM()
    edges.append([a - 1, b - 1, c])

def bellman(edges, num_v):
    dist = [-float('inf') for i in range(num_v)]
    dist[0] = 0

    # 一回目のループ
    for i in range(N - 1):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    # 負閉路検出
    nega = [0] * N
    for i in range(N):
        for edge in edges:
            # rootが既に更新されているなら行く際も更新される
            if nega[edge[0]] == 1:
                nega[edge[1]] = 1
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                nega[edge[1]] = 1

    if nega[N - 1]:
        print('inf')
        exit()

    return dist

print(bellman(edges, N)[N - 1])

Measured memory_bytes: 84868
import java.util.*;

public class Main {
    public static void main(String args[]) {
       //Nを取得
       Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();
       
       //出力
       //例えば、100回目の ABC は ABC100 です。
       System.out.println("ABC" + N);
    }
}

Measured memory_bytes: 38708
#define MAX 1000000

#include <stdio.h>
#include <string.h>

//?§???????.
typedef struct command {
	char txt[12];
	int x;
}com;

//????????????????????£?¨?.
void ins(int x);
void del(int x);
void delF(void);
void delL(void);

//??°?????????????????°.
int head = 0;
int tail = 0;
int num[MAX];


int main(void) {
	int n = 0;		//????????°.
	com buf;		//????????????.
	int i = 0;
	int k = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%s", buf.txt);		//?????????????????????.
		
		if (strcmp(buf.txt, "insert") == 0) {
			scanf("%d", &buf.x);
			ins(buf.x);
		}
		else if (strcmp(buf.txt, "delete") == 0) {
			scanf("%d", &buf.x);
			del(buf.x);
		}
		else if (strcmp(buf.txt, "deleteFirst") == 0) {
			delF();
		}
		else if (strcmp(buf.txt, "deleteLast") == 0) {
			delL();
		}
		/*
		for (k = head - 1; k >= tail; k--) {
			if (k != tail)
				printf("%d ", num[k]);
			else
				printf("%d\n", num[k]);
		}*/
	}

	for (i = head - 1; i >= tail; i--) {
		if (i != tail)
			printf("%d ", num[i]);
		else
			printf("%d\n", num[i]);
	}

	return 0;
}

void ins(int x) {
	num[head] = x;
	head++;
}

void del(int x) {
	int i = 0;
	int v[2] = {};

	int j = 1;

	v[1] = num[head - 1];

	for (i = head - 1; i >= tail; i--) {
		if (num[i] == x)
			break;
		if (i == tail)
			j = 0;
	}

	if (j) {
		for (i = head - 1; i >= tail; i--) {
			v[0] = num[i];
			num[i] = v[1];

			if (v[0] == x)
				break;
			else {
				v[1] = v[0];
			}
		}
		head--;
	}
}

void delF(void) {
	num[head - 1] = 0;
	head--;
}

void delL(void) {
	num[tail] = 0;
	tail++;
}

Measured memory_bytes: 4504
N = gets.to_i

a, b = 1, 1

N.times do |i|
  
  x, y = gets.split.map(&:to_i)
  
  n = [ (a+x-1)/x, (b+y-1)/y ].max
  a, b = x * n, y * n

end

p a + b


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;

const int mod = 1000000007;
const int inf = 1e9;
#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


ll choose(int n, int k) {
    ll ret = 1;
    k = min(k, n-k);
    for(int i = n; i >= n-k+1; i--) {
        ret *= i;
    }
    for(int i = 1; i <= k; i++) {
        ret /= i;
    }
    return ret;
}

ll ipow(int n, int k) {
    ll ret = 1;
    for(int i = 0; i < k; i++) {
        ret *= n;
    }
    return ret;
}

int main(){
    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        int b;
        cin >> b;
        a[i] = b%2;
    }
    int all = count(a.begin(), a.end(), 1);
    ll ans = 0;
    int init = (p == 1);
    for(int i = init; i <= all; i+=2) {
        ans += choose(all, i) * ipow(2, n-all);
    }
    cout << ans << endl;

}

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


long long int dfs(long long int sum, long long int r,string s, int dp){
  if(dp==s.size()){
    return sum + r;
  }
  else{
    long long int a = dfs(sum + r, s[dp]-'0', s, dp+1);//'+'in
    long long int b = dfs(sum, r*10+s[dp]-'0', s, dp+1);//not'+'in
    return a+b;
  }
}

int main(){
  string s;
  cin >> s;
  cout << dfs(0,s[0]-'0',s,1) << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().doIt();
	}
	void doIt() {
		solveC();
	}
	void solveC() {
		int N = sc.nextInt();
		int K = sc.nextInt();
		long [] h = new long[N];
		for(int i = 0; i < N; i++) {
			h[i] = sc.nextLong();
		}
		Arrays.sort(h);
		long ans = Long.MAX_VALUE;
		for(int i = K-1; i < N; i++) {
			long d = h[i] - h[i-K+1];
			ans = Math.min(ans, d);
		}
		System.out.println(ans);
		
	}
	void solveA() {
		int N = sc.nextInt();
		String ans = "Christmas";
		for(int i = N; i < 25; i++) {
			ans += " Eve";
		}
		System.out.println(ans);
	}
	void solveB() {
		int N = sc.nextInt();
		int [] p = new int[N];
		for(int i = 0; i < N; i++) {
			p[i] = sc.nextInt();
		}
		Arrays.sort(p);
		int ans = 0;
		for(int i = 0; i < N-1; i++) {
			ans +=p[i];
		}
		ans += p[N-1]/2;
		System.out.println(ans);
		
	}
}


Measured memory_bytes: 50164
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i < (n); i++)

int main(){
    int n;
    cin >> n;
    long long a;
    long long ans = 1;
    bool ok = true;
    rep(i,n){
        cin >> a;
        if(a==0){
            cout << 0 << endl;
            return 0;
        } else if(a > 1000000000000000000/ans){
            ok = false;
        }else{
            ans *= a;
        }
    }
    if(ok)cout << ans << endl;
    if(!ok)cout << "-1" << endl;
}

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

int matrixLR[501][501];//用来存储列车起止的矩阵 
int matrixPQ[501][501];//用来存储每个起止城市包含的列车数量的矩阵 
int result[100000]; 

int main(){
	
	int n,m,q;
	cin>>n>>m>>q;
	//填入数字 
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		matrixLR[l][r]++;
		//cout<<l<<"->"<<r<<":"<<matrixLR[l][r];
	}
	/**打印matrixLR	
		for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<matrixLR[i][j]<<" ";
		}
		cout<<endl;
	}
*/
	
	//先算对角线 
	for(int i=1;i<=n;i++){
		matrixPQ[i][i]=matrixLR[i][i];
	}
	//从对角线开始往右上方逐渐推
	for(int i=1;i<n;i++){
		for(int j=1;j<=n-i;j++){
			int row=j;
			int col=i+j;
		
			//每个单元格但是左侧单元格+下方单元格+LR矩阵的同单元格
			//从n开到m的列车总和=n开到m-1的列车总和+n+1开到m的列车总和+恰好n开到md的列车-n+1开到m-1的和 
			// 1开到4的总和=1开到3的总和+2开到4的总和+刚好1开到4的-2开到3的总和 
			matrixPQ[row][col]=matrixPQ[row+1][col]+matrixPQ[row][col-1]+matrixLR[row][col]-matrixPQ[row+1][col-1];
			//	cout<<row<<"->"<<col<<":"<<matrixPQ[row][col]<<endl; 
		}
	} 
	/**打印matrixPQ	 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<matrixPQ[i][j]<<" ";
		}
		cout<<endl;
	}
	*/

	
	for(int i=0;i<q;i++){
		int pi,qi;
		cin>>pi>>qi;
		result[i]=matrixPQ[pi][qi];
	}
	
	for(int i=0;i<q;i++){
		cout<<result[i]<<endl;
	}
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define I64 "%I64d"
#define RAN(v)v.begin(),v.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
template<class T>
inline void upd1(T&a,T b){a>b?a=b:0;}
template<class T>
inline void upd2(T&a,T b){a<b?a=b:0;}
struct ano{
	operator ll(){
		ll x=0,y=0,c=getchar();
		while(c<48)
			y=c==45,c=getchar();
		while(c>47)
			x=x*10+c-48,c=getchar();
		return y?-x:x;
	}
}buf;
const int N=5e5+5;
char a[N],b[N];
int c[N],f[N][3];
int sol(int l,int r){
	int k=0,m=0;
	for(int i=l;i<=r;++i)
		if(a[i]=='1'){
			++k;
			if(i==r||a[i+1]=='0')
				c[++m]=k,k=0;
		}
	f[0][1]=-1e9;
	for(int i=1;i<=m;++i){
		f[i][0]=max(f[i-1][2]+c[i],f[i-1][0]+c[i]-1);
		f[i][1]=max(f[i-1][2],f[i-1][1]+c[i]-1);
		f[i][2]=max(f[i-1][2],max(f[i-1][0],f[i-1][1]+c[i]));
		if(c[i]!=1)
			upd2(f[i][1],f[i-1][0]);
	}
	return f[m][2];
}
int main(){
	int l=1,r=buf,s=0;
	scanf("%s",a+1);
	while(a[l]=='0')++l;
	while(a[r]=='0')--r;
	for(int i=l;i<=r;++i)
		if(a[i]=='1'&&a[i+1]!='1'&&a[i+2]!='1'){
			s+=sol(l,i);
			l=i+1;
			while(a[l]=='0')++l;
		}
	printf("%d\n",s);
}

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  constexpr int64_t mod = 1000000007;

  int64_t n;
  std::string s;
  std::cin >> n >> s;

  int64_t m = 0;
  int64_t ans = 1;

  for (const auto c : s) {
    if (m % 2 == 0) {
      if (c == 'W') {
        if (m == 0) {
          std::cout << 0 << std::endl;
          return 0;
        } else {
          ans *= m;
          ans %= mod;
          m--;
        }
      } else {
        m++;
      }
    } else {
      if (c == 'W') {
        m++;
      } else {
        if (m == 0) {
          std::cout << 0 << std::endl;
          return 0;
        } else {
          ans *= m;
          ans %= mod;
          m--;
        }
      }
    }
  }
  if (m != 0) {
    std::cout << 0 << std::endl;
  } else {
    for (int64_t i = 1; i <= n; i++) {
      ans *= i;
      ans %= mod;
    }
    std::cout << ans << std::endl;
  }

  return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int D = sc.nextInt();
        int diff = 25 - D;

        System.out.print("Christmas");
        for (int i = 0; i < diff; i++) {
            System.out.print(" Eve");
        }

        System.out.println();
    }

}





Measured memory_bytes: 21716
/*
	  Chase
	   Your
	  Legend

	英雄志逐传奇
*/

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <stdio.h>

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

int main() {
	string s;
	cin >> s;

	ll gcnt = 0;
	ll pcnt = 0;
	rep(i, s.size()) {
		if (s[i] == 'g') {
			gcnt++;
		}
		else {
			pcnt++;
		}
	}
	cout << (s.size() / 2) - pcnt << endl;

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
    
    #define fio ios_base::sync_with_stdio(false), cin.tie(NULL)
    #define ll long long int
    #define ull unsigned long long int
    #define ld long double
    #define sb __builtin_popcount
    #define vi vector<int>
    #define vl vector<ll>
    #define vc vector<char>
    #define ii pair<int, int>
    #define pq priority_queue<ii, vector<ii>, greater<ii>>
    #define vii vector<ii>
    #define viii vector<tuple<ll, ll, ll>>
    #define sz(a) int((a).size())
    #define f(a, b) for (int i = a; i < b; i++)
    #define fr(a, b) for (int i = a - 1; i >= b; i--)
    #define tr(x, m) for (auto x : m)
    #define in(a, b) (b.find(a) != string::npos)
    #define minin(a) *min_element(all(a))
    #define maxin(a) *max_element(all(a))
    #define bs(l, h, k) equal_range(l, h, k);
    #define X first
    #define Y second
    #define fill(a, x) memset(a, x, sizeof(a))
    #define pb push_back
    #define pf push_front
    #define mp make_pair
    #define all(v) v.begin(), v.end()
    #define rall(v) reverse(v.begin(), v.end())
    #define unq(v) v.erase(unique(all(v)), v.end())
    #define el "\n"
    #define mx3(a, b, c) max(max(a, b), c)
    #define S(v) accumulate(all(v), (ll)0)
    #define IP(v1, v2) inner_product(all(v1), v2.begin(), (ll)0)
    const long double PI = atan(1.0) * 4.0;
    const ll MOD = 1e9 + 7;
    const ll INF = 1e18;
    const ld EPS = 0.0000001;
      
        int main() {
            fio;
            ll n;
            cin>>n;
            ll ans=0;
            for(ll i=1;i<=n;i++){
            if(i%3!=0 && i%5!=0)
                 ans+=i;
            }
            cout<<ans<<el;
            return 0;
        }


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

using namespace std;

int query(int i) {
    cout << i << endl << flush;
    string s;
    cin >> s;
    if(s=="Vacant") {
        exit(0);
    } else if(s=="Male") {
        return 0;
    } else {
        return 1;
    }
}

int main() {
    int n;
    cin >> n;
    int l = 0, r = n, ls, rs;
    ls = rs = query(l);
    for(int t=1; t<20; t++) {
        int m = (l + r + 1) / 2;
        int ms = query(m);
        if(((m-l)&1)^(ls^ms)) {
            r = m;
            rs = ms;
        } else {
            l = m;
            ls = ms;
        }
    }
}


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

using namespace std;

int main(int argc, char const *argv[])
{
    int n; cin >> n;
    vector<int> h(n, 0);
    for(int i=0;i<n;++i) cin >> h[i];
    int c = 1; n = h[0];
    for(auto v = h.begin()+1;v!=h.end();++v) {
        if(*v>=n) ++c;
        n = max(*v,n);
    }
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 100011;

ll n, S, i, l, r;
ll x[maxN], p[maxN];
ll ans;

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%lld%lld", &n, &S);
    for (i = 1; i <= n; i++)
        scanf("%lld%lld", &x[i], &p[i]);

    l = 1; r = n;
    while (true) {
        if (S < x[l]) {
            ans += x[r] - S;
            break;
        }

        if (S > x[r]) {
            ans += S - x[l];
            break;
        }

        ans += x[r] - x[l];

        bool any = false;
        while (x[r] > S && p[l] >= p[r]) {
            p[l] += p[r];
            r--;
            any = true;
        }

        if (any) continue;

        while (x[l] < S && p[l] < p[r]) {
            p[r] += p[l];
            l++;
        }
    }

    printf("%lld", ans);

    return 0;
}


Measured memory_bytes: 1792
from collections import deque

n, x, y = map(int, input().split())
eage = [[] for _ in range(n)]

for i in range(n-1):
  eage[i].append( i+1 )
  eage[i+1].append( i )

x -= 1
y -= 1

eage[x].append( y )
eage[y].append( x )

visited = [[-1] * n for _ in range(n)]

counter = [0] * n
for start_point in range(n):
  visited[start_point][start_point] = 0
  # [0] とか [0, 2, 3] とか [1, 3]
  q = deque([start_point])
  while q:
    v = q.popleft()
    for j in eage[v]:
      # 未訪問
      if visited[start_point][j] == -1:
        # v が start_point の切り替え役
        visited[start_point][j] = visited[start_point][v] + 1
        q.append( j )
  for c in visited[start_point]:
    counter[c] += 1

for ans in counter[1:]:
  print(ans // 2)


Measured memory_bytes: 78684
#include <iostream>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <vector>
#include <cmath>
#include <cstdint>
#include <string>
#include <climits>

using namespace std;

int main() {
  int count;
  std::vector<int> X;
  cin >> count;
  for (int i = 0; i < count; ++i) {
    int x;
    cin >> x;
    X.push_back(x);
  }
  int minX = INT_MAX;
  int maxProfit = INT_MIN;
  for (int j = 1; j < X.size(); ++j) {
    minX = min(minX, X[j - 1]);
    maxProfit = max(X[j] - minX, maxProfit);
  }
  cout << maxProfit << endl;
}



Measured memory_bytes: 3912
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.List

main = do
  n <- readLn :: IO Int
  a <- group . sort <$> getIntListBC
  let num = if even n then [1+(i*2) | i <- [0..(div n 2)-1]]
                      else [i*2 | i <- [0..(div n 2)]]
      rep = map head a
      count = map length a
  if num == rep && check count (even n)
    then print $ power $ div n 2
    else print 0

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine

check :: [Int] -> Bool -> Bool
check num b
  | b == True = and $ map (==2) num
  | otherwise = (head num) == 1 && (and $ map (==2) $ tail num)

power :: Int -> Int
power 0 = 1
power n = flip mod (10^9+7) . (*2) $ power (n-1)


Measured memory_bytes: 17788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(auto it = (o).begin(); it != (o).end(); ++ it)
typedef long long ll;
struct edge { int to; int from; int cost; };
struct vertex { int x; int y; int idx;};

struct UnionFind {
    vector<int> par; // 親
    vector<int> rank; // 木の深さ

    UnionFind() {
    }

    // n要素で初期化
    void init(int n) {
        par.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    // 木の根を求める
    int find(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            return par[x] = find(par[x]);
        }
    }

    // xとyの属する集合を併合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }

        if (rank[x] < rank[y]) {
            par[x] = y;
        }
        else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

    // xとyが同じ集合に属するか否か
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int cost(const vertex& v1, const vertex& v2) {
    return min(abs(v1.x - v2.x), abs(v1.y - v2.y));
}

bool compX(const vertex& v1, const vertex& v2) {
    return v1.x < v2.x;
}

bool compY(const vertex& v1, const vertex& v2) {
    return v1.y < v2.y;
}

bool compCost(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

vector<vertex> vt;
vector<edge> es;
UnionFind uf;

class Solution {
public:
    void solve(std::istream& in, std::ostream& out) {
        int n;
        in >> n;
        vt.clear();
        vt.resize(n);
        rep(i, n) {
            in >> vt[i].x >> vt[i].y;
            vt[i].idx = i;
        }
        
        es.clear();
        uf.init(n);
        sort(vt.begin(), vt.end(), compX);
        int c;
        edge e;
        rep(i, n - 1) {
            e.from = vt[i + 0].idx;
            e.to = vt[i + 1].idx;
            e.cost = cost(vt[i + 0], vt[i + 1]);
            es.push_back(e);
        }

        sort(vt.begin(), vt.end(), compY);
        rep(i, n - 1) {
            e.from = vt[i + 0].idx;
            e.to = vt[i + 1].idx;
            e.cost = cost(vt[i + 0], vt[i + 1]);
            es.push_back(e);
        }

        sort(es.begin(), es.end(), compCost);

        ll res = 0;
        each(it, es) {
            if (!uf.same(it->to, it->from))
            {
                uf.unite(it->to, it->from);
                res += it->cost;
            }
        }

        out << res << endl;
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}

#include <fstream>
#include <iostream>

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;

    solve(in, out);
    return 0;
}


Measured memory_bytes: 6900
N, Y = map(int, input().split())

for x in range(N+1):
    for y in range(N + 1 - x):
        z = N - x - y
        total_yen = 10000 * x + 5000 * y + 1000 * z
        if total_yen == Y:
            print(x, y, z)
            exit()
print(-1, -1, -1)


Measured memory_bytes: 2940
houses = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]
n = int(input())
for i in range(n):
    b, f, r, v = map(int, input().split())
    houses[b-1][f-1][r-1] += v
for b in range(4):
    for f in houses[b]:
        print('', *f)
    if b != 3:
        print('#' * 20)


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

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
//const LL LINF = INF * (LL) INF;

int n , x , y;
int a[2001];

int dpT[2001][2];
/*int dp(int idx1 , int idx2 , int step)
{
	if(idx1 == n || idx2 == n)
		return abs(a[idx1] - a[idx2]);
	if(dpT[idx1][idx2][step] != -1)
	{
		return dpT[idx1][idx2][step];
	}
	int ans = 0;
	if(step == 0)
	{
		ans = -1;
		int newIdx = max(idx1 , idx2) + 1;
		for(int j = newIdx; j <= n; j++)
		{
			ans = max(ans , dp(j , idx2 , 1));
		}
	}
	else
	{
		ans = INF;
		int newIdx = max(idx1 , idx2) + 1;
		for(int j = newIdx; j <= n; j++)
		{
			ans = min(ans , dp(idx1 , j , 0));
		}
	}
	return dpT[idx1][idx2][step] = ans;
}*/
int main()
{
	cin >> n >> x >> y;
	a[0] = y;
	memset(dpT , -1 , sizeof dpT);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i + 1];
	}
	for(int i = n - 1; i >= 0; i--)
	{
		for(int step = 0; step < 2; step++)
		{
			int ans = 0;
			if(step == 0)
			{
				ans = 0;
			}
			else
				ans = INF;
			for(int j = i + 1; j <= n; j++)
			{
				if(j == n && step == 0)
				{
					ans = max(ans , abs(a[i] - a[n]));
					continue;
				}
				if(j == n && step == 1)
				{
					ans = min(ans , abs(a[i] - a[n]));
					continue;
				}
				if(step == 0)
				{
					ans = max(ans , dpT[j][1]);
				}
				else
					ans = min(ans , dpT[j][0]);
			}
			dpT[i][step] = ans;
		}
	}
	cout << dpT[0][0];
	//cout << dp(0 , 0 , 0);
}


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

const int Mod=1e9+7;

int N,M,Ans;
int F[3005][3005][2];

void Add(int &x,int y){
	if((x+=y)>=Mod)
		x-=Mod;
}

int main(){
	int i,j,k;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)
		F[0][i][0]=1;
	F[0][0][1]=1;
	for(i=0;i<M;i++)
		for(j=0;j<=N;j++)
			for(k=0;k<2;k++)
				if(F[i][j][k]){
					if(j){
						Add(F[i+1][j][k|(j<2)],F[i][j][k]);
						Add(F[i+1][j-1][k|(j<2)],F[i][j][k]);
					}
					if(j<N){
						Add(F[i+1][j][k],F[i][j][k]);
						Add(F[i+1][j+1][k],F[i][j][k]);
					}
				}
	for(i=0;i<=N;i++)
		Add(Ans,F[M][i][1]);
	printf("%d\n",Ans);
	return 0;
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int n,q,p[400001];
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
int main()
{
	scanf("%d%d",&n,&q);
	priority_queue<tuple<int,int,int,int>> s;
	while(q--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		s.emplace(-c,0,a,b);
		s.emplace(-c-1,1,a,(a+1)%n);
		s.emplace(-c-2,1,b,(b+1)%n);
	}
	for(int i=1;i<=n;i++)p[i]=i;
	unordered_set<int> vis;
	long long ans=0;
	int i=1;
	while(i<n)
	{
		int w=-get<0>(s.top()),v=get<1>(s.top()),x=get<2>(s.top()),y=get<3>(s.top()),px=find(x),py=find(y);s.pop();
		if(px!=py)p[px]=py,ans+=w,i++;
		if(v&&!vis.count(x))vis.insert(x),s.emplace(-w-2,1,(x+1)%n,(x+2)%n);
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 20580
x, y = map(int, input().split())

a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]

if x in a and y in a:
  print('Yes')
elif x in b and y in b:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
n,m=map(int,input().split())
l=[]
if n%2==0:
  i=1
  while i<n//2+1-i:
    l.append((i,n//2+1-i))
    i+=1
  j=1
  while j<n//2-j:
    l.append((n//2+j,n-j))
    j+=1
else:
  for i in range(1,n//2+1):
    l.append((i,n-i))
for a,b in l[:m]:
  print(a,b)

Measured memory_bytes: 21700
#include <iostream>
#include <vector>
#include <string>
//#include "./libb/lib.hpp"

using namespace std;

int main()
{
    int aa;
    int bb;
    int cc;
    int dd;
    cin >> aa >> bb >> cc >> dd;

    while((aa > 0) || (cc > 0)){

        cc -= bb;
        //cout << "cc is " << cc << endl;
        if(cc <= 0){
            cout << "Yes" << endl;
            return 0;
        }

        aa -= dd;
        //cout << "aa is " << aa << endl;
        if(aa <= 0){
            cout << "No" << endl;
            return 0;
        }

    }

    cout << "any" << endl;
    return 1;
}

Measured memory_bytes: 3592
n = int(input())

s = [list(input()) for _ in range(n)]
a = [0 for _ in range(26)]

for i in range(len(s[0])):
    a[ord(s[0][i]) - ord("a")] += 1

for i in range(1, n):
    b = [0 for _ in range(26)]
    for j in range(len(s[i])):
        if a[ord(s[i][j]) - ord("a")] == 0:
            continue
        else:
            b[ord(s[i][j]) - ord("a")] += 1

    for k in range(26):
        a[k] = min(a[k], b[k])

if a.count(0) == 26:
    print()
else:
    ans = "" 
    for i in range(26):
        for j in range(a[i]):
            ans += chr(i + ord("a"))
    print(ans)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
	int X, Y, Z;
	int counter[5];
	for (int i = 0; i < 3; i++)
	{
		cin >> counter[i];
	}
	X = counter[2];
	Y = counter[0];
	Z = counter[1];
	cout << X << ' ' << Y << ' ' << Z;
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b)-1; i >= (a); --i)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;


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

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

	VI np, f, t;
	FOR (i, 0, n)
	{
		int x;
		scanf("%d", &x);
		if (x & 1) np.PB(x);
		else if (x % 4 == 0) f.PB(x);
		else t.PB(x);
	}

	if (SZ(np) == SZ(f) + 1 && SZ(t) == 0)
	{
		printf("Yes\n");
	}
	else
	if (SZ(np) > SZ(f))
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
	/*	FOR (i, 0, SZ(np))
		{
			printf("%d %d ", np[i], f[i]);
		}

		FOR (i, SZ(np), SZ(f))
		{
			printf("%d ", f[i]);
		}

		FOR (i, 0, SZ(t))
		{
			printf("%d ", t[i]);
		}
		printf("\n");*/
	}

} 


Measured memory_bytes: 1012
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	string s; cin >> s;
	vi v(26);
	for (auto i : s)
	{
		v[i - 'a']++;
	}
	bool f = true;
	for (auto i : v)
	{
		if (i % 2) f = false;
	}
	cout << (f ? "Yes" : "No") << endl;
	return 0;
}

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

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        s: String,
    }
    
    let ans = if s == "RRR".to_string() {
        3
    } else if s == "RSR".to_string() || s ==  "SSR".to_string() || s == "RSS".to_string() || s == "SRS".to_string() {
        1
    } else if s == "RRS".to_string() || s == "SRR".to_string() {
        2
    } else {
        0
    };

    println!("{}", ans)
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
int main() {
  int A,B;
  cin>>A>>B;
  
  if(A-2*B>0) {
    cout<<A-2*B<<endl;
  }
  
  else{
    cout<<"0"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
S = gets.chomp
RS = S.split("").reverse.join("")
flag = true
index = S.length-1

if S != RS
  flag = false
end
sub_str1 = S.slice(0..(index-1)/2)
if sub_str1 != sub_str1.split("").reverse.join("")
  flag = false
end
sub_str2 = S.slice((index+3)/2..-1)
if sub_str2 != sub_str2.split("").reverse.join("")
  flag = false
end

puts flag ? "Yes" : "No"

Measured memory_bytes: 1788