akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main(void){
    int n=0,m=0;
    while(cin>>n,n){
        char change[100][2];
        char s;
        for(int i=0;i<n;i++){
            cin >> change[i][0] >> change[i][1];
        }
        cin >> m;
        for(int j=0;j<m;j++){
            cin >> s;
            for(int k=0;k<n;k++){
            
                if(s==change[k][0]){
                s = change[k][1];
                break;
                }
            
            }
            cout << s;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
char map[505][505];
int def[505][505];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<int>to[200005];

int main() {
	int n, m;
	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		a--;
		b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	queue<ll>que;
	vector<int>dist(n, inf);
	vector<int>pre(n, -1);
	dist[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (int id : to[v]) {
			if (dist[id] != inf)continue;
			dist[id] = dist[v] + 1;
			pre[id] = v;
			que.push(id);
		}
	}
	cout << "Yes" << endl;
	for (int i = 1; i < n; i++) {
		int ans = pre[i]++;
		cout << pre[i] << endl;
	}
	return 0;
}
	
	

Measured memory_bytes: 13072
#include<bits/stdc++.h>
using namespace std;
const int inf = 1012345678;

int main(){
 int N; cin >> N;
  int H[N];
  for(int i=0;i<N;i++){
    cin >> H[i] ;
  }
  
  int ans =0;
  for(int i=0;i<N;i++){
    bool is_candidate = true;
    for(int j=0;j<i;j++){
      if(H[j]>H[i]){
        is_candidate = false;
        break;
      }
    }
    if(is_candidate){
      ans++;
    }
  }
  cout << ans << endl;
}


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

using namespace std;

typedef long long ll;
 
#define rep(i,n) for(int i=0;i<(n);++i)

int upper_Bound(ll A[],int N,ll key){
    int left=-1;
    int right=N;
    int mid;
    while(right-left>1){
        mid=(left+right)/2;
        if(A[mid]<key){
            left=mid;
        }else{
            right=mid;
        }
        
       // cout<<"upper left:"<<left<<":"<<A[left]<<" right:"<<right<<":"<<A[right]<<endl;
    }
    return left;
}

int lower_Bound(ll A[],int N,ll key){
    int left=-1;
    int right=N;
    int mid;
    while(right-left>1){
        mid=(left+right)/2;
        if(key<A[mid]){
            right=mid;
        }else{
            left=mid;
        }
       // cout<<"lower left:"<<left<<":"<<A[left]<<" right:"<<right<<":"<<A[right]<<endl;
    }
    return right;
}


int main(){
  /*
    ll arr1[]={2,3,3,3,5,6};
   
    ll a=upper_Bound(arr1,6,3);
    cout<<a<<endl;

    ll b=lower_Bound(arr1,6,3);
    cout<<b<<endl;
    cout<<(a+1)*(3-b);
    */
   
    int N;
    cin>>N;
    
    ll A[N];
    rep(i,N){
        cin>>A[i];
    }
    sort(A,A+N);
    
    ll B[N];
    rep(i,N){
        cin>>B[i];
    }
    sort(B,B+N);
    
    ll C[N];
    rep(i,N){
        cin>>C[i];
    }
    sort(C,C+N);
    
    ll a,c;
    
    ll count=0;
    
    rep(i,N){
        a=upper_Bound(A,N,B[i]);
        c=lower_Bound(C,N,B[i]);
        count+=(a+1)*(N-c);
    }
    
    cout<<count<<endl;
    
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

ll pd[3000];
ll rd[3000];
ll Ep(int x, int y){
  if(y == 0) return 1;
  if(y == 1) return x;
  ll r = Ep(x,y/2);
  if(y%2 == 1) return r *r%MOD *x%MOD;
  else return r *r%MOD;
}
ll Ftl(ll x){
  if(x == 1 || x == 0) return 1;
  if(pd[x] != 0) return pd[x];
  return pd[x] = Ftl(x-1) *x%MOD;
}
ll rFtl(ll x){
  if(x == 1 || x == 0) return 1;
  if(rd[x] != 0) return rd[x];
  return rd[x] = rFtl(x-1)*Ep(x,MOD-2)%MOD;
}
ll comb(ll m, ll n){
  if(m < n) return 0;
  return Ftl(m) *rFtl(n)%MOD *rFtl(m-n)%MOD;
}

int main(){
  int n, k;
  cin >> n >> k;
  int r = n-k;
  for(int i=1; i<=k; ++i){
    if(r+1<i) cout << 0 << endl;
    else{
      int ans = comb(r+1,r-i+1) * comb(k-1,k-i) %MOD;
      cout << ans << endl;
    }
  }
}

Measured memory_bytes: 3660
N = int(input())
cnt = 0
t = 0
for i in range(N):
    a,b = map(int,input().split())
    if a == b:
        cnt += 1
    else:
        cnt = 0
    if cnt == 3:
        print("Yes")
        t = 1
        break
if t == 0:
    print("No")

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

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    int to_i(const string& s) {
        istringstream is(s);
        int n; is >> n;
        return n;
    }


    int N;
    vector<string> S;
    bool input() {
        cin >> N;
        if (N == 0) return false;
        S.clear(); S.resize(N); cin >> S;
        return true;
    }

    int level(const string& s) {
        for (int i = 0; i < int(s.size()); i++) if (s[i] != '.') return i;
        assert(false);
    }

    int calc(char op, int a, int b) {
        //cerr << a << " " << op << " " << b << endl;
        switch (op) {
            case '+': return a + b;
            case '*': return a * b;
            default: assert(false);
        } 
    }

    int dfs(int& j) {
        const string& s = S[j];
        int l = level(s);
        if (isdigit(s[l])) {
            j++;
            return to_i(s.substr(l, s.size() - l));
        } else {
            char op = s[l];
            int ans = (op == '+' ? 0 : 1);
            j++;
            while (j < N && level(S[j]) > l) {
                ans = calc(op, ans, dfs(j));
            }
            return ans;
        }
    }

    void solve() {
        int j = 0;
        cout << dfs(j) << endl;
    }
}

int main() {
    while (input()) solve();
    return 0;
}

Measured memory_bytes: 3148
while True:
    n = int(input())
    if n == 0:
        break
    d = {}
    for _ in range(n):
        a, b = input().split()
        d[a] = b
    m = int(input())
    ans = []
    for _ in range(m):
        a = input().strip()
        if a in d.keys():
            ans.append(d[a])
        else:
            ans.append(a)
    print("".join(ans))

Measured memory_bytes: 8640
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize);
    let mut sum = 0;
    for i in 1..n + 1 {
        for j in 1..n + 1 {
            for k in 1..n + 1 {
                sum += num::integer::gcd(i, num::integer::gcd(j, k));
            }
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 2196
N, M = gets.split.map(&:to_i)

mod = 10 ** 9 + 7

def fact(n)
  mod = 10 ** 9 + 7
  (1..n).inject(1){ |res, i| res * i % mod }
end

if ( N - M ).abs > 1
  puts 0
elsif N == M
  puts 2 * fact(N) * fact(M) % mod
else
  puts fact(N) * fact(M) % mod
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;


int main(){
    
    int N,K;
    cin >> N >> K;
    vector<int> h(N);
    rep(i,N) cin >> h[i];
    vector<int> dp(N,2000000000);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 1; k+i < N && k <= K; k++) {
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i]-h[i+k]));
        }
        
    }
    
    cout << dp[N-1] << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int a[20][20],n,ans,h[20];
int t[20];
void dfs(int p,int s){
	if(p==n+1){
		ans=max(ans,s);return ;
	}
	if(t[p]==2){
		for(int i=1;i<=n;i++){
			if(a[p][i]==1&&t[i]==2){
				return ;
			}
			if(a[p][i]==2&&t[i]==1){
				return;
			}
		}
		int last[20];
		for(int i=1;i<=n;i++){
			last[i]=t[i];
			if(a[p][i]!=0)t[i]=a[p][i];
		}
		h[p]=1;
		dfs(p+1,s+1);
		h[p]=0;
		for(int i=1;i<=n;i++){
			t[i]=last[i];
		}
	}else if(t[p]==1){
		dfs(p+1,s);
	}else{
		t[p]=1;
		dfs(p+1,s);
		t[p]=0;
		for(int i=1;i<=n;i++){
			if(a[p][i]==1&&t[i]==2){
				return ;
			}
			if(a[p][i]==2&&t[i]==1){
				return;
			}
		}
		int last[20];
		for(int i=1;i<=n;i++){
			last[i]=t[i];
			if(a[p][i]!=0)t[i]=a[p][i];
		}
		h[p]=1;t[p]=2;
		dfs(p+1,s+1);
		h[p]=0;t[p]=0;
		for(int i=1;i<=n;i++){
			t[i]=last[i];
		}
	}
}
int main(){
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		int l,r;
		for(int j=1;j<=x;j++){
			cin>>l>>r;
			a[i][l]=r+1;
		}
		a[i][i]=2;
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()
#print(s[1])

east = [0]*(n+1)#自分より左に何人Eがいるか
for i in range(n+1):
    if i == 0:
        east[i] = 0
    else:
        if s[i-1] =="E":
            east[i] = east[i-1] +1
        else:
            east[i] = east[i-1]
#print(east)

ans = float("inf")
for i in range(n):
    lefte = east[i]#自分より左にいるE
    righte = east[-1] - east[i+1]#自分より右にいるE
    leftw = i - lefte#自分より左にいるW
    rightw = n - i - 1 - righte#自分より右にいるw
    x = 0
    x += leftw
    x += righte
    if x < ans:
        ans = x
print(ans)

Measured memory_bytes: 44792
N, K = map(int, input().split())
P = list(map(int, input().split()))

# N:  処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 10**6
seg_min = [INF]*(2*N0)
seg_max = [-INF]*(2*N0)


def update(index, value):
    index += N0 - 1
    seg_min[index] = value
    seg_max[index] = value
    while index > 0:
        index = (index - 1) // 2
        seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])
        seg_max[index] = max(seg_max[index * 2 + 1], seg_max[index * 2 + 2])


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret_min = INF
    ret_max = -INF
    while first <= last:
        if not first & 1:
            ret_min = min(ret_min, seg_min[first])
            ret_max = max(ret_max, seg_max[first])
        if last & 1:
            ret_min = min(ret_min, seg_min[last])
            ret_max = max(ret_max, seg_max[last])
        first = first // 2
        last = last // 2 - 1
    return ret_min, ret_max


for i in range(N):
    update(i, P[i])

ans = 1
for i in range(1, N - K + 1):
    s, b = query(i-1, K+i-1)
    # print(s, b, P[i - 1], P[K + i - 1])
    if s != P[i-1] or b != P[K+i-1]:
        ans += 1

kaburi = 0
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        cnt += 1
    else:
        cnt = 0
    if cnt == K-1:
        kaburi += 1
kaburi = max(0, kaburi - 1)

print(ans - kaburi)


Measured memory_bytes: 114300
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int amt = 0;
		int max = 0;

		for(int i = 0; i < n; i++) {
			int v = sc.nextInt();
			amt += v;
			max = Math.max(max, v);
		}

		amt -= max/2;

		System.out.println(amt);

	}

}



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

int main(){
  string s;
  cin>>s;
  int a=0;
    if(s[0]==s[1]){
      cout<<"Bad"<<endl;
      a++;
    }
   else if(s[1]==s[2]){
      cout<<"Bad"<<endl;
      a++;
    }
   else if(s[2]==s[3]){
      cout<<"Bad"<<endl;
      a++;
    }
    if(a==0){
      cout<<"Good"<<endl;
    }
  
  return 0;
}


Measured memory_bytes: 256
<?php 

$mod = 10**9+7;

function carcu(int $x, int $y){
    $mod = 10**9+7;
    $num = 1;
    for($i=0;$i<$y;$i++){
        $num=$num*$x%$mod;
    }
    return $num;
}

$n = fgets(STDIN);

$ans = carcu(10,$n) - carcu(9,$n) - carcu(9,$n) + carcu(8,$n);
$ans%=$mod;
$ans=($ans+$mod)%$mod;
echo $ans."\n";


Measured memory_bytes: 16100
#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    
    if ((a + b)%2 == 0)
        printf("%d\n", (a+b)/2);
    
    else
        printf("%d\n", (a+b+1)/2);


    return 0;
}


Measured memory_bytes: 128
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n;
  std::cin>>n;

  struct Edge{ll l,r,level;};

  std::queue<Edge> que;

  std::vector<std::vector<ll>> level(n,std::vector<ll>(n,0));

  que.push(Edge{0,n-1,1});

  while(que.size()){
    Edge e=que.front();que.pop();

    ll num=(e.r-e.l+1)/2;
    rep(i,e.l,e.l+num){
      rep(j,e.l+num,e.r+1){
        level[i][j]=e.level;
      }
    }

    if(e.l!=e.l+num-1)que.push(Edge{e.l,e.l+num-1,e.level+1});

    if(e.l+num!=e.r)que.push(Edge{e.l+num,e.r,e.level+1});
  }

  rep(i,0,n){
    rep(j,i+1,n){
      std::cout<<level[i][j];
      if(j!=n-1)std::cout<<" ";
    }
    std::cout<<"\n";
  }

  return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,ans=0;
	cin>>n;
	vl a(n),b(n),c(n);
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	rep(i,n-1)cin>>c[i];
	rep(i,n){
		ans+=b[a[i]-1];
		if(i&&(a[i]-1==a[i-1]))ans+=c[a[i-1]-1];
		//puta(ans);
	}
	cout<<ans<<endl;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int n;
  string s;
  cin >> n >> s;
  if (n % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  for (int i = 0; i < n / 2; i++) {
    if (s[i] != s[n / 2 + i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n,c[10][10];

void solve(){
    cin >> n;
    int keta=1;
    Rep(i,1,n+1){
        if(i==10*keta)keta*=10;
        int sta=i/keta,end=i%10;
        //cout << sta << " " << end << " " << endl;
        c[sta][end]+=1;
    }
    ll ans=0;
    rep(i,10){
        rep(j,10){
            ans+=c[i][j]*c[j][i];
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "")
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

void init_io() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(30);
}

int main() {
    init_io();
    ll N, M, C;
    cin >> N >> M >> C;
    V<ll> B(M);
    for(ll &e : B) cin >> e;
    ll ans = 0;
    for(ll i = 0; i < N; i++) {
        V<ll> A(M);
        for(ll &e : A) cin >> e;
        ll tmp = C;
        for(ll j = 0; j < M; j++) tmp += A[j] * B[j];
        if(tmp > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    while True:
        m, f, r = map(int, input().split())
        if (m, f, r) == (-1, -1, -1):
            break

        if m == -1 or f == -1:
            print("F")
            continue

        m = m if m > -1 else 0
        f = f if f > -1 else 0
        r = r if r > -1 else 0
        mf = m + f

        if mf >= 80:
            print("A")
        elif 65 <= mf < 80:
            print("B")
        elif 50 <= mf < 65:
            print("C")
        elif 30 <= mf < 50:
            if r >= 50:
                print("C")
            else:
                print("D")
        else:
            print("F")


if __name__ == "__main__":
    main()

Measured memory_bytes: 5600
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;
const int maxN = 100005;

#define all(x) (x).begin(), (x).end()
#define make_unique(x) (x).resize(unique(all((x))) - (x).begin())

vector <string> v;

int main() {
  string str;
  cin >> str;
  int n = str.length();
  for (int ln = 1; ln <= min(5, n); ++ln) {
    for (int i = 0; i < n - ln + 1; ++i) {
      v.pb(str.substr(i, ln));
    }
  }
  sort(v.begin(), v.end());
  make_unique(v);
  int k;
  cin >> k;
  cout << v[k - 1] << '\n';
  return 0;
}


Measured memory_bytes: 1660
package main

import (
	"fmt"
	"strings"
)

func main() {
	var A, B int
	fmt.Scan(&A, &B)

	N := 50
	h, w := 2*N, 2*N

	Map := make([]string, h)
	for i := 0; i < N; i++ {
		Map[i] = strings.Repeat("#%", N)
		Map[h-1-i] = strings.Repeat(".%", N)
	}

	cnt := 0
	for A-1 > 0 {
		if A-1 >= N {
			Map[cnt*2] = strings.Replace(Map[cnt*2], "%", ".", N)
			A -= N
		} else {
			Map[cnt*2] = strings.Replace(Map[cnt*2], "%", ".", A-1)
			A -= (A - 1)
		}
		cnt++
	}
	for i := 0; i < N; i++ {
		Map[i] = strings.ReplaceAll(Map[i], "%", "#")
	}

	cnt = 0
	for B-1 > 0 {
		if B-1 >= N {
			Map[h-1-cnt*2] = strings.Replace(Map[h-1-cnt*2], "%", "#", N)
			B -= N
		} else {
			Map[h-1-cnt*2] = strings.Replace(Map[h-1-cnt*2], "%", "#", B-1)
			B -= (B - 1)
		}
		cnt++
	}
	for i := 0; i < N; i++ {
		Map[h-1-i] = strings.ReplaceAll(Map[h-1-i], "%", ".")
	}

	fmt.Println(h, w)
	for i := 0; i < h; i++ {
		fmt.Println(Map[i])
	}
}


Measured memory_bytes: 1872
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
 
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
 
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")


#define lli long long int 
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define loopb(i,a,b) for (lli i=a;i>=b;i--)
#define pb push_back
#define mod 1000000007
#define fast() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define gcd(a,b) (__gcd((a),(b)))
#define lcm(a,b)(((a)*(b))/gcd((a),(b)))
#define ma 1e18
#define bc __builtin_popcountll
#define vi vector<lli>
#define pr pair<lli,lli>
#define vp vector<pr>
#define F  first
#define S   second
#define lld long double 
lli h[100002];
lli dp[100002];
lli n;
lli solve(lli num)
{if(dp[num]!=-1)
{return dp[num];
}
else
{if(num==n)
{dp[num]=0;
return 0;
}
else
{if(num+2<=n)
{dp[num]=min(solve(num+1)+abs(h[num+1]-h[num]),solve(num+2)+abs(h[num+2]-h[num]));
return dp[num];
}
else
{dp[num]=solve(num+1)+abs(h[num+1]-h[num]);
return dp[num];
}
}}
}
int main()
{fast();
cin>>n;
mem(dp,-1);
loop(i,1,n+1)
{cin>>h[i];
}
cout<<solve(1)<<"\n";
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define rep(i, n) for(int i=1; i<int(n); i++)
#define ALL(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;

bool comp(ll x, ll y){
	ll dx = 0, dy = 0, nx = x, ny = y;
	while(x > 0){
		dx += x % 10;
		x = (x - (x % 10))/10;
	}
	while(y > 0){
		dy += y % 10;
		y = (y - (y % 10))/10;
	}
	if(nx * dy <= ny * dx) return true;
	else return false;
}

int main(){
	int K; cin >> K;
	vector<ll> ans;
	for(int i=1; i<1000; i++){
		ll c = 0, t = 1;
		rep(j, 14){
			ans.push_back(i*t+c);
			c = c * 10 + 9;
			t *= 10;
		}
	}
	sort(ALL(ans));
	int mi[ans.size()];
	mi[ans.size() - 1] = ans.size() - 1;
	for(int i=ans.size()-2; i>=0; i--){
		if(comp(ans[i], ans[mi[i+1]])){
			mi[i] = i;
		}else{
			mi[i] = mi[i+1];
		}
	}
	int now = 0;
	while(K){
		if(now != 0 && ans[now] == ans[now-1]){ now++; continue; }
		if(comp(ans[now], ans[mi[now]])){
			cout << ans[now] << endl;
			K--;
		}
		now++;
	}
	return 0;
}


Measured memory_bytes: 512
s = input()
s_array = list(set(s))
if len(s_array) == 1:
    print(0)
    exit()

ans = float('inf')
s_len = len(s)
for target in s_array:
    s_check = s
    for i in range(1,s_len):
        count = 0
        s_dosh = [""] * (s_len-i)
        for j in range(s_len-i):
            if s_check[j] == target or s_check[j+1] == target:
                s_dosh[j] = target
            else:
                s_dosh[j] = s[j]
                count = 1
        s_check = ''.join(s_dosh)
        # print(s_check)
        if count == 0:
            ans = min(ans,i)
            break

print(ans)

Measured memory_bytes: 3188
n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break

Measured memory_bytes: 12860
"""
Created on Wed Jan  1 17:06:59 2020
"""

n = int(input())
l = list(map(int, input().split()))
l.sort()
l.reverse()
a = 0
b = 0
for i in range(n):
    if i % 2 == 0:
        a += l[i]
    else:
        b += l[i]
print(a - b)


Measured memory_bytes: 3060
import collections as co
n=int(input())
cnt=0
s=[''.join(sorted(input())) for _ in range(n)]
m=co.Counter(s)
for item in m:
    cnt += m[item]*(m[item]-1)/2
print(int(cnt))
'''
for i in range(1,n):
    for j in range(i):
        if s[j] == s[i]:
            cnt+=1
print(cnt)
'''


Measured memory_bytes: 19760
'use strict'
 
function main(s) {
  let n = s.split('\n')[0].split(' ');
  let target = Number(n[1]+n[2]);
  //console.log(target);
  let ans = target % 4 === 0? 'YES':'NO';
  console.log(ans);
}
 
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

bool dp[85][85][2*85*85];  // dp[i][j][k] : (i,j)の偏りをkにできるならtrue

int main() {
    ll h, w;
    cin >> h >> w;

    vvl a(h, vl(w));
    rep(i, h) {
        rep(j, w) {
            cin >> a[i][j];
        }
    }
    vvl b(h, vl(w));
    rep(i, h) {
        rep(j, w) {
            cin >> b[i][j];
        }
    }

    dp[0][0][abs(a[0][0] - b[0][0])] = true;
    rep(i, h) {
        rep(j, w) {
            exrep(k, 0, 2*80*80) {
                if(dp[i][j][k]) {
                    if(i+1 < h) {
                        dp[i+1][j][k + abs(a[i+1][j] - b[i+1][j])] = true;
                        dp[i+1][j][abs(k - abs(a[i+1][j] - b[i+1][j]))] = true;
                    }
                    if(j+1 < w) {
                        dp[i][j+1][k + abs(a[i][j+1] - b[i][j+1])] = true;
                        dp[i][j+1][abs(k - abs(a[i][j+1] - b[i][j+1]))] = true;
                    }
                }
            }
        }
    }
    
    rep(k, 2*85*85) {
        if(dp[h-1][w-1][k]) {
            out(k);
            re0;
        }
    }

    re0;
}

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

int main()
{
	int N,p=0,w=0,g=0,y=0;

	cin >> N;
	char s[N];

	for(int i = 0; i < N; i++)
	{
		cin >> s[i];
		if(s[i] == 'P')
		{
           p++;
		}
		else if(s[i] == 'W')
		{
		   w++;	
		}
		else if(s[i] == 'G')
		{
			g++;
		}
		else
		{
			y++;
		}
	}

	if(p>0 && w>0 && g>0 && y>0)
	{
		cout << "Four" << endl;
	}

	else if((p==0 && w>0 && g>0 && y>0) || (p>0 && w==0 && g>0 && y>0) || (p>0 && w>0 && g==0 && y>0) || (p>0 && w>0 && g>0 && y==0))
	{
       cout << "Three" << endl;
	}
	else if((p==0 && w==0 && g>0 && y>0) || (p>0 && w==0 && g==0 && y>0) || (p>0 && w>0 && g==0 && y==0))
	{
		cout << "Two" <<endl;
	}
	else if((p==0 && w==0 && g==0 && y>0) || (p>0 && w==0 && g==0 && y==0))
	{
		cout << "One" << endl;
	}
	else
	{
		cout << "Zero" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include <cmath>
using namespace std;

int main(){
    int N,M;
    cin>>N>>M;
    int s[M],c[M],num[N],hantei=1,ans=0;
    for (int i=0;i<N;i++){
        num[i]=-1;
    }
    for (int i=0;i<M;i++){
        cin>>s[i]>>c[i];
        if (num[s[i]-1]==-1) num[s[i]-1]=c[i];
        else if (num[s[i]-1]!=c[i]) hantei=hantei*0;
        if (N>=2){
            if (s[i]==1&&c[i]==0) hantei=hantei*0;
        } 
    }
    for (int i=0;i<N;i++){
        if (num[i]==-1){
            if (i==0) {
                if (M==0&&N==1)num[0]=0;
                else num[0]=1;
            }
            else num[i]=0;
        }
        ans+=pow(10,N-i-1)*num[i];
    }
    if (hantei==0) cout<<"-1"<<endl;
    else cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val edge = Array(n * 3) { mutableSetOf<Int>() }
    for (i in 0 until m) {
        val (u, v) = readLine()!!.split(' ').map(String::toInt)
        edge[(u - 1) * 3].add((v - 1) * 3 + 1)
        edge[(u - 1) * 3 + 1].add((v - 1) * 3 + 2)
        edge[(u - 1) * 3 + 2].add((v - 1) * 3)
    }
    val (s, t) = readLine()!!.split(' ').map(String::toInt)
    val deq = LinkedList<Int>()
    deq.add((s - 1) * 3)
    val deka = 999999998
    val score = Array(3 * n) { deka }
    score[(s - 1) * 3] = 0
    while (deq.isNotEmpty()) {
        val meu = deq.remove()!!
        val meumeu = meu % 3
        edge[meu].forEach {
            if (score[meu] + 1 < score[it]) {
                score[it] = score[meu] + 1
                deq.add(it)
            }
        }
    }
    print(if (score[(t - 1) * 3] % 3 == 0) score[(t - 1) * 3] / 3 else -1)
}


Measured memory_bytes: 171956
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define MM <<" "<<
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setpercision(x)
using ll=long long;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using pl=pair<ll,ll>;
template<class T> inline bool chmin(T& a, T b){
    if(a>b){a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){
    if(a<b){a=b;return true;}return false;}
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};

int main(){
    string S;cin>>S;
    int count=0;
    string now="";
    rep(i,S.size()){
        if(now.size()==2 or now!=S.substr(i,1)){
            now=S.substr(i,1);
            count++;
        }
        else if(S.size()-i>=2){
            now=S.substr(i,2);
            count++;
            i++;
        }
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.*;

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

		String output = sc.next();
		char validate = output.charAt(0);

		if(Character.isUpperCase(validate)){
			output = "A";
		}else {
			output ="a";
		}
		
		System.out.println(output);
	}
}

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

using namespace std;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int k, GCD = 0;
	cin >> k;
	for (int a = 1; a <= k; ++a) {
		for (int b = 1; b <= k; ++b) {
			for (int c = 1; c <= k; ++c) {
				GCD += gcd(gcd(a, b), c);
			}
		}
	}
	cout << GCD << '\n';
	return 0;
}

Measured memory_bytes: 3556
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] count = line.split(" ");
		int a = Integer.parseInt(count[0]);
		int b = Integer.parseInt(count[1]);

		System.out.print((a / b) + " ");
		System.out.print((a % b) + " ");

		double c = (double) a / (double) b;

		System.out.printf("%5f",  c);
	}

}


Measured memory_bytes: 26392
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		const long MOD = 1000000007;
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			int n = cin.Int();
			long x = cin.Long();
			long[] ss = cin.ArrayLong(n);
			Array.Sort(ss);
			Array.Reverse(ss);

			int m = Math.Max((int)ss[0], (int)x) + 1;
			long[,] dp = new long[n + 1, m];
			dp[0, x] = 1;
			for (int i = 0; i < n; i++) {
				long rate = n - i - 1;
				for (long j = 0; j < m; j++) {
					long dst = j % ss[i];
					dp[i + 1, j] = (dp[i + 1, j] + ((dp[i, j] * rate) % MOD)) % MOD;
					dp[i + 1, dst] = (dp[i + 1, dst]  + dp[i, j]) % MOD;
				}
			}

			long ans = 0;
			for (int i = 0; i < m; i++) {
				ans = (ans + ((dp[n, i] * i) % MOD)) % MOD;
			}

			Console.WriteLine(ans);
		}
	}

	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private string[] buf_;
		private int index_;
		Func<string> reader_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => 
			int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

Measured memory_bytes: 166752
#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() {
	int	N;
	cin >> N;
	int i;
	i = 1;
	int	count;
	while (i < 10 && i <= N)
	{
		count++;
		i++;
	}
	i = 100;
	while (i < 1000 && i <= N)
	{
		count++;
		i++;
	}
	i = 10000;
	while (i < 100000 && i <= N)
	{
		count++;
		i++;
	}
	cout << count << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int N;
  scanf("%d",&N);
  int s[N],sum=0,w=101;
  for(int i=0;i<N;i++){
    scanf("%d",&s[i]);
    sum=sum+s[i];
    if(s[i]<w&&s[i]%10!=0){
      w=s[i];
    }
  }
  if(sum%10!=0){
    printf("%d",sum);
  }else if(w==101){
    printf("%d",0);
  }else{
    printf("%d",sum-w);
  }
  return 0;
}


Measured memory_bytes: 128
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include "bits/stdc++.h"

using namespace std;
typedef unsigned long long ll;
typedef int                     integer;
#define int                     long long
#define ii                      pair<int,int>
#define vii                     vector<pair<int,int>>
#define vi                      vector<int>
#define vvi                     vector<vector<int>>
#define f(a,b,c)                for(int a=b;a<c;a++)
#define s(x)                    in>>x
#define s2(x,y)                 in>>x>>y
#define s3(x,y,z)               in>>x>>y>>z
#define s4(x,y,z,w)             in>>x>>y>>z>>w
#define p(x)                    out<<(x)<<endl
#define p2(x,y)                 out<<(x)<<' '<<(y)<<endl
#define p3(x,y,z)               out<<(x)<<' '<<(y)<<' '<<(z)<<endl
#define p4(x,y,z,w)             out<<(x)<<' '<<(y)<<' '<<(z)<<' '<<(w)<<endl
#define p1d(a,n)                for(int ix=0;ix<n;ix++) out<<a[ix]<<(ix == n-1? '':' '); out<<endl
#define p2d(a,n,m)              for(int ix=0;ix<n;ix++){ for(int jx=0;jx<m;jx++) out<<a[ix][jx]<<" "; out<<endl;}
#define pl(x)                   out<<(x)
#define pll(x)                  out<<(x)<<' '
#define range(v)                v.begin(),v.end()
#define rst(x)                  memset(x, -1, sizeof(x))
#define UNVISITED               -1
#define VISITED                 0
#define EXPLORED                2

#define EACH(x, a) for (auto& x: a)
template<class T> void read_v(T& x, std::istream& in) {
    in >> (x);
}
template<class A> void read_vec(vector<A>& x, std::istream& in) {
    EACH(a, x)
        read_v(a, in);
}

bool sortpairbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
template <typename T>
T factmod(T a, T modulus){ int res = 1, i; for (i = 2; i <= a; i++){ res *= i; res%=modulus;} return res; }
template <typename T>
int powmod(T a,T b,int m){ int ans=1; while(b>0){if(b&1){ans*=a;ans%=m;}a*=a;a%=m;b>>=1;} return ans; }
template <typename T>
int power(T a, T b){ int ans=1; while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;}

const int CMOD = 1e9 + 7;
int dp_solve(vector<int>& dp, int n){
    if(n <= 2){return 0;}
    dp[3] = 1;
    vector<int> newdp = dp;
    for(int i = 3 + 1; i <= n; i++){
        dp[i] = (dp[i - 1] + dp[i - 3]) % CMOD;
    }
    return dp[n];
}
void ssolve(std::istream& in, std::ostream& out){
    int n; s(n);
    vector<int> dp(n + 1, 0);
    p(dp_solve(dp, n));
    return;
}

class DRedistribution {
public:
void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    in.tie(nullptr);out.tie(nullptr);
    int t;
    int READ = 0;
    if(READ) s(t);
    else t = 1;
    while(t--){
        ssolve(in, out);
    }
}
};

integer main() {
    DRedistribution solver;
    std::istream& in(std::cin);
     std::ostream& out(std::cout);
     solver.solve(in, out);
}

Measured memory_bytes: 3608
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

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

int main()
{
	int h, w;
	while(scanf("%d%d", &w, &h), w){
		char field[32][32];
		rep(i, h){
			scanf("%s", field[i]);
		}

		int t;
		for(t=0; t<180; ++t){
			int human = 0;
			rep(i, h) rep(j, w){
				int dir = -1;
				if(field[i][j] == 'E') dir = 0;
				if(field[i][j] == 'N') dir = 1;
				if(field[i][j] == 'W') dir = 2;
				if(field[i][j] == 'S') dir = 3;

				if(dir<0)
					continue;
				++human;

				const int dd[] = {3, 0, 1, 2};
				int newdir = dir;
				rep(k, 4){
					int pd = (dir + dd[k]) % 4;
					int py = i + dy[pd];
					int px = j + dx[pd];
					if(field[py][px] == '.' || field[py][px] == 'X'){
						newdir = pd;
						break;
					}
				}
				field[i][j] = "ENWS"[newdir];
			}
			
			char next[32][32];
			rep(i, h) rep(j, w)
				next[i][j] = field[i][j];
			
			rep(i, h) rep(j, w){
				rep(k, 4){
					if(field[i][j] != '.' && field[i][j] != 'X')
						continue;
					
					int py = i + dy[k];
					int px = j + dx[k];
					if(py<0 || h<=py || px<0 || w<=px)
						continue;
					
					if(field[py][px] == "WSEN"[k]){
						if(field[i][j] == '.'){
							next[i][j] = field[py][px];
						}else
							--human;
						next[py][px] = '.';
						break;
					}
				}
			}
			if(human == 0)
				break;
			rep(i, h) rep(j, w)
				field[i][j] = next[i][j];
		}
		if(t == 180)
			puts("NA");
		else
			printf("%d\n", t+1);
	}

	return 0;
}

Measured memory_bytes: 0
#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 7)

# 1 ✕ 1 (str)
S = input().rstrip()

# 1 ✕ 1 (str)
T = input().rstrip()

if len(S) < len(T):
    print("UNRESTORABLE")
    sys.exit()

array = []
for i in range(len(S) - len(T) + 1):
    for t in range(len(T)):
        if S[i + t] not in ("?", T[t]):
            break
    else:
        # tmp = S[0:i]
        # tmp += T
        # tmp += S[i + len(T):]
        # tmp.replace("?", "a")
        # array.append(tmp)
        memo = S[:i] + T + S[i + len(T):]
        array.append(memo.replace('?', 'a'))

if len(array) == 0:
    print("UNRESTORABLE")
else:
    print(min(array))
    # print(sorted(list(map(lambda x:, array)))[0])


Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include <cstring>
#include <vector>
#include <queue>
#include <iomanip>
#include <stack>
#include <set>
#include <iterator>
#include <queue>

using namespace std;
typedef long long ll;

ll ans=1, mx, sum,flag, mn = 1e14, cnt;


int main(){
	ll n,m;
	cin>>n>>m;
	for(ll i=1; i<=n; i++){
		ans *=i%1000000007;
		ans %=1000000007;
	}
	for(ll i=1; i<=m; i++){
		ans *=i%1000000007;
		ans %=1000000007;
	}	
	

	if(abs(n-m)>1) cout<<0;
	else if(n==m){
		cout<<(ans*2)%1000000007;
	}
	else cout<<ans%1000000007;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <typename T> bool chmax(T &a, const T &b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> bool chmin(T &a, const T &b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
const long long INFLL = 1LL << 60;
const long long MOD = 1e9 + 7;

int main() {
    ll N;
    cin >> N;
    for(ll h = 1; h < 3501; h++) {
        for(ll n = 1; n < 3501; n++) {
            if(4.0 * n * h - N * n - N * h == 0) continue;
            double w = (N * n * h) / (4.0 * n * h - N * n - N * h);
            if(ceil(w) == floor(w) && w > 0) {
                cout << fixed << setprecision(0) << h << " " << n << " " << w
                     << endl;
                exit(0);
            }
        }
    }
}


Measured memory_bytes: 3756
#include <stdio.h>

int main(void)
{
	char str[16];
	int i, last;

	while (~scanf("%s", str)){
		last = 9;
		while (last > 0){
			for (i = 0; i < last; i++){
				str[i] = ((str[i] - '0') + (str[i + 1] - '0')) % 10 + '0';
			}
			last--;
		}
		printf("%c\n", *str);
	}

	return (0);
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using ll = long long;
const ll MOD = 1e9 + 7;
const long long INF = 1LL << 60;

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> c(h);
    rep(i, h) cin >> c.at(i);

    int answer = 0;

    for (int hbit = 0; hbit < (1 << h); hbit++)
    {
        for (int wbit = 0; wbit < (1 << w); wbit++)
        {
            // vector<int> hs;
            // vector<int> ws;
            set<int> hs;
            set<int> ws;
            for (int hi = 0; hi < h; ++hi)
            {
                if (hbit & (1 << hi))
                {
                    // hs.push_back(hi);
                    hs.insert(hi);
                }
            }
            for (int wi = 0; wi < w; ++wi)
            {
                if (wbit & (1 << wi))
                {
                    // ws.push_back(wi);
                    ws.insert(wi);
                }
            }

            // cout << "h:" << hbit << ":";
            // for (int i = 0; i < (int)hs.size(); ++i)
            // {
            //     cout << hs.at(i) << " ";
            // }
            // cout << "w:" << wbit << ":";
            // for (int i = 0; i < (int)ws.size(); ++i)
            // {
            //     cout << ws.at(i) << " ";
            // }
            // cout << endl;
            // cout << hbit << endl;

            vector<string> temp_c = c;
            for (int i = 0; i < h;++i){
                for (int j = 0; j < w;++j){
                    if(hs.count(i)!=0 || ws.count(j)!=0)
                        temp_c.at(i).at(j) = 'r';
                }
            }
            int count_black = 0;
            for (int i = 0; i < h; ++i)
            {
                for (int j = 0; j < w;++j){
                    if(temp_c.at(i).at(j)=='#')
                        count_black++;

                }
            }
            if (count_black==k){
                answer++;
            }
        }
    }

    cout << answer << endl;
}

Measured memory_bytes: 3632
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
 
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;

int main(){
	string S;
	int ans=0;
	cin>>S;
	rep(i,S.size()){
		if(S[i]=='1')
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}



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

ll dp[110][110][330];

int main(){
    ll n,mw;cin>>n>>mw;
    ll w[111],v[111];
    rep(i,0,n)cin>>w[i]>>v[i];
    ll geta=w[0];
    rep(i,0,n)w[i]-=geta;
    
    rep(i,0,n){
        rep(j,0,i+1){
            rep(k,0,3*n+1){
                dp[i+1][j+1][k+w[i]]=max(dp[i+1][j+1][k+w[i]],dp[i][j][k]+v[i]);
                dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
            }
        }
    }
    ll an=0;
    rep(j,0,n+1){
        rep(k,0,3*n+1){
            if(j*geta+k<=mw)an=max(an,dp[n][j][k]);
        }
    }
    cout<<an<<endl;
}

    









Measured memory_bytes: 27008
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	void doIt() {
		int n = sc.nextInt();
		int a[] = new int[n];
		long sum = 0l;
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			int num = sc.nextInt();
			a[i] = Math.abs(num);
			sum += a[i];
			if(num < 0)cnt++;
		}
		Arrays.sort(a);
		if(cnt % 2 != 0) {
			sum -= a[0] * 2;
		}
		System.out.println(sum);
	}




	public static void main(String[] args) {
		new Main().doIt();
	}
}


Measured memory_bytes: 51148