akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
int raw[maxn];
int main(){
	int n;
	ll ans = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d",&raw[i]);
	sort(&raw[1],&raw[n+1]);
	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j++)
			if(i != j){
				int a = raw[i],b = raw[j];
				int L = max(a-b,b-a),R = a+b;
				int x = upper_bound(&raw[1],&raw[n+1],L)-raw;
				int y = lower_bound(&raw[1],&raw[n+1],R)-raw;
				ans += (y-x) > 0?y-x:0;
				if(x <= i and i <= y)ans--;
				if(x <= j and j <= y)ans--;
//				cout << ans << endl;
			}
	printf("%lld\n",ans/3);
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN=210000;
typedef long long ll;
ll myabs(ll x) {return x>0?x:-x;}

ll a[MAXN];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]-=i;
    sort(a+1,a+n+1);
    ll b=a[(n+1)/2];

    ll ans=0;
    for(int i=1;i<=n;i++) ans+=myabs(a[i]-b);
    printf("%lld",ans);
}


Measured memory_bytes: 1664
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)


int main(){
	int m,nmin,nmax;
	while(cin>>m>>nmin>>nmax&&(m||nmin||nmax)){
		vector<int> v(m);
		rep(i,m)cin>>v[i];
		
		int maxi = -1;
		int pos = -1;
		for(int i=nmin;i<=nmax;i++){
			int t = v[i-1]-v[i];
			if(maxi<=t){
				maxi = t;
				pos = i;
			}
		}
		cout<<pos<<endl;
	}
}

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

int main() {
    int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
    int dx = tx - sx;
    int dy = ty - sy;

    cout << string(dx, 'R') << string(dy, 'U');
    cout << string(dx, 'L') << string(dy, 'D');
    cout << 'D' << string(dx+1, 'R') << string(dy+1, 'U') << 'L';
    cout << 'U' << string(dx+1, 'L') << string(dy+1, 'D') << 'R';
    cout << endl;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		if (x - r < 0 || x + r > W || y - r < 0 || y + r > H) {
		    System.out.println("No");
		} else if (x - r >= 0 || x + r >= W || y - r >= 0 || y + r >= H) {
		    System.out.println("Yes");
		}
    }
}



Measured memory_bytes: 26344
def is_kaibun(s):
    n = len(s)
    for i in range(n):
        if s[i] != s[n-1-i]:
            return False
    return True

def is_tsuyoi(s):
    n = len(s)
    if not is_kaibun(s):
        return False
    if not is_kaibun(s[:(n-1)//2]):
        return False
    if not is_kaibun(s[(n+3)//2-1:]):
        return False

    return True

S = input()

print('Yes' if is_tsuyoi(S) else 'No')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define F first
#define S second
#define forit(it,cont) for(auto it=cont.begin();it!=cont.end();it++)
#define for0(i,n) for(i=0;i<n;i++)
#define for1(i,n) for(i=1;i<=n;i++)
#define for0r(i,n) for(i=n-1;i>=0;i--)
#define for1r(i,n) for(i=n;i>=1;i--)
#define ll long long 
vector<ll> h(100010);
vector<ll> res(100010,INT_MAX);
int main()
{
	IOS;
	ll n,i,k,j;
	cin>>n>>k;
	for0(i,n)
	cin>>h[i];
	res[0]=0;
	for(i=1;i<n;i++)
	{
		j=i-1;
		while(j>=i-k&&j>=0)
		{
			res[i]=min(res[i],(res[j]+abs(h[i]-h[j])));
			j--;
		}
	}
	cout<<res[n-1]<<endl;
	return 0;	
}


Measured memory_bytes: 1792
import java.util.Scanner;

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

    int count = 0;
    for (int i = 0; i < S.length()/2 ; i++) {
      if (S.charAt(i) != S.charAt(S.length() - i - 1)) {
        count++;
      }
    }

    System.out.println(count);
  }
}


Measured memory_bytes: 23508
n = int(input())
result = 0
max_div = 0
one = 0
zero = 0

def func(zero, one):
    res = 1
    if min(zero,one) == 0:
        return 1
    
    for i in range(min(zero, one)):
        res *= (zero + one - i)
    for i in range(1,min(zero,one)+1):
        res //= i
    return res

if n < 3:
    result = 0
else:
    max_div = n // 3
    
    for div in range(max_div):
        zero = div + 1
        one = n - 3 * zero
        result += func(zero-1, one)

print(result % (10 ** 9 + 7))

Measured memory_bytes: 73588
def main():
    n=int(input())
    s= ["".join(sorted(input())) for i in range(n)]
    check = {}
    ans = 0
    for i in s:
        if i in check:
            ans += check[i]
            check[i] += 1
        else:
            check[i] = 1
            
    print(ans)
    
main()

Measured memory_bytes: 19404
n = int(input())
c, fb, la, both = 0, 0, 0, 0
for _ in range(n):
  s = input()
  c += s.count("AB")
  if s[0] == "B" and s[-1] == "A":
    both += 1
  else:
    if s[0] == "B":
      fb += 1
    if s[-1] == "A":
      la += 1
if both == 0:
  c += min(fb, la)
else:
  if fb+la > 0:
    c += both + min(fb, la)
  else:
    c += both-1
print(c)

Measured memory_bytes: 3060
import copy

def j(n):
    if n:print("yes")
    else:print("no")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)
a = ["Sunny","Cloudy","Rainy"]
n = input()
b = a.index(n)
b+=1
b%=3
print(a[b])

Measured memory_bytes: 3572
H,W,K = map(int,input().split())
listc = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            listc[i][j] = 0
        else:
            listc[i][j] = 1

ans = 0
#print(listc[1])
for i in range(2**H):
    l = i
    tmp = []
    for j in range(H-1,-1,-1):
        if l >= (2**j):
            tmp.append(listc[j])
            l -= 2**j
    #print(tmp)
    for j in range(2**W):
        h = j
        t = 0
        for k in range(W-1,-1,-1):
            if h >= (2**k):
                for x in range(len(tmp)):
                    t += tmp[x][k]
                h -= 2**k
        #print(j,t)
        if t == K:
            ans += 1

print(ans)

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

int main(int argc, char *argv[]){
  int n;
  cin >> n;
  int x, y, b, p;
  for (int i = 0; i < n; i++) {
    int fee = 1e9;
    cin >> x >> y >> b >> p;
    for (int i = b; i <= 6; i++) {
      for (int j = p; j <= 6; j++) {
        int tmp = 0, a = 0, b = 0;
        if(i >= 5 && j >= 2){
          tmp += (i*x + j*y)*0.8;
          a = i, b = j;
        }
        tmp += x*(i - a) + y*(j - b);
        fee = min(fee, tmp);
      }
    }
    std::cout << fee << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
  
const ll MOD=1e9+7;
const ll INF=1e18;
  
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
 
int dp[1000005][2];
 
int main(){
    for(int i = 1;i <= 1000000;i++){
        dp[i][0] = 10000000;
        dp[i][1] = 10000000;
    }
 
    for(int i = 1; i*(i+1)*(i+2)/6 < 1000000;i++){
        int simen = i*(i+1)*(i+2)/6;
        for(int j = 0; j + simen < 1000000;j++){
            for(int k = 0;k < 2;k++){
                if(k == 1 && simen % 2 == 0) continue;
                dp[j+simen][k] = min(dp[j+simen][k],dp[j][k]+1);
            }
        }
    }
    int n;
    while(true){
        cin >> n;
        if(n == 0) break;
        cout << dp[n][0] << " " << dp[n][1] << endl;
    }
}


Measured memory_bytes: 10908
from bisect import bisect
n = input()
A = map(int, raw_input().split())
st = [(0, 0)]

part = [0]*(n+1)
block = [0]*(n+1)

for i in xrange(n):
    if st[-1][0] < A[i]:
        st.append((A[i], i))
    idx = bisect(st, (A[i], -1))
    part[idx] += A[i] - st[idx-1][0]
    block[idx-1] += 1
ans = [0]*n
tmp = 0
for i in range(1, len(st))[::-1]:
    tmp += block[i]
    ans[st[i][1]] = tmp*(st[i][0] - st[i-1][0]) + part[i]
print "\n".join(map(str, ans))


Measured memory_bytes: 31436
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
#define F first
#define S second
#define MK make_pair
const ll E=1e17+7;
const ll MOD=1000000007;
 
 
 
 
int main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> x,y;
    for(int i=0;i<n;i++){
        ll k;
        cin>>k;
        x.push_back(k);
    }
    for(int i=0;i<m;i++){
        ll k;
        cin>>k;
        y.push_back(k);
    }
    ll xsum=0;
    ll ysum=0;
    for(int i=1;i<n;i++){
        ll k=x[i]-x[i-1];
        k%=MOD;
        k*=i;
        k%=MOD;
        k*=n-i;
        k%=MOD;
        xsum+=k;
        xsum%=MOD;
    }
    for(int i=1;i<m;i++){
        ll k=y[i]-y[i-1];
        k%=MOD;
        k*=i;
        k%=MOD;
        k*=m-i;
        k%=MOD;
        ysum+=k;
        ysum%=MOD;
    }
    ll ans=xsum*ysum;
    ans%=MOD;
    cout<<ans<<endl;
    
    
    return 0;
}

Measured memory_bytes: 2548
#include<stdio.h>

int main(void){
  int n;
  scanf("%d",&n);

  int xy[300][3];
  int a , kei = 0;

  for(int i = 0;i < n;i ++){
    scanf("%d",&a);
    kei += a;
    for(int j = kei - a;j < kei;j ++){
      scanf("%d %d",&xy[j][0],&xy[j][1]);
      xy[j][2] = i + 1;
    }
  }

  /*for(int i = 0;i < kei;i ++){
    for(int j = 0;j < 3;j ++){
      printf("%d ",xy[i][j]);
    }
    putchar('\n');
  }*/

  int b[40000][15] , max = 0;

  for(int i = 0;i < (1<<n);i ++){
    int s = 0 , count = 1 , t = i;
    while(count <= n){
      if(t%2 == 1){
        s ++;
        b[i][count] = 1;
      }
      else{
        b[i][count] = 0;
      }
      count ++;
      t /= 2;
    }
    count = 0;
    while(count < kei){
      if(b[i][xy[count][2]] == 1){
        if(b[i][xy[count][0]] != xy[count][1]){
          s = 0;
        }
      }
      count ++;
    }
    if(max < s){
      max = s;
    }
  }

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

  return 0;
}

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

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

	string a, b;

	int x, y;

	cin >> a >> b;
	cin >> x >> y;

	string temp;

	cin >> temp;

	if (temp == a)
	{
		cout << x - 1 << " " << y;
		return 0;
	}
	else
	{
		cout << x << " " << y - 1;
	}
	return 0;
}

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

int main() {
	const int n = 6;
	int dice[n];
	int y[6];
	int top, front;
	int p;
	int dice_result[6];
	const int dice_tem[4][6] = { { 3,2,6,1,5,4 },{ 2,6,3,4,1,5 },
	{ 5,1,3,4,6,2 },{ 4,2,1,6,5,3 } };
	for (int i = 0; i < n; i++) {
		cin >> dice[i];
	}
	int num;
	cin >> num;
	for (int v = 0; v < num; v++) {
		cin >> top >> front;
		for (int d = 0; dice[0] != top ; d++) {
			if (d == 0)continue;

			for (int i = 0; i < n; i++) {
				dice_result[i] = dice[dice_tem[d % 2][i] - 1];
			}
			for (int i = 0; i < n; i++)dice[i] = dice_result[i];
		}
		
		for (p = 0; p < 4; p++) {
			for (int i = 0; i < n; i++) {
			dice_result[i] = dice[dice_tem[p][i]-1];
		}
			if (front == dice_result[0]) break;
		}
		int a = p == 0 ? 2 : p == 1 ? 0 : p == 2 ? 3 : p == 3 ? 1 : -1;
		
		for (int i = 0; i < n; i++)y[i] = dice[dice_tem[a][i] - 1];
		cout << y[0]  << endl;
		

	}
	return 0;
}
		


Measured memory_bytes: 3076
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<map>
#define int long long int
#define mod 1000000007
void dfs(vector<pair<int,int>> adj[],int src,int value[],bool visited[],int curr,int dist)
{
	if(visited[src])
	   return ;
	else
	{
		visited[src]=true;
		if(dist%2==0)
		{
			value[src]=curr;
		}
		else
		{
			value[src]=1-curr;
		}
		for(auto p:adj[src])
		{
			dfs(adj,p.first,value,visited,value[src],p.second);
		}
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<pair<int,int>> adj[n+1];
	int j;
	for(j=0;j<n-1;j++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	int value[n+1];
	bool visited[n+1]={false};
	dfs(adj,1,value,visited,0,0);
	for(j=1;j<=n;j++)
	{
		cout<<value[j]<<endl;
	}
}	



Measured memory_bytes: 10880
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 100000+5
#define MOD 20190823
#define eps 1e-8
#define mp make_pair
#define INF 1000000000+9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline void read(ll &f){
	f=0;
    ll x=1;
    char ch=getchar();
    while(ch<48 || ch>57) {
        if(ch=='-') {
            x=-1;
        }
        ch=getchar();
    }
    while(ch<=57 && ch>=48) {
        f=f*10+ch-'0';
        ch=getchar();
    }
    f*=x;
}
ll n,m;
char c[25][25];
ll d[25][25];
ll ans=0;
bool vst[25][25];
void BFS(ll x,ll y){
	queue<pair<ll,ll> > q;
	q.push(mp(x,y));
	ll temp=0;
	vst[x][y]=1;
	while(!q.empty()){
		ll dx=q.front().first,dy=q.front().second;
		q.pop();
		ll p=d[dx][dy];
		if(vst[dx+1][dy]==0 && dx+1<=n && c[dx+1][dy]!='#'){
			d[dx+1][dy]=p+1;
			vst[dx+1][dy]=1;
			temp=max(temp,d[dx+1][dy]);
			q.push(mp(dx+1,dy));
		}
		if(vst[dx][dy+1]==0 && dy+1<=m && c[dx][dy+1]!='#'){
			d[dx][dy+1]=p+1;
			vst[dx][dy+1]=1;
			temp=max(temp,d[dx][dy+1]);
			q.push(mp(dx,dy+1));
		}
		if(vst[dx-1][dy]==0 && dx-1>=1 && c[dx-1][dy]!='#'){
			d[dx-1][dy]=p+1;
			vst[dx-1][dy]=1;
			temp=max(temp,d[dx-1][dy]);
			q.push(mp(dx-1,dy));
		}
		if(vst[dx][dy-1]==0 && dy-1>=1 && c[dx][dy-1]!='#'){
			d[dx][dy-1]=p+1;
			vst[dx][dy-1]=1;
			temp=max(temp,d[dx][dy-1]);
			q.push(mp(dx,dy-1));
		}
	}
//	for(ll i=1;i<=n;i++){
//		for(ll j=1;j<=m;j++){
//			cout<<d[i][j]<<" ";
//		}
//		cout<<endl;
//	}
//	cout<<endl<<endl<<endl;
	ans=max(ans,temp);
}
int main(){
	read(n),read(m);
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++){
			if(c[i][j]=='.'){
				mem(vst,0);
				mem(d,0);
				BFS(i,j);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main(){
  int x;
  cin>>x;
  for(int i=x;i<1000000;i++){//xから順に調べる
    bool flag=true;
    for(int a=2;a<sqrt(i);a++){
      if(i%a==0){
        flag=false;//わりきれちゃった！素数じゃない！
        break;
      }
    }
    if(flag){
      cout<<i<<endl;
      break;
    }
  }
    
}



Measured memory_bytes: 256
using System;

 public class AtCorder
 {
   static void Main(string[] args)
   {
     string input = Console.ReadLine();
     string result = Calc(int.Parse(input));
     Console.WriteLine(result);
   }
   
  public static string Calc(int number)
  {
    if(number < 4)
      return "No";
    
    int num = number/4;
    
    for(int i=num; i>=0; i--)
    {
      int result = number - i*4;
      if(result == 0)
        return "Yes";
      
      result = result % 7;
      
      if(result == 0)
        return "Yes";
    }
    
    return "No";
  }
}

Measured memory_bytes: 13140
#include <iostream>

#define modulo 1e9 + 7
using namespace std;

int noOfWays(char **arr, int n, int m){
    if(arr[0][0]=='#'){
        return 0;
    }
    if(arr[n-1][m-1]=='#'){
        return 0;
    }
    int dp[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j] = 0;
        }
    }
    for(int i=0;i<n;i++){
        if(arr[i][0]=='#'){
            break;
        }
        dp[i][0] = 1;
    }
    for(int j=0;j<n;j++){
        if(arr[0][j]=='#'){
            break;
        }
        dp[0][j] = 1;
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(arr[i][j]!='#'){
                dp[i][j] = (dp[i-1][j]%1000000007 + dp[i][j-1]%1000000007)%1000000007;
            }
        }
    }

    return dp[n-1][m-1]%1000000007;
}

int main() {
    int n,m;
    cin >> n >> m;
    char **arr = new char*[n];
    for(int i=0;i<n;i++){
        arr[i] = new char[m];
        for(int j=0;j<m;j++){
            cin >> arr[i][j];
        }
    }

    cout << noOfWays(arr, n, m) << endl;
}


Measured memory_bytes: 8436
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){

    string s;
    cin>>s;
    int sn=0;
    
    for(int i=0;i<s.size();i++){
        char l=s[i];
        sn+=atoi(&l);
    }
    
    int n=atoi(s.c_str());
    //cout<<sn<<' '<<n<<endl;
    cout<<((n%sn)?"No":"Yes")<<endl;
    

return 0;
}


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

int search(int A[], int n, int key) {
  int i = 0;
  A[n] = key;
  while (A[i] != key) i++;
  return i != n;
}

int main() {
  int n, A[10000+1], q, key, sum = 0;

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

  cin >> q;

  for (int i = 0; i < q; i++) {
    scanf("%d", &key);
    if ( search(A, n, key) ) sum++;
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 3208
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int N;

long long int x[100005], y[100005];

vector<pair<long long int, int> > VX, VY;

int check[100005];

vector<int> Adj[100005];
vector<long long int> d[100005];

set<pair<long long int, int> > S;
long long int dis[100005];

int main(void) {

	cin >> N;

	long long int tmp;
	for (int i = 1; i <= N; i++) {
		cin >> tmp; x[i] = tmp;
		cin >> tmp; y[i] = tmp;
	}

	//========================= X
	VX.push_back(pair<long long int, int>(-10000000004, -111));
	for (int i = 1; i <= N; i++) {
		VX.push_back(pair<long long int, int>(x[i], i));
	}
	sort(VX.begin(), VX.end());
	for (int i = 1; i <= N - 1; i++) {
		long long int distance = VX[i + 1].first - VX[i].first;
		int u = VX[i + 1].second;
		int v = VX[i].second;
		Adj[u].push_back(v);   d[u].push_back(distance);
		Adj[v].push_back(u);   d[v].push_back(distance);
	}

	//=============================== Y
	VY.push_back(pair<long long int, int>(-10000000004, -111));
	for (int i = 1; i <= N; i++) {
		VY.push_back(pair<long long int, int>(y[i], i));
	}
	sort(VY.begin(), VY.end());
	for (int i = 1; i <= N - 1; i++) {
		long long int distance = VY[i + 1].first - VY[i].first;
		int u = VY[i + 1].second;
		int v = VY[i].second;
		Adj[u].push_back(v); d[u].push_back(distance);
		Adj[v].push_back(u); d[v].push_back(distance);
	}

	//===============================

	/*for (int u = 1; u <= N; u++) {
		for (int v = 1; v <= N; v++) {
			cout << "d[" << u << "][" << v << "]= " << d[u][v] << endl;
		}
	}*/

	for (int i = 1; i <= N; i++) { dis[i] = 10000000003; }
	long long int ans = 0;
	dis[1] = 0; 
	S.insert(pair<long long int, int>(dis[1], 1));

	while (S.size()) {
		auto it = S.begin();
		long long int distance = (*it).first;
		int K = (*it).second;
		S.erase(*(it));
		if (check[K] == 1) { continue; }
		ans += distance;
		check[K] = 1;

		//cout << "K= " << K << " distance= " <<distance<<endl;
		
		for (int i = 0; i < (int) Adj[K].size(); i++) {
			int H = Adj[K][i];
			if (check[H] == 1) { continue; }
			S.erase(pair<long long int, int>(dis[H], H));
			if (dis[H] > d[K][i]) { dis[H] = d[K][i]; }
			S.insert(pair<long long int, int>(dis[H], H));
		}
		//cout << "ans= " << ans << endl;
	};

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 24688
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
const double PI = 3.1415926535897932;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}


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

	cout << r * r << endl;
	return 0;
}


Measured memory_bytes: 3608
"use strict";
    function Main(input) {
        let cin = new Inputer(input);
        let N = cin.getInt();
        let S = new Array(N + 1);
        S[0] = 0;
        for (let i = 1; i <= N; i++) {
            S[i] = S[i - 1] + cin.getInt();
        }
        let ans = Number.MAX_SAFE_INTEGER;
        let l = 1, r = 3;
        for (let i = 2; i <= N - 2; i++) {
            while (Math.abs(S[l] - (S[i] - S[l])) > Math.abs(S[l + 1] - (S[i] - S[l + 1]))) l++;
            while (Math.abs(S[N] - S[r] - S[r] + S[i]) > Math.abs(S[N] - S[r + 1] - S[r + 1] + S[i])) r++;
            let max = Math.max(...[S[l], S[i] - S[l], S[r] - S[i], S[N] - S[r]]);
            let min = Math.min(...[S[l], S[i] - S[l], S[r] - S[i], S[N] - S[r]]);
            ans = Math.min(ans, Math.abs(max - min));
        }
        console.log(ans);
    }
class Inputer{constructor(t){if(typeof t=='undefined')throw new Error('引数（stdin）を省略できません！');this.cnt=0;this.items=t.split(/\n|\s/)}getInt(){return this.items[this.cnt++]-0}getIntArray(t){if(typeof t=='undefined')throw new Error('引数（1以上）を省略できません！');if(t<1)throw new Error('引数は1以上であること！');let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getInt();return r}getStr(){return this.items[this.cnt++]}getStrArray(t){if(typeof t=='undefined')throw new Error('引数（1以上）を省略できません！');if(t<1)throw new Error('引数は1以上であること！');let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getStr();return r}}
if (typeof window == "undefined") Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 56344
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    string ans = "";
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'B') {
            if (ans.length() > 0) {
                ans.erase(ans.length() - 1 , 1);
            }
        }
        else {
            ans += s[i];
        }
    }
    cout << ans << endl;
}

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

using namespace std;



int main(){

	int n,d; cin >> n>> d; //d次元、ｎ個の点
	vector<vector <int>> A(n,vector<int>(d));
	for(int i = 0 ; i < n ; i++){
		for ( int k = 0 ; k < d ; k ++){
			cin >>A.at(i).at(k);
		}
	//	cout<<"ここからが実行結果"<<endl;
	}
	int ans=0;//disが整数となるとき1ずつ増やす
//	int DIS=0;//DISは距離の二乗（ルートついてない形）
	double dis=0;//disは距離、DISにルートはっつけたやつ
	for(int i = 0 ;i<n;i++){
				int b =0;
		for(int k=0 ;i+k<n;k++){
			int a,c;//k=0 ha mawasanai
			for(int m = 0 ; m<d; m++){
				 if(i!=i+k){
		//		cout<<A.at(i).at(m)<<" "<<A.at(i+k).at(m)<<"sozai"<<endl;
				 a =  (A.at(i).at(m))-(A.at(i+k).at(m)); //距離の素、こいつを二乗したやつを足し合わせたのがDIS
			//	 cout<<"a:"<<a<<endl;
				//ここにaの2乗をしたものを作らないといけない、それの名前はcにする。
				c = pow(a, 2.0);
			//	cout<<"c:"<<c<<endl;
				b+= c;
				//cout<<"b:(disの2乗)"<<b<<endl;
				if(m == d-1){// disは要らんくなったな。bがdisだ。つまり、bを2分の1乗すればdisが出る。disが整数かどうかの判定結果でansを動かす。
					dis = pow(b,0.5);
				//	cout<<"distance:"<<dis<<endl;
					int B=dis/1;
					if(B==dis){
						//disが整数なのでインクリメント
						ans++;
					}
					}
				}
			}
				b=0;
			}

	}

			cout << ans << endl;

}





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

int N,Q,EBY,WY,q; string EN,now;
map<string,pair<int,int>> calendar;
map<int,string> era;
set<int> years;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> N >> Q,N){
        calendar.clear(); era.clear(); years.clear();
        for (int i=0;i<N;++i){
            cin >> EN >> EBY >> WY;
            if (calendar.count(EN)) calendar[EN].second=max(calendar[EN].second,WY);
            else calendar[EN]={WY-EBY+1,WY};
        }
        for (auto p:calendar){
            era[p.second.second]=p.first;
            years.insert(p.second.second);
        }
        for (;Q--;){
            cin >> q;
            auto itr=years.lower_bound(q);
            if (itr==years.end()){
                cout << "Unknown" << '\n';
                continue;
            }
            now=era[*itr];
            if (q<calendar[now].first) cout << "Unknown" << '\n';
            else cout << now << ' ' << q-calendar[now].first+1 << '\n';
        }
    }
}


Measured memory_bytes: 3428
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using Int = long long int;
const Int INF = 1LL << 30;

Int N, A, B;
vector<Int> H;

int main() {
    scanf("%lld%lld%lld", &N, &A, &B);
    H.resize(N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &H[i]);
    }

    Int dam = A - B;
    Int ub = INF, lb = -1;
    while(ub - lb > 1) {
        Int mid = (ub + lb) / 2;

        Int sum = 0;
        for(int i=0; i<N; i++) {
            Int h = max(0LL, H[i] - B * mid);
            sum += (h + dam - 1) / dam;
        }
        
        if(sum > mid) lb = mid;
        else ub = mid;
    }

    printf("%lld\n", ub);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PI 				acos(-1)
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define sz(a)			a.size()
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define MOD1			998244353
#define fore(i, b, e)	for(int i = b; i < e; i++)
#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
using namespace __gnu_pbds;

typedef long long 		ll;
typedef unsigned long long 		ull;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//find_by_order kth largest  order_of_key <
const int tam = 100010;
const int MOD = 1e9+7;
const double EPS = 1e-9;
int parent[100010];
int find(int n)
{
	if(parent[n] == -1) return n;
	return parent[n] = find(parent[n]);
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//freopen("qwe.txt", "r", stdin);
	//freopen("asd.txt", "w", stdout);
	int n, m;
	cin>>n>>m;
	int ar[n];
	fore(i, 0, n){cin>>ar[i]; ar[i]--;}
	int a, b;
	mem(parent, -1);
	while(m--)
	{
		cin>>a>>b;
		a--;b--;
		a = find(a);
		b = find(b);
		if(a != b)
		{
			parent[a] = b;
		}
	}
	int res = 0;
	fore(i, 0, n)
	{
		if(find(i) == find(ar[i]))
		{
			res++;
		}
	}
	cout<<res<<'\n';
	return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS2

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,n) for(i=1;i<=n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define fast ios_base:: sync_with_stdio( false ); cin.tie(0); cout.tie(0);
#define eb              emplace_back
#define em              emplace
#define pb              push_back
#define Mp              make_pair
#define ff              first
#define ss              second
#define mod 1000000007
const double pi = 3.14159265358979323846;
typedef long long ll;
using namespace std;

const int M = (int)(2e6 + 239);

int getnum(string a)
{
    int i,p=0;
    rep0(i,a.size())
    {
        p*=10;
        p+=a[i]-'0';
    }
    return p;
}

int main()
{
    fast

    double a,b,c,d=0;
    cin>>a>>b;
    vector<double>v;
    for(int i=0; i<a; i++)
    {
        cin>>c;
        v.push_back(c);
        d+=c;
    }
    sort(v.begin(),v.end(),greater<double>());
    bool flag=false;
    for(int i=0; i<b; i++)
    {
        double temp=v[i]/d;
        //cout<<temp<<endl;
        if(temp<(1/(4*b)))
        {
            flag=true;
            break;
        }
    }
    if(flag)
    {
        cout<<"No"<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
    }
}


Measured memory_bytes: 256
import sys

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if (a == b):
    print('YES')
    sys.exit(0)
if (v <= w):
    print('NO')
    sys.exit(0)
res = abs(a - b) / (v - w)
if (res > t):
    print('NO')
else:
    print('YES')
sys.exit(0)



Measured memory_bytes: 9164
#include <cstdio>
 #include <cstdlib>
 #include <iostream>
 #include <fstream>
 #include <sstream>
 #include <set>
 #include <map>
 #include <vector>
 #include <list>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 #include <string>
 #include <stack>
 #include <queue>
 #include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
 #include <cassert>
 #include <iomanip>        //do setprecision
 #include <ctime>
 #include <complex>
 using namespace std;

 #define FOR(i,b,e) for(int i=(b);i<(e);++i)
 #define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
 #define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
 #define REP(x, n) for(int x = 0; x < (n); ++x)

 #define ST first
 #define ND second
 #define PB push_back
 #define PF push_front
 #define MP make_pair
 #define LL long long
 #define ULL unsigned LL
 #define LD long double
 #define pii pair<int,int>
 #define pll pair<LL,LL>

 const double pi = 3.14159265358979323846264;
 const int mod=1000000007;

int main(){
	int n,a[111]={};
	LL sum=0;
	cin>>n;
	FOR(i,0,n){
		cin>>a[i];
		sum+=a[i];
		a[i]*=n;
	}
	int ans=0,best=mod;
	FOR(i,0,n){
		if(abs(sum-a[i])<best){
			best=abs(sum-a[i]);
			ans=i;
		}
	}
	cout<<ans<<endl;
	 return 0;
}


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

#include <limits.h>

using namespace std;

typedef long long ll;

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;
}

const int INF = INT_MAX / 2;
// {diff_y, diff_x} of up, right, down, and left
const vector<pair<int, int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

vector<vector<char>> board;
vector<vector<int>> dist;

void dfs(const int cur_h, const int cur_w, const int cur_d) {
    dist[cur_h][cur_w] = cur_d;

    for (auto dir : dirs) {
        const int next_h = cur_h + dir.first;
        const int next_w = cur_w + dir.second;
        if (board[next_h][next_w] != '#' && dist[next_h][next_w] > cur_d + 1) {
            dfs(next_h, next_w, cur_d + 1);
        }
    }
}

int main(void) {
    int H, W;
    cin >> H >> W;

    int n_black = 0;

    board.resize(H + 2, vector<char>(W + 2, '#'));
    for (int h = 1; h <= H; h++) {
        for (int w = 1; w <= W; w++) {
            cin >> board[h][w];
            if (board[h][w] == '#') {
                n_black++;
            }
        }
    }

    dist.resize(H + 2, vector<int>(W + 2, INF));
    dfs(1, 1, 0);

    // for (int h = 1; h <= H; h++) {
    //     for (int w = 1; w <= W; w++) {
    //         cout << dist[h][w] << " ";
    //     }
    //     cout << endl;
    // }

    if (dist[H][W] != INF) {
        cout << H * W - n_black - (dist[H][W] + 1) << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3684
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

template <typename T>
bool is_prime(T N){
    T n = N;
    for(ll i = 2; i*i <= N; i++){
        if(N%i == 0){
            while(N%i == 0){
                N /= i;
            }
        }
    }
    if (N == n) return true;
    else return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int X;
    cin >> X;
    for(int i = X;  ;i++){
        if(is_prime<ll>(i)) {
            cout << i << 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;
using ll = long long;
using pii = pair<int, int>;

const int N_MAX = 200005;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v(N_MAX);
	rep(i, n) {
		int a;
		cin >> a;
		a--;
		v[a]++;
	}
	sort(v.begin(), v.end(), greater<int>());
	int cnt = 0;
	rep(i, k) cnt += v[i];
	cout << n - cnt << endl;
	return 0;
}

Measured memory_bytes: 4024
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int lli;

const lli inf = 1000000000;

lli cst[101][101];
int n;

lli dij(int s, int t)
{
  lli d[101];
  bool vis[101];

  fill(vis, vis+(n+1), false);
  fill(d, d+(n+1), inf);
  d[s] = 0;

  while(1){
    int v = -1;
    for(int i = 1; i <= n; ++i)
      if(!vis[i] && (v == -1 || d[i] < d[v])) v = i;

    if(v == -1) break;

    vis[v] = true;
    for(int i = 1; i <= n; ++i)
      d[i] = min(d[i], d[v]+cst[v][i]);
  }

  return d[t];
}

int main()
{
  int s, t, u, m;

  while(cin>>n>>m && n+m){
    fill(&cst[0][0], &cst[n+1][0], inf);
    for(int i = 1; i <= n; ++i) cst[i][i] = 0;

    while(m--){
      cin >> s;
      if(s){
	cin >> s >> t >> u;
	if(cst[s][t] > u)
	  cst[s][t] = cst[t][s] = u;
      } else {
	cin >> s >> t;
	u = dij(s, t);
	cout << ((u >= inf)? -1: u) << endl;
      }
    }
  }

  return 0;
}

Measured memory_bytes: 948
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long u,v,x,y,op=0;
	cin>>x>>y;
	u=abs(x);
	v=abs(y);
	op+=abs(v-u);
	if(x==y){
		cout<<0<<endl;
		return 0;
	}
	if(y>0&&x==0) cout<<op<<endl;
	else if(y==0&&x>0) cout<<op+1<<endl;
	else if(x==0&&y<0) cout<<op+1<<endl;
	else if(y==0&&x<0) cout<<op<<endl;
	else if((x<0&&y>0)||(x>0&&y<0)){
		cout<<op+1<<endl;
	}
	else if(x<=0&&y<=0){
		if(x>y)
		cout<<op+2<<endl;
		else if(x<y) cout<<op<<endl;
	}
	else if(x>=0&&y>=0){
		if(x>y){
			op=x+y;
			cout<<op<<endl;
		}
		else if(x<y) cout<<op<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
a,b=map(int,input().split())
count=0
for i in range(a,b+1):
  i=str(i)
  j=-1
  k=0
  while i[k]==i[j]:
    k+=1
    j-=1
    if k==(len(i)//2)+1:
      count+=1
      break
print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <complex>

using namespace std;
typedef long long ll;


typedef complex<double> xy_t;
double dot_product(xy_t a, xy_t b) { return (conj(a)*b).real(); }
double cross_product(xy_t a, xy_t b) { return (conj(a)*b).imag(); }

typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする

vector<int> G[100005];
std::vector<P> tree[100010];

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

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define re(i,a,b) for(i=a;i<=b;i++)
#define pb push_back
#define lb lower_bound
#define ub upper_bound

ll i,j,k,ii,jj;
ll n,m,sum,num;
ll ans=0;
ll a,b,c,d,e,h,w;
ll x[500005],y[100005],z[100005];
char s[100005],t[100005];
vector <ll> aa,bb;
bool ok=false;
bool check[100005];

int main(){
    cin>>s>>t;
    n=strlen(s);
    m=strlen(t);
    for(i=n-m;i>=0;i--){
        bool dame=false;
        for(j=0;j<m;j++){
            if(s[i+j]!=t[j] && s[i+j]!='?'){
                dame=true;
            }
        }
        if(!dame){
            //p(i);
            for(j=0;j<n;j++){
                if(s[j]!='?'){
                    cout<<s[j];
                }else if(i<=j && j<=i+m-1){
                    //p("ei!");
                    cout<<t[j-i];
                }else{
                    //p("oi!");
                    cout<<"a";
                }
            }
            el;
            return 0;
        }
    }
    p("UNRESTORABLE");
    
    return 0;
}



Measured memory_bytes: 6656
#include <stdio.h>
int main() {
	int n,i,w=0,b=0,min;
	char s[200001];
	scanf("%d %s",&n,s);
	for(i=0;i<n;i++){if(s[i]=='.')w++;}
	min=w;
	for(i=0;i<n;i++){
		if(s[i]=='#'){b++;}
		else{w--;}
		if(b+w<=min){min=b+w;}	}
	printf("%d",min);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

ll h, w;
VS s;

int main(){
    cin >> h >> w;
    s.resize(h);
    rep(i, 0, h) cin >> s[i];
    ll num = 0;
    rep(i, 0, h) {
        rep(j, 0, w){
            if(s[i][j] == '.') num++;
        }
    }
    num -= 2;
    vector<vector<ll>> d(h, vector<ll>(w,1e18));
    /* dijkstra's scope */{
        typedef pair<ll, pair<ll,ll>> pl;
        priority_queue<pl, vector<pl>, greater<pl>> que;
        que.push({0, {0, 0}});
        d[0][0] = 0;
        while(!que.empty()){
            auto q = que.top();
            que.pop();
            auto i = q.second.first;
            auto j = q.second.second;
            if(q.first > d[i][j]) continue;
            rep(g, 0, 4){
                auto ni = i + d1[g];
                auto nj = j + d2[g];
                if(ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
                if(s[ni][nj] == '#') continue;
                if(d[ni][nj] <= q.first + 1) continue;
                d[ni][nj] = q.first + 1;
                que.push({d[ni][nj], {ni, nj}});
            }
        }
    }
    if(d[h-1][w-1] != 1e18) cout << num - d[h-1][w-1] + 1 << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3616
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<bitset>
#include<stack>

#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 llong long long
#define pb(a) push_back(a)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> lltpl;

int dy8[8] = { 2,2,-2,-2,1,1,-1,-1 };
int dx8[8] = { 1,-1,1,-1,2,-2,2,-2 };
int dx4[4] = { 1,0,0,-1 };
int dy4[4] = { 0,1,-1,0 };


/******************************************************************************************/


const int IINF = 1e9 + 7;
const ll LINF = LLONG_MAX;
constexpr ll MOD = 1e9 + 7;



template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}

// vector
template <typename T>
istream& operator>>(istream & is, vector<T> & vec) { for (T& x : vec) is >> x; return is; }
// pair
template <typename T, typename U>ostream& operator<<(ostream & os, pair<T, U> & pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; }
// vector
template <typename T>ostream& operator<<(ostream & os, const vector<T> & vec) { os << "{";	for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); }os << "}"; return os; }
// map
template <typename T, typename U>ostream& operator<<(ostream & os, map<T, U> & map_var) { os << "{";	repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; }os << "}"; return os; }
// set
template <typename T>ostream& operator<<(ostream & os, set<T> & set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; }os << "}"; return os; }


int dp[50];

int main() {

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

	dp[0] = 1;

	for (int i = 0; i <= 30; i++)
	{
		dp[i + 1] += dp[i];
		dp[i + 2] += dp[i];
		dp[i + 3] += dp[i];
	}


	while (cin >> n, n) {

		cout << ceil((dp[n]/(double)10) / (double)365) << endl;

	}





	return 0;
}



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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	int N; cin >> N;
	vector<int> a(N + 1);
	for(int i = 1; i <= N; i++) cin >> a[i];
	set<int> b;
	for(int i = N; i > 0; i--) {
		int sum = 0;
		for(int j = i + i; j <= N; j += i) {
			if(b.count(j)) sum++;
		}
		if(sum % 2 != a[i]) b.insert(i);
	}
	int M = b.size();
	int cnt = 0;
	cout << M << endl;
	for(auto p: b) {
		cnt++;
		if(cnt == b.size()) {
			cout << p << endl;
			return 0;
		}
		cout << p << " ";
	}
}

Measured memory_bytes: 9564
main = do
  [w, h, x, y] <- map read . words <$> getLine :: IO [Int]
  putStr . show $ fromIntegral w * (fromIntegral h) / 2
  putStr " "
  putStrLn $ if (even w && x == w `div` 2) &&
                (even h && y == h `div` 2)
             then "1"
             else "0"


Measured memory_bytes: 508
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n;
    cin >> n;
    vector<char> a(n);
    rep(i, n) cin >> a[i];
    auto f = [&] (char a, char b) {
        if(a == 'T' && b == 'F') return 'F';
        else return 'T';
    };
    char x = a[0];
    REP(i, 1, n) x = f(x, a[i]);
    cout << x << endl;
    return 0;
}


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

const int N = 100000 + 10;

int n, m, t, x[N], y[N], d[N];

int main() {
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &d[i]), d[i] = (d[i] == 1 ? 1 : -1);
  for (int i = 0; i < n; ++i) y[i] = ((x[i] + d[i] * t) % m + m) % m;
  int k = 0;
  for (int i = 0; i < n; ++i) if (d[i] > 0) k = (k + (x[i] + t) / m) % n; else k = (k - (m - x[i] - 1 + t) / m) % n;
  std::sort(y, y + n);
  k = (k + n) % n;
  std::rotate(y, y + k, y + n);
  for (int i = 0; i < n; ++i) printf("%d\n", y[i]);
  return 0;
}


Measured memory_bytes: 2304
s=input()
qq=int(input())
re=0
l=''
r=''
f=1
for _ in range(qq):
  q=list(input().split())
  if len(q)==1:
    re+=1
    if f:
      f=0
    else:
      f=1
  else:
    t=q[2]
    if f:
      if q[1]=='1':
        l+=t
      else:
        r+=t
    else:
      if q[1]=='1':
        r+=t
      else:
        l+=t
if re%2==0:
  print(l[::-1]+s+r)
else:
  print(r[::-1]+s[::-1]+l)

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

namespace _1_4_C {
    class Program {
        static void Main(string[] args) {
            while (true) {
                var input = Console.ReadLine().Split(' ');

                if (input[1] == "?")
                    break;

                var nums = new int[] {
                int.Parse(input[0]),
                int.Parse(input[2])
                };

                Console.WriteLine(OperationCalculator(nums[0], nums[1], input[1]));
            }
        }

        static int OperationCalculator(int rhs, int lhs, string op) {
            if (op == "+")
                return rhs + lhs;
            if (op == "-")
                return rhs - lhs;
            if (op == "*")
                return rhs * lhs;
            if (op == "/")
                return rhs / lhs;
            return 0;
        }
    }
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9

using namespace std;
typedef long long ll;

int main(void) {
  int N;
  cin >> N;
  int N1 = N % 10;
  if (N1 == 2 || N1 == 4 || N1 == 5 || N1 == 7 || N1 == 9) {
    cout << "hon" << endl;
  }
  else if (N1 == 0 || N1 == 1 || N1 == 6 || N1 == 8) {
    cout << "pon" << endl;
  }
  else {
    cout << "bon" << endl;
  }
  return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct SuffixArray{
  string s;
  vector<int> sa,rev;

  SuffixArray(){}
  SuffixArray(const string &S):s(S){
    int n=s.size();
    s.push_back('$');
    sa.resize(n+1);
    iota(sa.begin(),sa.end(),0);
    sort(sa.begin(),sa.end(),
         [&](int a,int b){
           if(s[a]==s[b]) return a>b;
           return s[a]<s[b];
         });
    vector<int> c(n+1,0),r(n+1),cnt(n+1);
    for(int i=0;i<=n;i++) r[i]=s[i];
    for(int len=1;len<=n;len*=2){
      for(int i=0;i<=n;i++){
        c[sa[i]]=i;
        if(i>0 &&
           r[sa[i-1]]==r[sa[i]] &&
           sa[i-1]+len<=n &&
           r[sa[i-1]+len/2]==r[sa[i]+len/2]) c[sa[i]]=c[sa[i-1]];
      }
      iota(cnt.begin(),cnt.end(),0);
      copy(sa.begin(),sa.end(),r.begin());
      for(int i=0;i<=n;i++){
        int s1=r[i]-len;
        if(s1>=0) sa[cnt[c[s1]]++]=s1;
      }
      c.swap(r);
    }
    rev.resize(n+1);
    for(int i=0;i<=n;i++) rev[sa[i]]=i;
  }
  int operator[](int i) const{return sa[i];}

  bool lt_substr(string &t,int si,int ti){
    int sn=s.size(),tn=t.size();
    while(si<sn&&ti<tn){
      if(s[si]<t[ti]) return 1;
      if(s[si]>t[ti]) return 0;
      si++;ti++;
    }
    return si==sn&&ti<tn;
  }

  int lower_bound(string& t){
    int l=0,r=s.size();
    while(l+1<r){
      int m=(l+r)>>1;
      if(lt_substr(t,sa[m],0)) l=m;
      else r=m;
    }
    return r;
  }

  int upper_bound(string& t){
    t.back()++;
    int res=lower_bound(t);
    t.back()--;
    return res;
  }

  // O(|T|*log|S|)
  int count(string& T){
    return upper_bound(T)-lower_bound(T);
  }
};

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  string t;
  cin>>t;
  int q;
  cin>>q;
  SuffixArray sa(t);
  while(q--){
    string p;
    cin>>p;
    cout<<!!sa.count(p)<<"\n";
  }
  cout<<flush;
  return 0;
}



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

#define INF 1LL << 30
typedef long long ll;

int A, B, K;

int main() {
  cin >> A >> B >> K;
  int cnt = 0;
  for (int i=100;i>0;i--){
    if (A%i==0 && B%i==0){
      cnt++;
      if (cnt == K){
        cout << i << endl;
      }
    }
  }
  
}



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

int main()
{
	unsigned long long int n;

	char s[26];

	int i;
	for(i=0;i<26;i++)
	{
		s[i]=i+'a';
	}

	cin>>n;

	string s1;

	while(n>0)
	{
		if(n%26==0)
		{s1+='z';n-=1;}
		else
		s1+=s[(n%26)-1];
		n=n/26;
	}

	int k=s1.length();


	for(i=k-1;i>=0;i--)
		cout<<s1[i];


}


Measured memory_bytes: 3640