akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int diff(int a, int b){
    return a<b?b-a:a-b;
}
int main(){
    int N;
    cin >> N;
    int h[N];
    int cost[N];
    int nowpos=0;
    for(int i=0; i<N; i++){
        cin >> h[i];
    }
    cost[0]=0;
    cost[1]=diff(h[0],h[1]);
    for(int i=2; i<N; i++){
        cost[i] = min( cost[i-1]+diff(h[i],h[i-1]) , cost[i-2]+diff(h[i],h[i-2]) );
    }
    cout << cost[N-1];
    return 0;
}

Measured memory_bytes: 1024
from math import ceil
from decimal import Decimal

N = int(input())
T,A = [],[]
for i in range(N):
    t,a = map(int,input().split())
    T.append(t)
    A.append(a)

t,a = 1,1
for i in range(N):
    r = Decimal(max(ceil(t/T[i]),ceil(a/A[i])))
    t = r*T[i]
    a = r*A[i]

print(t+a)

Measured memory_bytes: 5076
import bisect

n = int(input())
# bisectが昇順のリストにしか対応していないのでマイナスをかける。
# -> ansの順序が昇順で管理できるようになる。最小値をans[-1]で管理する。
A = [- int(input()) for _ in range(n)]

ans = [A[0]]
for a in A[1:]:
  # ansの最小値以下の数値 -> append, else: a > ans[?] を満たす左端の?の値を書き換える。
  if a >= ans[-1]:
    ans.append(a)
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print(len(ans))

Measured memory_bytes: 8604
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n,d;
	cin>>n>>d;

	lli cnt=0;

	lli e = d*2+1;

	lli ans = n/e;
	if(n%e)ans++;
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()

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

	EACH(c, s){
		if(c == '7'){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;


	return 0;
}


Measured memory_bytes: 3036
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
idx=bisect.bisect_left(a,a[-1]//2)
if n==2:
  print(a[1],a[0])
  exit()
if idx==0:
  print(a[-1],a[idx])
else:
  if a[idx]-a[-1]//2<=a[-1]//2-a[idx-1]:
    print(a[-1],a[idx])
  else:
    print(a[-1],a[idx-1])

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

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  int b[N];
  int w[N];
  int cur_rev_num = 0;
  for (int i = 0; i < N; i++) {
    cur_rev_num += (S[i] == '#' ? 1 : 0);
    b[i] = cur_rev_num;
  }
  cur_rev_num = 0;
  for (int i = 0; i < N; i++) {
    cur_rev_num += (S[N-i-1] == '.' ? 1 : 0);
    w[N-i-1] = cur_rev_num;
  }
  int min_rev_num = N;
  for (int i = 0; i < N; i++) {
    min_rev_num = min(min_rev_num, b[i]+w[i]);
  }
  cout << min_rev_num-1 << endl;
}


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

using namespace std;

struct Point {
	double x, y;
};

bool PointInTri(const vector<Point>& tri, const Point& p) {
	int cnt = 0;
	for (int i=1; i<4; i++) {
		Point p0 = tri[i-1], p1 = tri[i%3];
		bool flag0x = (p.x <= p0.x), flag0y = (p.y <= p0.y);
		bool flag1x = (p.x <= p1.x), flag1y = (p.y <= p1.y);
		
		if (flag0y != flag1y) {
			if ( (flag0x == flag1x) && flag0x) {
				cnt += flag0y ? -1 : 1;
			} else if (p.x <= ( p0.x+(p1.x-p0.x)*(p.y-p0.y)/(p1.y-p0.y) ) ) {
				cnt += flag0y ? -1 : 1;
			}
		}
	}
	return cnt!=0;
}

int main() {
	int n; cin >> n;
	
	vector<Point> tri(3);
	for (int i=0; i<n; i++) {
		cin >> tri[0].x >> tri[0].y >> tri[1].x >> tri[1].y >> tri[2].x >> tri[2].y;
		Point p1; cin >> p1.x >> p1.y;
		Point p2; cin >> p2.x >> p2.y;
		bool flag1 = PointInTri(tri, p1), flag2 = PointInTri(tri, p2);
		if ( (flag1 && !flag2) || (!flag1 && flag2) ) cout << "OK" << endl;
		else cout << "NG" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1220
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = Integer.parseInt(in.nextLine());
        if (1800 <= n && n <= 1999) {
            System.out.println(1);
        } else if (1600 <= n && n <= 1799) {
            System.out.println(2);
        } else if (1400 <= n && n <= 1599) {
            System.out.println(3);
        } else if (1200 <= n && n <= 1399) {
            System.out.println(4);
        } else if (1000 <= n && n <= 1199) {
            System.out.println(5);
        } else if (800 <= n && n <= 999) {
            System.out.println(6);
        } else if (600 <= n && n <= 799) {
            System.out.println(7);
        } else if (400 <= n && n <= 599) {
            System.out.println(8);
        }
    }
}


Measured memory_bytes: 35808
N,M = map(int,input().split())
diff = []
for i in range(N):
    like = list(map(int,input().split()))
    like.pop(0)
    diff += like
likesum = 0
for i in range(M):
    if diff.count(i+1) == N:
        likesum += 1
print(likesum)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    map<string,ll> m;
    int n;
    cin>>n;
    rep(i,n){
        string s;
        cin>>s;
        sort(ALL(s));
        m[s]++;
    }
    ll ans=0;
    for(auto x:m){
        ans+=x.second*(x.second-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 11136
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
int main(){
    stack<int> ST;
    stack<pair<int, int> > MIZU;
    char YAMA[2000001];
    int sum = 0;
    
    cin >> YAMA;
    int len = strlen(YAMA);
    for (int i = 0; i < len; i++) {
        if (YAMA[i] == '\\') ST.push(i);
        else if(YAMA[i] == '/' && ST.size() > 0){
            int ker = ST.top();ST.pop();
            sum += i-ker;
            int mymizu = i-ker;
            while (MIZU.size() > 0 && ker < MIZU.top().first) {
                mymizu += MIZU.top().second; MIZU.pop();
            }
            MIZU.push(make_pair(ker,mymizu));
        }
    }
    
    stack<int> ss;
    
    while (MIZU.size() > 0) {
        ss.push(MIZU.top().second);
        MIZU.pop();
    }
    int coun = ss.size();
    printf("%d\n",sum);
    printf("%d",coun);
    while (ss.size() > 0) {
        printf(" %d",ss.top());
        ss.pop();
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 1292
m,f,r = 0,0,0
table = []
i = 0

while m != -1 or f != -1 or r != -1:
  m,f,r = (int(x) for x in input().split())
  table.append([m,f,r])

for p in table:
  m,f,r = p[0],p[1],p[2]
  if m == -1 and f == -1 and r == -1:
    break
  if m == -1 or f == -1:
    print('F')
  elif m + f >= 80:
    print('A') 
  elif m + f >= 65:
    print('B')
  elif m + f >= 50:
    print('C')
  elif m + f >= 30:
    if r >= 50:
      print('C')
    else:
      print('D')
  else:
    print('F')


Measured memory_bytes: 5604
#include<iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

vector<int> g[100005];

int ans[100005];
ll A;
int e[100005];
int maxe,s;
bool use[10005];
int a[10005];
int b[10005];
int main() {
  int n;
  cin >> n;
  for(int i = 0; i < n - 1; i++) {

    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
    e[a[i]]++;
    e[b[i]]++;
  }

  for(int i = 0; i < n; i++) {
    if(maxe < e[i]) {
      maxe = e[i];
      s = i;
    }
  }
  
  vector<int> c(n);
  for(int i = 0; i < n; i++) cin >> c[i];
  sort(c.begin(),c.end(),greater<int> ());

  queue<int> q;
  q.push(s);
  use[s] = true;
  int k = 0;
  while(!q.empty()) {
    int v = q.front();
    q.pop();
    ans[v] = c[k++];
    for(int i = 0; i < g[v].size(); i++) {
      int u = g[v][i];
      if(!use[u]) {
	use[u] = true;
	q.push(u);
      }
    }
  }

  for(int i = 0; i < n - 1; i++) {
    A += min(ans[a[i]],ans[b[i]]);
  }
  cout << A << endl;

  for(int i = 0; i < n - 1; i++) {
    cout << ans[i] <<" ";
  }
  cout << ans[n-1] << endl;
}
  


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

int n, a, b, c, x, y[110];

int main() {
	while (cin >> n >> a >> b >> c >> x, n) {
		rep (i, n) cin >> y[i];
		int cnt = 0, index = 0;
		while (cnt < 10001) {
			if (x == y[index]) index++;
			if (index == n) {
				cout << cnt << endl;
				goto end;
			}
			x = (a * x + b) % c;
			cnt ++;
		}
		cout << -1 << endl;
end:;
	}
	return 0;
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,a[200010];
    long long sum = 0,b[200010];
    cin >> n;
    b[0] = 0;
    a[0] = 0;
    long long mod = 1000000007;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = (b[i-1]+a[i-1]) % mod;
    }
    for(int i = 1; i <= n; i++){
        sum = (sum + a[i]*b[i]%mod)%mod;
    }
    cout << sum << endl;
  return 0;
}


Measured memory_bytes: 5856
# ITP1_11_B: Dice2

class Dice
  Side = Struct.new :neighbors, :back

  class << self
    def layout_sides(top, front, right, left, back, bottom)
      Hash.new.tap do |sides|
        sides[top]    = Side.new [front, right, back, left], bottom
        sides[front]  = Side.new [bottom, right, top, left], back
        sides[right]  = Side.new [bottom, back, top, front], left
        sides[left]   = Side.new [bottom, front, top, back], right
        sides[back]   = Side.new [top, right, bottom, left], front
        sides[bottom] = Side.new [back, right, front, left], top
      end
    end
  end

  def initialize(labels, top = labels[0], front = labels[1])
    @sides = Dice.layout_sides *labels
    put_as top, front
  end

  def put_as(top, front)
    neighbors  = @sides[top].neighbors
    org_idx    = neighbors.index(front)
    step       = org_idx % neighbors.size
    @neighbors = neighbors.rotate(step)
    @top_side  = top
    self
  end

  def pip_of(side)
    case side
    when :top
      @top_side
    when :bottom
      @sides[@top_side].back
    else
      @neighbors.at case side
      when :front then 0
      when :right then 1
      when :back  then 2
      when :left  then 3
      end
    end
  end
end

labels = gets.split.map &:to_i
n_changes = gets.to_i

dice = Dice.new labels
n_changes.times do
  top, front = gets.split.map &:to_i
  puts dice.put_as(top, front).pip_of(:right)
end

Measured memory_bytes: 8664
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>

typedef long long ll;

using namespace std;

int main() {
    string s;
    cin >> s;
    char c = s[s.length() - 1];
    if(c == '3'){
        cout << "bon" << endl;
    } 
    else if(c == '0' || c == '1' || c == '6' || c == '8'){
        cout << "pon" << endl;
    }
    else {
         cout << "hon" << endl;
    }
    
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
main(){
    bool flag=true,flag2;
    int n;
    ll ans=0;
    cin>>n;
    int a[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            ans+=a[i][j];
            flag2=true;
            for(int k=0;k<n;k++){
                if(a[i][k]>a[i][j]+a[j][k])flag=false;
                if(flag2&&i!=k&&j!=k&&a[i][j]==a[i][k]+a[j][k]){
                    ans-=a[i][j];
                    flag2=false;
                }
            }
        }
    }

if(flag)cout<<ans<<endl;
else cout<<-1<<endl;
}

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

const int inf = 1e9 + 1e6;

signed main () {
    int n;
    cin >> n;
    vector < int > x(n), y(n), h(n);
    pair < int, pair < int, int > > check = make_pair(inf, make_pair(-1, -1));
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> h[i];
        if (h[i])
            check = min(check, make_pair(h[i], make_pair(x[i], y[i])));
    }
    for (int cx = 0; cx <= 100; ++cx) {
        for (int cy = 0; cy <= 100; ++cy) {
            int cur_h = 1;
            if (check.first < inf)
                cur_h = check.first + abs(check.second.first - cx) + abs(check.second.second - cy);
            bool ok = 1;
            for (int i = 0; i < n; ++i) {
                if (max(cur_h - abs(x[i] - cx) - abs(y[i] - cy), 0) != h[i])
                    ok = 0;
            }
            if (ok) {
                cout << cx << ' ' << cy << ' ' << cur_h << '\n';
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
N=int(input())
ans=[0 for a in range(11000)]
for i in range(1,101):
  for x in range(1,101):
    for y in range(1,101):
      v=x*x+y*y+i*i+x*y+y*i+i*x
      if v<=N:
        ans[v]+=1
for b in range(1,N+1):
  print(ans[b])

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int flag = 3;
	while( 1 )
	{
		int t = n % 10;
		n /= 10;
		if( t == 2 || t == 4 || t == 5 || t == 7 || t == 9 ) flag = 1;
		else if( t == 0 || t == 1 || t == 6 || t == 8 )
		{
			if( flag == 3 ) flag = 2;
		}
		break; 
	} 
	if( flag == 1 ) cout << "hon" << '\n';
	else if( flag == 2 ) cout << "pon" << '\n';
	else cout << "bon" << '\n';
	return 0;
}


Measured memory_bytes: 3132
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long k = sc.NextLong();
        long[] aa = sc.LongArray();

        long max = aa.Max();
        long gcd = aa[0];
        for (int i = 0; i < n; i++)
        {
            gcd = Gcd(gcd, aa[i]);
        }

        bool ok = true;
        if (k > max)
        {
            ok = false;
        }
        if ((max - k) % gcd != 0)
        {
            ok = false;
        }

        string answer = ok ? "POSSIBLE" : "IMPOSSIBLE";

        Console.WriteLine(answer);
    }

    // 最大公約数（long）
    private static long Gcd(long a, long b)
    {
        if (a < b)
        {
            return Gcd(b, a);
        }
        while (b != 0)
        {
            long r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 38528
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
c = Counter(s)
a,b,c,d = [c['N'], c['S'], c['W'], c['E']]
if (a and b) or (not a and not b):
    if (c and d) or (not c and not d):
        print('Yes')
        quit()
print('No')

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back

typedef long long ll;
typedef pair<int,int> P;
//-----------------------------------------------------------------------

vector<pair<int,P> > p;

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

    for(int i=1;i<=150;i++){
        for(int j=i+1;j<=150;j++){
            p.pb(make_pair(i*i+j*j,P(i,j)));
        }
    }
    sort(p.begin(),p.end());

    int h,w;
    while(cin>>h>>w,h+w){
        pair<int,P> q=make_pair(h*h+w*w,P(h,w));
        pair<int,P> r=*upper_bound(p.begin(),p.end(),q);
        cout<<r.second.first<<" "<<r.second.second<<endl;
    }
}


Measured memory_bytes: 3340
// #define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using V = vector<int>;
using VV = vector<V>;

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;
}
//~ int A = (1<<2) | (1<<3) | (1<<5) | (1<<7);
//~ for (int bit=A; ; bit=(bit-1)&A){
//~ if (!bit) break;
//~ }
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}
//~ int n=5;
//~ int k=3; // nCkの組み合わせ、ただしk=0には対応してない
//~ int bit=(1<<k)-1; // 1000 -> 0111
//~ for(; bit < (1<<n); bit=nex_combination(bit){
//~ }
bool isPrime(int a) {
    if (a == 2) return true;
    if (a <= 1 || a % 2 == 0) return false;

    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return false;
    }
    return true;
}
//~ vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};
vector<int> aaa;
// index が条件を満たすかどうか
bool isOK(int index, int key) {
    if (aaa[index] >= key)
        return true;
    else
        return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
    int ng = -1;  //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok =
        (int)aaa
            .size();  // 「index =
                      // a.size()-1」が条件を満たさないこともあるので、初期値は
                      // a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

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

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//~ int v[100100];
//~ int INF = 1 << 30;
//~ vector<vector<int>> dp(310, vector<int>(310));
//~ ll dp[110][100100];
//~ vector<int> dp(100100, 0));

//~ int seen[110];
//~ int ans[110][2];
//~ ll MOD = 1e9 + 7;

void memo() {
    int n = 100;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    sort(ans.begin(), ans.end(), [&](int i, int j) { return a[i] < a[j]; });

    double t1 = 0.1;
    cout << fixed << setprecision(6) << t1 << endl;
}

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    vector<int> a(m);
    rep(i, m) cin >> a[i];

    int costn = 0;
    int cost0 = 0;
    rep(i, m) {
        if (a[i] < x) cost0++;
        if (a[i] > x) costn++;
    }

    int ans = min(costn, cost0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
#include <iostream>
    using namespace std;
    int main() {
      int a,b;
      string r,g,x;
      cin>>r;
      cin>>g;
      cin>>a>>b;
      cin>>x;
      if(x==r){
          a-=1;
      }
      else{
          b-=1;
      }
        cout<<a<<' '<<b;
     }

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


using namespace std;

int sum;
deque<int>ans;

main()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
    if (n == 2)
    {
        cout << 2;
        return 0;
    }
    if (n == 4)
    {
        cout << 1 << " " << 3;
        return 0;
    }
    int i = 1;
    while (sum + i <= n)
    {
        sum += i;
        i++;
    }
    i--;
    int dif = n - sum;

    dif--;

    int nt = i - dif;

    for (int j = 1; j <= i + 1; j++)
    {
        if (j != nt)ans.pb(j);
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";

}




Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const ll LINF = (ll)1 << 60;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int h1,h2,k1,k2;
  cin>>h1>>h2>>k1>>k2;
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int sum1=0,sum2=0;
  sum1+=h1*a; sum1+=h2*b;
  sum2+=k1*a; sum2+=k2*b;
  sum1+=(h1/10)*c; sum1+=(h2/20)*d;
  sum2+=(k1/10)*c; sum2+=(k2/20)*d;

  if(sum1>sum2){
    cout<<"hiroshi"<<'\n';
  }
  else if(sum1<sum2){
    cout<<"kenjiro"<<'\n';
  }
  else{
    cout<<"even"<<'\n';
  }

  return(0);
}


Measured memory_bytes: 3168
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,all,x;
  cin >> n;
  vector<int>p(n);
  for(int i=0;i<n;i++){
    cin >> p.at(i);
  }
  all=0;
  for(int i=0;i<n;i++){
    all += p.at(i);
  }
  x = p.at(0);
  for(int i=1;i<n;i++){
    if(x<=p.at(i)){
      x = p.at(i);
    }
  }
  cout << all - x/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace io{
	const int l=1<<20;
	char buf[l],*s,*t;
	inline char gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			return s==t?EOF:*s++;
		}
		return *s++;
	}
	char c;
	template<class IT>inline void gi(IT &x){
		x=0;c=gc();while(c<'0'||c>'9')c=gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=gc();}
	}
};
using io::gi;
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
const ll p=998244353ll,inf=1000000000000000000ll;
const int N=100005;
int a[128][N];
char s[N],t[N];int vis[128];
int main(){
	int n,m,i,c,x,y=0;
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	for(i=1;i<=n;++i)vis[s[i]]=1;
	for(i=1;i<=m;++i)if(!vis[t[i]]){printf("-1");return 0;}
	for(c=0;c<128;++c)if(vis[c]){
		x=0;
		for(i=n;i>=1;--i){
			a[c][i]=x;
			if(s[i]==c)x=i;
		}
		for(i=n;i>=1;--i)if(!a[c][i])a[c][i]=x;
//		for(i=1;i<=n;++i)printf("%d ",a[c][i]);printf("\n");
	}
	x=a[t[1]][n];
	for(i=2;i<=m;++i){
		c=t[i];
		if(a[c][x]<=x)++y;
		x =a[c][x];
	}
	printf("%lld",(((ll)y)*n)+x);
	return 0;
}

Measured memory_bytes: 12800
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

int main()
{
	string s;

	cin >> s;

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

	for (int i = 0; i + 1 < s.size(); i++) {
		if (s[i] == s[i + 1]) {
			cout << "no" << endl;
			return(0);
		}
	}
	cout << "yes" << endl;

	return (0);
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC087A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, a, b, p1, p2, x;
            var word = Console.ReadLine().Split(' ');
            n = int.Parse(word[0]);
            a = int.Parse(word[1]);
            b = int.Parse(word[2]);
            x = a * n;
            if (x > b)
                x = b;
            p1 = (a * n); p2 = b;
            Console.WriteLine(x);
            Console.ReadKey();
 }}}

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

int main() {
  string s;
  cin >> s;
  
  int min = 1000;
  int n = 753;
  
  int h=0;
  int t=0;
  int o=0;
  
  for(int i=0; i < s.size()-2; i++){
    
    h=100 * (s.at(i)-'0');
    t=10 * (s.at(i+1)-'0');
    o=1 * (s.at(i+2)-'0');
      
    if(h+t+o >= n){
      if(h+t+o - n <= min){
      min = h+t+o - n;
      }
    }
    
    else{
      if(n - (h+t+o) <= min){
      min = n - (h+t+o);
      }
    }
    
  }
  
  cout << min << endl;
  
	return 0;
}


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

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

    string ans = "APPROVED";

    for(int i=0;i<N;i++){
        if(A[i] % 2 == 0){
            if(A[i] % 3 != 0 and A[i] % 5 != 0){
                ans = "DENIED";
                break;
            }
        }
    }

    cout << ans << endl;
    return 0; 
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAXSIZE 200

int get_num2(int x);

int main(void){
    int n;
    scanf("%d", &n);
    int a[MAXSIZE], min = 100;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        int num2 = get_num2(a[i]);
        if(num2 < min) min = num2;
    }
    printf("%d\n", min);
    return 0;
}

int get_num2(int x){
    int num2 = 0;
    while(x % 2 == 0){
        x /= 2;
        num2++;
    }
    return num2;
}

Measured memory_bytes: 128
#include <algorithm>
#include <array>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <utility>

using namespace std;

#define E18 1000000000000000000

int main() {
  long long a;

  cin >> a;

  string b_str;

  cin >> b_str;

  // b_strを100倍したlong longに変換
  long long b;
  int dot_pos = b_str.find(".");
  if (dot_pos != string::npos) {
    b_str.replace(dot_pos, 1, "");
  }
  b = stoll(b_str);

  cout << a * b / 100 << endl;

  return 0;
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
typedef pair<ll,ll> ipair;
#define F first
#define S second
 
/*
//functions from gfg
 
long long int power(long long int x,long long int y,long long  int p)
{
    long long int res = 1;     // Initialize result
 
    x = x % p;  // Update x if it is more than or 
                // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            {//d=(long double)x/p;
            res = (res*x) % p;
            }
 
        // y must be even now
        y = y>>1; // y = y/2
        x=(x*x)%p;
        
    }
    return res%p;
}
 
long long int gcd(long long int a,long long int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
}
 
long long int binomialCoeff(long long int n, ll k) 
{ 
    ll res = 1; 
  
    // Since C(n, k) = C(n, n-k) 
    if (k > n - k) 
        k = n - k; 
  
    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] 
    for (ll i = 0; i < k; ++i) 
    { 
        res *= (n - i); 
        res /= (i + 1); 
    } 
  
    return res; 
} 
 

void sieve(int n, vector<ll> &primes) 
{ 
    vector<int> prime(n,1);
    ll p;
    for ( p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == 1) 
        { 
            
            for (int i=p*p; i<=n; i += p) 
                prime[i] = 0; 
        } 
    } 
  
    for(p=2;p<=n;p++)
    {
        if(prime[p])
        primes.pb(p);
    }
   
} 


void dfs(vector<ll> adj[] ,ll src,vector<ll> &vis)
{
    vis[src]=1;
    for(ll i=0;i<adj[src].size();i++)
    {
        if(vis[adj[src][i]]==0)
        dfs(adj,adj[src][i],vis)
    }
}
 
*/

int main() {
    ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    
    ll n,i,j,p,k,m,t,ans=0;
    cin>>n>>t;
    ll dp[3005][3005];
    memset(dp, 0, sizeof(dp)); 
    vector<ll> a(n),b(n);
    vector<pair<ll,ll> > val(n);
    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        val[i].F=a[i];
        val[i].S=b[i];
    }
    sort(val.begin(),val.end());
    for(i=0;i<n;i++)
    {
        a[i]=val[i].F;
        b[i]=val[i].S;
    }
    for(i=0;i<t;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i+a[j]<t)
            {
                dp[j+1][i+a[j]] = max(dp[j][i]+b[j],dp[j+1][i+a[j]]);
            }
            
            dp[j+1][i] = max(dp[j][i],dp[j+1][i]);
            
        }
    }
    for(i=0;i<n;i++)
    {
        ans=max(ans,dp[i][t-1]+b[i]);
    }
    cout<<ans<<endl;
    
    // for(i=0;i<n;i++)
    // {
    //     cout<<a[i]<<" ";
    // }
    // cout<<endl;
    
    return 0;
}

Measured memory_bytes: 74312
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int N;
vector<int> g[100010];
int K;
ll val[100010];
const ll INF=1e12;

ll L[100010],R[100010];

void fail(){
    cout<<"No"<<endl;
    exit(0);
}

pair<ll,ll> predfs(int now,int par){
    ll l=-INF,r=INF;
    for(auto nex:g[now]){
        if(nex==par) continue;
        ll a,b;
        tie(a,b)=predfs(nex,now);
        if(a==-INF-1) continue;
        if(l!=-INF&&l%2!=a%2) fail();
        l=max(l,a);
        r=min(r,b);
        if(r<l) fail();
    }
    L[now]=l;
    R[now]=r;

    if(val[now]>=0){
        if(l==-INF){
            L[now]=val[now];
            R[now]=val[now];
        }else if(l<=val[now]&&val[now]<=r&&l%2==val[now]%2){
            L[now]=val[now];
            R[now]=val[now];
        }else fail();
    }
    return mkp(L[now]-1,R[now]+1);
}

void dfs(int now,int par,ll parentVal){
    if(parentVal-1>=L[now]&&parentVal-1<=R[now]) val[now]=parentVal-1;
    else val[now]=parentVal+1;

    for(auto nex:g[now]){
        if(nex==par) continue;
        dfs(nex,now,val[now]);
    }
    return;
}

int main(){
  cin>>N;
  for(int i=0;i<N-1;i++){
      int a,b;
      cin>>a>>b;
      a--;b--;
      g[a].push_back(b);
      g[b].push_back(a);
  }
  for(int i=0;i<=N;i++) val[i]=-1;
  cin>>K;
  for(int i=0;i<K;i++){
      int v,p;
      cin>>v>>p;
      v--;
      val[v]=p;
  }

  predfs(0,-1);
  dfs(0,-1,L[0]+1);

  cout<<"Yes"<<endl;
  for(int i=0;i<N;i++) cout<<val[i]<<endl;

  return 0;
}


Measured memory_bytes: 16640
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
template<typename V> constexpr typename V::value_type sum(const V &v) { return accumulate(all(v), 0); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int n, m, p;
  while (cin >> n >> m >> p, n) {
    m--;
    int s = 0;
    int x[n];
    rep(i, n) {
      cin >> x[i];
      s += x[i];
    }
    s *= (100 - p);
    cout << (x[m] ? s / x[m] : 0) << endl;
  }
}

Measured memory_bytes: 3056
using System;
using System.IO;
using System.Linq;

namespace ABC163C {
    class Program {
        static void Main(string[] args) {
            var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
            Console.SetOut(sw);

            var n = int.Parse(Console.ReadLine());
            var employees = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var decs = new int[n-1];

            for (var i = 0; i < employees.Length; i++) {
                decs[employees[i]-1] = decs[employees[i]-1] + 1;
            }

            foreach (var i in decs) {
                Console.WriteLine(i);
            }

            Console.WriteLine(0);
            
            Console.Out.Flush();
        }
    }
}

Measured memory_bytes: 43684
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()

a = li()
min_cost = float('inf')

for i in range(2**n):
    select = []
    a2 = a.copy()
    for j in range(n):
        if (i >> j)&1:
            select.append(j)

    if(len(select) != k):
        continue

    cost = 0
    b_max = a2[0]
    for j in range(1,n):
        if j in select:
            if(a2[j] <= b_max):
                cost += b_max+1 - a2[j]
                a2[j] = b_max+1
        b_max = max(b_max, a2[j])
    min_cost = min(min_cost, cost)

print(min_cost)

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

long long n, p;


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

int main(){
  cin >> n >> p;
  map<long long, int> mp;
  mp = prime_factor(p);
  long long res = 1;
  for(pair<long long, int> x : mp){
    res *= pow(x.first, x.second/n);
  }
  cout << res << endl;
  return 0;
}


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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e15;

int main() {
  ll n;
  cin >> n;
  vector<ll> p(n);
  REP(i, n) cin >> p[i];

  ll ans = 1;
  ll mn = p[0];
  FOR(i, 1, n) {
    if (p[i] <= mn) ++ans;
    mn = min(mn, p[i]);
  }

  cout << ans << endl;
  return 0;
}

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

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

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

template<typename T> inline T divrup(T a, T b) { if (a % b) return a/b+1; else return a/b;}

#define dbg_v1(i,V) do{cout<<"-v1----\n";rep(i,V.size())cout<<" "<<i<<"\t:"<<V[i]<<endl;cout<<endl;}while(0)
#define dbg_v2(i,k,V) do{cout<<"-v2----\n";rep(i,V.size()){rep(k,V[0].size())cout<<" "<<V[i][k];cout<<endl;}}while(0)

int main() {
    ios::sync_with_stdio(false);//stdoutとcoutの同期解除
    cin.tie(nullptr);//cinとcoutの同期解除
    
    int A,B;
    cin >>A>>B;
    //-----------------------------------
    int ans=B;
    if(A<=5)ans=0;
    else if(A<=12)ans/=2;


    cout << ans <<endl;
    return (0);
}

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

int M,N,K,D[3][1001][1001];
char c[1000][1005];

int check(char c){
	if(c=='J') return 0;
	if(c=='O') return 1;
	return 2;
}

int main(){
	scanf("%d%d%d",&M,&N,&K);
	for(int i=0;i<M;i++) scanf("%s",c[i]);
	D[check(c[0][0])][1][1]=1;
	for(int k=0;k<3;k++) for(int i=1;i<=M;i++) for(int j=1;j<=N;j++)
		D[k][i][j]=D[k][i-1][j]+D[k][i][j-1]-D[k][i-1][j-1]+(k==check(c[i-1][j-1]));
	for(int i=0;i<K;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int res[3];
		for(int k=0;k<3;k++) printf("%d%s",D[k][c][d]-D[k][a-1][d]-D[k][c][b-1]+D[k][a-1][b-1],k==2?"\n":" ");
	}
}

Measured memory_bytes: 13872
#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 x, a, b; cin >> x >> a >> b;
    string ans;
    if(abs(x-a) < abs(x-b)) ans = "A";
    else ans = "B";
    cout << ans;
}


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

int main()
{
	int N;
	cin >> N;
	
	int max_mod = 0;
	for (int i = 0; i < N; ++i)
	{
		int a;
		cin >> a;

		max_mod += a - 1;
	}

	cout << max_mod << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskB solver = new TaskB();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskB {

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int[] arr = in.nextIntArray(n);
      Arrays.sort(arr);
      out.println(arr[n - 1] - arr[0]);
    }

  }

  static class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 13];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == -1) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return -1;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    }

    public int[] nextIntArray(int n) {
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = nextInt();
      }
      return arr;
    }

  }
}



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

#define INF (1<<30)
#define MP make_pair

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

class State
{
public:
	int x,y,c;
	State(int x, int y, int c)
	:x(x),y(y),c(c)
	{}
};

int main()
{
	int W,H,t;
	while(cin >> W >> H, W||H)
	{
		int nodeX[32][32][32]={0};
		int nodeY[32][32][32]={0};		

		for(int y=0; y<H; y++)
		{
			for(int x=0; x<W-1; x++)
			{
				cin >> t;
				nodeX[x][x+1][y] = t;
				nodeX[x+1][x][y] = t;
			}
			
			if(y!=H-1)
			for(int x=0; x<W; x++)
			{
				cin >> t;
				nodeY[x][y][y+1] = t;
				nodeY[x][y+1][y] = t;
			}
		}

		queue<State> q;
		
		q.push(State(0,0,1));
		
		bool h[35][35]={0};
		
		bool g=false;
		while(!q.empty())
		{
			State s=q.front(); q.pop();
			if(s.x == W-1 && s.y == H-1)
			{
				g=true;
				cout << s.c << endl;
				break;
			}
			
			for(int i=0; i<2; i++)
			{
				int tx=s.x+dx[i], ty=s.y+dy[i];
				if(tx<0||ty<0||tx>=W||ty>=H) continue;
				if(nodeX[s.x][tx][ty]==1) continue;
				
				
				if(h[tx][ty]) continue;
				h[tx][ty]=1;
				
				q.push(State(tx,ty,s.c+1));
				
				
			}
			for(int i=2; i<4; i++)
			{
				int tx=s.x+dx[i], ty=s.y+dy[i];
				if(tx<0||ty<0||tx>=W||ty>=H) continue;
				
				if(nodeY[tx][s.y][ty]==1) continue;
				
				if(h[tx][ty]) continue;
				h[tx][ty]=1;
				
				q.push(State(tx,ty,s.c+1));
			}
			
		}
		
		if(!g) cout << 0 << endl;
		
	
	}

}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------

void _main() {
	int S;
	cin >> S;
	int A = (S / 100);
	int B = (S % 100);
	/*どちらも13以上またはどちらも0ならＮＡ
	Aが13以上または０かつＢが13以下ならＹＹＭＭ
	Aが13以下かつBが13以上または0ならＭＭＹＹ
	それ以外ならＡＭＢＩ
	*/
	string ans = (A >= 13 && B >= 13 || (A==0)&&(B == 0)|| (A==0)&&(B>=13)||(A>=13&&B==0)) ? "NA" : (A >= 13|| A==0) && B < 13? "YYMM" : (A <= 13 && (B >= 13|| B == 0)) ? "MMYY" : "AMBIGUOUS";
	cout << ans << endl;
}

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

#define YES "Yes"
#define NO "No"
#define NINE (int)9
#define ASCII_0 48
#define CHAR_END_1 '\n'
#define CHAR_END_2 '\0'

int main()
{
    char get_c = 0;
    int sum_get_c = 0;

    get_c = getchar();

    while ((get_c != CHAR_END_1)&&(get_c != CHAR_END_2))
    {
        sum_get_c += (get_c - ASCII_0);

        if (sum_get_c > NINE)
        {
            sum_get_c %= NINE;
        }

        get_c = getchar();
    }

    if ((sum_get_c%NINE) == 0)
    {
        printf("%s", YES);
    } else {
        printf("%s", NO);
    }
    

    return 0;
}

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

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ( abs(a-c) <= d || abs(a-b) <= d && abs(b-c) <= d ) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include        <map>
#include      <cmath>
#include      <queue>
#include     <string>
#include     <cstdio>
#include     <vector>
#include    <cstring>
#include   <iostream>
#include  <algorithm>
using namespace std;
#define ll long long
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 500+5;
const ll mod = 1e9+7;


int main(){
    int a, b;
    scanf("%d%d",&a,&b);
    for(int i=max(-1000000,b-a+1);i<=min(1000000,b+a-1);i++){
        printf("%d%c",i," \n"[i==min(1000000,b+a-1)]);
    }
    return 0;
}


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

#define fi first
#define se second
#define show(x) cerr << #x << "=" << "\n"
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

string s;
int k;
char c[100];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1 = freopen("in.txt", "r", stdin);
  //stream2 = freopen("out.txt", "w", stdout);
  if (stream1 == NULL) return 0;
  //if (stream2 == NULL) return 0;:w
#endif
  cin >> s >> k;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 26; j++) {
      c[26 * i + j] = (char)('a' + j);
    }
  }
  int n = (int)s.size();
  for (int i = 0; i < n; i++) {
    int tmp = (26 - (int)(s[i] - 'a')) % 26;
    if (tmp > 0 && tmp <= k) {
      s[i] = 'a';
      k -= tmp;
    }
  }
  if (k > 0) {
    k %= 26;
    s[n - 1] = c[s[n - 1]- 'a' + k];
  }
  cout << s << endl;
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
  #include "dbgtoki.hpp"
  #define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i)  
#else
  #define DUMP(i)  
#endif

#define GETTYPE(i) 
#define TOSTRING(x) #x
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

const int EPS = 1e-9;

int main (){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x,y;
  while(cin >> x >> y){
    int ans = x + y;
    if(x > y) swap(x , y);
    FOR(i,1,max(x,y)){
      if(x * i % y == 0){
	ans--;
      }
      
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3220
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int x[500];
int ans[250000];
vector <int> v[250000];

int main() {
    int n, i, j;
    priority_queue <pair<int, int> > q;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d", &x[i]);
    
    for (i = 0; i < n; i++) {
        x[i]--;
        
        for (j = 0; j < i; j++) q.push(make_pair(-x[i], i + 1));
        
        ans[x[i]] = i + 1;
        
        for (j = 0; j < n - i - 1; j++) v[x[i]].push_back(i + 1);
    }
    
    for (i = 0; i < n * n; i++) {
        if (ans[i] > 0) {
            if (q.size() > 0 && -q.top().first <= i) {
                puts("No");
                
                return 0;
            }
            
            for (j = 0; j < v[i].size(); j++) q.push(make_pair(-1e9, v[i][j]));
        } else {
            if (q.empty()) {
                puts("No");
                
                return 0;
            }
            
            ans[i] = q.top().second;
            
            q.pop();
        }
    }
    
    puts("Yes");
    
    for (i = 0; i < n * n; i++) {
        if (i > 0) putchar(' ');
        printf("%d", ans[i]);
    }
    
    puts("");
    
    return 0;
}


Measured memory_bytes: 10096