akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define pb push_back
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define Unique(n)        (n).erase(unique(all(n)), (n).end())
#define NumofDigits(n)   ((long long)log10(n)+1)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-9;
const int mod = 1e9+7;
/*
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll fastpow(ll b, ll p)
{if(!p)return 1;ll ret = fastpow(b, p >> 1);ret *= ret;if(p&1)ret*= b;return ret;}
*/
int dx[] = { -1,-1,-1,0,+1,+1,+1,0 };   // direction array
int dy[] = { -1,0,+1,+1,+1,0,-1,-1 };
ll gcd(ll a, ll b){return !b ? a : gcd(b, a % b);}
vector<ll>ans;
int main()
{
    ios::sync_with_stdio(0);
/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    clock_t START_TIME = clock();
#endif*/
    ll a,b,g;
    cin>>a>>b;
    g=gcd(a,b);
    for(ll i=2LL; i*i<=g; i++)
        if(g%i==0)
        {
            ans.pb(i);
            while(g%i==0)
                g/=i;
        }
    if(g>1)
        ans.pb(g);
    cout<<sz(ans)+1;
    return 0;

/*#ifndef ONLINE_JUDGE
    cout << endl << "// Time taken = " << fixed << setprecision(5) << (clock() - START_TIME) * 1e3 / CLOCKS_PER_SEC << " ms";
#endif*/
}


Measured memory_bytes: 256
import           Data.Maybe
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = uncurry solve . tuple <$> readParams >>= print

readParams :: IO [Int]
readParams = map readInt . B.words <$> B.getLine

readInt :: B.ByteString -> Int
readInt = fromJust . fmap fst . B.readInt

tuple :: [a] -> (a, a)
tuple [a,b] = (a,b)

solve :: Int -> Int -> Int
solve = lcm


Measured memory_bytes: 380
// Aizu Vol-1 0158: Collatz's Problem
// 2017.8.2

#include <stdio.h>
#include <stdlib.h>

char *gets(char *);
char buf[50];

int main()
{
	int n, k;

	while (gets(buf) != NULL) {
		if (!(n = atoi(buf))) break;
		k = 0;
		while (n > 1) {
			if (n & 1) n = n + ((n+1)>>1), k++;
			else n >>= 1;
			k++;
		}
		printf("%d\n", k);
	}
	return 0;
}

Measured memory_bytes: 524
N,M,C = [ int(it) for it in input().split() ]
bl = [ int(it) for it in input().split() ]
c = 0
for i in range(N):
  al = [ int(it) for it in input().split() ]
  s = C
  for i in range(M):
    s += al[i]*bl[i]
  if (s>0):
    c += 1
print ( c ) 
    
  

Measured memory_bytes: 3060
N, A, B, C = map(int, input().split())

l = []
for i in range(N):
    l.append(int(input()))

def dfs(i, a, b, c):
    if i == N:
        if min(a,b,c) == 0:
            return float("INF")
        else:
            return abs(a-A) + abs(b-B) + abs(c-C)
    else:
        ans0 = dfs(i+1, a, b, c) #棒iを使わないパターン
        ans1 = dfs(i+1, a+l[i], b, c) + (10 if a!=0 else 0)
        ans2 = dfs(i+1, a, b+l[i], c) + (10 if b!=0 else 0)
        ans3 = dfs(i+1, a, b, c+l[i]) + (10 if c!=0 else 0)
    return min(ans0, ans1, ans2, ans3)

print(dfs(0, 0, 0, 0))


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

int main() {
  long long int a, b, x;
  cin >> a >> b >> x;
  long long int ans = (a == 0 ? (b / x + 1) : (b / x + 1) - ((a - 1) / x + 1));

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)

int n,H,W;
int memo[65536];
int visi[65536];
int Q[65537];
int head = 0 , size = 0;
vector<int> mask1,mask2;

vector< vector<char> > goal(4,vector<char>(4));

int w[20],h[20];

inline void gen(int s,int x,int y){
	rep(k,3){
		int a=0,b=0;
		rep(i,h[s]){
			rep(j,w[s]){
				int tx = x + j;
				int ty = y + i;
				if(tx >= 0 && tx < 4 && ty < 4 && ty >= 0){
						a |= 1<<(ty*4+tx);
						b |= (goal[ty][tx] == k)<<(ty*4+tx);
				}
			}
		}
		mask1.push_back(a);
		mask2.push_back(b);
	}
}
int f(int init){
	Q[size++] = init;
	memo[init] = 0;
	int good = (1<<16)-1;
	while(head < size){
		int q = Q[head++];
		int cost = memo[q];
		if(good == q) return cost;
		
		rep(i,mask1.size()){
			int bit = (q & ~mask1[i]) | mask2[i];
			if(!visi[bit]){
				visi[bit] = 1;
				memo[bit] = cost + 1;
				Q[size++] = bit;
			}
		}
	}
	

}

int main(){
	cin >> n;
	rep(i,n) cin >> h[i] >> w[i];
	rep(i,4)rep(j,4){
		char c;cin >> c;
		if(c=='R')c = 0;
		if(c=='G')c = 1;
		if(c=='B')c = 2;
		goal[i][j] = c;
	}
	
	rep(k,n){
		rep(i,7)rep(j,7){
			gen(k,i-3,j-3);
		}
	}

	
	cout << f(0) << endl;
	
	
}

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int n; 
vector<int> l;
bool isOK(int index, int key){
    if(l[index] >= key) return true;
    else return false;
}
int binary_search(int key){
    int ng = -1;
    int ok = (int)l.size();

    while(abs(ok-ng)>1){
        int mid = (ok + ng) /2;

        if(isOK(mid,key)) ok = mid;
        else ng = mid;
    }
    return ok;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    l.resize(n);
    rep(i,n) cin>>l[i];
    sort(all(l));
    i64 ans = 0;
    rep(i,n-1){
        rep(j,i+1,n){
			i64 a = l[i];
			i64 b = l[j];
			i64 left = binary_search(max(a-b,b-a)+1);
			i64 right = binary_search(a+b);
			ans += (right-1) - left + 1;
			if(left<=i&&i<right) --ans;
			if(left<=j&&j<right) --ans;
		}
    }
    cout<<ans/3<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=1<<29,MOD=1e9+7;

int main(){
	int n; cin>>n;
	int a[n];
	rep(i,n){
		cin>>a[i];a[i]--;
	}
	int cnt=0;
	rep(i,n){
		if(a[a[i]]==i) cnt++;
	}
	cout<<cnt/2<<endl;
	return 0;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] A = new int[n];
		
		String[] tmpArray = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			A[i] = Integer.parseInt(tmpArray[i]);
		}
		
		int m = Integer.parseInt(br.readLine());
		int[] B = new int[m];
		
		tmpArray = br.readLine().split(" ");
		for(int i = 0; i < m; i++){
			B[i] = Integer.parseInt(tmpArray[i]);
		}
		
		for(int i = 0; i < m; i++){
			if(canMake(A, B[i], 0)){
				System.out.println("yes");
			}
			
			else{
				System.out.println("no");
			}
		}
	}

	private static boolean canMake(int[] a, int n, int depth) {
		// TODO ?????????????????????????????????????????????
		if(a.length == depth){
			return false;
		}
		
		if(a[depth] == n){
			return true;
		}
		
		int nextN = n - a[depth];
		//???????????¢???????¶????????????¨??????????????¢
		if(canMake(a, n, depth + 1)){
			return true;
		}
		
		if(canMake(a, nextN, depth+1)){
			return true;
		}
			
		return false;
	}

}

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

int N;
const int MAX_N = 100;
int A[2][MAX_N];

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

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int col_i = 0;
        for (int j = 0; j < N; j++) {
            if (j < i) col_i += A[0][j];
            else if (j == i) col_i += A[0][j] + A[1][j];
            else col_i += A[1][j];
        }
        ans = max(ans, col_i);
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <set>
#include <queue>

using namespace std;

#define INF (100000000000000000LL)

typedef pair<long long,int> P; // cost , park

int main() {
    int N,M,C;
    cin >> N >> M >> C;

    vector<P> to[N];
    long long total=0;
    for(int i=0; i<M; ++i) {
        int A,B;
        long long D;
        cin >> A >> B >> D;
        to[A-1].push_back(P(D,B-1));
        to[B-1].push_back(P(D,A-1));
        total+=D;
    }

    unordered_set<int> visit;
    priority_queue<P,vector<P>,greater<P> > q; // cost, park

    vector<P> dist(N);
    for(int i=0; i<N; ++i) dist[i]=make_pair(INF,i);

    q.push(P(0,0));
    while(visit.size()!=N) {
        P p=q.top(); q.pop();
        if(visit.count(p.second)!=0) continue;
        visit.insert(p.second);
        dist[p.second].first=p.first;
        for(auto x : to[p.second]) {
            if(visit.count(x.second)!=0 || dist[x.second].first<p.first+x.first) continue;
            dist[x.second].first=p.first+x.first;
            q.push(P(dist[x.second].first,x.second));
        }
    }

    sort(dist.begin(),dist.end());
    vector<long long> distsum(N);
    visit.clear();
    distsum[0]=0;
    visit.insert(0);
    for(int i=1; i<N; ++i) {
        distsum[i]=distsum[i-1];
        visit.insert(dist[i].second);
        for(auto x : to[dist[i].second]) {
            if(visit.count(x.second)!=0) distsum[i]+=x.first;
        }
    }

    long long ans=total;

    for(int i=1; i<N; ++i) {
        ans=min(ans,C*dist[i].first+total-distsum[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 22092
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
n,q=NM()
l=[]
for i in range(n):
    s,t,x=NM()
    l.append((s-x,t-x,x))
l.sort()
INF=float("inf")
l+=[(INF,INF,INF)]
d=LN(q)
q=[]
from heapq import heappush,heappop
j=0
for i in d:
    while l[j][0]<=i:
        s,t,x=l[j]
        heappush(q,(x,t))
        j+=1
    if len(q)==0:
        print(-1)
    else:
        while q:
            x,t=heappop(q)
            if t>i:
                heappush(q,(x,t))
                print(x)
                break
        else:
            print(-1)

Measured memory_bytes: 122624
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a2=sorted(a)
num=a2[0]
count=1
ans=0
for i in range(1,n):
    if a2[i]==num:
        count+=1
    else:
        if count%2==1:
            ans+=1
        num=a2[i]
        count=1
if count%2==1:
        ans+=1
print(ans)

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

int main(){
	int A,B;
	int sum=0;
	cin >> A >> B;
	sum = A + B;
	if(sum<2*A-1){
		sum = 2*A-1;
	}
	else if(sum<2*B-1){
		sum = 2*B-1;
	}
	cout << sum;
} 

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define For(i, j, k) for(int i = j; i <= (int)k; ++ i)
#define Forr(i, j, k) for(int i = j; i >= (int)k; -- i)
#define INF 0x3f3f3f3f
using namespace std;

ll tar, Ans = 0;
ll p[20];

inline void file(){
	freopen("arc075_F.in", "r", stdin);
	freopen("arc075_F.out", "w", stdout);
}

ll dfs(int l, int r, ll delta){
	if(l >= r)	return delta ? 0 : (l == r ? 10 : 1);
	int t = (10 - delta%10) % 10;
	ll v = delta - (t * p[r-l] - t);
	return ((l ? 10 : 9) - t) * dfs(l + 1, r - 1, abs(v) / 10);
}

int main(){
	p[0] = 1;
	For(i, 1, 18)	p[i] = p[i-1] * 10;
	scanf("%lld", &tar);
	
	For(i, 0, 18)	Ans += dfs(0, i,tar);
	
	printf("%lld", Ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long arr[1000007];
long long cs[1000007];
long long ps[1000007];

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

   if(n==0)
    cout<<1<<endl;

   else
    cout<<0<<endl;


    return 0;

}











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

int main(void) {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> jobs(M);
  for (int i = 0; i < N; i++) {
    int A, B;
    cin >> A >> B;
    if (A <= M) jobs[M - A].push_back(B);
  }

  long long ans = 0;
  priority_queue<int> que;
  for (int i = M - 1; i >= 0; i--) {
    for (int j = 0; j < jobs[i].size(); j++) {
      que.push(jobs[i][j]);
    }
    if (!que.empty()) {
      ans += que.top();
      que.pop();
    }
  }
  cout << ans << endl;
  return 0;
}

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

  ll x = min(b-1, n);
  ll ans = floor(a*x/b);
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3596
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container, std.typecons;
import std.numeric, std.math;
import core.bitop;

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

bool INSIDE(T)(T x, T b, T e) { return x >= b && x < e; }

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

struct UnionFind
{
	void init(long n) { par = new long[](n); foreach (i; 0..n) par[i] = i; }
	long root(long i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(long i, long j) { return root(i) == root(j); }
	void unite(long i, long j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; }
	long[] par;
}

void main()
{
	auto H = RD!long;
	auto W = RD!long;
	auto c = new long[][](10);
	foreach (i; 0..10)
	{
		c[i] ~= RDR.split.to!(long[]);
	}
	auto A = new long[][](H);
	foreach (i; 0..H)
	{
		A[i] ~= RDR.split.to!(long[]);
	}

	auto bestCost = new long[](10);
	foreach (i; 0..10)
	{
		auto cost = new long[](10);
		fill(cost, long.max);
		cost[i] = 0;
		long[] open = [i];
		while (!open.empty)
		{
			auto node = open.front;
			open.popFront;
			cost[1] = min(cost[1], cost[node] + c[node][1]);
			foreach (j; 0..10)
			{
				if (i == j || j == 1) continue;

				if (cost[node] + c[node][j] < cost[1] && cost[node] + c[node][j] < cost[j])
				{
					cost[j] = cost[node] + c[node][j];
					open ~= j;
				}
			}
		}
		bestCost[i] = cost[1];
	}

	long ans;
	foreach (i; 0..H)
	{
		foreach (j; 0..W)
		{
			if (abs(A[i][j]) == 1) continue;
			ans += bestCost[A[i][j]];
		}
	}

	writeln(ans);
	stdout.flush();
}

Measured memory_bytes: 3708
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

int main() {

    char r;
    char g;
    char b;

    scanf("%c %c %c", &r, &g, &b);

    char temp[4];
    temp[0] = r;
    temp[1] = g;
    temp[2] = b;
    
    int num=atoi(temp);
    
    if(num%4==0){
        puts("YES");
    }else{
        puts("NO");
    }
        
    


    return 0;

}


Measured memory_bytes: 128
(defun calc (l)
  (let ((result 1))
    (dolist (x l)
      (setq result (* result x))
      (when (> result 1000000000000000000)
        (setq result nil)
        (return-from calc -1)))
    result))

(defun main ()
  (let ((l nil))
    (dotimes (x (read))
      (let ((tmp (read)))
        (if (zerop tmp)
            (progn
              (princ 0)
              (return-from main nil))
            (push tmp l))))
    (princ (calc l))))

(main)


Measured memory_bytes: 78340
from collections import deque

def bfs(grid, sy, sx, target, wall):
    grid[sy][sx] = wall
    queue = deque([])
    queue.append([sy, sx, 1])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if [y_, x_] == target:
                return cnt+1
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_,cnt+1])
            grid[y_][x_] = wall
    return 0

H,W = map(int, input().split())
wall = '#'
edges = [wall] * (W+2)
grid = [edges]
b_cnt = 0
for i in range(H):
    s = input()
    grid.append([wall] + list(s) + [wall])
    b_cnt += s.count(wall)
grid.append(edges)
cost = bfs(grid, 1,1, [H,W], wall)
print(H*W - b_cnt - cost if cost else -1)


Measured memory_bytes: 3316
from collections import deque

def new_color(s, i, color):
  return s[:i - 1] + color * 2 + s[i + 1:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return

  another = {("r", "g"):"b", ("g", "r"):"b", 
             ("r", "b"):"g", ("b", "r"):"g",
             ("g", "b"):"r", ("b", "g"):"r"}
  visited = {s:True}
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i, another[(ci, temp)])
        if new in monos:
          print(score)
          return

        if new not in visited:
          visited[new] = True
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()


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

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	vector<int> d(n);
	vector<pair<int, int>> e(m);
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		d[b]++;
		g[a].push_back(b);
		e[i] = {a, b};
	}
	queue<int> q;
	REP(i, n) {
		if (d[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		REP(i, g[p].size()) {
			if (--d[g[p][i]] == 0) q.push(g[p][i]);
		}
	}
	if (*max_element(d.begin(), d.end()) == 0) {
		cout << -1 << endl;
		return 0;
	}

	vector<vector<int>> dist(n, vector<int>(n, 1e9 + 1)),
	    prev(n, vector<int>(n, -1));
	REP(i, n) {
		dist[i][i] = 0;
		q.push(i);
		while (!q.empty()) {
			int p = q.front();
			q.pop();
			for (auto a : g[p]) {
				if (dist[i][a] > dist[i][p] + 1) {
					q.push(a);
					dist[i][a] = dist[i][p] + 1;
					prev[i][a] = p;
				}
			}
		}
	}

	vector<int> res;
	REP(i, m) {
		if (dist[e[i].second][e[i].first] != 1e9 + 1) {
			int pos = e[i].first;
			while (pos != e[i].second) {
				res.push_back(pos);
				pos = prev[e[i].second][pos];
			}
			res.push_back(pos);
			break;
		}
	}
	reverse(res.begin(), res.end());
	set<int> st(res.begin(), res.end());
	{
		set<pair<int, int>> s(e.begin(), e.end());
		REP(i, res.size()) {
			assert(s.count({res[i], res[(i + 1) % res.size()]}));
		}
	}
	while (1) {
		bool f = false;
		REP(i, m) {
			if (st.count(e[i].first) && st.count(e[i].second)) {

				int a = find(res.begin(), res.end(), e[i].first) - res.begin(),
				    b = find(res.begin(), res.end(), e[i].second) - res.begin();
				if ((a + 1) % res.size() == b) continue;
				vector<int> next;
				if (a < b) {
					for (int i = 0; i <= a; ++i)
						next.push_back(res[i]);
					for (int i = b; i < res.size(); ++i)
						next.push_back(res[i]);
				} else {
					for (int i = b; i <= a; ++i)
						next.push_back(res[i]);
				}
				res = next;
				st = set<int>(res.begin(), res.end());
				f = true;
			}
		}
		if (!f) break;
	}
	cout << res.size() << endl;
	for (auto a : res)
		cout << a + 1 << endl;
}


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

string S;
int N;
bool f1, f2;

int main()
{
    cin >> S;
    N = (S[0] - '0') * 1000 + (S[1] - '0') * 100 + (S[2] - '0') * 10 + (S[3] - '0');
    int a = (N / 100), b = (N % 100);
    if(0 <= a && a <= 99 && 1 <= b && b <= 12)f1 = true;
    if(1 <= a && a <= 12 && 0 <= b && b <= 99)f2 = true;

    if(f1 && f2)cout << "AMBIGUOUS" << endl;
    else if(f1)cout << "YYMM" << endl;
    else if(f2)cout << "MMYY" << endl;
    else cout << "NA" << endl;

    return 0;

}


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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=20;
int n,k,tot;
int dp[1<<maxn+1][2][4];
int id[maxn+1][1<<maxn],cnt[1<<maxn+1];
char s[1<<maxn];

int main(){
	scanf("%d%d",&n,&k);
	rep(len,n+1)rep(mask,1<<len)id[len][mask]=tot++;
	rep(len,n+1){
		scanf("%s",s);
		rep(mask,1<<len)if(s[mask]=='1')
			dp[id[len][mask]][0][0]++;
	}
	rep(i,n+1)for(int len=n;len>=0;len--)rep(mask,1<<len)rep(f,4){
		int cur=dp[id[len][mask]][i&1][f];
		if(!cur)continue;
		if(i==len){
			cnt[id[len][mask]]+=cur;
			continue;
		}
		int c=((mask>>i)&1);
		if(!((f>>c)&1))dp[id[len][mask]][(i+1)&1][0]+=cur;
		if(len)dp[id[len-1][(mask&((1<<i)-1))|((mask>>(i+1))<<i)]][i&1][f|(1<<c)]+=cur;
		dp[id[len][mask]][i&1][f]=0;
	}
	for(int len=n;len>=0;len--)rep(mask,1<<len){
		if(cnt[id[len][mask]]>=k){
			string ans="";
			rep(i,len)ans+=char(((mask>>i)&1)+'0');
			reverse(ans.begin(),ans.end());
			printf("%s\n",ans.c_str());
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 124160
using System;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = input[0];
            var ABC = new ABC { A = input[1], B = input[2], C = input[3] };

            var S = new string[N + 1];
            for (int i = 0; i < N; i++) S[i] = Console.ReadLine();
            S[N] = string.Empty;

            var path = new char[N];

            for (int i = 0; i < N; i++)
            {
                var c = Set(ABC, S[i], S[i + 1]);
                if (c == null)
                {
                    Console.WriteLine("No");
                    return;
                }
                path[i] = c.Value;
            }

            Console.WriteLine("Yes");
            foreach (var c in path)
            {
                Console.WriteLine(c);
            }
        }

        static char? Set(ABC abc, string s1, string s2)
        {
            if ((s1 == "AB" && abc.A == 0 && abc.B == 0)
               || (s1 == "AC" && abc.A == 0 && abc.C == 0)
               || (s1 == "BC" && abc.B == 0 && abc.C == 0))
            {
                return null;
            }

            if (s1 == "AB")
            {
                if (abc.A == 0) return abc.Add(1, -1, 0);
                else if (abc.B == 0 || s2.Contains("B")) return abc.Add(-1, 1, 0);
                else return abc.Add(1, -1, 0);
            }

            if (s1 == "AC")
            {
                if (abc.A == 0) return abc.Add(1, 0, -1);
                else if (abc.C == 0 || s2.Contains("C")) return abc.Add(-1, 0, 1);
                else return abc.Add(1, 0, -1);
            }

            if (abc.B == 0) return abc.Add(0, 1, -1);
            else if (abc.C == 0 || s2.Contains("C")) return abc.Add(0, -1, 1);
            else return abc.Add(0, 1, -1);
        }

        class ABC
        {
            public long A { get; set; }
            public long B { get; set; }
            public long C { get; set; }
            public char Add(long a, long b, long c)
            {
                A += a;
                B += b;
                C += c;
                if (a == 1) return 'A';
                if (b == 1) return 'B';
                return 'C';
            }
        }
    }
}


Measured memory_bytes: 32380
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 100010;

string s,t;

int32_t main() {
	FAST
	cin >> s >> t;
	t = t.substr(0,t.length()-1);
	if (s == t) {
		cout << "Yes";
	} else cout << "No";
}







Measured memory_bytes: 3600
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int mod = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);

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

	ll as = n / (a + b);
	ll rem = n % (a + b);

	ll res = as * a + min(rem, a);

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

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main(){
    int r, D, xi;
    cin >> r >> D >> xi;
    int xj = 0;
    for (int i=0; i<10; i++) {
        xj = r * xi -D;
        cout << xj << endl;
        xi = xj;
    }
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
swi=[]
for _ in range(m):
    swi.append(list(map(int,input().split()))[1:])
res=list(map(int,input().split()))

sm=0
for x in range(2**n):
    onlst=[0 for _ in range(m)]
    for i in range(n):
        if x>>i&1:
            for j in range(m):
                if i+1 in swi[j] :
                    onlst[j]+=1
    if [x%2 for x in onlst]==res : sm+=1
print(sm)

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

template<class T> inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

struct Edge {
    int to, coin;
    int64_t cost;
    Edge(int _to, int _coin, int64_t _cost) : to(_to), coin(_coin), cost(_cost) {}
};

const int MAX = 3000;
const int64_t INF = 1e18;

int main() {
    int N, M, S;
    cin >> N >> M >> S;
    vector<vector<Edge>> G(N);
    for(int i = 0; i < M; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        G[u].emplace_back(v, a, b);
        G[v].emplace_back(u, a, b);
    }
    vector<int64_t> C(N), D(N);
    for(int i = 0; i < N; ++i) cin >> C[i] >> D[i];

    using V = tuple<int64_t, int64_t, int>;
    priority_queue<V, vector<V>, greater<V>> que;
    vector<vector<int64_t>> dist(N, vector<int64_t>(MAX + 1, INF));
    S = min(S, MAX);
    dist[0][S] = 0;
    que.emplace(0, S, 0);

    while(!que.empty()) {
        auto[cost, coin, cur] = que.top(); que.pop();
        for(auto &e : G[cur]) {
            int64_t ncoin = coin - e.coin;
            if(ncoin >= 0) {
                int64_t ncost = cost + e.cost;
                if(chmin(dist[e.to][ncoin], ncost)) {
                    que.emplace(ncost, ncoin, e.to);
                }
            }
        }
        int64_t ncost = cost + D[cur];
        int ncoin = coin + C[cur];
        chmin(ncoin, MAX);
        if(chmin(dist[cur][ncoin], ncost)) {
            que.emplace(ncost, ncoin, cur);
        }
    }

    for(int i = 1; i < N; ++i) {
        cout << *min_element(dist[i].begin(), dist[i].end()) << '\n';
    }
    return 0;
}


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

using namespace std;

const int N = 100005;

int a[N];

int main() {
	int n, x, y;
	scanf("%d %d %d", &n, &x, &y);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	long long ans = 0;
	for (int i = 1; i < n; i++) {
		ans += min(1ll * y, 1ll * x  * (a[i] - a[i - 1]));
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

set<int>ng={'q','w','e','r','t','a','s','d','f','g','z','x','c','v','b'};

signed main()
{
	IOS();
	vector<int>ans;
	while(1){
		int N,A,B;
		cin >> N >> A >> B;
		if(N == 0 && A == 0 && B == 0)break;
		vector<int>a(N);
		for(int i = 0;i < N;i++){
			cin>>a[i];
		}
		int ma = -1,it = -1;
		rep(i,A-1,B){
			if(ma<=a[i]-a[i+1]){
				ma = a[i] - a[i+1];
				it = i + 1;
			}
		}
		ans.push_back(it);
	}
	for(auto e:ans){
		cout<<e<<endl;
	}
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>

#define rep_ui(k,n)      for(ui  i = (k); i < (n); ++i)
#define rep_si(k,n)      for(int i = (k); i < (n); ++i)
#define rep_ul(k,n)      for(ul  i = (k); i < (n); ++i)
#define rep_sl(k,n)      for(ll  i = (k); i < (n); ++i)
#define rep_ui_down(k,n) for(ui  i = (k); i > (n); --i)
#define rep_si_down(k,n) for(int i = (k); i > (n); --i)
#define rep_ul_down(k,n) for(ul  i = (k); i > (n); --i)
#define rep_sl_down(k,n) for(ll  i = (k); i > (n); --i)

#define rep_uj(k,n)      for(ui  j = (k); j < (n); ++j)
#define rep_sj(k,n)      for(int j = (k); j < (n); ++j)
#define rep_uj_down(k,n) for(ui  j = (k); j > (n); --j)
#define rep_sj_down(k,n) for(int j = (k); j > (n); --j)

#define rep(k,n)         rep_ui(k,n)

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vc)
{
  boost::for_each(vc, [&os, &vc](T value) {
    os << value;
    if (value != vc.back())
      os << ' ';
    });
  return os;
}

template<class T1, class T2>
inline
std::ostream&
operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
  return os << p.first << ' ' << p.second;
}

void solve(void)
{
  //using std::string;
  //string S{}; std::cin >> S;
  
  ui N{}; std::cin >> N;
  typedef std::vector<ui> Vec;
  Vec P(N);
  rep(0, N) std::cin >> P[i];

  ui ans{};
  rep(1, N - 1)
  {
    Vec v = {P[i - 1], P[i], P[i + 1]};
    boost::sort(v);
    if (v[1] == P[i])
      ++ans;
  }

  std::cout << ans << '\n';

  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

struct team{
  int c;
  int p;
  int num;
  int w[100];
};


void f(int t,int p,int r){
  struct team a[100]={};
  rep(i,t+1){
    a[i].num=i;
  }

  rep(i,r){
    int tn,qn,ti;
    string s;
    cin>>tn>>qn>>ti>>s;
    if(s[0]=='W'){
      a[tn].w[qn]++;
    }
    else{
      a[tn].c++;
      a[tn].p+=ti+(a[tn].w[qn]*1200);
    }
  }

  FOR(i,1,t+1){
    int m=i;
    FOR(j,i+1,t+1){
      if(a[m].c<a[j].c||a[m].c==a[j].c&&a[m].p>a[j].p
        || a[m].c==a[j].c&&a[m].p==a[j].p&&a[m].num>a[j].num){
        m=j;
      }
    }
    struct team b = a[m];
    a[m]=a[i];
    a[i]= b;
  }


  FOR(i,1,t+1){
    cout<<a[i].num<<' ';
    cout<<a[i].c<<' ';
    cout<<a[i].p<<endl;
  }


}


int main(){

  while(1){
    int t,p,r;
    cin>>t>>p>>r;
    if(t==0) break;
    f(t,p,r);
  }


  return 0;
}


Measured memory_bytes: 3204
#include<iostream>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int, int>P;
priority_queue<P>Q;
int a[1141919];

int main() {
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < q; i++) {
		int f, g;
		cin >> f >> g;
		a[f] += g;
		Q.push(P(a[f], f*-1));
		while (Q.size()) {
			if (Q.top().first == a[-Q.top().second]) {
				cout << - Q.top().second << ' ' << Q.top().first << endl;
				break;
			}
			Q.pop();
		}
	}
	return 0;
}

Measured memory_bytes: 7784
import bisect
n = int(input())
x = [0]
while x[-1] < 1000000000000001:
    x.append(x[-1]+26**(len(x)))
d = 'abcdefghijklmnopqrstuvwxyz'
digits = bisect.bisect_left(x,n)
num = n - x[digits-1]-1
ans = ""
for i in range(digits):
    ans = ''.join([d[num%(26)],ans])
    num = num//26
print(ans) 

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

void dfs(const long long & N, long long cur, int use, long long & cnt) {
	if (cur > N) return;
	if (use == 0b111) cnt++;

	dfs(N, cur * 10 + 7, use | 0b100, cnt);
	dfs(N, cur * 10 + 5, use | 0b010, cnt);
	dfs(N, cur * 10 + 3, use | 0b001, cnt);
}

int main(void) {
	long long N, res = 0; cin >> N;
	dfs(N, 0, 0, res);

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

Measured memory_bytes: 256
n, m = map(int, input().split())
list_sc = [list(map(int, input().split())) for _ in range(m)]
    
num = [-1] * n
for s, c in list_sc:
    if num[s - 1] != -1 and num[s - 1] != c: # 同じ桁で被りがある
        print(-1)
        exit()
    if n > 1 and s == 1 and c == 0:          # 2桁以上で左端が0
        print(-1)
        exit()
    num[s - 1] = c
    
if n > 1 and num[0] == -1:                   # 2桁以上なら左端の最少は１
    num[0] = 1
    
for k in range(n):                           # 残りを0で埋める
    if num[k] == -1:
        num[k] = 0

num = "".join(map(str, num))
print(num)

Measured memory_bytes: 3064
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    s = s.replace("A","");
    int len = s.length();
    if(len == 0 || len == 3){
      System.out.println("No");
    }else{
      System.out.println("Yes");
    }
  }
}


Measured memory_bytes: 24276
import java.util.Scanner;

public class Main {

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

		int n = scan.nextInt();

		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = scan.nextInt();

		// run(a);
		runSel(a);

		scan.close();
		System.exit(0);
	}

	private static void runSel(int[] a) {
		int op = 0;
		for (int i = 0; i < a.length; i++) {
			int min = i;
			for (int j = i; j < a.length; j++)
				if (a[j] < a[min])
					min = j;
			if (min != i) {
				int tmp = a[i];
				a[i] = a[min];
				a[min] = tmp;
				op++;
			}
		}

		outResult(a, op);

	}

	private static void run(int[] a) {
		int op = 0;
		for (int i = 0; i < a.length; i++)
			for (int j = a.length - 1; j > i; j--)
				if (a[j] < a[j - 1]) {
					int tmp = a[j];
					a[j] = a[j - 1];
					a[j - 1] = tmp;
					op++;
				}

		outResult(a, op);
	}

	private static void outResult(int[] a, int op) {
		for (int i = 0; i < a.length; i++)
			if (i == 0)
				System.out.print(a[i]);
			else
				System.out.print(" " + a[i]);
		System.out.println();
		System.out.println(op);

	}

}

Measured memory_bytes: 26344
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
int main()
{
	string S;
	int N;
	map<string,int> us;
	cin >>N >> S;
	int top=0, bot=N;
	int ok = 0;
	while(bot-top>1)
	{
		int mid=(top+bot)/2;
		string s;
		ok=0;
		for(int i=0;i<N-mid+1;++i)
		{
			s = S.substr(i, mid);
			if(us.find(s)!=us.end())
			{
				if(us[s]+mid<=i)
				{
					ok = 1;
					break;
				}
			}
			else
			{
				us[s]=i;
			}
		}
		us.clear();
		if(ok)
		{
			top = mid;
		}
		else
		{
			bot = mid;
		}
	}
	cout << top << endl;
	return 0;
}




















Measured memory_bytes: 6668
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c = 'a';
  cin >> c;
  if(c == 'a' || c == 'i' || c == 'u' || c =='e' || c == 'o'){
    cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 3560
#include<iostream>

using namespace std;
 int N;
 int A[210];
int main(){
  cin >> N;
  for(int i = 0;i<N;i++){
    cin >> A[i];
  }
   	
    int res =0;
    
    while(true){
      bool exist_odd = false;
      
      for(int i = 0;i<N;i++){
        if(A[i] %2 !=0){
         exist_odd = true; 
        }
      }
        if(exist_odd) break;
        
        for(int i = 0;i<N;i++){
          A[i] /= 2;
        }
        res++;
      
      }
      cout << res << endl;
  }
  
  
  


Measured memory_bytes: 256
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  ll n,i,u,v;
  cin >> n;
  ll ans=0;
  for(i=1;i<=n;i++){
    ans+=i*(n-i+1);
  }
  for(i=0;i<n-1;i++){
    cin >> u >> v;
    if(u>v){
      swap(u,v);
    }
    ans=ans-(u-1)-(n-v);
    ans=ans-(u-1)*(n-v);
    ans--;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>
#include <assert.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		UINT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main()
{
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll X = 0;
	ll Y = 0;
	ll ans = 0;

	cin >> A >> B >> C >> X >> Y;

	// solve
	if (A >= 2 * C && B >= 2 * C) {
		ans += max(X, Y) * 2 * C;
	}
	else if (A >= 2 * C) {
		ans += X * 2 * C;
		if(Y > X) ans += (Y - X) * B;
	}
	else if (B >= 2 * C) {
		ans += Y * 2 * C;
		if (X > Y) ans += (X - Y) * A;
	}
	else if (A + B >= 2 * C) {
		ans += min(X, Y) * 2 * C;
		if (X > Y) {
			ans += (X - Y) * A;
		}
		else {
			ans += (Y - X) * B;
		}
	}
	else {
		// buy each pizza
		ans += X * A;
		ans += Y * B;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
long long a[200001],n,m;
long long read(){
    long long ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
int main()
{
	n=read(),m=read();
	for(int i=0;i<n;i++)a[i]=read();
	sort(a,a+n);
	int l=0,r=n-1,w=1; 
	long long ans=1;
	if(m&1)
	{	
		ans=a[r--];
		m--;
		w=(ans<0?-1:1);
	}
	while(m)
	{
		long long x=a[l]*a[l+1],y=a[r]*a[r-1];
		if(x*w>y*w)
			ans=(ans*(x%mod))%mod,l+=2;
		else
			ans=(ans*(y%mod))%mod,r-=2;
		m-=2;
	}
	printf("%lld",(ans%mod+mod)%mod);
}

Measured memory_bytes: 5292
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
double r = sc.nextDouble();
double pi = Math.PI;
double area = pi*r*r;
double length = 2*pi*r;
System.out.printf("%f %f",area,length);
sc.close();    
}    
}


Measured memory_bytes: 28288
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

int main() {
  int n, k;
  cin >> n >> k;
  int ans = 0, mod = 1e9 + 7;
  for (int i = k; i <= n + 1; ++i) {
    ll mi = 1ll * (0 + i - 1) * i / 2;  
    ll mx = 1ll * (n + n - i + 1) * i / 2;
    ll cnt = mx - mi + 1;
    ans = (cnt + ans) % mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
	int xmin, xmax, ymin, ymax;
	int W, H, N;
	int x, y, a;

	cin >> W >> H >> N;


	xmin = 0;
	xmax = W;
	ymin = 0;
	ymax = H;

	for (int i = 0;i < N;i++) {
		cin >> x >> y >> a;
		
		switch (a){
			case 1:
				if (xmin < x)
					xmin = x;
				break;
			case 2:
				if (xmax > x)
					xmax = x;
				break;
			case 3:
				if (ymin < y)
					ymin = y;
				break;
			case 4:
				if (ymax > y)
					ymax = y;
				break;
		}
	}
	int xans = xmax - xmin;
	int yans = ymax - ymin;
	if (xans >= 0 && yans >= 0) printf("%d\n", xans*yans);
	else printf("%d\n", 0);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)











int main(){
    ll n, k;
    string s;
    cin >> n >> k >> s;
    vector<ll> a;
    ll cnt = 1;
    char t = s[0];
    for(ll i = 1; i < n; i++){
        if(t == s[i]){
            cnt++;
        }
        else{
            a.push_back(cnt);
            cnt = 1;
        }
        t = s[i];
    }
    a.push_back(cnt);
    ll m = a.size();
    if(m <= k * 2 + 1){
        ll ans = 0;
        REP(i, m){
            ans += a[i];
        }
        cout << ans - 1 << endl;
        return 0;
    }
    ll r = 0;
    REP(i, m){
        r += a[i] - 1;
    }
    ll sum = 0;
    REP(i, k * 2 + 1){
        sum += a[i];
        r -= a[i] - 1;
    }
    ll ans = sum - 1 + r;
    for(ll i = k * 2 + 1; i < m; i++){
        sum += a[i];
        sum -= a[i - (k * 2 + 1)];
        r -= a[i] - 1;
        r += a[i - (k * 2 + 1)] - 1;
        ans = max(ans, sum - 1 + r);
    }
    cout << ans << endl;
}


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

using namespace std;

int main() {
    int n = 0, temp = 0;
    cin >> n;

    vector<int> a;

    for (int i = 0; i < n; ++i) {
        cin >> temp;
        a.push_back(temp);
    }

    sort(a.begin(), a.end());

    cout << a[a.size() - 1] - a[0] << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define xx first
#define yy second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int N=3e5+10;
const int M=1e6+10;
int n,a[N];
LL cnt[N];
LL ans[N],sum;

int main(){
	scanf("%d",&n); 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++;
	for(int i=1;i<=n;i++) sum+=cnt[i]*(cnt[i]-1)/2;
	for(int i=1;i<=n;i++){
		ans[i]=sum-cnt[a[i]]*(cnt[a[i]]-1)/2+(cnt[a[i]]-1)*(cnt[a[i]]-2)/2;
		printf("%lld\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926525
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

int dp[100005];
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  // DP解
  // dp[i]はi円までの操作の最小値
  int n;cin>>n;
  REP(i,n+1)dp[i]=i;
  set<int> s;
  REP(i,7)s.insert(pow(9,i));
  REP(i,8)s.insert(pow(6,i));
  for(auto x:s){
    for(int i=x;i<=n;i++){
      dp[i]=min(dp[i], dp[i-x]+1);
    }
  }
  P(dp[n]);

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int main(){	
	LL ai, ao, at, aj, al, as, az;
	scanf("%lld%lld%lld%lld%lld%lld%lld", &ai, &ao, &at, &aj, &al, &as, &az);
	LL ans = ai / 2 * 4 + ao * 2 + aj / 2 * 4 + al / 2 * 4;
	if (ai % 2 && aj % 2 && al % 2) ans += 6;
	else if (ai % 2 && aj % 2 && al > 0) ans += 2;
	else if (ai % 2 && aj > 0 && al % 2) ans += 2;
	else if (ai > 0 && aj % 2 && al % 2) ans += 2;
	printf("%lld", ans / 2);
	return 0;
}

Measured memory_bytes: 256