akhauriyash/Code-Regression huggingface dataset:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m=map(int,input().split())
half=n//2
lst=[]

if n%2==0:
    for i in range(m):
        if i%2==0:
            lst.append([1+i//2,n-i//2])
        else:
            lst.append([half-i//2,half+i//2+2])
else:
    for i in range(m):
        lst.append([half-i,half+i+1])

for i in range(m):
    print(*lst[i])

Measured memory_bytes: 87764
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  vector<vector<int>> A(3,vector<int>(3));
  REP(i, 3){
    REP(j, 3){
      cin >> A.at(i).at(j);
    }
  }
  int N;
  cin >> N;
  vector<int> B(N);
  REP(i, N) cin >> B[i];
  
  vector<vector<int>> C(3,vector<int>(3,0));
  
  
  REP(i,N){
    REP(j,3){
      REP(k,3){
        if(A.at(j).at(k) == B.at(i)){
          C.at(j).at(k) = 1;
        }
      }
    }
  }

  if(C.at(0).at(0) == 1&&C.at(0).at(1) == 1&&C.at(0).at(2) == 1
  || C.at(1).at(0) == 1&&C.at(1).at(1) == 1&&C.at(1).at(2) == 1
  || C.at(2).at(0) == 1&&C.at(2).at(1) == 1&&C.at(2).at(2) == 1
  || C.at(0).at(0) == 1&&C.at(1).at(0) == 1&&C.at(2).at(0) == 1
  || C.at(0).at(1) == 1&&C.at(1).at(1) == 1&&C.at(2).at(1) == 1
  || C.at(0).at(2) == 1&&C.at(1).at(2) == 1&&C.at(2).at(2) == 1
  || C.at(0).at(0) == 1&&C.at(1).at(1) == 1&&C.at(2).at(2) == 1
  || C.at(0).at(2) == 1&&C.at(1).at(1) == 1&&C.at(2).at(0) == 1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

using namespace std;

int main() {
	int a, b;
	cin>>a>>b;
	long x = 0, y = 0;
	for(int i = 0; i < a; i++) x = 10*x + b;
	for(int i = 0; i < b; i++) y = 10*y + a;
	cout<<max(x, y)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end() 
using namespace std;
typedef long long ll;

int n, k;

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cin >> n >> k;
   vector<int> cnt(k, 0);
   for(int i=1; i<=n; ++i) {
       ++cnt[i%k];
   }
   cout << (ll)cnt[0]*cnt[0]*cnt[0] + ((k%2 == 0) ? (ll)cnt[k/2]*cnt[k/2]*cnt[k/2]: 0) << "\n";
   return 0;
} 


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{

    int H1,M1,H2,M2,k;
    int defH , defM ;
    cin>>H1>>M1>>H2>>M2>>k;


        defH=H2-H1;
        defM=M2-M1;

        cout<<((defH*60)+defM) -k;


    return 0;
}


Measured memory_bytes: 3624
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>    
#define inf 100000000
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
    int i;scanf("%d",&i);
    return i;
}
long long llin(void){
    long long i;scanf("%lld",&i);
    return i;
}
double din(void){
    double i;scanf("%lf",&i);
    return i;
}
void chin(char s[]){
    scanf("%s",s);
}
void print(int a){
    printf("%d\n",a);
}
void llprint(long long a){
    printf("%lld\n",a);
}
void dprint(double a){
    printf("%.10f\n",a);
}
void print2(int a,int b){
    printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a<b?a:b;
}
double dmax(double a,double b){
    return a>b?a:b;
}
int cmp(const void *a,const void *b){
    return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
    return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
    return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
    return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}
long long gcd(long long x,long long y){
    return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
    return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
    int a[3]={},i,k,p;
    rep(i,3)scanf("%d ",&a[i]);
    scanf("%d",&k);
    sort(a,3);
    rep(i,k)a[2]*=2;
    print(a[0]+a[1]+a[2]);
    return 0;
}

Measured memory_bytes: 128
def round_up_division(num1, num2):
# 切り上げ除算
  div = -(-num1 // num2)
  return div

def binary_search(search_range, max_num, logs):
  search_min = 1
  search_max = search_range
  # 二分探索
  while True:
    # max_numを超えない最大回数にする
    count_a = 0
    # count_aより1短い長さ
    count_b = 0
    # 最小値と最大値の中間の値を出す
    half_num = (search_min + search_max - 1) // 2 + 1
    for i in range(logs):
      # 木を切る回数は(⌈(木の長さ)//(切りたい長さ)⌉-1)回
      count_a += round_up_division(A[i], half_num) - 1
      if half_num != 1:
        count_b += round_up_division(A[i], half_num - 1) - 1
    if count_a > K:
      # 多ければ長い半分で探索
      search_min = round_up_division(search_min + search_max, 2)
    elif half_num != 1 and count_b <= K:
      # 少なければ短い半分で探索
      search_max = half_num - 1
    else:
      # count_aが最大になれば終了
      return half_num
      break

N, K = map(int, input().split())
A = list(map(int, input().split()))
length_max = binary_search(max(A), K, N)
print(length_max)

Measured memory_bytes: 104244
A, B, C, D, E, F = map(int, input().split())

d = 0
for i in range(31):
    if i * 100 * A > F:
        break
    for j in range(31):
        if i * 100 * A + j * 100 * B > F:
            break
        if i == 0 and j == 0:
            break
        for k in range(0, 1501, C):
            if k > i * A * E + j * B * E:
                break
            m = i * 100 * A + j * 100 * B + k
            if m > F:
                break
            l1 = F - m
            l2 = i * A * E + j * B * E - k
            l = min(l1, l2)
            l = int(l / D) * D
            d1 = 100 * (k + l) / (m + l)
            if d < d1:
                w = m + l
                s = k + l
                d = d1
if d == 0:
    if 100 * A <= F:
        print('{0} {1}'.format(100 * A, 0))
    else:
        print('{0} {1}'.format(100 * B, 0))
else:
    print('{0} {1}'.format(w, s))

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int main()
{
    ll x;
    scanf("%lld",&x);

        ll ans=2*(x/11);
        if(x%11<=6&&x%11>0)
            ans++;
        else if(x%11>6)
            ans+=2;
            printf("%lld\n",ans);

    return 0;

}


Measured memory_bytes: 764
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FOOR(i,a,b) for(int i=a;i<=b;i++)
#define FI first
#define SE second
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define MOD 1000000007
#define INF 1000000007
using namespace std;
//
int main(){
  string S;
  cin>>S;
  int m=S.size();
  FOR(i,0,(int)S.size()-1){
    if(S[i]!=S[i+1]){
      m=min(m,max(i+1,(int)S.size()-i-1));
    }
  }
  cout<<m<<endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int a[50][4];
int N,M,Q;
int res=0;
void rec(int d,vector<int> x){
    int tmp=0;
    if(d==N-1){
        for(int i=0;i<Q;i++){
            if(x[a[i][1]-1]-x[a[i][0]-1]==a[i][2]){
                tmp += a[i][3];
            }
        }
        cerr << tmp << "!!\t";
        if(res<tmp) res=tmp;
    }else{
        for(int l=x[d];l<=M;l++){
            x[d+1]=l;
            rec(d+1,x);
        }
    }
}
int main(){
    cin >> N >> M >> Q;
    for(int i=0;i<Q;i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    }
    for(int i=1;i<=M;i++){
        vector<int> t(N,0);
        t[0]=i;
        rec(0,t);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3576
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String line = sc.nextLine();
			Scanner s = new Scanner(line);
			int n = s.nextInt();
			int m = 0;
			if (n < 37) { //37以上の場合はm=0は確かであるため
				for(int a=0; a<=9; a++) {
					for(int b=0; b<=9; b++) {
						for(int c=0; c<=9; c++) {
							for(int d=0; d<=9; d++) {
								if (a + b + c + d == n) m++;
							}
						}
					}
				}
			}
			System.out.println(m);
		}
	}
}

Measured memory_bytes: 24720
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please



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


	int N;
	cin >> N;

	ll kotae = 0;
	rep1(i, N) {
		kotae += i * ll(i + 1) / 2;
	}

	rep(i, N - 1) {
		int u, v;
		cin >> u >> v;
		if (u > v) swap(u, v);

		kotae -= ll(u) * (N - v + 1);


	}
	co(kotae);




	Would you please return 0;
}

Measured memory_bytes: 3624
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<string> A(N), B(M);
    rep(0, i, N)
    {
        cin >> A.at(i);
    }
    rep(0, i, M)
    {
        cin >> B.at(i);
    }

    for (ll i = 0; i <= N - M; i++)
    {
        for (ll j = 0; j <= N - M; j++)
        {
            ll flag = 1;

            for (ll k = 0; k < M; k++)
            {
                for (ll l = 0; l < M; l++)
                {
                    if (A.at(i + k).at(j + l) != B.at(k).at(l))
                    {
                        flag = 0;
                    }
                }
            }

            if (flag == 1)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3604
import java.util.*;
class Main{
	Scanner sc=new Scanner(System.in);
	void aa(){
		int n=sc.nextInt();
		int[] N=new int[n];
		for(int i=n;i>0;i--)N[i-1]=sc.nextInt();
		for(int i=0;i<n;i++)if(i!=n-1)System.out.print(N[i]+" ");
		System.out.println(N[n-1]);
	}
	public static void main(String[]arg){
		new Main().aa();
	}
}

Measured memory_bytes: 19096
N = int(input())
upper_row = list(map(int,input().split()))
lower_row = list(map(int,input().split()))

#下に降りるタイミングをiとする
max_ame = 0
for i in range(N):
    ame = sum(upper_row[:i+1])+sum(lower_row[i:])
    if ame > max_ame:
        max_ame = ame
print(max_ame)

Measured memory_bytes: 3060
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
C = [c1, c2, c3]

# a1を任意に決めるとなし崩し的にa,bが全て出るのであとは全マスでうまくいくか確かめるだけ
f = False
for i in range(C[0][0] + 1):
    a1 = i
    b1 = C[0][0] - a1
    b2 = C[0][1] - a1
    b3 = C[0][2] - a1
    a2 = C[1][0] - b1
    a3 = C[2][0] - b1
    if a1 + b1 == C[0][0] and a1 + b2 == C[0][1] and a1 + b3 == C[0][2] and a2 + b1 == C[1][0] and a2 + b2 == C[1][1] and a2 + b3 == C[1][2] and a3 + b1 == C[2][0] and a3 + b2 == C[2][1] and a3 + b3 == C[2][2]:
        f = True
        break

if f == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
n=input()
sn=[]
for num in range(int(n)):
    st=input()
    st=st.split()
    st[1]=int(st[1])
    st.append(num)
    sn.append(st)

sn2=sorted(sn, key=lambda x:(x[0],-x[1]))
for n in sn2:
    print(int(n[2]+1))

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

int main(){
	ll t1,t2,a1,a2,b1,b2;
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
	a1 *= t1;
	a2 *= t2;
	b1 *= t1;
	b2 *= t2;
	if((a1 + a2) < (b1 + b2)){
		swap(a1,b1);
		swap(a2,b2);
	}
	ll c1,c2;
	c1 = a1 - b1;
	c2 = a2 - b2;
	if(c1 + c2 == 0){
		cout << "infinity" << endl;
	}
	else if(c1 > 0){
		cout << 0 << endl;
	}
	else{
		ll sum = 0;
		if(c1 < 0)
			sum--;
		sum += c2 / (c1 + c2) * 2;	
		if(c2 % (c1 + c2) == 0)
			sum--;
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //c
  int n;
  cin >> n;
  vector<int> cnt(n + 1);
  for (int i = 1; i < n; i++) {
    int a;
    cin >> a;
    cnt[a]++;
  }
  for (int i = 1; i <= n; i++) {
    cout << cnt[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    ll a, b, n;
    cin >> a >> b >> n;

    chmin(n, b - 1);
    ll mx = a * n / b - n / b * a;

    cout << mx << endl;

    return 0;
}

Measured memory_bytes: 3652
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	m := getNextInt(scanner)
	nodes := make([]*Node, n)

	for i := 0; i < n; i++ {
		nodes[i] = &Node{
			root: i,
			cost: 0,
		}
	}

	ans := "Yes"
	for i := 0; i < m; i++ {
		l := getNextInt(scanner) - 1
		r := getNextInt(scanner) - 1
		d := getNextInt(scanner)

		r1 := root(l, nodes)
		r2 := root(r, nodes)

		if r1 == r2 {
			if nodes[l].cost+d != nodes[r].cost {
				ans = "No"
				break
			}
			continue
		}

		nodes[r2].root = r1
		nodes[r2].cost = d + nodes[l].cost - nodes[r].cost
	}

	fmt.Fprintln(writer, ans)
	writer.Flush()
}

type Node struct {
	root, cost int
}

func root(i int, nodes []*Node) int {
	if i == nodes[i].root {
		return i
	}

	r := root(nodes[i].root, nodes)
	nodes[i].cost += nodes[nodes[i].root].cost

	nodes[i].root = r

	return nodes[i].root
}


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

int main() {
    string s;
    cin >> s;
    if (s.size() == 1) cout << s[0] << endl;
    else {
        bool flag = true;
        for (int i = 1; i < s.size(); i++) if (s[i] != '9') flag = false;
        if (flag) {
            cout << 9 * (s.size() - 1) + (s[0] - '0') << endl;
            return 0;
        }
        else {
            cout << 9 * (s.size() - 1) + (s[0] - '0') - 1 << endl;
            return 0;
        }
    }
}

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

using namespace std;

int main() {
    long long ans = 0;
    int n, i = 1;
    cin >> n;
    vector<int> x(n + 1, 0), y(n + 1);
    while(cin >> x[i++] && i <= n);
    y[0] = 1e6 + 1;
    for(i = 2; i <= n; i++)
        y[i] = min(y[i - 1] + abs(x[i] - x[i - 1]), y[i - 2] + abs(x[i] - x[i - 2]));
    
    cout << y[n] << endl;
    return 0;
}

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

s = list(input())
t = list(input())

s.sort()
t.sort()

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

s = array_count(s)
t = array_count(t)

def get_item_1 (arr):
    newarr = []
    for i in range(len(arr)):
        newarr.append(arr[i][1])
    return newarr

s = get_item_1(s)
t = get_item_1(t)

s.sort()
t.sort()

if s == t:
    print("Yes")
else:
    print("No")


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

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

struct segment {
  ll num;
  ll parts;
};

struct output {
  ll num;
  ll rep;
};

bool compareS(segment s, segment t) {
  return s.num > t.num;
}


ll N = 0;
ll M = 0;
ll tmp;
ll ret = 0;
ll table[10] = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
ll dp[10005];

vector<segment> A;

void input() {
  IN(N);
  IN(M);
  REP(i, M) {
    IN(tmp);
    segment s = {tmp, table[tmp]};
    A.pb(s);
  }
}

void solve() {
  sort(ALL(A), compareS);

  dp[0] = 0;
  FOR(i, 1, N+1) {
    ll m = -INF;
    FOREACH(s, A) {
      if (i - s.parts >= 0) {
        m = max(m, 1 + dp[i - s.parts]);
      }
    }
    dp[i] = m;
  }
  
  ll i = N;
  while(i > 0) {
    FOREACH(s, A) {
      if ((i - s.parts >= 0) && (dp[i-s.parts] == dp[i] - 1)) {
        cout << s.num;
        i -= s.parts;
        break;
      }
    }
  }
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 384
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

int dp[80][80][25601];
int A[80][80];
int B[80][80];
int SHIFT = 12800;

int main(){

  // read problem
  long long int H, W;
  int tmp;
  int tmpmin, tmpmax;
  
  scanf("%lld%lld", &H, &W);
  for(long long int i = 0; i < H; i++){
    for(long long int j = 0; j < W; j++){
      scanf("%d", &tmp);
      A[i][j] = tmp;
    }
  }

  for(long long int i = 0; i < H; i++){
    for(long long int j = 0; j < W; j++){
      scanf("%d", &tmp);
      B[i][j] = tmp;
    }
  }

  // solve problem
  for(long long int i = 0; i < H; i++){
    for(long long int j = 0; j < W; j++){
      for(long long int k = 0; k < 25601; k++){
        dp[i][j][k] = 0;
      }
    }
  }

  dp[0][0][A[0][0] - B[0][0]+SHIFT] = 1;
  tmp = A[0][0] - B[0][0];
  for(long long int j = 1; j < W; j++){
    int i = 0;
    tmp = A[i][j] - B[i][j];
    tmpmin = std::max(0, tmp);
    tmpmax = std::min(25601, 25601-tmp);
    for(long long int k = tmpmin; k < tmpmax; k++){
      if(dp[i][j-1][k-tmp]){
        dp[i][j][k] = 1;
      }
    }
    tmp = -A[i][j] + B[i][j];
    tmpmin = std::max(0, tmp);
    tmpmax = std::min(25601, 25601-tmp);
    for(long long int k = tmpmin; k < tmpmax; k++){
      if(dp[i][j-1][k-tmp]){
        dp[i][j][k] = 1;
      }
    }
  }

  tmp = A[0][0] - B[0][0];
  for(long long int i = 1; i < H; i++){
    int j = 0;
    tmp = A[i][j] - B[i][j];
    tmpmin = std::max(0, tmp);
    tmpmax = std::min(25601, 25601-tmp);
    for(long long int k = tmpmin; k < tmpmax; k++){
      if(dp[i-1][j][k-tmp]){
        dp[i][j][k] = 1;
      }
    }
    tmp = -A[i][j] + B[i][j];
    tmpmin = std::max(0, tmp);
    tmpmax = std::min(25601, 25601-tmp);
    for(long long int k = tmpmin; k < tmpmax; k++){
      if(dp[i-1][j][k-tmp]){
        dp[i][j][k] = 1;
      }
    }
  }

  
  for(long long int i = 1; i < H; i++){
    for(long long int j = 1; j < W; j++){
      tmp = A[i][j] - B[i][j];
      tmpmin = std::max(0, tmp);
      tmpmax = std::min(25601, 25601-tmp);
      for(long long int k = tmpmin; k < tmpmax; k++){
        if(dp[i-1][j][k-tmp] || dp[i][j-1][k-tmp]){
          dp[i][j][k] = 1;
        }
      }
      tmp = -A[i][j] + B[i][j];
      tmpmin = std::max(0, tmp);
      tmpmax = std::min(25601, 25601-tmp);
      for(long long int k = tmpmin; k < tmpmax; k++){
        if(dp[i-1][j][k-tmp] || dp[i][j-1][k-tmp]){
          dp[i][j][k] = 1;
        }
      }
    }
  }

  // calculate answer
  int ans = 12800;
  for(long long int i = 0; i < 25601; i++){
    if(dp[H-1][W-1][i] == 1)
    ans = std::min(ans, (int)std::abs(i-SHIFT));
  }

  std::cerr << "Answer: " << std::endl;
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 640256
use std::cmp::max;
use std::cmp::min;

fn main() {
    let s = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        buf = buf.trim_end().to_owned();
        buf
    };
    let mut ans = 1000;
    for i in 0..26 {
        let target: char = std::char::from_u32('a' as u32 + i).unwrap();
        let mut prev: i32 = -1;
        let mut mx = 0;
        for (i, c) in s.chars().enumerate() {
            if c == target {
                mx = max(i as i32 - prev - 1, mx);
                prev = i as i32
            }
        }
        mx = max(mx, s.len() as i32 - prev - 1);
        ans = min(mx, ans);
    }
    println!("{}", ans);
}


Measured memory_bytes: 2128
#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#define pb push_back
#define ff first
#define ss second
using namespace std;

int main(){
   string s;
   cin>>s;
   int a = (s[0]-'0')*10+(s[1]-'0');
   int b = (s[2]-'0')*10+(s[3]-'0');
   
   if(a<=12 && a!=0 && b<=12 && b!=0){
       cout<<"AMBIGUOUS"<<endl;
   }
   else if(a<=12 && a!=0){
       cout<<"MMYY"<<endl;
   }
   else if(b<=12 && b!=0){
       cout<<"YYMM"<<endl;
   }
   else{
       cout<<"NA"<<endl;
   }
}

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

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define yes(c) cout << ((c) ? "yes" : "no") << endl;
 
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;

int main() {
  
  string s;
  cin >> s;
  
  if ( s[0] != 'A' ){
    cout << "WA" << endl;
    return 0;
  }
  
  int ichi,hantei = 0,count = 0;
  
  for ( int i = 2; i < s.size() -1; i++){
    if ( s[i] == 'C' ){
      hantei = 1;
      ichi = i;
      count++;
    }
  }
  
  if ( hantei == 0 || count >= 2 ){
    cout << "WA" << endl;
    return 0;
  }
  
  for ( int i = 1; i < s.size(); i++){
    if ( i == ichi ){
      continue;
    }
    if ( s[i] < 97 || s[i] > 122 ){
      cout << "WA" << endl;
      return 0;
    }
  }
  
  cout << "AC" << endl;

}

Measured memory_bytes: 256
/***
 @ Author       : RobsonChen
 @ Date         : 2020-09-20 19:35:23
 @ LastEditTime : 2020-09-20 19:50:59
 @ Got AC       : Σ(っ °Д °;)っ
*/
#include <bits/stdc++.h>

using namespace std;
typedef unsigned int INT;
typedef unsigned long long LONG;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int mod = 998244353;
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define FW freopen("data2.txt", "w", stdout);

//快速读入输出，只适用于整数，使用时流同步打开，C语言不准关流
// getchar()<<cin(关流)<<scanf()<<cin
template <class T>
inline bool Read(T& ret)
{
    char c;
    int sgn;
    if (static_cast<void>(c = getchar()), c == EOF)
        return 0;
    while (c != '-' && (c < '0' || c > '9'))
        c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (static_cast<void>(c = getchar()), c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}

//输出只能用于整数
template <class T>
inline void Write(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        Write(x / 10);
    putchar(x % 10 + '0');
}

LL sum[N * 2] = { 0 }, num = 1;

void slove(int qnum)
{
    LL n, x, m;
    cin >> n >> x >> m;
    LL ans = x;
    LL pos = 0;
    unordered_set<LL> k;
    unordered_map<LL, int> order;
    k.insert(x);
    order[x] = 1;
    sum[num] = x;
    for (int i = 2; i <= n; ++i) {
        LL cur = (x * x) % m;
        if (cur == 0) {
            cout << ans << endl;
            return;
        }
        if (k.count(cur)) {
            pos = order[cur];
            break;
        }
        num++;
        sum[num] = sum[num - 1] + cur;
        k.insert(cur);
        ans += cur;
        x = cur;
        order[cur] = i;
    }
    if (pos == 0) {
        cout << ans << endl;
        return;
    }
    ans += (ans - sum[pos - 1]) * ((n - num - 1) / (num - pos + 1));
    n = (n - num - 1) % (num - pos + 1);
    ans += (sum[pos + n] - sum[pos - 1]);
    cout << ans << endl;
}

int main()
{
    int qnum = 1;
    // cin >> num;
    for (int i = 1; i <= qnum; ++i) {
        slove(i);
    }
    // system("pause");
    return 0;
}

Measured memory_bytes: 7744
program Sum_of_Large_Numbers;
var
  n, k: int64;
begin
  read(n, k);
  writeln(((3*(n+1)*(n+k+1)*(n-k+2)+6*(n-k+2)-(n+1)*(n+2)*(2*n+3)+(k-1)*k*(2*k-1)) div 6) mod 1000000007);
end.

Measured memory_bytes: 1384
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 62);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------

// function -------------------------------------------

// main -----------------------------------------------

int main() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll max = a * c;
	chmax(max, a * d);
	chmax(max, b * c);
	chmax(max, b * d);
	cout << max << endl;
	return 0;
}

Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>

using namespace std;

typedef complex<double> xy_t;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF= 1 << 30;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;

const int mod = 100000;
int dp[102][102][4];

int main(){
	int h, w;
	while(cin >> w >> h && (w || h)){
		if(w == 1 && h == 1){
			cout << 1 << endl;
			continue;
		}
		memset(dp, 0, sizeof(dp));
		dp[1][1][2] = dp[1][1][3] = 1;
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				dp[i][j+1][0] = (dp[i][j+1][0] + dp[i][j][0] + dp[i][j][2]) % mod;
				dp[i][j+1][2] = (dp[i][j+1][2] + dp[i][j][1]) % mod;
				dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][1] + dp[i][j][3]) %mod;
				dp[i+1][j][3] = (dp[i+1][j][3] + dp[i][j][0]) % mod;
			}
		}
		int res = 0;
		for(int i = 0; i < 4; i++) res += dp[h][w][i];
		cout << res % mod << endl;
	}
	return 0;
}

Measured memory_bytes: 0
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 20:51:45 2020

@author: naoki
"""
from collections import deque
N, X, Y = map(int,input().split())

distance_count = [0] * (N + 1)
route = [[i-1, i+1] for i in range(N+1)]

del route[-1][-1]

All_distances = [0]*N
route[X].append(Y)
route[Y].append(X)
#%%
for j in range(1,N):
    todo = deque([j])
    seen = [0 for i in range(N+1)]
    distance = [N+1] * (N+1)
    distance[j] = 0
    while len(todo) > 0:
        now = todo.pop()
        if now == N+1 or now == 0:
            continue
        for checking in route[now]:
            kari1 = distance[checking]
            kari2 = distance[now] + 1
            if seen[checking] < 2 and kari1 > kari2:
                distance[checking] = kari2
                todo.append(checking)
                seen[checking] += 1
            elif kari1 > kari2:
                distance[checking] = kari2
    for i in range(j,len(distance)):
        if distance[i] != N+1:
            All_distances[distance[i]] += 1
for i in range(1,N):
    print(All_distances[i])

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

int main(){
  int a,b,c,max=0,min=100;
  cin >> a >> b >> c;
  if(a>max) max=a;
  if(b>max) max=b;
  if(c>max) max=c;
  if(a<min) min=a;
  if(b<min) min=b;
  if(c<min) min=c;
  cout << max-min;
}

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

using ll = long long;
/* inline */ constexpr auto EPS = 1e-9;

template <typename T, typename U>
inline constexpr auto strict__ (U && x) noexcept -> U
{
  static_assert (std::is_same <T, std::decay_t <U>>::value, "strict type check error");
  return std::forward <U> (x);
}

#define REP(n) for (decltype (n) i = 0, len__ = (n); i < len__; ++ i)
#define ALL(x) x.begin (), x.end ()
#define PRINT(x) std::cout << #x << " = " << x << std::endl;


// C++14 version
namespace detail
{
  template <unsigned r>
  struct combination_helper
  {
    template <typename Iterator, typename F, typename ... Ts>
    static constexpr auto f (Iterator begin, Iterator end, F callback, Ts && ... results) -> void
    {
      for (auto ite = begin; ite < end; ++ ite)
      {
        combination_helper <r - 1>::f (ite + 1, end, callback, std::forward <Ts> (results) ..., * ite);
      }
    }
  };
  template <>
  struct combination_helper <0u>
  {
    template <typename Iterator, typename F, typename ... Ts>
    static constexpr auto f (Iterator, Iterator, F callback, Ts && ... results) -> void
    {
      callback (std::forward <Ts> (results) ...);
    }
  };
} // namespace detail

template <unsigned r, typename Iterator, typename F>
auto combination (Iterator begin, Iterator end, F callback) -> void
{
  return detail::combination_helper <r>::f (begin, end, callback);
}


struct Pos
{
  int x, y;
  friend auto operator << (std::ostream & stream, const Pos & p) -> decltype ((stream))
  {
    return stream << "(" << p.x << ", " << p.y << ")";
  }
};

auto calc (int dx, int dy, const std::vector <Pos> & ps, const Pos & now, bool visited [], int cost) -> decltype (cost)
{
  //PRINT (now);

  // no cost move
  REP (ps.size ())
  {
    if (! visited [i] && now.x + dx == ps [i].x && now.y + dy == ps [i].y)
    {
      visited [i] = true;
      return calc (dx, dy, ps, ps [i], visited, cost);
    }
  }
  
  // cost 1
  REP (ps.size ())
  {
    if (! visited [i])
    {
      visited [i] = true;
      return calc (dx, dy, ps, ps [i], visited, cost + 1);
    }
  }
  
  return cost;
}


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

  int n;
  std::cin >> n;
  std::vector <Pos> ps;
  REP (n)
  {
    int x, y;
    std::cin >> x >> y;
    ps.push_back (Pos {x, y});
  }
  
  std::sort (ALL (ps), [] (const Pos & p1, const Pos & p2) {
    return p1.y == p2.y ? p1.x < p2.x : p1.y < p2.y;
  });
  
  int ans = n == 1 ? 1 : 10000;
  combination <2> (ALL (ps), [&] (auto && p1, auto && p2) {
    //PRINT (p1);
    //PRINT (p2);
    
    auto p = p2.x - p1.x;
    auto q = p2.y - p1.y;
    bool visited [51] = {true};
    auto cost = calc (p, q, ps, ps [0], visited, 1);
    //PRINT (cost); std::cout << std::endl;
    ans = std::min (ans, cost);
  });
  
  std::cout << ans << std::endl;
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


Measured memory_bytes: 256
N = int(input())

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

Fo = 0
Tw = 0
Od = 0

for i in a:

    if i % 4 == 0:
        Fo += 1

    elif i % 2 == 0:
        Tw = 1

    else:
        Od += 1

if Tw + Od <= Fo + 1:

    print ("Yes")

else:
    print ("No")


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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int h,w;
string s[110][110];

int main(){
  cin >> h >> w;
  rep(i,h) {
    rep(j,w)
    cin >> s[i][j];
  }
  rep(i,h) rep(j,w) {
    if( s[i][j] == "snuke") {
      cout << (char)('A'+j) << i+1 << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 384
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;

namespace Atcoder_Answer
{
    class Program
    {
        const Int32 mod = 1000000007;

        static void Main(string[] args)
        {
            long X = long.Parse(ReadLine());
            long M = 100;

            for (int loop = 1; ; loop++) 
            {
                M = (long)(M * 1.01);
                if (X <= M) 
                {
                    WriteLine(loop.ToString());
                    return;
                }
            }
        }
    }

    public static class Extension
    {
        #region 拡張:bool
        #region キャスト関連
        public static int ToInt(this bool Bool)
        {
            if (Bool) return 1;
            else return 0;
        }

        public static string ToString(this bool Bool, string TrueStr, string FalseStr)
        {
            if (Bool) return TrueStr;
            else return FalseStr;
        }
        #endregion
        #endregion

        #region 拡張:int
        #region キャスト関連
        public static char ToAlphaBets(this int Base) => (char)Base;
        #endregion
        #endregion

        #region 拡張:char
        #region 変換関連
        public static char NextAlpha(this char Char) => (char)((Char) + 1); //次の文字を取得
        #endregion
        #endregion

        #region 拡張:int[]
        public static long Sum(this int[] Array)
        {
            int Ret = 0;
            for (int loop = 0; loop < Array.Length; loop++) Ret += Array[loop];
            return Ret;
        }
        #endregion

        #region 拡張: string
        public static string Multi(this string THIS, int Value)
        {
            string RetValue = "";

            for (int loop = 0; loop < Value; loop++) RetValue += THIS;

            return RetValue;
        }
        #endregion

        #region 拡張: List<string>
        public static string Sum(this List<string> THIS, string Split)
        {
            string RetValue = "";

            for (int loop = 0; loop < THIS.Count; loop++)
            {
                RetValue += THIS[loop];
            }

            return RetValue;
        }
        #endregion
    }
}

Measured memory_bytes: 17632
a, b = gets.split.map(&:to_i)
ans=['','']
[a-1, b].each_with_index do |n,i|
  n.bit_length.times do |j|
    bit = 0
    if j ==0
      mod = n % 2**(2)
      bit = (mod==2||mod==1) ? 1 : 0
    else
      mod = n % 2**(j+1)
      bit =
        if mod<2**(j)
          0
        else
          cnt = mod-2**(j)+1
          cnt%2
        end
    end
    ans[i] = bit.to_s + ans[i]
  end
end
#puts ans.to_s
puts ans[0].to_i(2)^ans[1].to_i(2)

Measured memory_bytes: 1788
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 998244353;
#define SIZE 1100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
int main()
{
	invinit();
	int num, kai;
	scanf("%d%d", &num, &kai);
	ll ans = 0;
	for (int i = 0; i <= kai; i++)
	{
		int a = i, b = kai - i;
		if (a < b)ans += 0;
		else if (a >= b + num)
		{
			ans += com(a + b, a);
			ans %= mod;
		}
		else if (a == b)
		{
			if (num > a)continue;
			ans += mod + com(a + b - 1, a - 1) - com(a + b - 1, num - 2);
			ans %= mod;
		}
		else
		{
			int t = num - (a - b);
			if (t > b)continue;
			ans = (ans + com(a + b, a) + mod - com(a + b, t - 1)) % mod;
		}
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 25984
#include <iostream>
using namespace std;
int main(void){
    int n,i,j,a[100+1],tmp,count=0;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<n;i++){
        for(j=n-1;j>i;j--){
            if(a[j]<a[j-1]){
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
                count++;
            }
        }
    }
    for(i=0;i<n;i++){
        i==n-1?cout<<a[i]<<endl:cout<<a[i]<<" ";
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 2e9;
bool flag[N];
vector<pair<int, int> > e[N];
int del[N];
int ans[N];
bool multi, ok;
int delta;

void dfs1(int v) {
	flag[v] = true;
	for (auto x : e[v]) {
		int u = x.first;
		if (!flag[u]) {
			del[u] = -del[v];
			dfs1(u);
		}
		else {
			if (del[u] + del[v] != 0) {
				multi = 0;
			}
		}
	}
}

void dfs(int v) {
	if (!ok) return;
	flag[v] = true;
	for (auto x : e[v]) {
		int u = x.first;
		int w = x.second;
		if (!flag[u]) {
			ans[u] = w - ans[v];
			dfs(u);
		} else if (ans[u] + ans[v] != w) {
			ok = 0;
			if (del[u] == del[v] && (w - ans[u] - ans[v]) % 2 == 0) {
				delta = (w - ans[u] - ans[v]) / 2 / del[v];
			}
			else delta = -inf;
			return;
		}
	}
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		e[x].emplace_back(y, z);
		e[y].emplace_back(x, z);
	}
	memset(flag, 0, sizeof(flag));
	multi = 1;
	del[1] = 1;
	dfs1(1);
	memset(flag, 0, sizeof(flag));
	ans[1] = 1;
	ok = 1;
	dfs(1);
	if (!ok) {
		if (delta == -inf) {
			puts("0");
			return 0;
		}
		memset(flag, 0, sizeof(flag));
		ans[1] = 1+delta;
		ok = 1;
		dfs(1);
	}
	if (!ok) {
		puts("0");
		return 0;
	}
	if (!multi) {
		bool flag = 1;
		for (int i = 1; i <= n; i++) if (ans[i] <= 0) flag = 0;
		if (flag) puts("1");
		else puts("0"); 
	}
	else {
		int s = -inf, t=inf;
		for (int i = 1; i <= n; i++) {
			if (del[i] == 1) s = max(s, 1-ans[i]);
			else t = min(t, ans[i]-1);
		}
		if (t >= s) printf("%d\n", t - s + 1);
		else puts("0");
	}
	//for (int i = 1; i <= n; i++) cout << del[i] << ' ' << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 9728
n, m = list(map(int, input().split()))
roads = [list(map(int, input().split())) for i in range(m)]

# for road in roads:
#     if road[0] > road[1]:
#         road[0], road[1] = road[1], road[0]

for i in range(1, n + 1):
    counter = 0
    for road in roads:
        if i in road:
            counter += 1
    print(counter)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using uint = unsigned int;
using ull = unsigned long long;

int main(void){
    uint N;
    cin >> N;
    
    vector<uint> L(N);
    for (uint i=0; i<N; i++) {
        cin >> L[i];
    }
    
    sort(L.begin(), L.end());
    
    uint ans = 0;
    for (uint i=0; i<N; i++) {
        uint a = L[i];
        for (uint j=i+1; j<N; j++) {
            uint b = L[j];
            auto k = lower_bound(L.begin(), L.end(), a+b);
            ans += k - L.begin() - j - 1;
        }
    }

    cout << ans;
}


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

int main (void)
{
    char S[4];
    int i;

    gets(S);

    if (strlen(S) == 2) {
        puts(S);
    } else {
        putchar(S[2]);
        putchar(S[1]);
        putchar(S[0]);
        puts("");
    }

    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=1010;
long long child[maxn];

int main()
{
    long long n,x;
    scanf("%lld %lld",&n,&x);
    for(int i=0;i<n;i++)
        scanf("%lld",child+i);
    sort(child,child+n);
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        if(x>=child[i])
        {
            x-=child[i];
            ans++;
        }
        else
        {
            break;
        }
        if(i==n-1&&x!=0)
            ans--;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 128
n, k = gets.split.map(&:to_i)
p = gets.split.map(&:to_i)
sum = p[0...k].inject(:+)
max = sum
(n - k).times do |i|
    nextsum = sum - p[i] + p[i + k]
    max = nextsum if nextsum > max
    sum = nextsum
end
puts (max + k) / 2.0

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

int main() {
  int N;
  scanf("%d", &N);
  int t = N;
  int c = 0;
  
  while(t>0){
    c += t%10;
    t /= 10;
  }

  if(N%c == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define m 1000000007
using namespace std;
int main()
 {
     int n;
     cin>>n;
     bitset <4000000> dp;
     int ar[n];
     int sum=0;
     for(int i=0;i<n;i++)
     {
         cin>>ar[i];
         sum+=ar[i];
     }
     dp[0]=1;
     for(int i=0;i<n;i++)
     {
         dp|=(dp<<ar[i]);
     }
     int odd=sum%2;
     for(int i=sum/2+odd;i<=sum;i++)
     {
         if(dp[i]==1)
         {
             cout<<i<<endl;
             return 0;
         }
     }
}

Measured memory_bytes: 1664
import sys
input = sys.stdin.readline

n = int(input())

A = [None] + list(map(int, input().split()))
B = [None]*(n+1)

C = [0]*10001

k = 10000

for j in range(n):
    C[A[j+1]] += 1

for i in range(1, k+1):
    C[i] += C[i-1]


for j in range(1, n+1):
    B[C[A[j]]] = A[j]
    C[A[j]] -= 1

print(' '.join(map(str, B[1:])))


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

using namespace std;

int main() {
    int x,y;
    cin >> x >> y;
    string ans = "No";
    for (int i = 0; i < x+1; i++) {
        int b = x-i;
        if (2*i + 4*b == y) {
            ans = "Yes";
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
n = gets.to_i
a = gets.split(" ").map!{|i| i.to_i}
a.sort!.reverse!
sum = 0
0.upto(n-1) do |j|
  if j % 2 == 0
    sum += a[j]
  else sum -= a[j]
  end
end
puts sum


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
//関数
const long INF=1000000000000000;

int main(void){
    long N;
    double T,A;
    cin>>N>>T>>A;
    
    vector<double> H(N);
    for(int i=0;i<N;i++) cin>>H.at(i);
    
    
    long ans=-1;
    double d=(double) INF;
    for(int i=0;i<N;i++){
        if(abs((T-H.at(i)*0.006)-A)<d){
            d=abs((T-H.at(i)*0.006)-A);
            ans=i+1;
        }
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;

int main() {
  int N;
  cin >> N;
  VI result;
  rep(i, N) {
    int a;

    cin >> a;
    a *= -1;
    int id = 0;
    id = upper_bound(result.begin(), result.end(), a) - result.begin();
    if (id != (int)result.size()) {
      result.at(id) = a;
    } else {
      result.push_back(a);
    }
  }
  cout << result.size() << endl;
  return 0;
}


Measured memory_bytes: 892