akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

class U {
public:
  int n;
  vector<int> p, s;
  U(int _) {
    n = _;
    p.resize(n);
    s.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = i;
      s[i] = 1;
    }
  }
  bool connect(int a, int b) {
    int ap, bp;
    for (ap = p[a]; ap != p[ap]; ap = p[ap])
      ;
    for (bp = p[b]; bp != p[bp]; bp = p[bp])
      ;
    if (ap == bp)
      return true;
    int mi = min(ap, bp), ma = max(ap, bp);
    p[ma] = mi;
    s[mi] += s[ma];
    s[ma] = 0;
    for (int pp = a; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    for (int pp = b; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    return false;
  }
  int q(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap])
      ;
    return s[ap];
  }
  int parent(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap])
      ;
    return p[ap];
  }
  bool query(int a, int b) { return parent(a) == parent(b); }
};

struct N {
  int x, y, i;
};

struct P {
  int cost, i, j;
};

bool operator<(const P &lhs, const P &rhs) { return lhs.cost < rhs.cost; }

int main() {
  int n;
  cin >> n;
  vector<N> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].x >> v[i].y;
    v[i].i = i;
  }
  multiset<P> q;
  sort(v.begin(), v.end(),
       [](const N &lhs, const N &rhs) { return lhs.x < rhs.x; });
  for (int i = 1; i < n; i++) {
    q.insert(P{v[i].x - v[i - 1].x, v[i - 1].i, v[i].i});
  }
  sort(v.begin(), v.end(),
       [](const N &lhs, const N &rhs) { return lhs.y < rhs.y; });
  for (int i = 1; i < n; i++) {
    q.insert(P{v[i].y - v[i - 1].y, v[i - 1].i, v[i].i});
  }
  U u(n);
  int ans = 0, c = 0;
  while (c < n - 1) {
    P top = *q.begin();
    q.erase(q.begin());
    if (!u.connect(top.i, top.j)) {
      c++;
      ans += top.cost;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 14720
#include<stdio.h>
void bubbleSort(int[],int);

int main(){
  int A[100],n,i,j;

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

  return 0;
}

void bubbleSort(int a[], int n){
  int count=0,flag=1,i,j,temp;
  
  for(i = 0 ; flag ; i++){
    flag = 0;
      for(j = n - 1 ; j >= i+1 ; j--){
      if (a[j] < a[j-1]){
	temp = a[j];
	a[j] = a[j-1];
	a[j-1] = temp;
	flag = 1;
	count++;
      }
    }
  }

  for(i = 0 ; i < n ; i++){
    if(i > 0) printf(" ");
    printf("%d",a[i]);
  }
  printf("\n%d\n",count);
}
      
  



Measured memory_bytes: 2144
from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    paired_dict = {i: [] for i in range(n)}
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        paired_dict[a-1].append(b-1)
        paired_dict[b-1].append(a-1)

    done_set = set([])
    que = deque([a-1])
    i = 0
    ans = 0
    while que:
        x = que.popleft()
        done_set.add(x)
        if x in paired_dict.keys():
            for one in paired_dict[x]:
                if one in done_set:
                    continue
                que.append(one)
                done_set.add(one)

        while (not que) and len(done_set)!=n:
            if i not in done_set:
                que.append(i)
                ans+=1
            i+=1
            if n<i:
                i = 0

    print(ans)

if __name__=="__main__":
    main()


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

int main()
{
    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, N)
    {
        cin >> S.at(i);
    }
    vector<int> S_flag(N, 1);
    int M;
    cin >> M;
    vector<string> T(M);
    rep(i, M)
    {
        cin >> T.at(i);
    }

    int cnt = 0;
    int ans = 0;

    rep(i, N)
    {
        cnt = 0;
        if (S_flag.at(i) == 0)
        {
            break;
        }

        rep(j, N)
        {
            if (S.at(i) == S.at(j))
            {
                cnt++;
                S_flag.at(j) = 1;
            }
        }
        rep(j, M)
        {
            if (S.at(i) == T.at(j))
            {
                cnt--;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::iter::*;
#[allow(unused_imports)]
use std::cmp::*;

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(std::io::stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.read()).collect()
    }

    fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(104_857_600)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}

fn is_prime(n: u32) -> bool {
    if n <= 1 {
        return false;
    }
    for i in 2..n {
        if i * i > n {
            break;
        }
        if n % i == 0 {
            return false;
        }
    }
    true
}

fn eratosthenes_sieve(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..n+1 {
        if is_prime[i] {
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i;
            }
        }
    }
    is_prime
}

fn solve() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n = sc.read();
    let is_prime = eratosthenes_sieve(100000000);
    let mut cnt = 0;
    for _ in 0..n {
        let x: usize = sc.read();
        if is_prime[x] {
            cnt += 1;
        }
    }
    println!("{}", cnt);
}



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

#define fromto(i,a,b) for(int i=(a);i<=(b);++i)
int main() {
  int N; scanf("%d", &N);

  printf("%d\n", N*(N-1)/2 - N/2);
  fromto(i, 1, N) {
    fromto(j, i+1, N) {
      if (N % 2 == 1 && j == N - i)
        continue;
      if (N % 2 == 0 && j == N - i + 1)
        continue;
      printf("%d %d\n", i, j);
    }
  }
  return 0;
}


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

#define PB push_back
#define SZ(c) int((c).size())
#define ALL(c) (c).begin(), (c).end()
#define CONTAINS(c, x) ((c).find(x) != (c).end())
#define REP(i, n) for(int i=0; i<n; i++)
#define WAIT cout<<flush, system("PAUSE");
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 1100100;

int N, C, K, A[MAX], t, c, sol;

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

	cin >> N >> C >> K;
	REP(I, N){
		cin >> A[I];
	}
	sort(A, A+N);
	
	REP(I, N){
		sol ++;
		t = A[I] + K;
		c = 0;
		while(I<N && A[I] <= t && c < C){
			I++;
			c++;
		}
		// i does not fit!
		I--;
	}
	cout << sol << endl;
}


















Measured memory_bytes: 640
#include<stdio.h>

void run(void){
  int n;
  scanf("%d",&n);
  int h[100];
  int i;
  for(i=0;i<n;i++) scanf("%d",h+i);
  int ans=0;
  while(1){
    int l=0;
    while(l<n && h[l]==0) l++;
    if(l==n) break;
    int r=l;
    while(r<n && h[r]>0) r++;
    for(i=l;i<r;i++) h[i]--;
    ans++;
  }
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#-*-coding:utf-8-*-

def main():
    #入力
    N = int(input())
    lists = []
    for i in range(N):
        lists.append(list(map(int, input().split())))
    
    #変数
    position = [0, 0]
    begin_time = 0
    move_flag = 0

    #時間の変位-移動距離が0位上かつ、2の倍数であったらその位置に行くことができる
    for i in range(N):
        #時間の変位
        time_diff = lists[i][0] - begin_time
        begin_time = lists[i][0]
        #距離を求める
        distance = abs(lists[i][1] - position[0]) + abs(lists[i][2] - position[1])
        position = [lists[i][1], lists[i][2]]
        if time_diff - distance >= 0 and (time_diff - distance) % 2 == 0:
            move_flag = 1
        else:
            move_flag = 0
            break
    
    if move_flag == 1:
        print('Yes')
    elif move_flag == 0:
        print('No')

    
if __name__ == '__main__':
    main()
    

Measured memory_bytes: 27324
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<fstream>
#include<stdlib.h>
#include<set>
#include<climits>
#include<cmath>  
#include<memory.h> 
#include<sstream>
#include<time.h>
#include<iomanip>
using namespace std;
const unsigned long long BIGEST=1000000000000000000+1000000000000000000;
const long long BIGER=1000000000000000000;
const int BIG=1000000000;
const long long MOD=1000000007;
const long long LMOD=1000000007;
//const long long LMOD=1000000007;
#define Fi first
#define Se second
#define P2 pair
#define Pii pair<int,int>
#define Pll pair<long long,long long>
#define Cb make_pair
#define ll long long
#define Ull unsigned long long
#define Sf scanf
#define Pf printf
#define Pb push_back
#define Psh push
#define Stc stack
#define Vct vector
#define Ret return
#define Re0 return 0z
#define Sz size
#define Is insert
#define Que queue
#define Emp empty
#define Fro front
#define Rv reverse
#define Er erase
#define Bg begin
#define Srt sort
#define Pq priority_queue
#define Ite iterator
char c[100005];
ll n;
ll f[100005][13];
int main()
{
	Sf("%s",c+1);
	while(c[++n]);n--;
	f[0][0]=1;
	for(ll i=1;i<=n;i++)
	{
		if(c[i]!='?')
		{
			for(ll j=0;j<13;j++)
			{
				f[i][(j*10+c[i]-'0')%13]+=f[i-1][j];
				f[i][(j*10+c[i]-'0')%13]%=LMOD;
			}
		}
		else
		{
			for(ll j=0;j<10;j++)
			{
				//if(j==0&&i==1)continue;
				for(ll k=0;k<13;k++)
				{
					f[i][(k*10+j)%13]+=f[i-1][k];
					f[i][(k*10+j)%13]%=LMOD;
				}
			}
		}
	}
	/*
	for(ll i=0;i<=n;i++)
	{
		for(ll j=0;j<13;j++)
		{
			cout<<f[i][j]<<" ";
		}
		cout<<endl;
	}
	*/
	cout<<f[n][5];
	return 0;
}

Measured memory_bytes: 10496
n = int(input())
cnt = 0

for i in range(1,n+1):
  if i<10:
    cnt += 1
  elif i<100:
    cnt += 0
  elif i<1000:
    cnt += 1
  elif i<10000:
    cnt +=0
  elif i<100000:
    cnt+=1
    
print(cnt)
  

Measured memory_bytes: 2940
#include <iostream>

using namespace std;

int main(void)
{
    u_int m, n;
    cin >> n >> m;

    u_int a[n][m], b[m];
    for (u_int i = 0; i < n; i++)
        for (u_int j = 0; j < m; j++)
            cin >> a[i][j];
    for (u_int i = 0; i < m; i++)
        cin >> b[i];

    for (u_int i = 0; i < n; i++) {
        u_int c = 0;
        for (u_int j = 0; j < m; j++)
            c += a[i][j] * b[j];
        cout << c << endl;
    }
        
    return 0;
}

Measured memory_bytes: 1192
import sys
# sys.setrecursionlimit(10**10)
# N = int(sys.stdin.readline().rstrip())
# S = sys.stdin.readline().rstrip()
# N, K = map(int, sys.stdin.readline().rstrip().split())
X = list(map(int, sys.stdin.readline().rstrip().split()))
print(X.index(0) + 1)

Measured memory_bytes: 9096
N = int(input())
p = [int(input()) for i in range(N)]
ans = sum(p)
s = list(filter(lambda x: x % 10 != 0, p))
if ans % 10 == 0:
    if len(s) == 0:
        print(int(0))
    else:
        ans = ans - min(s)
        print(ans)
else:
    print(ans)

Measured memory_bytes: 3060
N = input()
if N[len(N)-1] == '3':
    print('bon')
elif N[len(N)-1] == '0' or N[len(N)-1] == '1' or N[len(N)-1] == '6' or N[len(N)-1] == '8':
    print('pon')
else:
    print('hon')


Measured memory_bytes: 9112
#include <iostream>
using namespace std;
typedef unsigned long long ll;

int main()
{
    ll n;
    cin >> n;
    ll p[50];
    if(n % 2){
        cout << 0 << endl;
        return 0;
    }
    p[0] = 2;
    for(int i = 1; i < 28; i++) p[i] = p[i - 1] * 5;
    ll ans = 0;
    for(int i = 1; i < 28; i++) ans += n / p[i];
    cout << ans << endl;
}

Measured memory_bytes: 256
// AOJ 0332: Disappearing Sequence
// 2017.10.28 bal4u@uu

#include <stdio.h>

int c[102];
char dp[102][102];
 
int main()
{
	int n, i, j, k, m;

	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", c+i);
    for (i = 1; i < n; i++) if (c[i-1] == c[i]) dp[i-1][i+1] = 1;
    for (m = 2; m <= n; m++) for (i = 0; i <= n-m; i++) {
		j = i+m;
		for (k = i+1; k < j; k++) {
			dp[i][j] |= dp[i][k] & dp[k][j];
			if (c[i] == c[j-1]) {
				dp[i][j] |= dp[i+1][j-1];
				if (c[i] == c[k]) dp[i][j] |= dp[i+1][k] & dp[k+1][j-1];
			}
		}
		if (c[i] && c[j-1]) {
			if (i > 0 && c[i-1] == c[i]) dp[i-1][k] |= dp[i][j];
			if (j < n && c[j-1] == c[j]) dp[i][j+1] |= dp[i][j];
		}
	}
	puts(dp[0][n] ? "yes" : "no");
    return 0;
}

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

int main() {
    long long n, k;
    cin >> n >> k;

    long long c[100100] = {0};
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        c[a] += b;
    }

    long long ans = 0, cnt = 0;
    for (int i = 1; i <= 100000; i++) {
        if (c[i] != 0) {
            cnt += c[i];
            ans = i;
            if (cnt >= k) break;
        }
    }

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

Measured memory_bytes: 1024
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');
		int a = int.Parse(input[0]);
		int b = int.Parse(input[1]);
		int answer = 1;
    int answerMemo = a;
    while(answerMemo < b)
    {
      answerMemo += a-1;
      answer++;
    }
    if(b == 1) answer = 0;

		Console.WriteLine(answer);
	}
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountll
#define m_p make_pair
#define infi 1e18+1
#define eps 0.000000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>//usage rand<long long>()
T rand() {
    return uniform_int_distribution<T>()(rng);
}
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
//////////////
auto clk=clock();
#define all(x) x.begin(),x.end()
#define S second
#define F first
#define sz(x) ((long long)x.size())
#define int long long  
#define f80 __float128
#define pii pair<int,int>
/////////////

signed main()
{
	fastio;
	#ifdef ANIKET_GOYAL
		freopen("inputf.in","r",stdin);
		freopen("outputf.in","w",stdout);
	#endif
	int n,m;
	cin>>n>>m;
	int to=0;
	int a[n+1];
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		to+=a[i];
	}
	int c=0;
	for(int i=1;i<=n;++i)
	{
		if(a[i]*4*m>=to)
			++c;
	}
	if(c>=m)
	{
		cout<<"Yes";
	}
	else
		cout<<"No";
	#ifdef ANIKET_GOYAL
		cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
	#endif
}

Measured memory_bytes: 256
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.ST                 as ST
import qualified Data.Array.Unboxed            as AU
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Foldable                 as DF
import           Data.Int
import qualified Data.IntMap                   as IM
import           Data.List
import qualified Data.Map                      as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import qualified Data.Sequence                 as SQ
import           Data.Time
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
readInts n = replicateM n readInt
readString = map BS.unpack . BS.words <$> BS.getLine
readStrings n = replicateM n <$> readString
toPair [x, y] = (x, y)

main = do
  [n] <- readInt
  a   <- readInt
  mapM_ print $ solve a

f a = (sum a', M.fromList a'')
 where
  a' = map (\x -> g $ length x) $ group $ sort a
  a'' :: [(Int, Int)]
  a'' = map (\x -> (head x, length x)) $ group $ sort a

g :: Int -> Int
g x | x < 2     = 0
    | otherwise = x * (x - 1) `div` 2

solve :: [Int] -> [Int]
solve a = map (\x -> m - g (a' M.! x) + g (a' M.! x - 1)) a
  where (m, a') = f a



Measured memory_bytes: 68092
#include <stdio.h>
#include <math.h>

int main()
{
  long n = 0;
  scanf("%ld", &n);
  
  long a[n];
  {
  	for(int i = 0; i < n; ++i)
  	{
      scanf("%ld", &a[i]);
  	}
  }
  
  for(int i = 0; i < n; ++i)
  {
    long j = i - n / 2;
    {
      if(j < 0)
      {
        j = -(j * 2 + 1 - n % 2);
      }
      else
      {
        j = j * 2 - n % 2;
        j = (j < 0) ? 0 : j;
      }
    }    
  	printf("%d ", a[j]);
  }

  return 0;
}

Measured memory_bytes: 3712
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;

    void calc(char k)
    {
        if(id >= S.Length)
        {
            flag = false;
            return;
        }
        if (S[id] == k)
        {
            id++;
        }
        else
        {
            flag = false;
        }
    }

    string S;
    bool flag = true;
    int id = 0;
    void solve()
    {
        S = cin.next;
        int N = S.Length;

        if (id < S.Length && S[id] == 'A')
        {
            id++;
        }
        calc('K');
        calc('I');
        calc('H');
        if (id < S.Length && S[id] == 'A')
        {
            id++;
        }

        calc('B');
        if (id < S.Length && S[id] == 'A')
        {
            id++;
        }

        calc('R');
        if (id < S.Length && S[id] == 'A')
        {
            id++;
        }

        if (id < S.Length)
        {
            flag = false;
        }
        if (flag)
        {
            WriteLine("YES");
        }
        else
        {
            WriteLine("NO");
        }
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13140
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

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

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

bool is_prime(long long n)
{
    if (n == 1) {
        return false;
    }

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main()
{
    long long n;
    std::cin >> n;

    std::string s, t;
    std::cin >> s >> t;

    for (int i = 0; i < n; i++) {
        std::cout << s[i] << t[i];
    }

    std::cout << std::endl;
}


Measured memory_bytes: 256
/**********************************************************************
   File hoge.cpp
   Author  harunaya
   Date   2020-03-04(Wed)
   note
**********************************************************************/

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
//#define PI(acos(-1))
using namespace std;
typedef long long ll;

int main() {
  string S;
  cin >> S;
  int A = (S[0] - '0') * 10 + (S[1] - '0');
  int B = (S[2] - '0') * 10 + (S[3] - '0');
  bool YYMM = (1 <= B && B <= 12);
  bool MMYY = (1 <= A && A <= 12);
  if (YYMM) {
    if (MMYY) puts("AMBIGUOUS");
    else puts("YYMM");
  }
  else {
    if (MMYY) puts("MMYY");
    else puts("NA");
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <cctype>
#include <complex>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;


bool solve(){
	
	string str[7] = {
		"Monday",
		"Tuesday",
		"Wednesday",
		"Thursday",
		"Friday",
		"Saturday",
		"Sunday"
	};
	int hoge[]={31,29,31,30,31,30,31,31,30,31,30,31};
	int m, d;
	while(1){
		cin>> m>> d;
		if(m==0&&d==0) break;
		int num = d;
		for(int i=0;i<m-1;i++){
			num += hoge[i];
		}
		int day = (2+num)%7;
		cout<< str[day]<< endl;
		
	}
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	solve();

	return 0;
}

 

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define range(i, l, r) for(long long int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (long long int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint N; cin >> N;
    vec<lint> A_list(N);
    range(i, 0, N) cin >> A_list.at(i);
    unordered_map<lint, lint> num_occurances_of_prefix_sum = {{0, 1}};
    lint prefix_sum = 0, ans = 0;
    for (const auto& A : A_list) {
        prefix_sum += A;
        ans += num_occurances_of_prefix_sum[prefix_sum];
        num_occurances_of_prefix_sum[prefix_sum] += 1;
        // cout << num_occurances_of_prefix_sum << "\n";
    }
    cout << ans << "\n";
}

Measured memory_bytes: 10056
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

typedef unsigned long long int ulint;
typedef long long int lint;

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

  vector<string> S;
  vector<ulint> T;
  
  for (int i = 0; i < N; ++i) {
    string s;
    ulint t;
    cin >> s >> t;
    S.push_back(s);
    T.push_back(t);
  }

  string X;
  cin >> X;
  
  auto v = find(S.begin(), S.end(), X);

  ulint num = v - S.begin();

  ulint ret = accumulate(T.begin() + num + 1, T.end(), 0);
  cout << ret << endl;
  
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
int n, a[200001];
ll k;
multiset<int>s;
vector<int> vec;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int cur = 1;
    while(1){
        if(s.find(cur) == s.end()){
            s.insert(cur); vec.pb(cur);
        }
        else{
            break;
        }
        cur = a[cur];
    }
    int id;
    for(int i = 0; i < vec.size(); i++){
        if(vec[i] == cur){id = i; break;}
    }

    if(k < s.size()){
        cout << vec[k] << endl;
    }
    else{
        cout << vec[id+(k-id)%(vec.size()-id)] << endl;
    }
}


Measured memory_bytes: 13844
#include <iostream>
#include <stack>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[200005];
llint b[200005], cap[200005];
stack<P> stk;
llint l[200005], r[200005];

llint check(llint p)
{
	llint ret = 0;
	for(int i = p+1; i <= n; i++){
		if(b[i-1] <= b[i]) break;
		while(b[i-1] > b[i]){
			b[i] *= 4;
			ret++;
		}
	}
	return ret;
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	stk.push(make_pair(n+1, 1e18));
	for(int i = 1; i <= n; i++) b[i] = a[i];
	for(int i = n-1; i >= 1; i--){
		r[i] = r[i+1];
		if(b[i+1] >= b[i]){
			llint t = b[i], cnt = 0;
			while(t*4 <= b[i+1]){
				t *= 4;
				cnt++;
			}
			stk.push(make_pair(i+1, cnt));
			continue;
		}
		llint t = b[i+1], cnt = 0;
		while(t < b[i]){
			t *= 4;
			cnt++;
		}
		llint add = 0;
		while(cnt){
			if(stk.top().second > cnt){
				stk.top().second -= cnt;
				add += cnt * (stk.top().first - (i+1));
				break;
			}
			else{
				add += stk.top().second * (stk.top().first - (i+1));
				cnt -= stk.top().second;
				stk.pop();
			}
		}
		r[i] += 2*add;
	}
	
	//for(int i = 1; i <= n; i++) cout << r[i] << " ";  cout << endl;
	
	while(stk.size()) stk.pop();
	stk.push(make_pair(n+1, 1e18));
	for(int i = 1; i <= n; i++) b[i] = a[n-i+1];
	l[n] = 1;
	for(int i = n-1; i >= 1; i--){
		l[i] = l[i+1]+1;
		if(b[i+1] >= b[i]){
			llint t = b[i], cnt = 0;
			while(t*4 <= b[i+1]){
				t *= 4;
				cnt++;
			}
			stk.push(make_pair(i+1, cnt));
			continue;
		}
		llint t = b[i+1], cnt = 0;
		while(t < b[i]){
			t *= 4;
			cnt++;
		}
		llint add = 0;
		while(cnt){
			if(stk.top().second > cnt){
				stk.top().second -= cnt;
				add += cnt * (stk.top().first - (i+1));
				break;
			}
			else{
				add += stk.top().second * (stk.top().first - (i+1));
				cnt -= stk.top().second;
				stk.pop();
			}
		}
		l[i] += 2*add;
	}
	
	//for(int i = 1; i <= n; i++) cout << l[i] << " ";  cout << endl;
	
	llint ans = 1e18;
	for(int i = 1; i <= n; i++){
		ans = min(ans, l[n+2-i] + r[i]);
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 11392
#include<stdio.h>
int main(){
    int a,b;
    int low,high;
    scanf("%d %d",&a,&b);
    
    if(a > b){
        low = b;
        high = a;
    }else{
        low = a;
        high = b;
    }
    
    if(a == b){
        for(int i = 0 ; i < b ; i++){
            printf("%d",a);
        }
    }else{
        for(int i = 0 ; i < high ; i++){
            printf("%d",low);
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1001;
const int INF = 1e18 + 7;
int n;
int a[N];
vector <int> q;
void solve(vector <bool> mask) {
    #ifdef HOME
    cout << "solve: ";
    for (auto e : mask) cout << e << ' ';
    cout << '\n';
    #endif

    if (mask.size() == 1) return;
    if (!mask[0]) {
        q.push_back(1);
        vector <bool> t;
        for (int i = 1; i < (int)mask.size(); ++i) t.push_back(mask[i]);
        solve(t);
        return;
    }   
    if (!mask.back()) {
        q.push_back(mask.size());
        vector <bool> t;
        for (int i = 0; i < (int)mask.size() - 1; ++i) t.push_back(mask[i]);
        solve(t);
        return;
    }   
    int p = -1;
    for (int i = 0; i < (int)mask.size(); ++i) {
        if (!mask[i]) {
            p = i;
            break;
        }   
    }   
    if (!mask[p + 1]) ++p;
    q.push_back(p + 1);
    vector <bool> t;
    for (int i = 0; i < (int)mask.size(); ++i) {
        if (i != p && i != p + 1) {
            t.push_back(mask[i]);
        }   
    }    
    solve(t);
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    bool c = 1;
    for (int i = 0; i < n; ++i) c &= a[i] < 0;
    if (c) {
        int mx = -INF, pos = -1;
        for (int i = 0; i < n; ++i) {
            if (mx < a[i]) {
                mx = a[i];
                pos = i;
            }   
        }   
        cout << mx << '\n';
        cout << n - 1 << '\n';
        for (int i = 0; i < pos; ++i) cout << "1\n";
        for (int i = 0; i < n - pos - 1; ++i) cout << n - pos - i << '\n'; 
        exit(0);                                                            
    }   
    int ans = -INF;
    vector <int> ansp;
    for (int c = 0; c <= 1; ++c) {
        vector <int> p;
        int nn = 0;
        for (int i = c; i < n; i += 2) {
            if (a[i] >= 0) {
                p.push_back(i);
                nn += a[i];
            }                           
        }   
        if (ans < nn) {
            ans = nn;
            ansp = p;
        }   
    }      
    cout << ans << '\n';
    vector <bool> mask(n);
    for (int e : ansp) mask[e] = 1;
    solve(mask);
    cout << q.size() << '\n';
    for (int e : q) cout << e << '\n';
}   

Measured memory_bytes: 512
//be name khoda
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define F first
#define S second
#define int long long

const int maxn = 1e5+10;
const int mod = 998244353;
//const int inf = 1e9;

int n, m;
int ball[maxn], is[maxn];

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n >> m;
    is[1] = 1;
    fill(ball, ball+maxn, 1);
    for(int i = 1, x , y; i <= m; i++)
    {
        cin>> x >> y;

        ball[x]--;
        ball[y]++;

        if(is[x]) is[y] = 1;
        if(!ball[x]) is[x] = 0;
    }

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









Measured memory_bytes: 1792
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

s = input()
if s[-1] == 's':
    s += 'es'
else:
    s += 's'
print(s)

Measured memory_bytes: 9296
#include<iostream>
#include<cstdio>

using namespace std;
 
#define NMAX 1000
#define tMAX 1260
int main(void){
	
	int N,M;
	int r;
	int use[NMAX+1][tMAX+1];
	int t,n,m,s;
	int q;
	int ts,te;
	int cnt;
	bool f;

	while(1){
		cin>>N>>M;
		if(N==0&&M==0) break;

		for(int i=1;i<=N;i++){
			for(int j=0;j<=tMAX;j++){
				use[i][j]=0;
			}
		}

		cin>>r;
		for(int i=0;i<r;i++){
			cin>>t>>n>>m>>s;
			if(s==1) use[n][t]=m;
			else use[n][t]=-1*m;
		}

		for(int i=1;i<=N;i++){
			for(int j=1;j<=tMAX;j++){
				use[i][j]+=use[i][j-1];
			}
		}

		cin>>q;

		for(int i=0;i<q;i++){
			cin>>ts>>te>>m;
			cnt=0;
			for(int j=ts;j<te;j++){
				f=false;
				for(int i=1;i<=N;i++){
					if(use[i][j]==m) f=true; 
				}
				if(f) cnt++;
			}
			cout<<cnt<<endl;
		}

	}

	return 0;
}

Measured memory_bytes: 5996
#include<bits/stdc++.h>
#define ll long long
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define MAX 1000000007
using namespace std;
int main()
{
 	speed_up
   ll r,d,x2;cin>>r>>d>>x2;
   ll curr=x2;
   for(ll i=2000;i<2010;i++)
   {
   	 ll a=r*curr-d;
   	 cout<<a<<endl;
   	 curr=a;
   }
     
	
	
	
	
	
	
 return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#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;


int main(void){
  long long n,a,b;
  vector<long long> x;
  long long x_;
  cin >> n >> a >> b;
  for(int i = 0; i < n; i++){
    cin >> x_;
    x.push_back(x_);
  }
  long long ret = 0;
  for(int i = 0; i < n-1; i++){
    ret += min((x[i+1]-x[i])*a, b);
  }
  cout << ret << "\r\n";
  return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1e9+7;

int main(){
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
    }
    n -= k;
    int ans = 1;
    k--;
    if(n > 0){
        ans += n/k;
        if(n%k) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main( ) {
	
	int max;
	int buy[100000];
	double sum = 0;
	int answer;
	int i;

	scanf( "%d",&max );

	for( i = 0; i < max; i++ ) {
		scanf( "%d", &buy[ i ] );
		sum += buy[ i ];
	}

	answer = ( int )( sum / (double)max );

	printf( "%d\n",answer );

	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(a, b) for (int i = a; i < b + 1; i++)
#define all(v) v.begin(), v.end()
#define SENTINEL 2000000000
#define NIL -1
using namespace std;
typedef long long ll;

const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template <class T>inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}


int main()
{
    ll n,a,b;
    cin >> n >> a >> b;
    ll ans=0;
    ans+=(n/(a+b))*a;
    n -=(n / (a + b))*(a+b);
    ans+=min(a,n);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int two(int x){
	int count=0;
	while(x%2==0){
		count++;
		x/=2;
	}
	return count;
}
int main(){
    int n,a[1000],count;
    cin>>n;
    for(int i=0;i<n;i++){
		cin>>a[i];
		if(i==0)count=two(a[i]);
		count=min(count,two(a[i]));
	}
	cout<<count<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
const int N = 2e5 + 10;
const ll inf = 1e15 + 42;
#define endl "\n"
const ll mod = 1000000007;

typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds;

//Ordered set
//pbds s1

//NO of names of 1 letter = 26
//no of names of 2 letter = 26*26
//no of names of i letter = 26^i
// 26 + 26*26 + 26*26*26 + .... + 26^i >= 10^15
// 26*(26^i-1) / 25 >= 1e15
// i ~ 10

//given value and length of string, find ans

string go (ll n, int cnt) {
    if (cnt == 1) {
        string v = "";
        char ch = char('a'+n-1);
        v += ch;
        return v;
    }
    string ans = "";
    ll cc = 1;
    for (int i=1; i<cnt; i++)
        cc = cc * 26;
    char ch = 'a';
    for (; ch <= 'z'; ch++) {
        if (n <= cc) {
            break;
        } 
        n -= cc;
    }
    ans += ch;
    ans = ans + go (n, cnt-1);
    return ans;
}

void testCase() {
    ll n;
    cin >> n;
    //find no of characters in the name
    ll st = 26;
    int cnt = 1;
    while (1) {
        if (n <= st) {
            break;
        }
        n -= st;
        st = st*26;
        cnt++;
    }
    cout << go (n, cnt) << endl;
}
 
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    testCase();
    return 0;
}

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

approved = True
for i in range(n):
	if a[i] % 2 == 0 and (a[i] % 3 != 0 and a[i] % 5 != 0):
		approved = False
		break

if approved:
	print('APPROVED')
else:
	print('DENIED')

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


//CODE
void solve(void)
{
  string str;
  cin>>str;
  int Q;
  cin>>Q;
  int rev = 0;
  string front;
  string end;
  for (int q = 0; q < Q; q++)
  {
    int A;
    cin>>A;
    if(A == 1)
    {
      rev ^= 1;
    }
    else
    {
      int F;
      cin>>F;
      char C;
      cin>>C;
      F--;
      int mode = F^rev;
      if(mode == 0)
      {
        front += C;
      }
      else
      {
        end += C;
      }
    }
  }
  reverse(front.begin(),front.end());
  string ANS = front + str + end;
  if(rev == 1)reverse(ANS.begin(),ANS.end());
  cout<<ANS<<endl;
  

  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();
  

 
  return 0;
}


Measured memory_bytes: 1300
//#pragma GCC target("avx2")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int s;
    cin >> s;

    vector<mint> dp(s + 1, 0);
    dp[0] = 1;
    REP(i, s + 1) {
        FOR(j, 3, s + 1) {
            if (i + j > s) break;
            dp[i + j] += dp[i];
        }
    }

    print(dp[s]);

}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

signed main()
{
  int N;
  cin >> N;
  if(N == 1) {
    cout << 1 << endl;
  } else {
    printf("%.10f\n", 1.0 * ((N+1) / 2) /N);
  }
  
  return 0;
}


Measured memory_bytes: 256