akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

int main(){
    string s;
    int k;
    cin>>s>>k;
    int num=s.size();
    ll dp[num+1][2][k+2];
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=0;i<num;i++){
        int D=s[i]-'0';
        for(int j=0;j<2;j++){
            for(int l=0;l<=k;l++){
                for(int d=0;d<=(j?9:D);++d){
                    if(d!=0)dp[i+1][j||(d<D)][l+1]+=dp[i][j][l];
                    else dp[i+1][j||(d<D)][l]+=dp[i][j][l];
                }
            }
        }
    }
    cout<<dp[num][0][k]+dp[num][1][k]<<endl;
}


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

int n;
char grid[255][255];
int dx[] = {1,0,1,-1};
int dy[] = {0,1,1,1};

int solv(int sx, int sy) {
	int res = 0;
	for (int i=0; i<4; ++i) {
		int cnt = 0, x = sx, y = sy;
		while (0 <= x && x < n && 0 <= y && y < n) {
			cnt = (grid[y][x] == '1' ? cnt+1 : 0);
			res = max(res, cnt);
			x += dx[i];
			y += dy[i];
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	while (cin >> n, n) {
		char c;
		for (int i=0; i<n*n; ++i) {
			cin >> grid[i/n][i%n];
		}
		int res = 0;
		for (int i=0; i<n; ++i) {
			res = max(max(res, solv(0, i)), max(solv(n-1, i), solv(i, 0)));
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1264
#include <iostream>
#include <cstring>
#include <cctype>	
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

// 0:TOP 1:FRONT 2:RIGHT 3:LEFT 4:BACK 5:BOTTOM
string list[24] = {
	"012345","024135","031425","043215","103254","120534",
	"135024","152304","201453","215043","240513","254103",
	"304152","310542","345012","351402","402351","425031",
	"430521","453201","513240","521430","534120","542310"
};

bool used[8];
string data[8];
char puzzle[6][8];

// eêÉÂ¢ÄobNgbN·éÛÉµª¶¶È¢æ¤mF·é×«Æ±ëB
// ôFnumberAïFface ÉÎµÄ¢éÏÈtH[}bgBIíèÍ -1B
int connect[8][8] = {
	{-1},
	{0,3,-1},		// Êu:0 ÉÊ:3 ªÚ±µÄ¢é
	{1,1,-1},		// Êu:1 ÉÊ:1 ªÚ±µÄ¢é
	{0,1,2,2,-1},	// Êu:0 ÉÊ:1 ªÚ±µAÊu:2 ÉÊ:2 ªÚ±µÄ¢é
	{0,5,-1},		// Êu:0 ÉÊ:5 ªÚ±µÄ¢é
	{1,5,4,3,-1},	// Êu:1 ÉÊ:5 ªÚ±µAÊu:4 ÉÊ:3 ªÚ±µÄ¢é
	{2,5,5,1,-1},	// Êu:2 ÉÊ:5 ªÚ±µAÊu:5 ÉÊ:1 ªÚ±µÄ¢é
	{3,5,4,1,6,2,-1}// Êu:3 ÉÊ:5 ªÚ±µAÊu:4 ÉÊ:1 ªÚ±µAÊu:6 ÉÊ:2 ªÚ±µÄ¢é
};

bool ok (char a, char b )
{
	return (tolower(a ) == tolower(b ) && a != b );
} 

bool backTrack (int cur )
{
	if (cur == 8 )
		return true;

	rep (d, 8 ){
		if (used[d] ) continue;

		used[d] = true;
		rep (i, 24 ){
			rep (j, 6 )
				puzzle[cur][j] = data[d][list[i][j]];

			bool f = true;
			for (int j = 0; connect[cur][j] != -1; j += 2 ){
				int pos = connect[cur][j];
				int face = connect[cur][j+1];
				f &= ok (puzzle[pos][5-face], puzzle[cur][face] );
			} // end for
			if (f )
				if (backTrack(cur + 1 ) )
					return true;
		} // end rep
		used[d] = false;
	} // end rep

	return false;
}
	
int main()
{
	rep (i, 24 )
		rep (j, 6 )
			list[i][j] -= '0';

	while (cin >> data[0] , data[0] != "0" ){
		for (int i = 1; i < 8; i++ )
			cin >> data[i];
		memset (used, false, sizeof (used ) );

		cout << (backTrack (0 ) ? "YES" : "NO" ) << endl;
	} // end while

		
	return 0;
}

Measured memory_bytes: 904
public class Main {
	public static void main(String[] args) {
		
		for (int i = 1; i<10; i++) {
			for (int j = 1; j<10; j++) {
				int res = i*j;
				System.out.println(i + "x" + j +"=" +res);
			}	
		}
	}
}


Measured memory_bytes: 24032
"""
A:プラグの数
B:必要なプラグの数
"""

A, B = map(int, input().split())
count = 0

if B == 1:
    print(0)
elif A >= B:
    print(1)
else:
    while True:
        B -= (A - 1)
        count += 1
        if B <= A:
            count += 1
            break

    print(count)


Measured memory_bytes: 9152
fun burger_count(lv:Int):Pair<Long,Long>{
    if(lv == 0){
      return Pair(1L, 1L);
    }
    val (patty,all) = burger_count(lv - 1);
    return Pair(patty * 2 + 1L, all * 2 + 3L);
}
fun eat_patty(lv:Int,remain_eat:Long):Pair<Long,Long>{
  if (remain_eat == 0L){
    return Pair(0,0);
  }
  if(lv == 0){
    return Pair(1,remain_eat-1);
  }
  else{
    if (remain_eat < 1){
      return Pair(0,0);
    }else{
      val (p,a) = burger_count(lv - 1);
      if(a * 2 < remain_eat - 3){
        return Pair(p * 2 + 1,remain_eat - 3 - (a * 2));
      }else if(a <= remain_eat - 2){
         val (peatedd,rd) = eat_patty(lv - 1,remain_eat - 2 - a);
         return Pair(p + peatedd + 1,rd);
      }else{
         return eat_patty(lv - 1,remain_eat - 1);
      }
    }
  }  
}


fun main(args: Array<String>) {
    val (n,x) = readLine()!!.split(" ").map { num ->num.toLong() };   
    
    val (eat,all) = eat_patty(n.toInt(),x);
    
    println(eat);
}

Measured memory_bytes: 37932
#include <iostream>

int main() {
  std::string s;
  std::cin >> s;
  if (s[2] == s[3] && s[4] == s[5]) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  return 0;
}


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

using namespace std;

int main(){
  ll N,M,ans=0;
  cin>>N>>M;

  if(M/2>=N){
    ans+=N;
    M-=N*2;
    ans+=M/4;
  }else ans+=M/2;
  cout<<ans<<endl;
}


Measured memory_bytes: 256
/*
	ax+by=c,
	 dx+ey=f
	x=(E1*B2-B1*E2)/(A1*B2-B1*A2)
	y=(E2*A1-E1*A2)/(A1*B2-A2*B1)
*/

#include<iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include<string>
#define round(d, n)	 (double((d) * pow(10, n) + 0.5) / pow(10, n))
using namespace std;

int main(){
	double a,b,c,d,e,f;
	double x, y;
	list<double> xy;
	
	while(!(cin>>a>>b>>c>>d>>e>>f).eof()){
		xy.push_back((c*e-f*b)/(a*e-b*d));
		xy.push_back((f*a-d*c)/(a*e-d*b));
	}
	list<double>::iterator it = xy.begin();
	while(it != xy.end()){
		x = *it;
		it++;
		y = *it;
		cout << fixed << setprecision(3) << round(x,4) << " " << round(y,4) << endl;
		it++;
	}
}

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

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    LL h,sum=0;
    int n;
    cin>>h>>n;
    while(n--)
    {
        int x;
        cin>>x;
        sum+=x;
    }
    if(sum>=h)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}




















Measured memory_bytes: 256
#include<iostream>
    using namespace std ;
    int main(){
        char a ;
        cin>>a;
        if(a=='A')cout<<"T"<<endl;
        if(a=='T')cout<<"A"<<endl;
        if(a=='C')cout<<"G"<<endl;
        if(a=='G')cout<<"C"<<endl;
        return 0 ;
    }

Measured memory_bytes: 256
N = int(input())
n = 0
h = 0
w = 0

for i in range(1, 3501):
    for j in range(1, 3501):
        tmp1 = N * i * j
        tmp2 = (4 * i * j) - (N * j) - (N * i)
        if tmp2 != 0:
            s, m = divmod(tmp1, tmp2)
            if m == 0 and s >= 0:
                n, h, w = i, j, s
                print(n, h, w)
                exit()


Measured memory_bytes: 41068
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		String[] a = sc.next().split("");
		String[] b = sc.next().split("");
      
        // 長さとか一文字目ずつ比較して確認する
        String ans = "";
        if (a.length > b.length) {
          ans = "GREATER";
        } else if (a.length < b.length) {
          ans = "LESS";
        } else {
          for(int i = 0; i < a.length; i++) {
            int aValue = Integer.parseInt(a[i]);
            int bValue = Integer.parseInt(b[i]);
            if (aValue > bValue) {
              ans = "GREATER";
              break;
            } else if (aValue < bValue) {
              ans = "LESS";
              break;
            } else if (i == a.length - 1) {
              ans = "EQUAL";
            }
          }
        }
    
		// 出力
		System.out.println(ans);
	}
}

Measured memory_bytes: 21844
#e
n,p=map(int,input().split())
s=input()
ans=0
if p == 2:
    for i in range(n):
        if s[i] in ["0","2","4","6","8"]:
            ans+=i+1
elif p == 5:
    for i in range(n):
        if s[i] in ["0","5"]:
            ans+=i+1
else:
    mod=[1] + [0]*(p-1)
    a=0
    for i in range(n):
        si = int( s[n-1-i] )
        a = si*pow(10,i,p) + a 
        mod[ a%p ]+=1
    ans =  sum(m*(m-1)//2 for m in mod)
print(ans)

Measured memory_bytes: 41180
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int a[10];
	int sum1,sum2,ans;
	for(int i=0;i<3;i++)
	{
	scanf("%d",&a[i]);	
	}
	sort(a,a+3);
    sum1=0;
    ans=0;
    sum1=a[2]-a[1];
	ans+=sum1;
	sum2=a[2]-a[0]-sum1;
	if(sum2%2==0) 
	ans+=sum2/2;
	else
	ans+=sum2/2+2;
	printf("%d\n",ans);
	return 0;
	 
	
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 10000
int n,a[MAXN+5];
int ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==a[i-1])
		{
			a[i]=n+i;ans++;
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 256
class Node{
  constructor(id, parent, children) {
    this.id = id;
    this.parent = parent;
    this.children = children;
  }

  get type() {
    if (this.parent === null) return 'root';
    if (this.children.length === 0) return 'leaf';
    return 'internal node';
  }

  get depth() {
    const getDepth = (node, i) => {
      return node.parent === null ? i : getDepth(node.parent, i + 1);
    };
    return getDepth(this, 0);
  }

  toString() {
    return `node ${this.id}: parent = ${this.parent !== null ? this.parent.id : -1}, depth = ${this.depth}, ${this.type}, [${this.children.map(n => n.id).join(', ')}]`;
  }
};

class Tree {
  static get Node() {
    return Node;
  }

  constructor(n) {
    this.nodes = [];
  }

  add(id, childrenIds) {
    let node = this.find(id);
    childrenIds.forEach((cid) => {
      let c = this.find(cid);
      c.parent = node;
      c.id = cid;
      node.children.push(c);
    })
  }

  find(id) { if (!this.nodes[id]) return this.nodes[id] = new Tree.Node(id, null, []); return this.nodes[id]; }

  print() { console.log(this.nodes.sort((a, b) => a.id - b.id).map(n => n.toString()).join('\n')); }
}

(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  let tree = new Tree(n);
  let id, k, childrenIds;
  lines.map(l => l.split(' ')).forEach(function(line) {
    id = Number(line.shift());
    k = Number(line.shift());
    childrenIds = line.map(Number);
    tree.add(id, childrenIds);
  });
  tree.print();
})();



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

struct Node{
	Node *parent, *left, *right;
	int key, priority;
};

Node *deleteN(Node*,int);

Node *root, *NIL;


Node *rightRotate(Node *t){
	Node *s = t->left;
	t->left = s->right;
	s->right = t;
	return s;
}

Node *leftRotate(Node *t){
	Node *s = t->right;
	t->right = s->left;
	s->left = t;
	return s;
}

Node *insert(Node *t,int key, int priority){
	if(t == NIL){//cout<<key<<" "<<priority<<endl;
		Node *temp;
		temp = new Node;
		temp->key = key;
		temp->priority = priority;
		temp->left = NIL;
		temp->right = NIL;
		return temp;
	}
	if(key == t->key){
		return t;
	}
	
	if(key < t->key){
		t->left = insert(t->left, key, priority);
		if(t->priority < t->left->priority)
			t = rightRotate(t);
	} else {
		t->right = insert(t->right, key, priority);
		if(t->priority < t->right->priority)
			t = leftRotate(t);
	}
	return t;
}

bool find(Node *t, int key){
	while(t != NIL && key != t->key){
		if(key < t->key) t = t->left;
		else t = t->right;
	}
	return t!=NIL;
}

void inorder(Node *t){
	if(t == NIL) return;
	cout<<" "<<t->key;
	inorder(t->left);
	inorder(t->right);
}

void preorder(Node *t){
	if(t == NIL)return;
	preorder(t->left);
	cout<<" "<<t->key;
	preorder(t->right);
}

void print(Node *t){
	preorder(t);
	cout<<endl;
	inorder(t);
	cout<<endl;
}

Node *_delete(Node *t, int key){
	if(t->left == NIL && t->right == NIL){
		if(t->parent != NIL){
			if(t->parent->left->key == key) t->parent->left = NIL;
			else t->parent->right = NIL;
		}
		//delete t;
		return NIL;
	}else if(t->left == NIL)
		t = leftRotate(t);
	else if(t->right == NIL)
		t = rightRotate(t);
	else {
		if(t->left->priority > t->right->priority)
			t = rightRotate(t);
		else
			t = leftRotate(t);
	}
	return deleteN(t,key);
}

Node *deleteN(Node *t, int key){
	if(t == NIL)
		return NIL;
	if(key < t->key)
		t->left = deleteN(t->left, key);
	else if(key > t->key)
		t->right = deleteN(t->right, key);
	else 
		return _delete(t,key);
	return t;
}

int main(){
	int n, k, p;
	string order;
	
	cin>>n;
	
	for(int i = 0; i < n; i++){
		cin>>order;
		
		if(order == "insert"){
			cin>>k>>p;
			root = insert(root,k,p);
		} else if(order == "find"){
			cin>>k;
			cout<<(find(root,k)?"yes":"no")<<endl;
		} else if(order == "delete"){
			cin>>k;
			root = deleteN(root,k);
		} else if(order == "print"){
			print(root);
		}
	}
	return 0;
}


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

using namespace std;

int main()
{
	char pri[1000000];
	int i,j;
	
	for(i=0;i<1000000;i++)
	{
		pri[i]='1';
	}
	pri[0]=pri[1]='0';
	
	for(i=0;i<1000000;i++)
	{
		if(pri[i]=='1')
		{
			for(j=2;j*i<1000000;j++)
			{
				pri[i*j]='0';
			}
		}
	}
	
	int n,max,menu[100];
	vector<char> sum;
	
	
	for(;;)
	{
		cin >> n >> max ;
		if(n==0 && max==0)
			break;
		int ans=0;
		sum.clear();
		for(i=0;i<1000000;i++)
			sum.push_back(0);
		
		for(i=0;i<n;i++)
		{
			cin >> menu[i];
			sum[menu[i]]='1';
		}
		
		for(i=0;i<=max;i++)
		{
			if(sum[i]=='1')
			{
				if(pri[i]=='1')
					ans=i;
				for(j=0;j<n;j++)
				{
					if(i+menu[j]<=max)
						sum[i+menu[j]]='1';
				}
			}
		}
		if(ans==0)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
}

Measured memory_bytes: 2988
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007
using namespace std;
int n,m,k,fa[100009],num[100009];
vector<int>w[100009];
vector<int>w1[100009];
int findl(int x)
{
    return fa[x]==x?x:fa[x]=findl(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=n; i++)
        fa[i]=i,num[i]=1;
    for(int i=0; i<m; i++)
    {
        int x,y,tmp,tmp1;
        scanf("%d%d",&x,&y);
        w[x].push_back(y),w[y].push_back(x);
        tmp=findl(x),tmp1=findl(y);
        if(tmp!=tmp1)
            fa[tmp]=tmp1,num[tmp1]+=num[tmp];
    }
    for(int i=0;i<k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        w1[x].push_back(y),w1[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        int ans=num[findl(i)]-w[i].size()-1;
        for(int j=0;j<w1[i].size();j++)
        {
            int tmp=findl(i),tmp1=findl(w1[i][j]);
            if(tmp==tmp1)
                ans--;
        }
        printf("%d ",ans);
    }
    return 0;
}

Measured memory_bytes: 13176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    string s, t;
    cin >> s >> t;
    cout << t << s;
    return 0;
}

Measured memory_bytes: 384
n=int(input())
a=list(map(int, input().split()))
b=[0]*n
c=[0]*n
for i in range(n):
    b[i]=a[i]+i
    c[i]=i-a[i]
bs=sorted(b)
cs=sorted(c)
lx=[1+10**10]*n
ly=[2+10**10]*n
rx=[3+10**10]*n
ry=[4+10**10]*n

lx[0]=1
ly[0]=bs[0]
rx[0]=1
ry[0]=cs[0]

d=0
e=0
for j in range (1,n):
    if bs[j]==bs[j-1]:
        lx[d]+=1
    else:
        d+=1
        lx[d]=1
        ly[d]=bs[j]
        
for k in range (1,n):
    if cs[k]==cs[k-1]:
        rx[e]+=1
    else:
        e+=1
        rx[e]=1
        ry[e]=cs[k]
x=0
ans=0
for l in range(d):
    while ry[x]<=ly[l] and x<n-1:
        if ry[x]==ly[l]:
            ans+=(lx[l]*rx[x])
            x+=1
        else:
            x+=1
print(ans)



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

using namespace std;

long long solve(long long v) {
    if (v == 1) return 1;
    return 2LL * solve(v / 2) + 1LL;
}

int main() {
    long long h;
    scanf("%lld", &h);

    printf("%lld\n", solve(h));
}


Measured memory_bytes: 3868
from heapq import *

N, M = map(int, input().split())
A = list(map(int, input().split()))

# print(A)
A = [-a for a in A]
heapify(A)
# print(A)
for _ in range(M):
    x = -heappop(A)
    heappush(A, -(x/2))

print(sum([int(-a) for a in A]))

Measured memory_bytes: 14180
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;


int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  
  rep(i,n) cin >> p[i];
  sort(p.begin(),p.end());
  
  p[n-1] = p[n-1] / 2;
  
  int ans = 0;
  
  rep(i,n) ans += p[i];
  
  cout << ans;
  
  return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N = read_a_int()
A = read_ints()
if N == 1:
    print(0)
    exit()
B = [a - i for a, i in zip(A, range(1, N + 1))]
B.sort()

# 絶対値を区切る境目はどこがよいか？
B_cum = cumsum1d(B)
ans = 10**15
for k in range(1, N):
    tmp_sum = -B_cum.total(0, k) + B_cum.total(k, N)
    add = min((2 * k - N) * B[k - 1], (2 * k - N) * B[k])
    ans = min(ans, tmp_sum + add)


print(ans)
# 式ごちゃごちゃやったけど絶対楽な方法がある。
# 明日復習


Measured memory_bytes: 31008
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int inf = 1e9;

int32_t main(){
	cin.tie(0); ios::sync_with_stdio(0);
	
	int n;
	cin >> n;
	vector<int> a(n+2, inf), dp(n+2, inf);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	dp[0] = 0;
	for(int i = 0; i < n; i++){
		dp[i+1] = min(dp[i+1], dp[i] + abs(a[i] - a[i+1]));
		dp[i+2] = min(dp[i+2], dp[i] + abs(a[i] - a[i+2]));
	}
	
	cout << dp[n-1] << endl;
}


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

if n < 10:
    print(n)
elif 10 <= n < 100:
    print(9)
elif 100 <= n < 1000:
    print(9+(n-99))
elif 1000 <= n < 10000:
    print(9+900)
elif 10000 <= n < 100000:
    print(9+900+(n-9999))
elif 100000 <= n:
    print(9+900+90000)

Measured memory_bytes: 9192
x = gets.to_i

# a^5 - b^5 = x
# (a-b)(a^4+a^3b+a^2b^2+ab^3+b^4) = x
# x=k*lと因数分解 (k<=l)
# x > 0、R >= 0だから？、(a-b)>0
# aは絶対に0より大きい
# a-b=kだからb=a-k

def calc(a, b)
  a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
end

(1..x).each do |k|
  next if x % k != 0
  l = x / k
  (1..l).each do |a|
    break if a**4 > l
    b = a - k
    if calc(a, b) == l
      puts "#{a} #{b}"
      exit(0)
    end
  end
end


Measured memory_bytes: 14380
N = int(input())
A = list(map(int, input().split()))

# 参考：https://qiita.com/aki-takano/items/a43fac70b702d4f22d7e
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

L = lcm(A)
B = []
for a in A:
    B.append(L // a)

print(sum(B) % 1000000007)


Measured memory_bytes: 264432
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int M[200][200],X[]={-1,-1,0,0,1,1},Y[]={-1,0,-1,1,0,1};
main(){
	int r,n,k,x,y;
	for(;scanf("%d%d",&n,&k),n;printf("%d\n",r)){
		for(memset(M,r=0,sizeof(M));k;k--)scanf("%d%d",&x,&y),M[x+100][y+100]=1;
		scanf("%d%d",&x,&y);
		queue<pair<pair<int,int>,int> >q;
		for(q.push(make_pair(make_pair(x+100,y+100),0));!q.empty();){
			pair<pair<int,int>,int>p=q.front();q.pop();
			if(M[p.first.first][p.first.second])continue;
			r+=M[p.first.first][p.first.second]=1;
			if(p.second<n)for(int i=0;i<6;i++)q.push(make_pair(make_pair(p.first.first+X[i],p.first.second+Y[i]),p.second+1));
		}
	}
}

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

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(){
    ll n;
    cin >> n;
    ll count = 0;
    for(auto p : prime_factor(n)) {
        //cout << " " << p.first << " "  << p.second;
        bool flag = true;
        for(int i = 1; i >= 0; i++){
            count++;
            p.second -= i;
            if(p.second <= i) break;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#define ll long long
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
static const int MAX = 1000000007;
static const int MAXN = 100001;

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

    ll a, ans = n;
    if(ans / k > 1){
        ans -= (ans / k) * k;
    }
    if(ans > k) a = ans-k;
    else a = k-ans;
    
    while( ans > a ){
        ans = a;
        if(a > k) a = ans-k;
        else a = k-ans;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
  int X = 1, Y, A, B;
  cin >> A;
  cin >> B;
  
  for (Y = A;Y < B;Y += A) {
    Y -= 1;
    X++;
  }
  
  if (B == 1) {
   X = 0; 
  }
  
  cout << X;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define y1 abcde
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
#define int long long

const ll inf = 2e18;
const int L = 61;
const int N = 2e5 + 15;
int n, k, a[N], g[L][N], last[N], first[N];
bool used[N];
vector <int> ans;

main() {
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    fill(last, last + N, -1);
    fill(first, first + N, -1);
    cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        if(first[a[i]] == -1)
            first[a[i]] = i;
    }
    for(int i = n - 1; i >= 0; --i)
        last[a[i]] = i + n;
    for(int i = n - 1; i >= 0; --i) {
        g[0][i] = last[a[i]] - i + 1;
        last[a[i]] = i;
    }
    for(int i = 1; i < L; ++i)
        for(int j = 0; j < n; ++j)
            g[i][j] = min(inf, g[i-1][j] + g[i-1][(j + g[i-1][j]) % n]);
    int j = 0;
    for(int i = L - 1; i >= 0; --i)
        if(g[i][j % n] + j <= n * k)
            j += g[i][j % n];
    for(int i = j % n; i < n; ++i) {
        if(!used[a[i]]) {
            ans.pb(a[i]);
            used[a[i]] = true;
        }
        else
            while(used[a[i]]) {
                used[ans.back()] = false;
                ans.ppb();
            }
    }
    for(int i : ans)
        cout << i << ' ';
    return 0;
}

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

using namespace std;
using ll = long long;
vector<vector<char>> v3 = { {'a', 'a', '.'},
                            {'.', '.', 'a'},
                            {'.', '.', 'a'}};
vector<vector<char>> v4 = { {'a', 'a', 'b', 'a'},
                            {'c', 'c', 'b', 'a'},
                            {'a', 'b', 'c', 'c'},
                            {'a', 'b', 'a', 'a'}};
vector<vector<char>> v5 = { {'a', 'a', 'b', 'b', 'c'},
                            {'.', 'd', 'd', 'a', 'c'},
                            {'c', 'c', '.', 'a', 'b'},
                            {'b', '.', 'a', '.', 'b'},
                            {'b', '.', 'a', 'c', 'c'}};
vector<vector<char>> v6 = { {'a', 'a', 'b', 'b', '.', 'c'},
                            {'b', '.', '.', 'z', 'z', 'c'},
                            {'b', 'a', 'c', '.', '.', '.'},
                            {'.', 'a', 'c', '.', 'a', 'a'},
                            {'.', '.', 'a', 'c', 'c', 'b'},
                            {'c', 'c', 'a', '.', '.', 'b'}};
vector<vector<char>> v7 = { {'a', 'a', '.', '.', 'b', '.', 'a'},
                            {'.', '.', 'a', 'a', 'b', '.', 'a'},
                            {'a', 'c', '.', '.', 'a', 'a', '.'},
                            {'a', 'c', '.', '.', 'c', '.', '.'},
                            {'.', '.', 'b', 'b', 'c', 'b', 'b'},
                            {'.', '.', 'a', 'a', '.', 'c', 'a'},
                            {'a', 'a', '.', '.', '.', 'c', 'a'}};

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    int N_copy = N;
    vector<char> v(N, '.');
    vector<vector<char>> vn(N, v);
    if (N == 2){
        cout << -1 << endl;
    }
    else if (N == 3){
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << v3[i][j];
            }
            cout << endl;
        }
    }
    else
    {
        while (N > 7)
        {
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    vn[N_copy - N + i][N_copy - N + j] = v4[i][j];
                }
                
            }
            N -= 4;
        }
        vector<vector<char>> v_end;
        if (N == 4) v_end = v4;
        else if (N == 5) v_end = v5;
        else if (N == 6) v_end = v6;
        else v_end = v7;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                vn[N_copy - N + i][N_copy - N + j] = v_end[i][j];
            }
            
        }
        for (int i = 0; i < N_copy; i++)
        {
            for (int j = 0; j < N_copy; j++)
            {
                cout << vn[i][j];
            }
            cout << endl;
        }
        
    }
    
    
}

Measured memory_bytes: 2304
program kadai
implicit none

integer  ::  n,m,i,j,flag
integer,allocatable  ::  L(:)
integer,allocatable  ::  R(:)

read(*,*) n,m

allocate(L(m))
allocate(R(m))

do i=1,m
    read(*,*) L(i),R(i)
end do

flag=minval(R)-maxval(L)+1

if (flag<0) then
    flag=0
end if
write(*,*) flag


end program kadai

Measured memory_bytes: 1024
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const ll inf = 1e18;
const int N = 3000;
int n, m, mx = 3000, S;
struct Edge
{
	int fr, to, a, b;
} E[N];
vector<int> G[N];
ll dp[N][N], ans[N];
int vis[N][N], d[N], c[N];
queue<pair<int, int> > q;
int main()
{
	n = read(), m = read(), S = min(mx, read());
	for (int i = 1; i <= m; ++i)
	{
		E[i].fr = read(), E[i].to = read();
		E[i].a = read(), E[i].b = read();
		G[E[i].fr].push_back(i);
		G[E[i].to].push_back(i);
	}
	for (int i = 1; i <= n; ++i)
		c[i] = read(), d[i] = read(), ans[i] = inf;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= mx; ++j)
			dp[i][j] = inf;
	dp[1][S] = 0;
	q.push(make_pair(1, S)), vis[1][S] = 1;
	while (!q.empty())
	{
		int u = (q.front()).first, x = (q.front()).second;
		ans[u] = min(ans[u], dp[u][x]);
		q.pop();
		vis[u][x] = 0;
		if (x + c[u] <= mx && dp[u][x] + d[u] < dp[u][x + c[u]])
		{
			dp[u][x + c[u]] = dp[u][x] + d[u];
			if (!vis[u][x + c[u]])
				q.push(make_pair(u, x + c[u])), vis[u][x + c[u]] = 1;
		}
		for (int i : G[u])
		{
			int v = E[i].fr + E[i].to - u;
			if (x >= E[i].a && dp[u][x] + E[i].b < dp[v][x - E[i].a])
			{
				dp[v][x - E[i].a] = dp[u][x] + E[i].b;
				if (!vis[v][x - E[i].a])
					q.push(make_pair(v, x - E[i].a)), vis[v][x - E[i].a] = 1;
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}


Measured memory_bytes: 5840
/* include c++ libraries */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>

/* include c-lang libraries */
#include <climits>
#include <cmath>

/* include my libraries */
//#include <show_vec.hh>

using namespace std;

#define LINE DEBUG{ printf("LINE : %d\n", __LINE__); }
#define DEBUG if(false)

using ll = long long;
template<class T> using vec = vector<T>;

const int MOD = 1000000007;

int main(){
  ll N, D;
  cin >> N >> D;
  int count = 0;
  for(int i = 0; i < N; i++){
    ll x, y;
    cin >> x >> y;
    double d = sqrt((double)((x*x) + (y*y)));
    if((double)D >= d){
      count++;
    }
  }
  cout << count << endl;

  return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair

using namespace std;

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10);
	int n; cin >> n;
	std::vector<pair<int, int> > a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i].second >> a[i].first;
	}
	sort(a.begin(), a.end());
	int ii = 0;
	bool ok = true;
	for (int i = 0; i < n; ++i) {
		if (a[i].second + ii > a[i].first) {
			ok = false;
			break;
		} 
		ii += a[i].second;
	}
	if (ok) cout << "Yes";
	else cout << "No";
}

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

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = 200000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007

MOD = 10**9 + 7

C = [int(i) for i in input().split()]
C.sort(reverse=True)

ans = 0
for i in range(N):
    ans += C[i] * (1+divide(i, 2))

ans *= power(2, 2*N-1)
ans %= MOD

print(ans)

Measured memory_bytes: 116004
#include <bits/stdc++.h>
#define ll long long
#define inf 100000000000000000
#define mod 1000000007
#define endl '\n'
#define omarshagar                    \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
using namespace std;

int main()
{

   omarshagar
    int n;
   cin>>n;
   int arr[n+1];
   int arr2[n];
   for(int i=0;i<n+1;i++)
   {
       cin>>arr[i];
   }
   for(int i=0;i<n;i++)
   {
       cin>>arr2[i];
   }
   ll res=0;
   for(int i=0;i<n;i++)
   {
       ll tmp=min(arr[i],arr2[i]);
       arr[i]-=tmp;
       arr2[i]-=tmp;
       res+=tmp;
       tmp=min(arr[i+1],arr2[i]);
       arr[i+1]-=tmp;
       arr2[i]-=tmp;
       res+=tmp;
   }
   cout<<res<<endl;
}


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

int solve(int N) {
    vector<int> A(N);
    int sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }
    sort(A.begin(), A.end());
    auto Itere = upper_bound(A.begin(), A.end(), sum / N);
    return Itere - A.begin();
}

int main() {
    int N;
    vector<int> ans;
    while (cin >> N) {
        if (!N) break;
        ans.push_back(solve(N));
    }

    for (int i : ans) cout << i << endl;
}


Measured memory_bytes: 3148
#include<stdio.h>

typedef long long ll;

ll max(ll a,ll b){
  if(a > b){
    return  a;
  }
  else{
    return b;
  }
}

int main(void){
 ll a , b , c , d;
 scanf("%lld %lld %lld %lld",&a ,&b ,&c ,&d);


 ll ans1 , ans2 , ans3 , ans4;
 ans1 = a * c;
 ans2 = a * d;
 ans3 = b * c;
 ans4 = b * d;

 ll ans = max(max(ans1,ans2),max(ans3,ans4));

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

 return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int a;
    cin >> a;
    if(a >= 30) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}



Measured memory_bytes: 3648
import java.io.*;
import java.util.*;
public class Main{
	public static void main(String args[]) throws IOException{
               BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));	
				int n = Integer.parseInt(reader.readLine());
				int[] list = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();					
				int p = 0;
				for(int i =0;i<n;i++) p=p^list[i];
				StringBuilder s = new StringBuilder("");
				for(int i = 0;i<n;i++){
					s.append((p^list[i])).append(" ");
				}
				System.out.println(s.toString());
	}
}


Measured memory_bytes: 62800
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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;
}


template <class T>
class SegTree {
    int n;// 葉の数
    vector<T> data;// データを格納するvector
    T def; // 初期値かつ単位元
    function<T(T, T)> operation; // 区間クエリで使う処理
    function<T(T, T)> update;// 点更新で使う処理

    // 区間[a,b)の総和。ノードk=[l,r)に着目している。
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def; // 交差しない
        if (a <= l && r <= b)
            return data[k]; // a,l,r,bの順で完全に含まれる
        else {
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
            return operation(c1, c2);
        }
    }

    public:
    // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
    // _update:更新関数
    SegTree(size_t _n, T _def, function<T(T, T)> _operation,
        function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        data = vector<T>(2 * n - 1, def);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    // [a, b)の区間クエリを実行
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    // 添字でアクセス
    T operator[](int i) {
        return data[i + n - 1];
    }
};

int main(){
    ll n;cin >> n;
    vpl v(n);
    rep(i,n)cin >>  v[i].fi >>v[i].se;
    sort(all(v));
    ll ans=0;
    SegTree<ll> st(n,inf,[](ll a,ll b){return min(a,b);},[](ll a,ll b){return b;});
    rep(i,n){
        st.change(i,v[i].se);
    }
    rep(i,n-1){
        pl left=v[n-1],right=v[i];
        left.se=st.query(i+1,n);
        ll mini=st.query(0,i);
        ll res=max(0LL,left.se-left.fi+1)+max(0LL,min(right.se,mini)-right.fi+1);
        chmax(ans,res);
        res=max(0LL,min(left.se,mini)-left.fi+1)+max(0LL,right.se-right.fi+1);
        chmax(ans,res);
    }
    cout << ans <<endl;
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;

int main() {
  // bfsで
  int N, X, Y;
  cin >> N >> X >> Y;
  --X; --Y;
  vector<int> cnt(N);
  rep(start, N) {
    queue<int> que;
    vector<int> dist(N, INF);   // 0-indexed
    auto push = [&](int next, int d) {
      if (dist[next] != INF) return;
      dist[next] = d;
      que.push(next);
    };
    push(start, 0);
    while (!que.empty()) {
      int next = que.front(); que.pop();
      int d = dist[next];
      if (next-1>=0) push(next-1, d+1);
      if (next+1<=N) push(next+1, d+1);
      if (next == X) push(Y, d+1);
      if (next == Y) push(X, d+1);
    }
    for (int i = 0; i < N; i++) {
      cnt[dist[i]]++;
    }
  }
  rep(i, N) cnt[i] /= 2;
  for (int i = 1; i < N; i++) {
    cout << cnt[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 3624
S = input()
if S == "AKIHABARA" or  S == "KIHABARA" or  S == "AKIHBARA" or  S == "AKIHABRA" or  S == "AKIHABAR" or S == "KIHBARA" or S == "KIHABRA" or S == "KIHABAR" or S == "AKIHBRA" or S == "AKIHBAR" or S == "AKIHABR" or S == "KIHBRA" or S == "KIHBAR" or S == "KIHABR" or S == "AKIHBR" or S == "KIHBR":
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int N,T;
    cin >> N >> T;
    vector<int>t(N);
    for(int i = 0; i < N; i++) {
        cin >> t[i];
    }
    int ans = 0;
    for(int i = 1; i < N; i++) {
        ans+=min(T,t[i]-t[i-1]);
    }
    ans+=T;
    cout << ans << endl;
}

Measured memory_bytes: 1792
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll modpow(ll n,ll k){
  if(k == 1){
    return n;
  }else if(k == 0){
    return 1;
  }else if(k%2==0){
    ll memo = modpow(n,k/2)%MOD;
    return memo*memo%MOD;
  }else{
    return n * modpow(n,k-1)%MOD;
  }
}

int main(){

  int n;
  cin>>n;
  cout<<(n-2)*180<<endl;

 

  return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    B = list(map(int, input().split()))

    ans = [B[0]]

    for i in range(1, N-1):
        ans.append(min(B[i-1], B[i]))
    ans.append(B[N-2])
    print(sum(ans))
if __name__ == '__main__':
    main()

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

const int N_MAX = 100;

void sitA( char* seat, int n )
{
	int i = 0;
	while( seat[ i ] != '#' ){
		++i;
	}
	seat[ i ] = 'A';
}

void sitB( char* seat, int n )
{
	int i = n - 1;
	while( i > 0 ){
		if( seat[ i ] == '#' ){
			if( seat[ i - 1 ] != 'A' && seat[ i + 1 ] != 'A' ){
				seat[ i ] = 'B';
				return;
			}
		}
		--i;
	}
	while( seat[ i ] != '#' ){
		++i;
	}
	seat[ i ] = 'B';
}

void sitC( char* seat, int n )
{
	int i = 0;
	while( i < n ){
		if( seat[ i ] != '#' ){
			if( seat[ i + 1 ] =='#' ){
				seat[ i + 1 ] = 'C';
				return;
			}
			if( i >= 0 && seat[ i - 1 ] == '#' ){
				seat[ i - 1 ] = 'C';
				return;
			}
		}
		++i;
	}
	seat[ n / 2 ] = 'C';
}

void sitD( char* seat, int n )
{
	int est[ N_MAX ];
	int s, e;
	vector< int > seated;
	for( int i = 0; i < n; ++i ){
		if( seat[ i ] != '#' ){
			seated.push_back( i );
		}
	}
	if( seated.size() == 0 ){
		seat[ 0 ] = 'D';
		return;
	}
	e = seated[ 0 ];
	for( int i = e; i >= 0; --i ){
		est[ i ] = e - i;
	}
	for( int i = 1; i < seated.size(); ++i ){
		s = e;
		e = seated[ i ];
		for( int j = 0; j <= ( e - s ) / 2; ++j ){
			est[ s + j ] = est[ e - j ] = j;
		}
	}
	for( int i = e; i < n; ++i  ){
		est[ i ] = i - e;
	}
	int estMax = 0, estIdx = 0;
	for( int i = 0; i < n; ++i ){
		if( est[ i ] > estMax ){
			estMax = est[ i ];
			estIdx = i;
		}
	}
	seat[ estIdx ] = 'D'; 
}

void sit( char a, char* seat, int n )
{
	switch( a ){
		case 'A': sitA( seat, n ); break;
		case 'B': sitB( seat, n ); break;
		case 'C': sitC( seat, n ); break;
		case 'D': sitD( seat, n ); break;
	}
}

int main()
{
	int n, m;
	char seat[ N_MAX + 1 ];
	while( cin >> n >> m && ( n || m ) ){
		for( int i = 0; i < n; ++i ){
			seat[ i ] = '#';
		}
		seat[ n ] = '\0';

		for( int i = 0; i < m; ++i ){
			char a;
			cin >> a;
			sit( a, seat, n );
		}
		cout << seat << endl;
	}
	return 0;
}

Measured memory_bytes: 1212
from collections import deque

N = int(input())

L = [[] for i in range(N)]

for i in range(N-1) :
    u,v,w = map(int,input().split())
    
    u -= 1
    v -= 1
    
    L[u].append([v,w])
    L[v].append([u,w])

ans = [0] + [-1 for i in range(N-1)]

q = deque([0])

while q :
    a = q.popleft()
    
    for b,w in L[a] :
        if ans[b] != -1 :
            continue
        
        ans[b] = (ans[a] + w) % 2
        q.append(b)

print(*ans, sep="\n")


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

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

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n;cin>>n;
  vector<double> hoge(n);
  rep(i,n)cin>>hoge[i];
  //2 $B8D$N6q:`$rFi$KF~$l$k$H!"$=$l$i$O>CLG$7$F?7$?$K(B 
  //1 $B8D$N6q:`$,@8@.$5$l$^$9!#$3$N?7$?$J6q:`$N2ACM$O(B
  //$B85$N(B 2 $B8D$N6q:`$N2ACM$r(B x , y $B$H$7$F(B ( x + y)/2$B$G$"$j!"(B
  //$B$3$N6q:`$r:F$SFi$KF~$l$k$3$H$b$G$-$^$9!#$3$N6q:`$N9g@.(B
  //$B$r(B N $B!](B 1 $B2s9T$&$H!":G8e$K(B 1 $B8D$N6q:`$,;D$j$^$9!#(B
  //$B$3$N6q:`$N2ACM$H$7$F9M$($i$l$k:GBg$NCM$r5a$a$F$/$@$5$$!#(B
  sort(hoge.begin(),hoge.end());
  double ans=hoge[0];
  rep2(i,1,n){
    ans+=hoge[i];
    ans/=2;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  int k;
  cin >> k;
  int n = 500;
  vector<vector<int>> mp(n);
  for (int i = 0; i < n; i++)
    mp[i].resize(n);
  if (k <= 500) {
    cout << k << endl;
    for (int i = 0; i < k; i++) {
      cout << i + 1;
      for (int j = 1; j < k; j++)
        cout << " " << i + 1;
      cout << endl;
    }
  } else {
    int c = 1;
    for (int i = 0; i < n; i++) {
      bool d = k - 500 > i;
      for (int j = 0; j < n; j++) {
        if (d)
          mp[(i + j) % n][j] = c + j % 2;
        else
          mp[(i + j) % n][j] = c;
      }
      if (d)
        c++;
      c++;
    }
    cout << n << endl;
    for (int i = 0; i < n; i++) {
      cout << mp[i][0];
      for (int j = 1; j < n; j++)
        cout << " " << mp[i][j];
      cout << endl;
    }
  }
  return 0;
}


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

const int MAX_ROW = 100000;  // 最大行数
const int MAX_COL = 60;  // 最大列数

struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    explicit BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    bitset<MAX_COL>& operator[] (int i) {return val[i];}
    BitMatrix operator* (BitMatrix B) {
        BitMatrix A = *this;
        BitMatrix R(A.H, B.W);  // 答え
        BitMatrix tB(B.W, B.H);  // Bの転置行列
        for (int i = 0; i < tB.H; i++) {
            for (int j = 0; j < tB.W; j++) {
                tB[i][j] = B[i][j];
            }
        }
        for (int i = 0; i < R.H; i++) {
            for (int j = 0; j < R.W; j++) {
                R[i][j] = ((A[i] & tB[j]).count() & 1);
            }
        }
        return R;
    }
};
ostream& operator<<(ostream& s, BitMatrix A) {
    s << endl;
    for (int i = 0; i < A.H; i++) {
        for (int j = A.W - 1; j >= 0; j--) {
            if (j != A.W - 1) cout << " ";
            s << A[i][j];
        }
        s << endl;
    }
    return s;
}
BitMatrix pow(BitMatrix A, int64_t n) {
    BitMatrix R(A.H, A.H);
    for (int i = 0; i < A.H; i++) R[i][i] = 1;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}
// Gauss-Jordan の掃き出し法(BitMatrix版)
int GaussJordan(BitMatrix &A, bool is_extended = false) {
    int rank = 0;
    for (int col = A.W - 1; col >= 0; col--) {
        if (is_extended && col == 0) break;
        int pivot = -1;
        for (int row = rank; row < A.H; row++) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);  // 行交換
        // 掃き出し
        for (int row = 0; row < A.H; row++) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        rank++;
    }
    return rank;
}


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

    int N;
    cin >> N;
    BitMatrix X(N, 60);
    int64_t a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        X.val[i] = (bitset<MAX_COL>) a;
    }
    bitset<MAX_COL> all_xor = 0;
    for (int i = 0; i < N; i++) {
        all_xor ^= X.val[i];
    }
    // all_xor が 0 になっている桁のみを考える
    for (int i = 0; i < N; i++) X.val[i] &= ~all_xor;

    GaussJordan(X);
    bitset<MAX_COL> bset = 0;
    for (int i = 0; i < N; i++) {
        bset ^= X.val[i];
    }
    uint64_t ret = bset.to_ullong() * 2 + all_xor.to_ullong();

    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<iomanip>
#include<map>
using namespace std;
typedef pair<int, pair<int, int> >PP;
typedef long long ll;
typedef pair<int, int>P;
typedef vector<int>vec;
int inf=-1;
ll mod = pow(10, 9) + 7;
 
int main(){
    int a,b;cin>>a>>b;
    if(a<=9 && b<=9){
        cout<<a*b<<endl;
    }
    else{
        cout<<-1<<endl;
    }
    return 0;
}

Measured memory_bytes: 256