akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8

# https://atcoder.jp/contests/abc119


def main():
    N = int(input())
    x, u = [None] * N, [None] * N

    for i in range(N):
        line = input().split()
        x[i], u[i] = float(line[0]), line[1]
    
    jpy = 0
    btc = 0.0
    for i in range(N):
        if u[i] == "BTC":
            btc += x[i]
        else:
            jpy += x[i]
    
    return jpy + 380000.0 * btc


print(main())


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 3e3;
int n, a[nsz + 5];
num dp[nsz + 5][nsz + 5], ans;

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    cont (i, n) {
        cin >> a[i];
        dp[i][i] = a[i];
    }
    circ (len, 2, n) {
        for (int l = 1, r = len; r <= n; ++l, ++r) {
            if (len & 1) {
                dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r]);
            } else {
                dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r]);
            }
        }
    }
    ans = dp[1][n] * ((n & 1) ? 1 : -1);
    cout << ans << ln;
}


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

// #define int long long

/* short */
#define pb push_back
#define print(Target) cout << Target << '\n'

/* REPmacro */
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPS(i, a, n) for (int i = (a); i < (n); i++)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* func */
inline bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}

/* const */
const int INF = INT_MAX;

int dp[31];

int shinobu(int n)
{
  if (dp[n] != -1){
    return (dp[n]);
  }
  if (n == 1) return (1);
  if (n == 2) return (2);
  if (n == 3) return (4);
  return (dp[n] = shinobu(n - 1) + shinobu(n - 2) + shinobu(n - 3));
}

signed main()
{
  ios::sync_with_stdio(false);
  int n;

  while (cin >> n, n){
    fill(dp, dp + 31, -1);
    print(shinobu(n) / 3650 + 1);
  }
  return (0);
}

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

using namespace std;

const ll mod=1e9+7;


int main(){
    ios;
    ll h,w;
    cin >> h >> w;
    vector<vector<ll>> a(h,vector<ll>(w)),b(h,vector<ll>(w)),c(h,vector<ll>(w));
    vector<vector<vector<ll>>> dp(h+1,vector<vector<ll>>(w+1,vector<ll>(10005)));
    rep(i,h){
        rep(j,w){
            cin >> a[i][j];
        }
    }
    rep(i,h){
        rep(j,w){
            cin >> b[i][j];
            c[i][j]=abs(a[i][j]-b[i][j]);
        }
    }
    rep(i,h){
        rep(j,w){
            if(i==0 && j==0){
                dp[i+1][j+1][c[i][j]]=1;
                continue;
            }
            for(ll k=0;k<=10000;k++){
                if(k+c[i][j]<=10000 && (dp[i+1][j][k] || dp[i][j+1][k])){
                    dp[i+1][j+1][k+c[i][j]]=1;
                }
                if(dp[i+1][j][k] || dp[i][j+1][k]){
                    dp[i+1][j+1][abs(k-c[i][j])]=1;
                }
            }
        }
    }
    
    for(ll k=0;k<=10000;k++){
        if(dp[h][w][k]){
            cout << k << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 522728
N=int(input())
wordcount={}
for i in range(N):
  s=str(input())
  wordcount[s]=wordcount.get(s,0)+1
M=int(input())
for i in range(M):
  s=str(input())
  wordcount[s]=wordcount.get(s,0)-1
counter=wordcount.values()
f=max(counter)
if f>=0:
  print(f)
else:
  print(0)



Measured memory_bytes: 3060
#include <iostream>
#include <queue>

using namespace std;

bool ok(int k, int p, queue<int> ws)
{
    int t = 0;
    while (!ws.empty()) {
        int w = ws.front();
        if (w > p)
            return false;
        if (t + w <= p) {
            t += w;
            ws.pop();
        } else {
            --k;
            t = 0;
        }
    }
    
    if (k <= 0)
        return false;
    else
        return true;
}

int main(void)
{
    int k, n, l = 0, r = 1000000000;
    queue<int> ws;
    
    cin >> n >> k;
    for (int i=0; i<n; i++) {
        int w; cin >> w;
        ws.push(w);
    }

    while (l+1 < r) {
        int m = (l+r)/2;
        ok(k, m, ws) ? r = m : l = m;
    }
    cout << (ok(k, r, ws) ? r : l) << endl;

    return 0;
}

Measured memory_bytes: 1952
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 0");
            WillReturn.Add("1 3");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("50");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 0");
            WillReturn.Add("1 1 1");
            //4
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("45 1");
            WillReturn.Add("17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26");
            //17592186044416
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int P = wkArr[1];

        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        //場合の数[2を法とした余り]のDP表
        long[] PrevDP = new long[2];
        PrevDP[0] = 1;

        foreach (int EachInt in AArr) {
            long[] CurrDP = (long[])PrevDP.Clone();
            for (int I = 0; I <= 1; I++) {
                if (PrevDP[I] == 0) continue;

                long NewI = (I + EachInt) % 2;
                CurrDP[NewI] += PrevDP[I];
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[P]);
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<P> vp;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    int a,b;
    cin >> a >> b;
    if(a == 0 || b == 0){
        cout << "Zero\n";
    }else if(a < 0 && b > 0){
        cout << "Zero\n";
    }else if(a > 0 && b > 0){
        cout << "Positive\n";
    }else if((b-a)%2 == 0){
        cout << "Negative\n";
    }else{
        cout << "Positive\n";
    }
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())

global fri
fri=[]
global tab
tab=[0]*n
def run(nn):
  #print(tab)
  global cnt
  if tab[nn]:
    return
  tab[nn]=1
  cnt+=1
  for i in fri[nn]:
    que.append(i)
for i in range(n):
  fri.append([])
for i in range(m):
  a,b=map(int,input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
i=0
mx=0
cc=0
while i<n:
  if tab[i]:
    i+=1
    continue
  que=[i]
  cnt=0
  while len(que)!=0:
    run(que.pop())
  mx=max(cnt,mx)
  i+=1
  cc+=1
print(cc-1)



Measured memory_bytes: 26548
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int ans = 0;
    int n;
    cin >> n;
    int arr[3][n + 1];
    memset(arr,0,sizeof(arr));
    for(int i = 1 ; i <= 2 ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            if(j == 1)
            cin >> arr[i][j];
            else
            {
                int v;
                cin >> v;
                arr[i][j] = v + arr[i][j - 1];
            }
        }
    }
    
    int mx = INT_MIN;
    for(int i = 1 ; i <= n ; i++) {
        mx = max(mx ,arr[1][i] + (arr[2][n] - arr[2][i - 1]));
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for x in range(m)]

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(list(filter(lambda x: len(x) == n, ends))))


Measured memory_bytes: 5236
s=input()
n=len(s)
def f(s):
    m=len(s)
    for i in range(-(-m//2)):
        if s[i]!=s[-1-i]:
            return False
    return True

if f(s) and f(s[:(n-1)//2]) and f(s[((n+3)//2)-1:]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9024
#include <bits//stdc++.h>
using namespace std;
#define rep(i,n,k) for(int i=n;i<k;i++)
#define int  long long
#define F first 
#define S second
#define P make_pair 
struct Runrun{
    vector<int> r;
};

signed main(void){
 
    
    int n,m,q,p,r,ans,t;
    string s;
    vector<int> v;
    ans=0;
    cin>>n;
    int a[n+1];
    a[0]=0;
    rep(i,1,n+1){
        int x,y;
        y=1;
        x=1;
        a[i]=a[i-1]+1;
        rep(j,1,10){
            x=x*6;
            if(i-x<0)
            break;
            a[i]=min(a[i-x]+1,a[i]);
        }
        x=1;
        rep(j,1,10){
            x=x*9;
            if(i-x<0)
            break;
            a[i]=min(a[i-x]+1,a[i]);
        }
       
    }
    cout<<a[n]<<endl;
  
}


Measured memory_bytes: 1024
def main():
    a,b,c = map(int, input().split())
    
    ab = [i for i in range(a, b + 1)]
    cnt = 0 #count
    for x in range(len(ab)):
        if c % ab[x] == 0:
            cnt += 1
        else:
            pass
    
    print(cnt)


if __name__ == "__main__":
    main()

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

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int in;cin >> in;
    if (in & 1 && i & 1) ans++;
  }
  cout << ans;
}            


Measured memory_bytes: 3568
/*
    Author: Alam Khan
    AUST CSE 40th Batch

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef deque<ll> dl;
typedef stack<ll> stl;
typedef set<ll> sl;
typedef map<string, ll> msl;
typedef map<ll,ll> mll;
#define sf(n)     scanf("%lld",&n)
#define sff(n,m)     scanf("%lld %lld",&n,&m)
#define sfff(n,m,r)     scanf("%lld %lld %lld",&n,&m,&r)
#define sfs(n)     scanf("%s",n)
#define pf(n)     printf("%lld\n",n)
#define pff(n,m)     printf("%lld %lld\n",n,m)
#define pfff(n,m,r)     printf("%lld %lld %lld\n",n,m,r)
#define pfs(n)     printf("%s\n",n)
#define pfcs(i,n)     printf("Case %lld: %lld\n",i,n)
#define pb     push_back
#define prf     printf
#define inf     2e18
#define low     -1000000000000
#define PI        acos(-1.0)
#define rep1(i,n) for(i=1;i<n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define repe1(i,n) for(i=1;i<=n;i++)
#define repe0(i,n) for(i=0;i<=n;i++)
#define repe(i,a,n) for(i=a;i<=n;i++)
#define endl  "\n"
#define FAST  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr freopen("input.txt","r",stdin)
#define fw freopen("output.txt","w",stdout)
ll a[200009];
int main()
{
    ll i,n,t,k,j,x=0,y=0,m;
    sff(k,n);
    rep0(i,n)
    {
        sf(a[i]);
    }
    x = inf;
    for(i=1;i<n-1;i++)
    {
       x  = min(a[i]-a[i+1]+k,x);
       x = min(x,a[i-1]+k-a[i]);
    }
    x = min(x,a[n-1]-a[0]);
    x= min(x,a[0]-a[1]+k);
    x = min(a[n-2]+k-a[n-1],x);
    cout<<x<<endl;
    return 0;
}



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

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                sum += gcd(gcd(i, j), k);
            }
        }
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 3672
function main(){
  var i = 0;
  while(true){
    var fieldInfo = input[i].split(' ');
    var width = fieldInfo[0] - 0;//toInt
    var height = fieldInfo[1] - 0;//toInt

    // 0 0が入力された
    if(!width && !height){
      break;
    }

    var start;
    var goal;
    var elem = [[],[],[],[],[]];
    for(var ei = 0;ei < 5; ei++){
      elem[ei].length = 0;
    }
    
    for(var y = 0; y < height; y++){
      i++;//1行進める
      for(var x = 0; x < width; x++){
        var c = input[i][x];

        switch(c){
        case 'S':
          start = new Pos(x, y);
          break;
        case 'G':
          goal = new Pos(x, y);
          break;
        case '.':
          break;
        default : // 入力値が正しいので、絶対に属性
          elem[c-1][elem[c-1].length] = new Pos(x, y);
          break;
        }
      }
    }

    
    var bestElement = -1;
    var distance = Infinity;
    
    // 属性ごとにループ
    for (var startElem = 0; startElem < 5; startElem++) {
      // DPの初期化 DP[属性][同じ属性内の連番]
      var dp = [[],[],[],[],[]];
      for(var h = 0; h < 5; h++){
        var hLength = elem[h].length;
        dp[h].length = hLength;
        for(var hidx = 0; hidx < hLength; hidx++){
          dp[h][hidx] = Infinity;
        }
      }
      
      // 最初に選んだパチモンから次に捕まえられる属性番号
      var first = (startElem + 1) % 5;

      for (var j = 0, firstLength = elem[first].length; j < firstLength; j++) {
        // s→e1を計算
        dp[first][j] = dist(start, elem[first][j]);
      }
      
      // s->1->2->3->4->g
      // なので、ループは間の-> * 3分まわす
      for (var e = 0; e < 3; e++) {
        // ex->e(x+1)
        var now = (first + e) % 5;
        var next = (now + 1) % 5;

        for (var j = 0, nowLength = elem[now].length; j < nowLength; j++) {
          for (var k = 0, nextLength = elem[next].length; k < nextLength; k++) {
            dp[next][k] = min(
              dp[next][k],
              dp[now][j] + 
                  dist(elem[now][j], elem[next][k]));
          }
        }
      }
      
      var last = (first + 3) % 5;
      var lastLength = elem[last].length;
      for (var j = 0; j < lastLength; j++) {
        // e4->g
        var d = dp[last][j] + 
                    dist(elem[last][j], goal);
        
        if (d < distance) {
          distance = d;
          bestElement = startElem + 1;
        }
        
      }
      
    }
    
    if (distance == Infinity) {
      console.log("NA");
    } else {
      console.log(bestElement + " " + distance);
    }

    i++;
  }
  

}

function dist(from, to){
  return Math.abs(from.x - to.x) + Math.abs(from.y - to.y)
}

function min(a1, a2){
  return a1 < a2 ? a1 : a2;
}

function Pos(a, b){
  this.x = a;
  this.y = b;
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  main();
});

Measured memory_bytes: 63484
import heapq
from collections import defaultdict

n, m, s, t = map(int, input().split())

money = defaultdict(set)
snuke = defaultdict(set)
for i in range(m):
    a, b, c, d = map(int, input().split())
    money[a-1].add((b-1, c))
    money[b-1].add((a-1, c))
    snuke[a-1].add((b-1, d))
    snuke[b-1].add((a-1, d))

def dijkstra(n, v, dedic):
    d = [float('inf')] * n
    d[v] = 0

    hq = [(0, v)]

    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in dedic[u]:
            if d[nv] > d[u] + c:
                d[nv] = d[u] + c
                heapq.heappush(hq, (d[u] + c, nv))

    return d

money_cost = dijkstra(n, s - 1, money)
snuke_cost = dijkstra(n, t - 1, snuke)

result = [10 ** 15 for _ in range(n)]
temp = 10 ** 15
for i in range(n - 1, -1, -1):
    temp = min(money_cost[i] + snuke_cost[i], temp)
    result[i] -= temp

for i in range(n):
    print(result[i])


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

int main(){
	int n;
	cin>>n;
	if(n%1000==0)cout<<0<<endl;
	else{
		cout<<1000-n%1000<<endl;
	}
	return 0;
}

Measured memory_bytes: 3644
#include <iostream>

using namespace std;

int main() {

  int n;
  int p,d1,d2;

  int max_dist;
  int max_p;


  while(cin >> n) {

    if(n==0) break;

    max_dist=0;

    for(int i=0;i<n;i++) {

      cin >> p >> d1 >> d2;

      if(d1+d2>max_dist) {

	max_dist=d1+d2;
	max_p=p;

      }

    }

    cout << max_p << " " << max_dist << endl;

  }

  return 0;

}

Measured memory_bytes: 868
n,k = gets.split.map(&:to_i)
h = gets.split.map(&:to_i)
k = [k,n-1].min
# 11行目で繰り返し最小値を比較するために一旦無限大で初期化
dp = Array.new(n){Float::INFINITY}
dp[0] = 0
# 飛び移れる最遠のところまでの初期値を入力
(1..k).each {|i| dp[i] = (h[i] - h[0]).abs}
# dp[i-j] <= j個手前までの最小コスト + そこから飛び移るときのコスト
(k+1...n).each do |i|
  (1..k).each {|j| dp[i] = [dp[i-j] + (h[i] - h[i-j]).abs, dp[i]].min}
end
p dp[n-1]


Measured memory_bytes: 21980
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI (acos(-1))
#define _GLIBCXX_DEBUG

int main(){
  
  string s;
  cin >> s;
  cout << s.substr(0,3) << 8 << s.substr(4) << endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main()
{
    int a, b, c, d, e, f;
    scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);

    int total = 100 * a, sugar = 0;

    for (int i = 0; i < 30; i++)
    {
        for (int j = 0; j < 30; j++)
        {
            if (a*i + b*j > f)
                continue;

            int water = (a * i + b * j) * 100;
            int maxSugar = min(f - water, water / 100 * e);

            for (int k = 0; k * c < maxSugar; k++)
            {
                int s = k * c + (maxSugar - k*c) / d * d;

                int t = water + s;

                if (sugar * t < s * total)
                {
                    total = t;
                    sugar = s;
                }
            }
        }
    }

    printf("%d %d\n", total, sugar);

    return 0;
}

Measured memory_bytes: 256
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);let input_i=-1;const tn=():number=>{input_i++;return Number(input[input_i])};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{input_i++;return String(input[input_i])};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{const t=[...ar];return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{const t=[...ar];return t.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1]}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const deduplicate=(a:any[]):any[]=>{return Array.from(new Set(a))}
const main=()=>{
  let n=tn()
  let nr=tnn(n)
  let j=false;
  let i=0
  let cnt=0
  let check=new Array(n)
  check.fill(false)
  while(!j){
    if(i==1){
      to(cnt)
      return
    }
    if(check[i]==true||i==nr[i]-1){
      to(-1)
      return
    }
    check[i]=true
    i=nr[i]-1
    cnt++;
  }
}
main()

Measured memory_bytes: 26700
from bisect import bisect_left, bisect, insort_left, insort
from itertools import accumulate
INF = float("inf")
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    sum_a = sum(A)
    X = list(accumulate(A))
    Y = list(accumulate(A[::-1]))
    Z = {sum_a // 2, (sum_a + 1) // 2}
    def f(z, B):
        ret = INF
        left = bisect_left(B, z)
        for a in [left, left + 1]:
            if a == n + 1:
                continue
            if a < n - 1:
                t = B[a]
                ret = min(ret, abs(t - (sum_a - t)))
            if a <= n:
                t = B[a - 1]
                ret = min(ret, abs(t - (sum_a - t)))
        return max(0, ret)
    ans = INF
    for z in Z:
        ans = min(ans, f(z, X), f(z, Y))
    print(ans)
solve()


Measured memory_bytes: 32040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

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

  int n;
  cin >> n;

  vector<int> dp(n+1000);
  repr(i, n+10, 0) {
    dp[i] = i;
  }

  for (int i = 0; i <= n; ++i) {
    for (int six = 1; i + six <= n; six*=6) {
      dp[i+six] = min(dp[i+six], dp[i] + 1);
    }

    for (int nine = 1; i + nine <= n; nine*=9) {
      dp[i+nine] = min(dp[i+nine], dp[i] + 1);
    }
  }

  cout << dp[n] << endl;
}

Measured memory_bytes: 640
c = []
for i in range(3):
  c.append([int(x) for x in input().split()])

ok = False
d1 = c[0][0] - c[0][1]
d2 = c[0][0] - c[0][2]
d3 = c[0][1] - c[0][2]
if c[1][0] - c[1][1] == c[2][0] - c[2][1] == d1:
  if c[1][0] - c[1][2] == c[2][0] - c[2][2] == d2:
    if c[1][1] - c[1][2] == c[2][1] - c[2][2] == d3:
      ok = True
if ok:
  print('Yes')
else:
  print('No')


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

int main() {
  int n, m, s = 0;
  cin >> n >> m;
  s += m;
  for(int i = 1; i < n; ++i){
    int p;
    cin >> p;
    s += p;
    m = max(m, p);
  }
  cout << s - m / 2 << endl;
}


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

string a, ab, ae;

bool pal(string x){
	string h = x;
	reverse(x.begin(), x.end());
	
	if(x == h){
		return true;
	}
	return false;
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> a;
	
	for(int i = 0; i < (a.size()-1)/2; i ++){
		ab += a[i];
	}
	
	for(int i = (a.size()+3)/2 - 1; i < a.size(); i ++){
		ae += a[i];
	}
	
	if(pal(a) and pal(ab) and pal(ae)){
		cout << "Yes";
		return 0;
	}
	cout << "No";
	
	return 0;
}


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

struct RSQ{
 UL N;
 vector<UL> V;
 void init(UL n){
  N=1; while(N<n) N<<=1;
  V.resize(N*2-1);
 }
 void add(UL p){
  UL i=p+N-1;
  V[i]++;
  while(i){
   i=(i-1)>>1;
   V[i]++;
  }
 }
 UL query(UL l,UL r,UL a=~0u,UL b=~0u,UL i=~0u){
  if(!~i){ a=i=0; b=N; }
  if(r<=a || b<=l) return 0;
  if(l<=a && b<=r) return V[i];
  UL q1=query(l,r,a,(a+b)>>1,(i<<1)+1);
  UL q2=query(l,r,(a+b)>>1,b,(i<<1)+2);
  return q1+q2;
 }
} Q;

UL N;
pair<UL,UL> A[200000];
UL xA[200000];
ULL ans;

int main(){
 scanf("%u",&N);
 rep(i,N) {
  UL a; scanf("%u",&a);
  A[i]={a,i};
 }
 Q.init(N);
 sort(A,A+N);
 rep(i,N) xA[A[i].second] = i;
 ans=0;
 rep(i,N){
  ans+=Q.query(xA[i],N);
  Q.add(xA[i]);
 }
 cout<<ans<<endl;
}


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

const int INF = (int)(2e+9);
int N;
vector<int> X;

int calcu(int p) {
	int sum = 0;
	for (int i = 0; i < N; ++i)
		sum += (X[i] - p) * (X[i] - p);
	return sum;
}

int main(void) {
	cin >> N;
	X.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> X[i];

	int min_val = INF;
	for (int i = 1; i <= 100; ++i) {
		int val = calcu(i);
		min_val = min(val, min_val);
	}

	cout << min_val << '\n';
	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

dic = defaultdict(int)
N = int(input())

for _ in range(N):
  dic[input()] += 1

print('AC x {}'.format(dic['AC']))
print('WA x {}'.format(dic['WA']))
print('TLE x {}'.format(dic['TLE']))
print('RE x {}'.format(dic['RE']))

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

int main()
{
	int n, k;
	vector<int> a;
	cin >> n >> k;
	do {
		a.push_back(n % k);
		n /= k;
	} while (n != 0);
	
	cout << a.size() << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000009;

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

void solve(int n,int m){
	int s[20],d[110];
	for(int i = 0;i < n;i++) cin >> s[i];
	for(int i = 0;i < m;i++) cin >> d[i];
	int dp[1 << 15];
	for(int i = 0;i < (1 << n);i++) dp[i] = INF;
	dp[0] = 0;
	for(int i = 0;i < m;i++) dp[0] += d[i];
	for(int i = 0;i < (1 << n);i++){
		int sum = 0;
		for(int j = 0;j < n;j++){
			if((i >> j) & 1) sum += s[j];
		}
		for(int j = 0;j < n;j++){
			if((i >> j) & 1) continue;
			int fukai = dp[i];
			for(int k = 0;k < m;k++){
				fukai -= max(0ll,abs(d[k] - sum) - abs(d[k] - (sum + s[j])));
			}
			chmin(dp[i | (1 << j)],fukai);
		}
	}
	cout << dp[(1 << n) - 1] << endl;
}

signed main(){
	int n,m;
	while(cin >> n >> m,n){
		solve(n,m);
	}
}


Measured memory_bytes: 3360
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int N;          cin>>N;
    int a[N+1];
    int p[N+1];   int dp[N+1][N+1];    
    a[0]=0;
    for(int i=1;i<=N;++i){
        cin>>a[i];
    }
    partial_sum(a,a+N+1,p);
    memset(dp,0,sizeof(dp));
    for(int cd=2;cd<=N;++cd){
        for(int i=1;i+cd-1<=N;i++){
            int j=i+cd-1;
            dp[i][j]=10e18;
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
            }            
            dp[i][j]+=p[j]-p[i-1];
        }
    }
    cout<<dp[1][N];
}

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

const int MOD = 1000000007;
const int INF = 1000000010;



int main(){
  long long n, m, k;
  const int max_n = 2 * 1e5;
  cin >> n >> m >> k;
  long long a[max_n + 10], b[max_n + 10];
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) cin >> b[i];
  
  long long sum_a[max_n+10];
  long long sum_b[max_n+10];
  for(int i = 0; i <= n; i++){
    if(i==0) sum_a[i] = 0;
    else sum_a[i] = sum_a[i-1] + a[i-1];
  }
  for(int i = 0; i <= m; i++){
    if(i==0) sum_b[i] = 0;
    else sum_b[i] = sum_b[i-1] + b[i-1];
  }
  long long time = 0;
  long long ans = 0;
  long long j = 0;
  long long past = 0;
  sum_b[m+1] = INF;
  for(long long i = n; i >= 0; i--){
    if(sum_a[i] > k) continue;
    while(sum_a[i] + sum_b[j] <= k){
      if(j == m+1) break;
      j ++;
      // if(j >= m) break;
    }
    ans = max(ans, i + j - 1);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 9816
# cook your dish here
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7
    if x == 9:
        return 6
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
for w in range(1,10):
    if n < f(w) and w in a:
        a.remove(w)
        m -=1
a.sort()
m = len(a)

dp = [[0]*(m+1) for i in range(n+2)]


def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    if f(a[i]) <= n:
        dp[f(a[i])][0] = 1
        dp[f(a[i])][i+1] = 1

for j in range(1,n+1):
    g(j)

ass = ''

for i in range(m):
    for k in range(dp[n][m-i]):
        ass += str(a[m-i-1])
print(ass)        

Measured memory_bytes: 4788
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
typedef pair<int,int> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
}
int N=3e5+9,k;
void input_(){
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
}
std::vector<int> dp(N,-1);
int f(int i,int n,int k,int *a){
    if(i==n-1) return 1;
    if(dp[i]!=-1) return dp[i];
    int x=-1,y=-1;
    for(int j=i+1;j<n;j++){
        if(a[j]-a[i]<=k&&a[j]>=a[i]){
            x=j;
            //cout<<a[j]-a[i]<<" "<<i<<"\n";
            break;
        }
    }
    for(int j=i+1;j<n;j++){
        if(a[i]-a[j]<=k&&a[j]<a[i]){
            y=j;
            break;
        }
    }
    if(x==-1&&y==-1) dp[i]=1;
    else if(x==-1) dp[i]=1+f(y,n,k,a);
    else if(y==-1) dp[i]=1+f(x,n,k,a);
    else dp[i]=max(1+f(x,n,k,a),1+f(y,n,k,a));
    //cout<<dp[i]<<" "<<i<<"\n";
    return dp[i];
}
void solve(){
    int n,k;
    cin>>n>>k;
    int a[n];
    int ans=0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        if(dp[i]==-1) ans=max(f(i,n,k,a),ans);
    }
    cout<<ans;
}
int main(){
    input_();
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int t=1;
	//cin>>t;
	while(t--) 
	    solve();
	return 0; 
}

Measured memory_bytes: 5576
S = input()
K = int(input())
count1 = 0

SL = list(S)
for i in range(0,101):
    if int(SL[i]) == 1:
        count1 += 1
    else:
        break
    if count1 == K:
        break

if count1 >= K:
    print(1)
else:
    if count1 >= 1:
        while "1" in SL:
            SL.remove("1")
    print(SL[0])


Measured memory_bytes: 3064
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV

main=B.interact $ B.pack.g.take 2.B.lines
g [s,t]=mk "" (ls-1) (lt-1) where
    ls = B.length s
    lt = B.length t
    rd si ti = (aa V.! si) UV.! ti
    mk as si ti
        | si<0 || ti<0 = as
        | B.index s si == B.index t ti = mk (B.index s si : as) (si-1) (ti-1)
        | rd (si+1) ti > rd si (ti+1) = mk as si (ti-1)
        | otherwise = mk as (si-1) ti
    aa :: V.Vector (UV.Vector Int)
    aa = V.scanl' p (UV.replicate (lt+1) 0) $ V.enumFromTo 1 ls where
        p v0 i = UV.scanl' m 0 $ UV.enumFromTo 1 lt where
            m pj j = if B.index s (i-1) == B.index t (j-1)
                then 1 + v0 UV.! (j-1)
                else max pj $ v0 UV.! j

Measured memory_bytes: 75388
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);
		String s1 = scan.next();
		String s2 = scan.next();
		String s3 = scan.next();

		String ans = "" + s1.toUpperCase().charAt(0) + s2.toUpperCase().charAt(0) + s3.toUpperCase().charAt(0);
		System.out.println(ans);
	}

}

Measured memory_bytes: 22732
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:
うしろから見ていく。
0なら、一つ前が0,1なら次へ。
高さhのとき：
    そのますもふくめて前にh+1ますなければ：-1
    あれば：+h回の操作
        次のますがh-1となっているか？
        なっていれば：さらに次
        なっていなければ：はじめから
'''

def main(): 
    N = II()
    A = []
    for i in range(N):
        A.append((i, II()))
    
    action = 0
    prev_h = 0
    for i, h in reversed(A):
        if h == 0:
            if prev_h <= 1:
                pass
            else:
                print(-1)
                return
        else:
            if i < h:
                print(-1)
                return
            else:
                if prev_h == 0 or prev_h < h+1:
                    action += h
                elif prev_h > h+1:
                    print(-1)
                    return
                else:
                    pass
        prev_h = h
    print(action)



main()

Measured memory_bytes: 54492
#include <stdio.h>

int main()
{
  int N, data[100], i;
  int flag, c=0, x;

  scanf("%d",&N);
  for(i = 0 ; i < N ; i++)
    scanf("%d",&data[i]);

  flag = 1;
  while(flag == 1){
    flag = 0;
    for( i = N-1 ; i > 0 ; i--){
      if(data[i] < data[i-1]){
	x = data[i];
	data[i] = data[i-1];
	data[i-1] = x;
	flag = 1;
	c++;
      }
    }
  }
  i=0;
  while(1){
    printf("%d",data[i]); 
    if(i == N-1)break;
    printf(" ");
    i++;
  }
  printf("\n");
  printf("%d\n",c);

  return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
//void IO(){
//	#ifndef ONLINE_JUDGE
//	    freopen("input.txt", "r", stdin);
//	    freopen("output.txt", "w", stdout);
//	#endif
//}
// end of Template

str s;
int a,b;
bool valid;
int main(){
	//IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>a>>b;
    valid = true;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='-'){
            if(i!=a){valid=false;}
        }
        else{
            if(i==a){valid=false;}
        }
    }
    if(valid)cout<<"Yes\n";
    else cout<<"No\n";
}


Measured memory_bytes: 256
#include <stdio.h>

int n, x, y, imos[100003], table[100002];

int main()
{
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        scanf("%d", &y); y++;
        
        imos[x]++;
        imos[y]--;
    }
    
    for(int i = 1; i <= 100001; i++)
    {
        table[i] = table[i - 1] + imos[i];
    }
    
    int ret = 0;
    
    for(int i = 1; i <= 100001; i++)
    {
        if(i - 1 <= table[i])
        {
            ret = i - 1;
        }
    }
    
    printf("%d\n", ret);
    
    return 0;
}

Measured memory_bytes: 3468
#include<stdio.h>

struct Card{
  char suit;
  char value;
};

void bubble(struct Card A[], int n){
  int i, j;
  struct Card t;
  for ( i = 0; i < n; i++ ){
    for ( j = n-1; j >= i+1; j-- ){
      if ( A[j].value < A[j-1].value ){
	t = A[j]; A[j] = A[j-1]; A[j-1] = t;
      }
    }
  }
}

void selection(struct Card A[], int n){
  int i, j, mini;
  struct Card t;
  for ( i = 0; i < n; i++ ){
    mini = i;
    for ( j = i; j < n; j++ ){
      if ( A[j].value < A[mini].value ) mini = j;
    }
    t = A[i]; A[i] = A[mini]; A[mini] = t;
  }
}

void print(struct Card A[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( i ) printf(" ");
    printf("%c%c", A[i].suit, A[i].value);
  }
  printf("\n");
}

int isStable(struct Card C1[], struct Card C2[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( C1[i].suit != C2[i].suit ) return 0;
  }
  return 1;
}

int main(){
  struct Card C1[101], C2[101];
  int n, i;
  char ch;

  scanf("%d\n", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%c%c ", &C1[i].suit, &C1[i].value);
  }

  for ( i = 0; i < n; i++ ) C2[i] = C1[i];

  bubble(C1, n);
  selection(C2, n);

  print(C1, n);
  printf("Stable\n");
  print(C2, n);
  if ( isStable(C1, C2, n) ){
    printf("Stable\n");
  } else {
    printf("Not stable\n");
  }

  return 0;
}



Measured memory_bytes: 2096
#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int My_Inf=2147483647;
const long long int My_LInf=9223372036854775807;

long long int gcd(long long int l, long long int r) {
	assert(l > 0 && r > 0);
	if (l > r)return gcd(r, l);
	else {
		if (r%l) {
			return gcd(l, r%l);

		}
		else {
			return l;
		}
	}
}

map<int, int>mp;

int main() {
	mp['1'] = 0;
	mp['2'] = 1;
	mp['3'] = 2;
	mp['4'] = 0;
	mp['6'] = 2;
	mp['7'] = 0;
	mp['8'] = 1;
	mp['9'] = 2;
	while (1) {
		string st; cin >> st;
		if (st == "#")break;
		int ans = 99999999;
		{
			int l = 0;
			int r = 2;
			bool isleft = true;
			int tired = 0;
			for (int i = 0; i < st.size(); ++i) {
				if (isleft) {
					if (r < mp[st[i]]) {
						r = mp[st[i]];
						tired++;
					}
					else {
						l = mp[st[i]];
						isleft =!isleft;
					}
				}
				else {
					if (l > mp[st[i]]) {
						l = mp[st[i]];
						tired++;
					}
					else {
						r = mp[st[i]];
						isleft = !isleft;
					}
				}

			}
			ans = min(ans, tired);
		}
		{
			int l = 0;
			int r = 2;
			bool isleft = false;
			int tired = 0;
			for (int i = 0; i < st.size(); ++i) {
				if (isleft) {
					if (r < mp[st[i]]) {
						r = mp[st[i]];
						tired++;
					}
					else {
						l = mp[st[i]];
						isleft = !isleft;
					}
				}
				else {
					if (l > mp[st[i]]) {
						l = mp[st[i]];
						tired++;
					}
					else {
						r = mp[st[i]];
						isleft = !isleft;
					}
				}

			}
			ans = min(ans, tired);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3172
import sys

input = sys.stdin.readline

n = int(input())

abc = [[int(i) for i in input().split()] for j in range(n)]

def happy(n, abc):
    da, db, dc = 0, 0, 0
    
    for a, b, c in abc:
        na = max(db, dc) + a
        nb = max(da, dc) + b
        nc = max(da, db) + c
        
        da, db, dc = na, nb, nc
    
    return max(da, db, dc)
    
print(happy(n, abc))

Measured memory_bytes: 24308
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXM=100005;
const int MAXN=405;
struct edge{int x,y,c,next;}a[2*MAXM];int len,last[MAXN];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
bitset<MAXN> bi[MAXN];
int vis[MAXN],tim,dead[MAXN],now;
bool ok;
int n,m,no[MAXN],INF;
void dfs(int x,int fa)
{
	vis[x]=tim;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa&&a[k].c<dead[x])
		{
			if(vis[y]==tim)
			{
				if(dead[y]!=INF){ok=false;return ;}
				continue;
			}
			bi[now][y]=1;
			dead[y]=a[k].c+1;dfs(y,x);
		}
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		ins(x,y,i);ins(y,x,i);
	}
	for(int i=1;i<=n;i++)
	{
		++tim;ok=true;memset(dead,63,sizeof(dead));INF=dead[0];
		now=i;bi[i][i]=1;dfs(i,0);
		if(!ok)no[i]=1;
	}int ans=0;
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
		if(!no[i]&&!no[j]&&!(bi[i]&bi[j]).count())
			++ans;
	pr2(ans);
	return 0;
}


Measured memory_bytes: 3328
/*
2020-04-25
atcoder ABC
D - Bouquet
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;

ll n, a, b;

ll modpow(ll, ll, ll);
ll combi_mod(ll, ll, ll);

void input() {
    cin >> n >> a >> b;
    return;
}

void solve() {
    // cout << modpow(2, n, mod) << endl;
    // cout << combi_mod(a, n, mod) << endl;
    // cout << combi_mod(b, n, mod) << endl;
    
    cout << (mod + mod + modpow(2, n, mod) - 1 - combi_mod(a, n, mod) - combi_mod(b, n, mod)) % mod << endl;
    return;
}

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

//2のn乗を繰り返し二乗法で求める関数(modの余剰あり)
ll modpow(ll a, ll n, ll p) {
    if(n == 1) return a % p;
    if(n % 2 == 1) {
        return (a * modpow(a, n - 1, p)) % p;
    } else {
        ll t = modpow(a, n / 2, p);
        return (t * t) % p ;
    }
}


//modの余剰という条件下でコンビネーションを返す関数
ll combi_mod(ll a, ll n, ll p){
    a = min(a, n - a);
    ll x = 1;
    ll y = 1;
    for(ll i = n - a + 1;i < n + 1; i++) {
        x = (x * i) % p;
    }
    for(ll i = 1; i < a + 1; i++){
        y = (y * i) % p;
    }
    return (x * modpow(y, p - 2, p)) % p; 
}

Measured memory_bytes: 256
<?php
//error_reporting(0);
$S = trim(fgets(STDIN));
//list($N,$M) = explode(" ",trim(fgets(STDIN)));
//$a = array_map('intval',explode(" ",trim(fgets(STDIN))));

$N=strlen($S);
$rev = strrev($S);
$p1 = substr($S,0,intdiv(($N-1),2));
$p1rev = strrev($p1);
$p2 = substr($S,-intdiv(($N-3),2)-1);
$p2rev = strrev($p2);

if (($S==$rev) && ($p1 == $p1rev) &&  ($p2 == $p2rev)) {
 printf("Yes\n");
}
else {
 printf("No\n");
}


Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
const int64_t INF = INT64_MAX;

int main() {
  const int N_MAX = 100;

  int N;
  cin >> N;

  vector<bitset<10>> F(N);
  rep(i, N) rep(j, 10) {
    bool a;
    cin >> a;
    if (a) F.at(i).set(j);
  }

  vector<vector<int64_t>> P(N, vector<int64_t>(11, 0));
  rep(i, N) rep(j, 11) {
    int64_t p;
    cin >> p;
    P.at(i).at(j) = p;
  }

  int64_t ans = -INF;

  for (int i = 1; i < (1 << 10); i++) {
    int64_t r = 0;
    bitset<10> bs(i);

    rep(j, N) {
      bitset<10> e = bs & F.at(j);
      r += P.at(j).at(e.count());
    }

    ans = max(ans, r);
  }

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


Measured memory_bytes: 256
import bisect

inf = float("inf")
ans = 0

a, b, q = map(int, input().split())
S = [-inf]+[int(input()) for _ in range(a)]+[inf]
T = [-inf]+[int(input()) for _ in range(b)]+[inf]
X = [int(input()) for _ in range(q)]

S.sort()
T.sort()


for x in X:
    ans = float('inf')
    i = bisect.bisect_right(S, x)
    j = bisect.bisect_right(T, x)
    d = inf
    for s in [S[i-1], S[i]]:
        for t in [T[j-1], T[j]]:
            d1 = abs(s-t) + min(abs(x-t), abs(x-s))
            if d1 < ans:
                ans = d1
    print(ans)


Measured memory_bytes: 17284
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
	IOS;
	int n;
	cin>>n;
	if(n==1)
	{
		return cout<<1,0;
	}
	int dp[10][10];
	memset(dp,0,sizeof(dp));
	dp[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		int l=i%10;
		int f=i/(ll)pow(10,(int)log10(i));
		dp[f][l]++;
	}
	ll ans=0;
	for(int i=1;i<=9;i++)
	ans+=(ll)pow(dp[i][i],2);
	
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
		
			if(i!=j)
			{
				ans+=((ll)dp[i][j]*dp[j][i]);
			}
		}
	}
	cout<<ans;
	
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>

vector <ll> v[15],cst;

ll fep(ll x, ll y, ll mod)
{ll res=1;while(y>0){if(y&1)res=(res*x)%mod;
    y=y>>1;x=(x*x)%mod;}return res%mod;}

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

	ll n,i,m,j,k,x,y,a,b,c,t,sm=0,xw;
	string s,w;
	
	cin >> n >> m >> xw;
	for(i=0;i<n;i++)
	{
		cin >> x;
		cst.pb(x);
		for(j=0;j<m;j++)
		{
			cin >> x;
			v[i].pb(x);
		}
	}
	k=pow(2,n);
	ll mini=1000000000000;
	for(i=0;i<k;i++)
	{
		a=i;
		ll sm=0;
		vector <ll> tmp;
		ll val[15]={0};
		while(a)
		{
			b=a%2;
			if(b)
				tmp.pb(1);
			else
				tmp.pb(0);
			a/=2;
		}
		while(tmp.size()<n)
			tmp.pb(0);
		for(j=0;j<n;j++)
		{
			sm+=tmp[j]*cst[j];
			if(tmp[j])
				for(ll p=0;p<m;p++)
					val[p]+=v[j][p];
		}
		ll p;
		for(p=0;p<m;p++)
			if (val[p]<xw)
				break;
		if(p==m)
			mini=min(mini,sm);
	}
	if(mini==1000000000000)
		mini=-1;
	cout << mini;
	return 0;
}


Measured memory_bytes: 4092