akhauriyash/Code-Regression huggingface dataset:
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		n: usize,
		m: usize,
		ab: [(usize, usize); m],
	}


	let mut gnext = vec![0usize; n];	// 人xが所属する現在グループのリンク
	for i in 0..n {
		gnext[i] = i;
	}

	let mut gnum = vec![1usize; n];	// 人xが所属する現在グループのリンク

	for i in 0..m {
		let mut ga = ab[i].0-1;
		loop {
			if gnext[ga] == ga {
				break;
			}
			ga = gnext[ga];
		}
		gnext[ab[i].0-1] = ga;
		let mut gb = ab[i].1-1;
		loop {
			if gnext[gb] == gb {
				break;
			}
			gb = gnext[gb];
		}
		gnext[ab[i].1-1] = gb;
		if ga == gb {
			continue;
		}
		gnext[gb] = ga;
		gnum[ga] += gnum[gb];
		gnum[gb] = 0;
	}

	let mut ans = 0;
	for i in 0..n {
		ans = max(ans, gnum[i]);
	}
	println!("{}", ans);
}



Measured memory_bytes: 10772
n=int(input())
a=list(map(int,input().split()))
dic={}
current=0
dic[0]=1
for i in range(n):
  current+=a[i]
  if current in dic:
    dic[current]+=1
  else:
    dic[current]=1
ans=0
for i in dic:
  ans+=(dic[i]*(dic[i]-1))//2
print(ans)

Measured memory_bytes: 124264
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000];
int main(){
	int n;
	while(true){
		cin>>n;
		if(!n)break;
		for(int i=0;i<n;i++)cin>>a[i];
		sort(a,a+n);
		int ret=1145141919;
		for(int i=0;i<n-1;i++)ret=min(ret,a[i+1]-a[i]);
		cout<<ret<<endl;
	}
	return 0;
}

Measured memory_bytes: 3132
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
   int a, b;
   cin >> a >> b;
   if(a >= b){
       for(int i = 1; i <= a; i++){
           cout << b;
       }
   } else {
       for(int i = 1; i <= b; i++){
           cout << a;
       }
   }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x, y;
  cin >> x >> y;
 
  if (x % 2 == 0 || y % 2 == 0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}


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

P = list(input().split())
stack = []

for c in P:
    if c in('+', '-', '*'):
        right = stack.pop()
        left = stack.pop()
        stack.append(str(eval(' '.join([left, c, right]))))
    else:
        stack.append(c)

print(stack.pop())



Measured memory_bytes: 5572
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <string.h>
#include <numeric>
using namespace std;

#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(i,v) for(auto &(i):(v))
#define eachr(i,v) for(auto &(i)=(v).rbegin();(i)!=(v).rend();(i)++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define endl "\n"

//typedef complex<double> P;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}
bool deq(double a,double b) {return abs(a-b)<eps;}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;



// AGC、GAC、ACGは含んではいけない
// A?GC、AG?Cもだめ
// 最後3文字だけ記憶しとけば十分 4^4 * 100
// TAGC - 0123

int n, dp[111][4][4][4], res;

signed main() {
	cin >> n;
	dp[0][0][0][0] = 1;
	rep(i,n) rep(a,4) rep(b,4) rep(c,4) if (dp[i][a][b][c]) rep(j,4) {
		if (b==1 && c==2 && j==3) continue;
		if (b==2 && c==1 && j==3) continue;
		if (b==1 && c==3 && j==2) continue;
		if (a==1 && c==2 && j==3) continue;
		if (a==1 && b==2 && j==3) continue;
		(dp[i+1][b][c][j] += dp[i][a][b][c]) %= mod;
	}
	rep(a,4) rep(b,4) rep(c,4) (res += dp[n][a][b][c]) %= mod;
	cout << res << endl;
}

Measured memory_bytes: 256
S = input()

zyouken1 = S[0:(len(S)-1)//2]
zyouken2 =S[(len(S)+2)//2:len(S)]


if (S == S[::-1]) and  (zyouken1 == zyouken1[::-1]) and (zyouken2 == zyouken2[::-1]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int sum = 0;
		for (int i = 0 ; i<n ; i++ ) {
			int num = Integer.parseInt(br.readLine());
			if ( num == 2 || num == 3) {
				sum++;
				continue;
			}
			double nd = (double) num;
			nd = Math.sqrt(nd);
			int a = (int) nd;
			if ( num % 2 == 1) {
				for (int j = 2; j<=a ; j++ ) {
					if ( num%j == 0 ) {
						break;
					}else if( j == a){
						sum++;
					}

				}
			}
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 27608
#include <iostream>
#include <string>
#include <algorithm>
  
using namespace std;
  
string s;
string s1 = " ',.!?";
string s2 = " abcABC";
string s3 = " defDEF";
string s4 = " ghiGHI";
string s5 = " jklJKL";
string s6 = " mnoMNO";
string s7 = " pqrsPQRS";
string s8 = " tuvTUV";
string s9 = " wxyzWXYZ";
  
int main(void){
  
  while( cin >> s ){
  
    int cnt = 0;
  
    for( int i = 0 ; i < s.size() ; i++ ){
      if( s[i] == '1' ){
    for( int j = i ; s[j] == '1' ; j++ , i++ ) cnt++;
    cout << s1[cnt];
    i--;
      }
      else if( s[i] == '2' ){
    for( int j = i ; s[j] == '2' ; j++ , i++ ) cnt++;
    cout << s2[cnt];
    i--;
      }
      else if( s[i] == '3' ){
    for( int j = i ; s[j] == '3' ; j++ , i++ ) cnt++;
    cout << s3[cnt];
    i--;
      }
      else if( s[i] == '4' ){
    for( int j = i ; s[j] == '4' ; j++ , i++ ) cnt++;
    cout << s4[cnt];
    i--;
      }
      else if( s[i] == '5' ){
    for( int j = i ; s[j] == '5'; j++ , i++ ) cnt++;
    cout << s5[cnt];
    i--;
      }
      else if( s[i] == '6' ){
    for( int j = i ; s[j] == '6'; j++ , i++ ) cnt++;
    cout << s6[cnt];
    i--;
      }
      else if( s[i] == '7' ){
    for( int j = i ; s[j] == '7' ; j++ , i++ ) cnt++;
    cout << s7[cnt];
    i--;
      }
      else if( s[i] == '8' ){
    for( int j = i ; s[j] == '8' ; j++ , i++ ) cnt++;
    cout << s8[cnt];
    i--;
      }
      else if( s[i] == '9' ){
    for( int j = i ; s[j] == '9' ; j++ , i++ ) cnt++;
    cout << s9[cnt];
    i--;
      }
      else if( s[i] == '0' && s[i + 1] == '0' && s[i + 2] == '0' ){
    cout << "  ";
    i += 2;
      }
      else if( s[i] == '0' && s[i + 1] == '0' ){
    cout << " ";
    i++;
      }
      cnt = 0;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1192
#include<string>
#include<iostream>
using namespace std;
int main(){
  string text,pattern;
  cin>>text>>pattern;
  int t=text.length();
   int p=pattern.length();
   int max=p,count,temp;
  for(int i=0;i<=t-p;i++){//
    temp=i;
    count=0;
    if(text.substr(i,i+p-1)==pattern){
      max=0;
      break;
    }
    else{
      for(int j=0;j<p;j++){
        if(text[temp++]!=pattern[j]){
          count++;
        }
      }
    if(count<=max)
      max=count;
    }
  }
 cout<<max;
  return 0;
}   

Measured memory_bytes: 3624
import sys
n = int(input())
p = list(map(int, input().split()))

count = 0
for i in range(n-2):
    if p[i] < p[i+1] and p[i+1] < p[i+2]:
        count += 1
    elif p[i] > p[i+1] and p[i+1] > p[i+2]:
        count += 1

print(count)







                                        




    




        


    







        



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,n,arr[1000],arr1[1000],c1,c2;
    cin>>n;
    c1=c2=0;
    for(i=0; i<n; i++)
    {
        cin>>arr[i];
        if(arr[i]%2==0)
        {
            arr1[c1]=arr[i];
            c1++;
        }
    }

    for(i=0; i<c1; i++)
    {
        if(arr1[i]%3==0||arr1[i]%5==0)
        {
            c2++;
        }
    }

    if(c1==c2)
    {
        printf("APPROVED");
    }
    else
    {
        printf("DENIED");
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 256
n=int(input())
s=list(input())
ans=[[0]*n for i in range(4)]
ans[1][1]=1
ans[2][0]=1
ans[3][0]=ans[3][1]=1
idx=-1
for i in range(4):
  for j in range(1,n-1):
    if s[j]=='o' and ans[i][j]==1 and ans[i][j-1]==1:
      ans[i][j+1]=1
    elif s[j]=='o' and ans[i][j]==1 and ans[i][j-1]==0:
      ans[i][j+1]=0
    elif s[j]=='o' and ans[i][j]==0 and ans[i][j-1]==1:
      ans[i][j+1]=0
    elif s[j]=='o' and ans[i][j]==0 and ans[i][j-1]==0:
      ans[i][j+1]=1
    elif s[j]=='x' and ans[i][j]==1 and ans[i][j-1]==1:
      ans[i][j+1]=0
    elif s[j]=='x' and ans[i][j]==1 and ans[i][j-1]==0:
      ans[i][j+1]=1
    elif s[j]=='x' and ans[i][j]==0 and ans[i][j-1]==1:
      ans[i][j+1]=1
    else:
      ans[i][j+1]=0
  flag1=False
  flag2=False
  if ans[i][n-1]==1 and ans[i][0]==ans[i][n-2] and s[n-1]=='o':
    flag1=True
  elif ans[i][n-1]==1 and ans[i][0]!=ans[i][n-2] and s[n-1]=='x':
    flag1=True
  elif ans[i][n-1]==0 and ans[i][0]==ans[i][n-2] and s[n-1]=='x':
    flag1=True
  elif ans[i][n-1]==0 and ans[i][0]!=ans[i][n-2] and s[n-1]=='o':
    flag1=True
  if ans[i][0]==1 and ans[i][n-1]==ans[i][1] and s[0]=='o':
    flag2=True
  elif ans[i][0]==0 and ans[i][n-1]==ans[i][1] and s[0]=='x':
    flag2=True
  elif ans[i][0]==1 and ans[i][n-1]!=ans[i][1] and s[0]=='x':
    flag2=True
  elif ans[i][0]==0 and ans[i][n-1]!=ans[i][1] and s[0]=='o':
    flag2=True
  if flag1 and flag2:
    idx=i
    break
if idx==-1:
  print(-1)
  exit()
t=[]
for i in range(n):
  if ans[idx][i]==1:
    t.append('S')
  else:
    t.append('W')
print(''.join(t))

Measured memory_bytes: 8236
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

signed main(){
    int N, sum = 0;
    cin >> N;
    vector<int> s(N);
    priority_queue<int, vector<int>, greater<int> > que;

    rep(N){
        cin >> s[i];
        sum += s[i];
        if(s[i] % 10 != 0) que.push(s[i]);
    }
    if(sum % 10 == 0 && !que.empty()){
        int t = que.top();  que.pop();
        sum -= t;
    }
    if(sum % 10 == 0){
        cout << 0;
    }else{
        cout << sum;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

int N;
ll x[110], y[110], z[110];

ll myabs(ll xx){
    if(xx >= 0){
        return xx;
    }
    else{
        return -xx;
    }
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i] >> z[i];
    }

    ll h_max = (ll)1e9+1;
    for(ll i = 0; i <= 100; i++){
        for(ll j = 0; j <= 100; j++){
            ll h = (ll)1e9+1;
            ll h_min = -1;
            bool ok = true;
            for(int k = 0; k < N; k++){
                ll dis = max(h_max-myabs(i-x[k])-myabs(j-y[k]), 0LL);
                if(z[k] == 0 && dis > h){
                    ok = false;
                    break;
                }
                else if(z[k] == 0){
                    h_min = max(h_min, dis);
                }
                else if(z[k] > 0 && h == (ll)1e9+1){
                    h = dis - z[k];
                }
                else if(z[k] > 0 && h != dis - z[k]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                for(int k = 0; k < N; k++){
                    ll dis = max(h_max-h-myabs(i-x[k])-myabs(j-y[k]), 0LL);
                    if(dis != z[k]){
                        ok = false;
                        break;
                    }
                }
            }
            if(ok){
                cout << i << " " << j << " " << h_max-h << endl;
                return 0;
            }
        }
    }


    exit(1);
}



Measured memory_bytes: 256
//2019.7.7 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define eps 1e-12
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define gc getchar
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//inline int read() {
//    res s=0,ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
inline int read() {
    res s=0,ch=gc(),w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace MAIN{
    int L,R;
    inline void MAIN(){
        L=read(),R=read();
        if(R-L+1>=2019)puts("0");
        else {
            res ret=inf;
            for(res i=L;i<=R;i++)
                for(res j=i+1;j<=R;j++)
                    ret=min(ret,int(1LL*i*j%2019));
            printf("%d\n",ret);
        }
    }
}
int main() {
//    srand((unsigned)time(NULL));
    // freopen("zao.in","r",stdin);
    // freopen("std.out","w",stdout);
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;

typedef vector<pair<int,int>> vpii;
typedef pair<int,int> pr;

int main(){
    int n;
    cin >> n;
    cout << n*n*n << endl;
}

Measured memory_bytes: 256
#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>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;






    
int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    map<ll,ll> M;
    for(int i=0;i<n;i++){
        cin>>a[i];
        M[a[i]]=i+1;
    }
    sort(a.begin(),a.end(),greater<ll>());
    vector<ll> parent(n,-1);
    vector<ll> count(n,1);
    vector<ll> cost(n,0);
    for(int i=0;i+1<n;i++){
        ll to=a[i]-n+count[i]*2;
        ll I=lower_bound(a.begin(),a.end(),to,greater<ll>())-a.begin();
        if(I==n || a[I]!=to){cout<<-1<<endl; return 0;}
        count[I]+=count[i];
        cost[I]+=cost[i]+count[i];
        parent[i]=I;
    }
    if(cost[n-1]!=a[n-1]){cout<<-1<<endl; return 0;}
    for(int i=0;i<n-1;i++){
        cout<<M[a[i]]<<" "<<M[a[parent[i]]]<<endl;
    }
    
    
        
    return 0;
}


Measured memory_bytes: 10752
# import sys
# import math
# import decimal
# import queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # queue
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mp = {}
    for i in range(n):
        if a[i] in mp.keys():
            mp[a[i]] += 1
        else:
            mp[a[i]] = 1
    res = 0
    b = [0] * (n + 1)
    for k in mp.keys():
       x = mp[k] * (mp[k] - 1) // 2
       res += x
       b[k] = x - (mp[k] - 1) * (mp[k] - 2) // 2
    for i in range(n):
        print(res - b[a[i]])
    return

if __name__=='__main__':
    main()


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

int main() {
	string	S;
	cin >> S;
	int	i, max_len;
	while (i < S.size())
	{
		while (i < S.size() && S.at(i) != 'A' && S.at(i) != 'C' && S.at(i) != 'G' && S.at(i) != 'T')
			i++;
		if (i < S.size() && (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T')) 
		{
			int	len;
			len = 0;
			while (i < S.size() && (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T'))
			{
				len++;
				i++;
			}
			if (len > max_len)
				max_len = len;
		}
	}
	cout << max_len << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main() {

    char c;
    int sum = 0;

    while (true)
    {
        scanf("%c", &c);

        if (c=='\n')
        {
            if (sum==0)
            {
                break;
            }
            printf("%d\n", sum);
            sum = 0;
            continue;
        }
        else
        {
            sum += (c-'0');
        }
    }
    return 0;
}


Measured memory_bytes: 2728
//
//  main.cpp
//  ITP1-8-C
//
//  Created by h3037153 on 2017/08/25.
//  Copyright ?? 2017??´ h3037153. All rights reserved.
//
#include<iostream>
#include<string>
#include<cctype>
#include<cstdio>
using namespace std;
int main(){
    char moji;
    string str[1200],no;
    int i,num,counter[26]={},ii=0;
    while(getline(cin,str[ii])){
    for(i=0;i<str[ii].size();i++){
        if(isupper(str[ii][i])){
            str[ii][i]=tolower(str[ii][i]);
        }
    }
    for(i=0;i<str[ii].size();i++){
        num=str[ii][i]-'a';
        counter[num]++;
    }
        i++;
    }
    
    //while(1){
        for(moji='a',i=0;moji<='z',i<=25;moji++,i++){
            printf("%c",moji);
            printf(" : ");
            printf("%d",counter[i]);
            printf("\n");
          /*for(moji='a';moji<='z';moji++){
              printf("%c",moji);
            
          }
          for(i=0;i<=25;i++){
                printf(" : ");
                printf("%d",counter[i]);
                printf("\n");
        }*/
    }
    
    
    return 0;
}

Measured memory_bytes: 3204
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	for (;;) {
		int N, M; cin >> N >> M;
		if (N == 0 && M == 0) break;
		vector<i_i> v(N);
		for (int i = 0; i < N; i++)
			cin >> v[i].second >> v[i].first;
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int D = v[i].second, P = v[i].first;
			int x = min(D, M);
			M -= x;
			ans += (D - x) * P;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
 
int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> p(m);
  for(int i=0; i<m; i++){
    cin >> p[i].second >> p[i].first;
  }
  sort(p.begin(), p.end());
  
  int ans = 1;
  int right_edge = p[0].first;
  for (int i=0; i<m; i++){
    if (p[i].second >= right_edge){
      ans ++;
      right_edge = p[i].first;
    }
  }
  cout << ans << endl;
  return 0;
}

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

using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
int in() {int x; cin>>x; return x;}
string stin() {string s; cin>>s; return s;}
/***** MAIN *****/
signed main() {
  string s = stin();
  int ans = LLONG_MAX;
  bool flag = true;
  REP(i,s.size()-1) {
    if(s[i] != s[i+1]) {
      flag = false;
      break;
    }
  }
  if(flag) {
    cout << 0 << endl;
    return 0;
  }
  for(char c = 'a'; c <= 'z'; ++c) {
    string tmp_s = s;
    int current_size = tmp_s.size();
    int ope_counter = 0;
    while(true) {
      REP(i,current_size-1) {
        if(tmp_s[i] == c || tmp_s[i+1] == c) tmp_s[i] = c;
      }
      ++ope_counter;
      --current_size;
      flag = true;
      REP(i,current_size-1) {
        if(tmp_s[i] != tmp_s[i+1]) {
          flag = false;
          break;
        }
      }
      if(flag) break;
    }
    ans = min(ans, ope_counter);
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

int main(){
    using namespace std;
    constexpr unsigned long MOD{1000000007};
    unsigned long S;
    cin >> S;
    unsigned long a{1}, b{0}, c{0};
    for(unsigned long i{0}; i < S; ++i){
        swap(a, c);
        swap(a, b);
        (c += b) %= MOD;
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const long long MOD = 1000000007;

auto smallestPrimeFactors(long long N){
    vector<long long> spf(N + 1);
    for(long long i = 0; i <= N; i++) spf[i] = i;
    for(long long i = 2; i * i <= N; i++){
        if(spf[i] != i) continue;
        for(long long j = i * i; j <= N; j += i){
            if(spf[j] == j) spf[j] = i;
        }
    }
    return spf;
}

auto factorization_spf(long long N, vector<long long>& spf){
    map<long long, long long> prime;
    while(N != 1){
        prime[spf[N]]++;
        N /= spf[N];
    }
    return prime;
}

signed main(){
    ll N;
    cin >> N;
    ll ans = 1;
    auto spf = smallestPrimeFactors(N);
    for(ll D = 2; D < N; D++){
        auto m = factorization_spf(D, spf);
        ll d = 1;
        for(auto p : m){
            d *= p.second + 1;
        }
        ans += d;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 11176
#include<algorithm>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

double x[10],y[10],total=0.00;
int a[10];
double AverageLength(double x1,double x2,double y1,double y2){
	double AverageLength_=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)*1.00);
	return AverageLength_;
}

double factorial(int n){
	int Factorial=1;
	for(int i=1; i<=n; i++)
		Factorial*=i;
	return double(Factorial*1.00);
}

int main(){
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>x[i]>>y[i];
	for(int i=1; i<=n; i++)
		a[i]=i;
	
	do{
		double sum=0.000;
		for (int i=2;i<=n;i++)
			sum+=AverageLength(x[a[i-1]],x[a[i]],y[a[i]],y[a[i-1]]);
		total+=sum;
	}while(next_permutation(a+1,a+n+1));
	
//	cout<<fixed<<setprecision(10)<<total*1.00/(factorial(n)*1.00)<<endl;
	printf("%.10lf\n",total*1.00/(factorial(n)*1.00));
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int

struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
ll euclidean_gcd(ll a, ll b) {
  if(a < b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
ll euclidean_lcm(ll a, ll b) {
  return a/euclidean_gcd(a,b)*b;
}
int main(void){
  ll a[10001],m;
  rep(i,10001)a[i]=0;
  rep(i,101){
    rep(j,101){
      rep(k,101){
        if(i==0||j==0||k==0)continue;
        m=i*i+j*j+k*k+i*j+j*k+k*i;
        if(m<10001)a[m]++;
      }
    }
  }
  ll n;
  cin >> n;
  rep(i,n){
    cout << a[i+1] << endl;
  }
}

Measured memory_bytes: 3664
#include <stdio.h>


int main(void)
{
    int n,judge=0;
    int d[100][2]={0};
    scanf("%d",&n);
    for(int i=0;i<=n-1;i++){
        scanf("%d%d",&d[i][0],&d[i][1]);
    }
    for(int i=2;i<=n-1;i++){
        if(judge == 1) break;
        if(d[i][0] == d[i][1]) {
            
            
            if(d[i-1][0] == d[i-1][1]) {
                
                
                if(d[i-2][0] == d[i-2][1]) {
                judge++;
                }
            
            }
        }
    }
    if(judge == 1){
        printf("Yes");
    }else{
        printf("No");
    }
    

}

Measured memory_bytes: 1728
import itertools

n = int(input())
p_L = list(map(int, input().split()))
q_L = list(map(int, input().split()))
p_val = 0
q_val = 0

all_list = list(map(list, list(itertools.permutations(range(1,n+1)))))

for i in range(len(all_list)):
    if all_list[i] == p_L:
        p_val = i
        
    if all_list[i] == q_L:
        q_val = i


        
print(max(p_val-q_val, q_val-p_val))
        

Measured memory_bytes: 15092
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [[0] for _ in range(w)]
dp[0][0] = 1

#print(dp)
N = 6401
for i in range(h):
    ndp = [[0]*N for _ in range(w)]
    for j in range(w):
        v = abs(a[i][j] - b[i][j])
        #print(v)
        for ii,c in enumerate(dp[j]):
            if ii+v < N:
                ndp[j][abs(ii+v)] |= c
            ndp[j][abs(ii-v)] |= c
        if j:
            for ii,c in enumerate(ndp[j-1]):
                if ii+v < N:
                    ndp[j][abs(ii+v)] |= c
                ndp[j][abs(ii-v)] |= c

    dp = ndp
    #print(dp)
    
c = [i for i,c in enumerate(dp[j]) if c]

#print(c)
print(min(c))














Measured memory_bytes: 137480
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

int main(void){
    string s;
    cin >> s;
    int count = 0;
    int check = 0;
    for(int i = 0; i < s.length(); i++){
        count = 0;
        for(int j = 0; j < s.length(); j++){
            if(s[i] == s[j])
                count++;
        }
        if(count % 2 == 0)
            check++;
    }
    if(check == s.length())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}


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

int main(){
	ll a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	ll ans = x * a + y * b;
	if(x > y) ans = min(ans, min(2 * y * c + a * (x - y), 2 * x * c));
	else ans = min(ans, min(2 * x * c + b * (y - x), 2 * y * c));
	cout << ans << '\n';
}


Measured memory_bytes: 256
import math
import bisect

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    pos.sort()
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(bisect.bisect_right(pos,r) - bisect.bisect_left(pos,l))

Measured memory_bytes: 58576
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int maxn=200111;
int n,m,a[maxn];

bool check(int v)
{
	for(int i=v;i<=n;i++)if(a[i]+a[v+n-i]<m)return false;
	return true;
}

int main()
{
	get2(n,m);n*=2;
	for(int i=1;i<=n;i++)get1(a[i]);
	sort(a+1,a+n+1);
	
	int lb=0,rb=n+1,mid;
	while(lb<rb-1)
	{
		mid=(lb+rb)>>1;
		if(check(mid))rb=mid;
		else lb=mid;
	}
	if(rb%2==0)rb++;
	int ans=0;
	for(int i=1;i<rb;i++)ans=max(ans,a[i]+a[rb-i]);
	for(int i=rb;i<=n;i++)ans=max(ans,a[i]+a[rb+n-i]-m);
	printendl(ans);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <limits>
#include <cmath>
#include <cstdio>

using namespace std;

#define EPS (numeric_limits<double>::epsilon())
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {
public:
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}

    Point operator+(const Point &p) const
    {
        return Point(x + p.x, y + p.y);
    }

    Point operator-(const Point &p) const
    {
        return Point(x - p.x, y - p.y);
    }

    Point operator*(const double &a) const
    {
        return Point(a * x, a * y);
    }

    Point operator/(const double &a) const
    {
        return Point(x / a, y / a);
    }

    double abs()
    {
        return sqrt(norm());
    }

    double norm()
    {
        return x * x + y * y;
    }

    bool operator<(const Point &p) const
    {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator==(const Point &p) const
    {
        return equals(x, p.x) && equals(y, p.y);
    }
};

typedef Point Vector;

struct Segment {
    Point p1, p2;
};
typedef Segment Line;


double dot(Vector a, Vector b)
{
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b)
{
    return a.x * b.y - a.y * b.x;
}

bool isParallel(Vector a, Vector b)
{
    return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2)
{
    return equals(cross(a2 - a1, b2 - b1), 0.0);
}

bool isOrthogonal(Vector a, Vector b)
{
    return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2)
{
    return equals(dot(a2 - a1, b2 - b1), 0.0);
}

Point project(Segment s, Point p)
{
    Vector hypo = p - s.p1;
    Vector base = s.p2 - s.p1;
    return base * (dot(hypo, base) / base.norm()) + s.p1;
}

Point reflect(Segment s, Point p)
{
    return (project(s, p) - p) * 2.0 + p;
}

int main()
{
    Point p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    Segment s{p1, p2};
    int query;
    cin >> query;
    Point p;
    for (int q = 0; q < query; q++)
    {
        cin >> p.x >> p.y;
        Point x = reflect(s, p);
        printf("%.10f %.10f\n", x.x, x.y);
    }
}


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

#define INF 1e9
using namespace std;

int main() {

    int N; cin >> N;

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

    vector<int> B(N);
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }

    long long ans = 0;

    for (int i = N; i > 0; --i) {
        if (A[i] + A[i-1] < B[i-1]) {
            ans += A[i] + A[i-1];
            A[i-1] = 0;
        } else {
            ans += B[i-1];
            if (A[i] < B[i-1]) {
                A[i - 1] = A[i] + A[i - 1] - B[i - 1];
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;
int main() {
  string s;
  cin >> s;
  if (s == "Sunny") cout << "Cloudy" << endl;
  else if (s == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
  return 0;
}

Measured memory_bytes: 3612
N,X,M = map(int,input().split())
t_loop = [X]
f_loop = [X]
f_memo = {X:1}
s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in f_memo:
        f_memo[new_val] = 1
        f_loop.append(new_val)
    else:
        f_memo[new_val] += 1
        if f_memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)

Measured memory_bytes: 90136
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e9+7;

int main()
{
    ll n,m,x,y;
    cin >> n >> m >> x >> y;
    rep(i,n){
        ll a;
        cin >> a;
        x=max(a,x);
    }
    rep(i,m){
        ll b;
        cin >> b;
        y=min(y,b);
    }
    if(x<y) cout << "No War" << endl;
    else cout << "War" << endl;
    return 0;
} 

Measured memory_bytes: 256
#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<cmath>
#define N 100005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll a[200000+5],num[200000+5];

int main()
{
	ll n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		num[a[i]]++;
	}
	//for(int i=1;i<=n;i++)
	//	printf("%lld ",num[i]);
///	cout<<endl;
	ll ans=0;
	for(int i=1;i<=n;i++)
		ans+=(num[i]-1)*num[i]/2;
	//cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		ll ans1;
		ans1=ans;
		ans1-=(num[a[i]]-1)*num[a[i]]/2;
		if(num[a[i]]>2)
		ans1+=(num[a[i]]-2)*(num[a[i]]-1)/2;
		printf("%lld\n",ans1);
	}
	return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h> //全てのヘッダファイルをインクルード

//ループ
#define rep(i, n) for(int i = 0; i < (n); i++) //普通のループ
#define repr(i, n) for(int i = n; i >= 0; i--) //逆ループ

//型名省略
typedef long long ll;
//値
static const ll MX = 100005;
static const ll MX_ll = 1e18;

using namespace std;

//ソート
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

//#include "./lib/generic/search.h"

int main(){
    int l, r, d, cnt=0;
    cin >> l >> r >> d;
    while(1){
        if(l%d==0) cnt++;
        if(l==r) break;
        l+=1;
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3632
sx, sy, tx, ty = map(int, input().split())
dx, dy = tx-sx, ty-sy
ans = "UD"[dy<0]*dy + "RL"[dx<0]*dx + "UD"[dy>0]*dy
dx += 1;dy += 1
print(ans + "RL"[dx>0]*dx + "UD"[dy<0]*dy + "RL"[dx<0]*dx + "UD"[dy>0] + "RL"[dx<0] + "UD"[dy>0]*dy + "RL"[dx>0]*dx + "UD"[dy<0])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ar[2005]={0};
int main(){
  ll n,z,w;
  cin>>n>>z>>w;
  for(int i=1;i<=n;i++) cin>>ar[i];
  if(n==1) cout<<abs(ar[1]-w)<<endl;
  else cout<<max(abs(ar[n]-w),abs(ar[n-1]-ar[n]))<<endl;
}


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

using namespace std;

class Poly{
public:
  int getSum(int a){
    int retV = a+a*a+a*a*a;
    return retV;
  }
};

int main(int argc, const char*argv[]){
  Poly p;
  int a;
  cin>>a;
  int s = p.getSum(a);
  cout<<s<<endl;
  return 0;
}


Measured memory_bytes: 3552
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
        


Measured memory_bytes: 52448
/*
* @Author: _dp95
* @Date:   2019-12-10 11:48:03
*/
#include "bits/stdc++.h"
using namespace std ;

#define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll ;
typedef long double ldb ;

#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'

#define all( x ) x.begin(),x.end() 
#define sz( x ) ( int )( x ).size( )
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

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

const int MAX = 2*1000*1000 + 10 ;
const ll INF = 1e18 ;
const int MOD = 1e9 + 7 ;

int n, m, s[ MAX ], dp[ MAX ] ;

int main( ){
  timesaver ;
  cin >> n >> m ;
  for( int i = 0 ; i < n ; i++ ){
    cin >> s[i] ;
  }
  for( int i = 0 ; i <= m ; i++ ){
    if(dp[i])
      continue ;
    for(int j = 0 ; j < n ;j++ )
      dp[i+s[j]] |= 1 ;
  }
  if(dp[m])
    cout << "First" << nl ;
  else
    cout << "Second" << nl ;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
struct __test {} test;
using namespace std;
template <typename T>const __test &operator<<(const __test& d,
const T& v) {return cerr << "\033[31m" << v << "\033[0m",d;}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

int n,A,x[55];
ll dp[55][55*55][55]={};

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> A;
	for(int i = 1; i <= n; ++i)
		cin >> x[i];
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int a = 0; a <= A*n; ++a) {
			for(int c = 0; c <= i; ++c) {
				dp[i][a][c] += dp[i-1][a][c];
				if(c && x[i]<=a) dp[i][a][c] += dp[i-1][a-x[i]][c-1];

			}
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++i) {
		ans += dp[n][A*i][i];
	}
	cout << ans << "\n";
}

Measured memory_bytes: 66560
import scala.io.{StdIn => in}
import scala.collection.{mutable => mu}

object Main extends App {
  val n = in.readInt

  val edges = Iterator.continually(in.readLine)
    .take(n-1)
    .map(_.split(" ").map(_.toInt))
    .toArray

  val que = mu.PriorityQueue.empty[Int]
  in.readLine.split(" ").map(_.toInt)
    .foreach(que enqueue _)

  val graph = Array.fill(n+1)(mu.ListBuffer.empty[Int])
  edges.foreach { e =>
    e(1) +=: graph(e(0))
    e(0) +=: graph(e(1))
  }

  val node = Array.ofDim[Int](n+1)

  def dfs(first:Int):Unit = {
    val visited = Array.ofDim[Boolean](n+1)
    val stk = mu.Stack.empty[Int]
    stk push first

    while(stk.nonEmpty) {
      val v = stk.pop
      if(!visited(v)) {
        visited(v) = true
        node(v) = que.dequeue
        graph(v) foreach stk.push
      }
    }
  }

  dfs(1)

  val ans = (0 until n-1)./:(0){(acc, i) => 
    acc + ( node(edges(i)(0)) min node(edges(i)(1)) )
  }

  println(ans)
  println(node.tail.mkString(" "))
}

Measured memory_bytes: 40388
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define debug(x) cout << #x << " = " << (x) << endl;
#define pb push_back
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000000000
#define EPS 0.00000000001
typedef long long ll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    //---------------------------------------------

    double n;
    cin>>n;
    int k=n;
    if(n==1){
        cout<<1.00000000000<<endl;
    }
    else if(k%2==1){
        //cout<<(n/2)+1;
        cout<<((k/2)+1)/n<<endl;
    }
    else{
        cout<<0.50000000000<<endl;
    }
}


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

div = []  # Nの約数を全列挙してdivとする
for i in range(1, int(N ** 0.5) + 1):
	if N % i == 0:
		div.append(i)
		if i != N // i:
			div.append(N // i)

for j in range(len(div)):
	if div[j] == 1:  # m=0はskip
		pass
	else:
		m = div[j] - 1
		if N // m == N % m:
			ans += m

print(ans)


Measured memory_bytes: 3268
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
    string s;
    int k;
    cin>>s>>k;
    ll n=s.size();
    ll dp[101][4][2] = {};
    dp[0][0][0]=1;
    dp[0][0][1]=0;


   for(int i=1;i<=n;i++){
        rep(j,4){
            int x = s[i-1]-'0';
            if(x==0){
                dp[i][j][0] += dp[i-1][j][0];
            }else{
               // ll l=max(0,j-1);
                if(j!=0){
                    dp[i][j][0] += dp[i-1][j-1][0];
                }


            }


            for(int k=0;k<=x-1;k++){
                if(k==0){
                    dp[i][j][1] += dp[i-1][j][0];
                }else{
                   if(j==0){
                      // dp[i][j][1]+=dp[i-1][j][0];
                   }else{
                       dp[i][j][1]+=dp[i-1][j-1][0];
                   }

                }
            }

            for(int k=0;k<=9;k++){
                if(k==0){
                    dp[i][j][1]+=dp[i-1][j][1];
                }else{
                    if(j==0){
                       // dp[i][j][1]+=dp[i-1][j][1];
                    }else{
                        dp[i][j][1]+=dp[i-1][j-1][1];
                    }
                }
            }
        }
    }


    cout<<dp[n][k][0]+dp[n][k][1]<<endl;
  



    
return 0;
}


Measured memory_bytes: 256
#include<queue>
#include<cstdio>
#include<algorithm>
#define MN 110001
using namespace std;

int read_p,read_ca;
inline int read(){
    read_p=0;read_ca=getchar();
    while(read_ca<'0'||read_ca>'9') read_ca=getchar();
    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p;
}
int n,l,t,p[MN],w[MN];
long long T=0;
int main(){
	register int i;
	n=read();l=read();t=read();
	for (i=0;i<n;i++) p[i]=read(),w[i]=read();
	for (i=0;i<n;i++) p[i]+=w[i]==1?t:-t,T+=p[i]/l,p[i]%=l;
	for (i=0;i<n;i++) if (p[i]<0){
		T--;
		p[i]+=l;
	}
	sort(p,p+n);T%=n;
	for (i=0;i<n;i++) printf("%d\n",p[(i+T+n)%n]);
}

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

int main(){
  string s, t;
  int ans=0, n;
  cin >> s >> t;
  n = s.size();
  rep(i,n)if(s[i] != t[i])ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3860
#include <stdio.h>
#include <stdlib.h>

int main()
{
  double n;
  scanf("%lf", &n);
  if ((int)n % 2 == 0) printf("%.8lf", 0.5);
  else
  {
    printf("%.8lf", ((n+1)/2)/n);
  }
  return 0;
}

Measured memory_bytes: 128