akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var n = long.Parse(Console.ReadLine());

        List<int> factorExponents = PrimeFactorize(n);

        var count = 0;
        for (int i = 0; i < factorExponents.Count; ++i)
        {
            var (ok, ng) = (1, factorExponents[i] + 1);
            while (Math.Abs(ok - ng) > 1)
            {
                var mid = (ng - ok) / 2 + ok;
                if (mid * (mid + 1) / 2 <= factorExponents[i])
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }

            count += ok;
            factorExponents[i] -= ok * (ok + 1) / 2;
        }

        Console.WriteLine(count);
    }

    private static List<int> PrimeFactorize(long n)
    {
        var factorExponents = new List<int>();
        for (var p = 2; p <= n / p; p += 2 - (1 - p % 2))
        {
            var e = 0;
            var t = n / p;
            while (t * p == n)
            {
                (n, t) = (t, t / p);
                ++e;
            }

            if (e > 0)
            {
                factorExponents.Add(e);
            }
        }
        if (n != 1)
        {
            factorExponents.Add(1);
        }

        return factorExponents;
    }
}


Measured memory_bytes: 27816
# C問題
n, x = map(int, input().split())
a = list(map(int, input().split()))
new_a = []
new_a += a
if a[0] > x:
    new_a[0] = x
for i in range(n-1):
    while True:
        if new_a[i] + new_a[i+1] > x:
            new_a[i+1] = x-new_a[i]
        if new_a[i] + new_a[i+1] <= x:
            break

print(sum(a) - sum(new_a))

Measured memory_bytes: 14276
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,sum=0,pt=1;
  vector<ll> ans;
  cin >> n;
  while(sum<n){
    sum+= pt;
    pt++;
  }
  pt--;
  while(n!=0){
    if(n>=pt){
      n-=pt;
      ans.push_back(pt);
    }
    pt--;
  }
  sum=0;
  for(int i=ans.size()-1;i>=0;i--){
    cout << ans[i]<<endl;
    sum+=ans[i];
  }
//  cout << sum<<endl;
}


Measured memory_bytes: 384
n = gets
class Coin
  def initialize(val, kind)
    @val = val
    @kind = kind
  end

  def to_jpy
    if @kind == 'BTC'
      @val * 380000.0
    else
      @val
    end
  end
end

coins = []
n.to_i.times do
  i = gets
  val, kind = i.split(' ').compact
  coins << Coin.new(val.to_f, kind)
end

print coins.map(&:to_jpy).inject(:+)


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll d[100005];
int n,m,r;
vector<pair<ll,int>>G[100005];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;

int main() {
	cin>>n>>m>>r;
	for (int i=0;i<n;i++) d[i]=INF;
	for (int i=0;i<m;i++) {
		int s,t; ll w; cin>>s>>t>>w;
		G[s].pb({w,t});
	}
	d[r]=0;
	pq.push({0,r});
	while (pq.size()) {
		ll dis=pq.top().ff;
		int v=pq.top().ss;
		pq.pop();
		if (d[v]<dis) continue;
		for (auto p:G[v]) {
			if (dis+p.ff<d[p.ss]) {
				d[p.ss]=dis+p.ff;
				pq.push({d[p.ss],p.ss});
			}
		}
	}
	for (int i=0;i<n;i++) {
		if (d[i]==INF) cout<<"INF";
		else cout<<d[i];
		cout<<'\n';
	}
}


Measured memory_bytes: 19400
using System;

class main
{
    static void Main(string[] args)
    {
        string s;
        int f = 90, f2 = 0;
        double x = 0, y = 0;
        while ((s = Console.ReadLine()) != null)
        {
            string[] d = s.Split(',');
            if (d[0] == "0" && d[1] == "0")
            {
                break;
            }
            int m = int.Parse(d[0]);
            int n = int.Parse(d[1]);
            double r = (f * (Math.PI / 180));
            double r2 = (f2 * (Math.PI / 180));
            x += (Math.Cos(r) * m);
            y += (Math.Cos(r2) * m);
            f -= n;
            f2 += n;
        }
        Console.WriteLine((int)x);
        Console.WriteLine((int)y);
    }
}

Measured memory_bytes: 5600
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,k = m()

co = 0

while n:
    co += 1
    n //= k

print(co)










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

#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)

#define P pair<int, int >


const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;

typedef long long ll;


//---functions---//
int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int s2i(string num){stringstream ss; ss << num << flush; int n; ss >> n; return n;}
string i2s(int n){stringstream ss; ss << n << flush; return ss.str();}

bool firstCompare(const P& firstElof, const P& secondElof){
    return firstElof.first < secondElof.first;
}
bool secondCompare(const P& firstElof, const P& secondElof){
    return firstElof.second > secondElof.second;
}
//---------------//

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

    cin >> N >> M;
    vector<int > X(M);
    vector<P > dX(M-1);
    REP(i, 0, M) cin >> X[i];

    if(N >= M){
        cout << 0 << endl;
    }else{

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

        REP(i, 0, M - 1) dX[i].second = X[i+1] - X[i], dX[i].first = i + 1;

        sort(dX.begin(), dX.end(), secondCompare);

        /*
        REP(i, 0, M) cout << X[i] << " ";
        cout << endl;

        REP(i, 0, M - 1) cout << dX[i].first << " ";
        cout << endl;
        */

        bool A[M];
        REP(i, 0, M) A[i] = true;
        A[0] = false;

        REP(i, 0, N - 1){
            A[dX[i].first] = false;
        }

        ll ans = 0;
        sort(dX.begin(), dX.end(), firstCompare);

        /*
        REP(i, 0, M){
            if(A[i]) cout << X[i] << " ";
            else cout << ". ";
        }
        cout << endl;
        */
        REP(i, 0, M - 1){
            if(A[i+1]) ans += dX[i].second;
        }

        cout << ans << endl;
    }
}


Measured memory_bytes: 1536
# -*- coding: utf-8 -*-                                                                                                                                                                  
s = str(input())
j1 = (s[0]=='A')
j2 = False
j3 = False

if 1 == s[2:len(s)-1].count('C'):
    j2 = True
    idx = s[2:len(s)-1].index('C')
    j3 = (s[1:2+idx].islower() and s[2+idx+1:].islower())

if j1 is j2 is j3 is True:
    print ('AC')
else:
    print ('WA')


Measured memory_bytes: 3060
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int count = scanner.nextInt();
			scanner.nextLine();
			BigDecimal rate = new BigDecimal("380000.0");
			BigDecimal sum = BigDecimal.ZERO;
			for (int i = 0; i < count; i++) {
				String amount = scanner.next();
				String currency = scanner.next();
				scanner.nextLine();
				if ("JPY".equals(currency)) {
					sum = sum.add(new BigDecimal(amount));
				} else {
					sum = sum.add((new BigDecimal(amount)).multiply(rate));
				}
			}
			System.out.println(sum);
		}
	}
}


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

int main() {
  int fH,fW;
  int sH,sW;
  long long fArea,sArea;
  
  cin >> fH >> fW >> sH >> sW;
  
  fArea = fH * fW;
  sArea = sH * sW;
  
  if(fArea >= sArea) cout << fArea;
  else cout << sArea;
}


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

using namespace std;

bool is753(int i) {
  bool has7{}, has5{}, has3{};
  while (i) {
    switch (i % 10) {
      case 7:
        has7 = true;
        break;
      case 5:
        has5 = true;
        break;
      case 3:
        has3 = true;
        break;
      default:
        return false;
    }
    i /= 10;
  }
  return has7 && has5 && has3;
}

int main() {
  int N, ans{};
  cin >> N;

  vector<long long> V{3, 5, 7};
  for (int i = 0;;++i) {
    auto next = V[i]*10;
    if (next > N) break;
    V.push_back(V[i]*10+3);
    V.push_back(V[i]*10+5);
    V.push_back(V[i]*10+7);
  }

  ans = count_if(begin(V), upper_bound(begin(V),end(V),N),
           [&](int x) { return is753(x); });
  cout << ans << endl;
}


Measured memory_bytes: 3844
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int[] a = sc.IntArray();

        var cnt = new long[n + 1];
        foreach (int i in a)
        {
            cnt[i]++;
        }

        var all = 0L;
        for (int i = 1; i <= n; i++)
        {
            all += cnt[i] * (cnt[i] - 1) / 2;
        }

        var ans = new long[n];
        for (int i = 0; i < n; i++)
        {
            var t = all;
            long tt = cnt[a[i]];
            t -= tt * (tt - 1) / 2;
            t += (tt - 1) * (tt - 2) / 2;
            ans[i] = t;
        }

        Console.WriteLine(string.Join("\n", ans));
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    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: 45836
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define orep(i, n) for(int i = 1; i <= (n); i++)
#define srep(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define ru(a,b) ((a+b-1) / b)
#define rng(x) (x).begin(),(x).end()
#define P pair<int,int>

typedef long long ll;
#define vi vector<int>;
#define vvi vector<vi>;
using namespace std;

int main() {
  string s;cin >> s;
  int ans = 0;
  rep(i,s.size()) {
    ans += s.at(i) - '0';
    ans %= 9;
  }

  if(!ans) cout << "Yes" << endl;
  else cout << "No" << endl;


  return 0;
}


Measured memory_bytes: 3724
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := NewScanner(os.Stdin)
	_ = sc.NextInt()
	K := sc.NextInt()
	S := sc.Next()
	fmt.Println(S[:K-1] + strings.ToLower(string(S[K-1])) + S[K:])
}

func vmin(v []int) int {
	mn := math.MaxInt32
	for i := 0; i < len(v); i++ {
		mn = min(mn, v[i])
	}
	return mn
}

func gcd(x, y int) int {
	if y > 0 {
		return gcd(y, x%y)
	}
	return x
}

func lcm(x, y int) int {
	return x / gcd(x, y) * y
}

func max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// scanner
type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner(r io.Reader) *Scanner {
	rdr := bufio.NewReaderSize(r, 1024)
	return &Scanner{r: rdr}
}

func (s *Scanner) ReadLine() {
	s.buf = make([]byte, 0)
	for {
		line, isp, err := s.r.ReadLine()
		if err != nil {
			os.Exit(1)
		}
		s.buf = append(s.buf, line...)
		if !isp {
			break
		}
	}
}

func (s *Scanner) NextInt64() int64 {
	i, err := strconv.ParseInt(s.Next(), 10, 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextInt() int {
	i, err := strconv.Atoi(s.Next())
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextFloat64() float64 {
	i, err := strconv.ParseFloat(s.Next(), 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) Next() string {
	s.Pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	next := string(s.buf[start:s.p])
	s.p++
	return next
}

func (s *Scanner) Pre() {
	if s.p >= len(s.buf) {
		s.ReadLine()
		s.p = 0
	}
}


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

using namespace std;

int PrimeNumber[1000001] = {0,0,1,1};

void findPrimeNumber(){
	int limit;
	bool flag;

	for (int i = 5; i < 1000001; i += 2) {
		limit = sqrt(i) + 1;
		flag = true;
		for (int j = 2; j < limit; j++) {
			if (i%j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			PrimeNumber[i] = 1;
		}
	}

	return;
}

int main() {
	int n, rest, sum;

	findPrimeNumber();
	while (cin >> n, n) {
		sum = 0;
		for (int i = 2; i < n; i++) {
			rest = n - i;
			if (i > rest) {
				break;
			}
			if (PrimeNumber[i] == 1 && PrimeNumber[rest] == 1) {
				sum++;
			}
		}
		 
		cout << sum << endl;
	}
	

	return 0;
}


Measured memory_bytes: 6956
N = int(input())
W = [input().rstrip() for _ in range(N)]
W_set = set(tuple(W))
for i in range(N-1):
  if W[i][-1] == W[i+1][0]:
    continue
  else:
    print("No")
    exit()
for word in W_set:
    if W.count(word) != 1:
        print("No")
        exit()
print("Yes")

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

class vertex{
public:
  vector<vertex*> to;
  bool visited;
  int num;
  int dis;

  vertex(){
    visited=false;
    dis = -1;
  }

  void bfs(int dis){
    this->dis=dis;
    visited=true;
    queue<vertex*> qv; qv.push(this);

    while(!qv.empty()){
      vertex* now = qv.front();  qv.pop();

      for(int i=0; i<now->to.size(); i++){
        if(!now->to[i]->visited){
          qv.push(now->to[i]);
          now->to[i]->visited = true;
          now->to[i]->dis = now->dis+1;
        }
      }
    }
  }

  void print(){
    cout << num << " " << dis << endl;
  }
};

int main(){
  int n; cin >> n;
  vertex graph[n+1];

  int v, k, to;
  for(int i=0; i<n; i++){
    cin >> v >> k;
    graph[v].num = v;
    for(int j=0; j<k; j++){
      cin >> to;
      graph[v].to.push_back(&graph[to]);
    }
  }

  graph[1].bfs(0);

  for(int v=1; v<=n; v++){
    graph[v].print();
  }

  return 0;
}



Measured memory_bytes: 3160
fun main(args: Array<String>) {

    var (R) = readInts()

    if (R < 1200) {
        println("ABC")
    }
    else if (R < 2800) {
        println("ARC")
    }
    else {
        println("AGC")
    }
}

fun readInts(): List<Int> = readStrings().map { it.toInt() }
fun readStrings(): List<String> = readLine()!!.split(" ")

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

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadInt();
        var k = N.ToString()[0];
        var ans = "";
        if (N <= int.Parse("" + k + k + k))
        {
            ans = "" + k + k + k;
        }
        else
        {
            var x = (N / 100 + 1).ToString();
            ans = x + x + x;
        }
        Console.WriteLine(ans);
    }
    static int MOD = (int)1e9 + 7;
    static int INF = (int)1e7 + 1;
    static long LINF = (long)1e13 + 1;
    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}



Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char a;
	for(int i=1;i<=8;i++)
		cin>>a;
	string x;
	x="2018/01/";
	cin>>a;
	x+=a;
	cin>>a;
	x+=a;
	cout<<x;
	return 0;
}

Measured memory_bytes: 256
import math
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    if i<k:
        # print(i,math.ceil(math.log2(k/i)))
        times=math.ceil(math.log2(k/i))
        ans+=math.pow(0.5,times)
    else:
        ans+=1
print(ans/n)


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

int main() {
    string s;
    cin >> s;
    map<char, int> num;
    for (int i = 0; i < s.size(); i++) {
        num[s[i]]++;
    }

    string ans = "";
    if (num.size() < 26) {
        for (char c = 'a'; c <= 'z'; c++) {
            if (num[c] == 0) {
                ans = s + c;
                break;
            }
        }
    } else {
        for (int i = 25; i >= 0; i--) {
            map<char, int> num2;
            for (int j = 0; j < i; j++) {
                num2[s[j]]++;
            }
            for (char c = s[i] + 1; c <= 'z'; c++) {
                if (num2[c] == 0) {
                    ans = s.substr(0, i) + c;
                    goto END;
                }
            }
        }
    }

    END:
    if (ans == "") {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

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

#define REP(i,n) for(i=0;i<n;i++)
#define ll long long

int main(void){
    int i,N,ctr=0;
    scanf("%d",&N);
    int a[N];
    REP(i,N){
        scanf("%d",&a[i]);
    }

    while(1){
        bool yn=0;
        REP(i,N){
            if(a[i]%2!=0) yn=1;
        }
        
        if(yn) break;
        REP(i,N){
            a[i]=a[i]/2;
        }
        ctr++;
    }

    printf("%d",ctr);
    
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define vi vector<int>

int n, m, q;
int a[55], b[55], c[55], d[55];
int ans=0;

void dfs(vi now)
{
	if(now.size()==n+1)
	{
		int nowans=0;
		rep(i, q)
		{
			if(now[b[i]]-now[a[i]]==c[i]) nowans+=d[i];
		}
		ans=max(ans, nowans);
	}
	else
	{
		for(int j=now[now.size()-1]; j<=m; j++)
		{
			vi tmp=now;
			tmp.push_back(j);
			dfs(tmp);
		}
	}
}

int main() {
	cin >> n >> m >> q;
	rep(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
	vi st;
	st.push_back(1);
  	dfs(st);
	cout << ans << endl;
	return 0;
}

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

int main(){
cout<<fixed<<setprecision(12);

int n;
while(cin>>n){
if(n==0){break;}
double a[n];
double al=0;
for(int i=0;i<n;i++){
cin>>a[i];
al+=a[i];
}

al=al/n;
double bun=0;
for(int i=0;i<n;i++){
bun+=(a[i]-al)*(a[i]-al)/n;
}

cout<<sqrt(bun)<<endl;
}

return 0;
}


Measured memory_bytes: 3248
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
typedef long long ll;

#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define MAX_INT 100000
#define MOD 1000000007



ll solve()
{
    ll n;cin>>n;
    if(n<=9) {return n;}
    vector<long long> a[1000000];
    for(int i=0;i<10;i++) a[i].push_back(i);n=n-9;
    for(int i=1;i<100000;i++)
    {
        for(auto x:a[i])
        {
            ll las=x%10;
            if(las-1>=0)  {a[i+9].push_back(x*10+las-1);n--;if(n==0) return(x*10+las-1);}
             {a[i+9].push_back(x*10+las);n--;if(n==0) return(x*10+las);}
            if(las+1<=9)  {a[i+9].push_back(x*10+las+1);n--;if(n==0) return(x*10+las+1);}
        }
        // for(auto x:a[i+9]) cout<<x<<" ";
        // cout<<endl;
    }
    
    
}
    
int main()
{
    IOS;
    
    //ll t;cin>>t;while(t--)
        cout<<solve();
 
    return 0;
}

Measured memory_bytes: 24576
def selectionSort(A,N):
    '''list of int, int -> list of int
    return sorted list(selection sort)
    '''
    assert(len(A) == N)
    outA = A.copy()
    cnt = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if outA[j] < outA[minj]:
                minj = j
        outA[i], outA[minj] = outA[minj], outA[i]
        if i != minj:
            cnt += 1
    return outA, cnt
def printlist(L):
    for itm in L[:-1]:
        print(itm, end = ' ')
    print(L[-1])

n = int(input())
A = list(map(int, input().split()))
A, num = selectionSort(A, n)
printlist(A)
print(num)



Measured memory_bytes: 5620
#include<stdio.h>

int reached[100010];

int main(){
	int N,ans=0;
	scanf("%d",&N);
	int a[N+1];
	for(int i=1;i<=N;i++)scanf("%d",&a[i]);
	
	int b=1;
	while(1){
		if(reached[b]==1){
			ans=-1;
			break;
		}
		if(b==2)break;
		reached[b]=1;
		b=a[b];
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 896
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M >> K >> Q >> L;
	while (N) {
		ans = 0;
		int num[100];
		for (int i = 0; i < N; i++) {
			cin >> num[i];
		}
		for (int i = 0; i <= 10001; i++) {
			if (num[ans] == L)ans++;
			L = (L*M + K) % Q;
			if (ans == N) {
				ans = i;
				break;
			}
			if (i == 10001)ans = 10001;
		}
		if (ans == 10001)cout << "-1\n";
		else cout << ans << endl;
		cin >> N >> M >> K >> Q >> L;
	}
	return 0;
}

Measured memory_bytes: 3076
using System;
using System.Collections.Generic;

namespace Echo
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputN = int.Parse(Console.ReadLine());
            string inputS = Console.ReadLine();

            List<char> inputString = new List<char>(inputS);
            int middlePoint = inputString.Count / 2;
            if (inputN % 2 != 0)
            {
                Console.WriteLine("No");
                return;
            }
            else
            {
                for (int i = 0; i < middlePoint; i++)
                {
                    if (inputString[i] != inputString[middlePoint + i])
                    {
                        Console.WriteLine("No");
                        return;
                    }
                }
                Console.WriteLine("Yes");
            }
        }
    }
}

Measured memory_bytes: 13268
#include<cstdio>
#include<algorithm>
#define MN 200001
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
ll n,m,a[MN],b[MN],A=0,B=0;
int main(){
    
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=m;i++) scanf("%lld",&b[i]);
    for (int i=1;i<n;i++) 
        A=((a[i+1]-a[i])*i%MOD*(n-i)+A)%MOD;
    for (int i=1;i<m;i++) 
        B=((b[i+1]-b[i])*i%MOD*(m-i)+B)%MOD;
    printf("%lld\n",A*B%MOD);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll a[n];
    ll sum=0;
    for(int i=0;i<n;i++){
    	cin>>a[i];
    	sum+=a[i];
    }
    ll x=sum/n,y=x+1;
    sum=0;
    for(int i=0;i<n;i++){
    	sum+=pow((a[i]-x),2);
    }
    ll ans=sum;sum=0;
    for(int i=0;i<n;i++){
    	sum+=pow((a[i]-y),2);
    }
    ans=min(ans,sum);
    cout << ans <<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////


int main() {

	ll N, A, B;
	cin >> N >> A >> B;

	cout << min(A * N, B);

	system("PAUSE");

	

}


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

const int MAX = 510000;
 const int MOD = 1000000007;
 
 long long fac[MAX], finv[MAX], inv[MAX];
 
 // テーブルを作る前処理
 void COMinit() {
     fac[0] = fac[1] = 1;
     finv[0] = finv[1] = 1;
     inv[1] = 1;
     for (int i = 2; i < MAX; i++){
         fac[i] = fac[i - 1] * i % MOD;
         inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
         finv[i] = finv[i - 1] * inv[i] % MOD;
     }
 }
 
 // 二項係数計算
 long long COM(int n, int k){
     if (n < k) return 0;
     if (n < 0 || k < 0) return 0;
     return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
 }
 
  long long modpow(long long a, long long n) {
      long long res = 1;
      while (n > 0) {
          if (n & 1) res = res * a % MOD;
          a = a * a % MOD;
          n >>= 1;
      }
      return res;
  }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll x,y,a,b,c;
    std::cin >> x>>y>>a>>b>>c;
    
    vector<ll> p(a);
    vector<ll> q(b);
    vector<ll> r(c);
    for (int i = 0; i < a; i++) {
        std::cin >> p[i];
    }
    for (int i = 0; i < b; i++) {
        std::cin >> q[i];
    }
    for (int i = 0; i < c; i++) {
        std::cin >> r[i];
    }
    sort(p.rbegin(),p.rend());
    sort(q.rbegin(),q.rend());
    sort(r.rbegin(),r.rend());
    
    ll pi,qi;
    pi = x-1;
    qi = y-1;
    
    ll sum = 0;
    for (int i = 0; i < x; i++) {
        sum += p[i];
    }
    for (int i = 0; i < y; i++) {
        sum += q[i];
    }
    
    for (int i = 0; i < c; i++) {
        if(pi>=0&&qi>=0){
            
            // std::cout << 1 << std::endl;
            // std::cout << r[i]<<" "<<min(p[pi],q[qi]) << std::endl;
            if(r[i]>min(p[pi],q[qi])){
                if(p[pi]<q[qi]){
                    sum += r[i]-p[pi];
                    pi--;
                }else{
                    sum += r[i]-q[qi];
                    qi--;
                }

            }else{
                break;
            }   
        }else{
            if(pi<0&&qi>=0){
                if(r[i]>q[qi]){
                    sum += r[i]-q[qi];
                    qi--;
                }else{
                    break;
                }
            }else if(qi<0&&pi>=0){
                if(r[i]>p[pi]){
                    sum += r[i]-p[pi];
                    pi--;
                }else{
                    break;
                }
            }else{
                break;
            }
        }
    }
    std::cout << sum << std::endl;
}



Measured memory_bytes: 2560
import bisect
import collections

def read():
    N = int(input().strip())
    S = str(input().strip())
    return N, S

def dig(S, T, N):
    k0, k1, k2 = -1, -1, -1
    for i in range(N):
        if S[i] == T[0]:
            k0 = i
            break
    if k0 == -1:
        return False
    for i in range(k0+1, N):
        if S[i] == T[1]:
            k1 = i
            break
    if k1 == -1:
        return False
    for i in range(k1+1, N):
        if S[i] == T[2]:
            k2 = i
            break
    if k2 == -1:
        return False
    return True


def solve(N, S):
    d = [collections.deque() for i in range(10)]
    count = 0
    for p in range(1000):
        T = '{:03d}'.format(p)
        count += 1 if dig(S, T, N) else 0
    return count
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)


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

using namespace std;

#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000000
#define INFL 10000000000000000LL
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main() {
  while(true){
    int n;
    cin >> n;
    if(n == 0) return 0;
    int a[n];
    REP(i, n) cin >> a[i];
    sort(a, a+n);
    int sum = 0;
    FOR(i, 1, n-1){
      sum += a[i];
    }
    cout << sum/(n-2) << endl;
  }
  return 0;
}



Measured memory_bytes: 2960
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int prime(int);
 
int main(){
int n,*data,i,count=0,check;
scanf("%d",&n);
data=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++) scanf("%d",&data[i]);
for(i=0;i<n;i++){
check=0;
check=prime(data[i]);
if(check==1) count++;
}
 
printf("%d\n",count);
  
free(data); 
return 0;
}
 
int prime(int data){
int i;
 
if(data==2) return 1;
if(data<2||data%2==0) return 0;
i=3;
while(i<=sqrt(data)){
if(data%i==0) return 0;
 
i+=2;
}
return 1;
}

Measured memory_bytes: 628
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18

int main()
{
    int N;
    cin >> N;
    ullong num;

    num = N / 3;
    ullong sub = 3 * (num * (num + 1)) / 2;

    num = N / 5;
    sub += 5 * (num * (num + 1)) / 2;

    num = N / 15;
    sub -= 15 * (num * (num + 1)) / 2;

    num = N;
    ullong ans = (num * (num + 1)) / 2;
    ans -= sub;
    cout << ans << endl;
}


Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int A = in.nextInt();
            int B = in.nextInt();
            int C = in.nextInt();
            System.out.println(A * C <= B ? C : (B / A));
        }
    }
}


Measured memory_bytes: 22740
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
using std::swap;
vector<int> A;
vector<int> B;

int main() {
	int N, x;
	cin >> N;
	A.resize(N);
	B.resize(N);
	rep(i, N) cin >> x, A[i] = x, B[i] = x;
	sort(B.begin(), B.end());
	rep(i, N) { 
			if (A[i] == B[N - 1])cout << B[N - 2] << "\n";
			else cout << B[N - 1] << "\n";
		
	}
	return 0;
}

Measured memory_bytes: 3200
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			int N = scan.nextInt();
			int X = scan.nextInt();
			int T = scan.nextInt();

			int s = N/X;

			if(N%X!=0)s++;

			System.out.println(T*s);
		}


	}


}


Measured memory_bytes: 35608
#include<bits/stdc++.h>
using namespace std;
#define N 3000
#define M 3000
#define pb push_back
char a[N+5],b[M+5];
int dp[N+1][M+1],path[N+1][M+1];
vector<char> ans;
int main(){
	int n,m,nowi,nowj,i;scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);
	for(i=1;i<=n;i++)for(int j=1;j<=m;j++){
		dp[i][j]=dp[i-1][j];path[i][j]=1;
		if(dp[i][j-1]>dp[i][j])dp[i][j]=dp[i][j-1],path[i][j]=2;
		if(a[i]==b[j]&&dp[i-1][j-1]+1>dp[i][j])dp[i][j]=dp[i-1][j-1]+1,path[i][j]=3;
	}
	nowi=n;nowj=m;
	while(nowi&&nowj){
		if(path[nowi][nowj]==1)nowi--;
		else if(path[nowi][nowj]==2)nowj--;
		else ans.pb(a[nowi]),nowi--,nowj--;
	}
	for(i=ans.size()-1;~i;i--)putchar(ans[i]);
	return 0;
}
/*1
axyb
abyxb
*/
/*2
aa
xayaz
*/
/*3
a
z
*/
/*4
abracadabra
avadakedavra
*/

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

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    int K, A, B;
    cin >> K >> A >> B;

    int cand = (B / K) * K;
    
    if (A <= cand) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }

    return 0;
}


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

int main(){
    int num;
    std::cin >>  num ;

    if(num % 10 == 7){
        std::cout << "Yes" << endl;
    }else if(num / 10 % 10 == 7){
        std::cout << "Yes" << endl;
    }else if(num / 100 % 10 == 7){
        std::cout << "Yes" << endl;
    }else {
        std::cout << "No" << endl;
    } 
// std::cout << <<endl   ;

    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


vector<ll> inv,fact,invfact;
void mod_build(int n=101010){
    fact.resize(n+1);
    inv.resize(n+1);
    invfact.resize(n+1);
    fact[0]=inv[0]=invfact[0]=1;
    inv[1]=1;
    rep(i,n){
        fact[i+1]=fact[i]*(i+1)%mod;
        if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
        invfact[i+1]=invfact[i]*inv[i+1]%mod;
    }
}
ll comb(int n,int k){
    if(k==0)return 1;
    if(n<0||k<0||k>n)return 0;
    return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
int main(){
    mod_build();
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    if(b%2){
        cout<<0<<endl;
        return 0;
    }
    b/=2;
    ll ans = 0;
    rep(i,a+1)rep(j,c/3+1){
        ans += comb(c-3*j-i+b-1,c-i-3*j)*comb(a,i)%mod*comb(a+b+j,j)%mod*comb(a+b,a)%mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}

Measured memory_bytes: 2560
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


n, m = LI()
par = [i for i in range(n)]
rank = [0] * n
for _ in range(m):
    a, b = LI()
    if root(a-1) != root(b-1):
        union(a-1, b-1)

s = set()
for i in range(n):
    s.add(root(i))
ans = len(s)-1
print(ans)

Measured memory_bytes: 86264
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define forn for(int i=0;i<n;i++)
#define pb push_back
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   int n,m,c;
   cin>>n>>m>>c;
   int b[m];
   vector<int> a(m);
   int ans=0;
   ll sum=0;
   for(int i=0;i<m;i++)
   {
       cin>>b[i];
   }
   for(int t=1;t<=n;t++)
   {
       for(int i=0;i<m;i++) {cin>>a[i]; sum+=a[i]*b[i];}
       sum+=c;
       if(sum>0) ans++;
       sum=0;
       a.clear();
   }
   cout<<ans<<endl;
   return 0;
   
 

}

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

int main() {
    string S; cin >> S;
    int nofzero = 0, nofone = 0;
    for (int i = 0; i < (int)S.length(); i++) {
        if(S[i] == '0') {
            nofzero++;
        } else {
            nofone++;
        }
    }
    cout << min(nofzero, nofone) * 2 << endl;
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var buff []byte

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buff, bufio.MaxScanTokenSize*1024)
	log.SetFlags(log.Lshortfile)
}

func main() {
	x := nextInt()
	for i := 0; i < 1000; i++ {
		a := i * i * i * i * i
		if a-1 == x {
			fmt.Println(i, 1)
			return
		} else if a+1 == x {
			fmt.Println(i, -1)
			return
		}
	}
	for i := -200; i <= 200; i++ {
		for j := -200; j <= 200; j++ {
			if i*i*i*i*i-j*j*j*j*j == x {
				fmt.Println(i, j)
				return
			}
		}
	}
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextFloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func nextInts(n int) (r []int) {
	r = make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 1756
#define rep(i, a, b) for(int i = a; i < (int)(b); i++)
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
template<class T> inline void chmax(T &a, const T &b) {if(a < b) a = b;}
template<class T> inline void chmin(T &a, const T &b) {if(a > b) a = b;}
const long long INF = 1LL<<60;

const ll MAXN = (ll)2e3+10;
const ll DIV = (ll)1e9+7;


int main(void) {
   ll M,D;
   cin>>M>>D;
   ll ans = 0;
   rep(j,1,M+1) rep(i,1,D+1) {
      if (j == (i/10)*(i%10)) {
         if (i/10==1) continue;
         if (i%10==1) continue;
         ans ++;
         // cout<<j<<" "<<i<<endl;
      }
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
def a(n) :
    if n % 2 == 0 :
        return n // 2
    else :
        return n * 3 + 1

while True :
    n = int(input())
    if n == 0 :
        break
    
    ans = 0
    while n != 1 :
        n = a(n)
        ans += 1
    print(ans)


Measured memory_bytes: 5592
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 201;
struct data {
  int nt, to;
} a[N << 1];
int head[N], cnt = 0;

void add(int x, int y) {
  a[++cnt].to = y;
  a[cnt].nt = head[x];
  head[x] = cnt;
}

int sz[N], w[N];
ll s[N];
void dfs(int u, int fa) {
  sz[u] = 1, s[u] = w[u];
  for(int i = head[u]; i; i = a[i].nt) {
    int to = a[i].to;
    if(to == fa) continue;
    dfs(to, u);
    sz[u] += sz[to];
    s[u] += s[to];
  }
}

ll f[N * N * N];
int c[N], p[N];

bool cmp(int x, int y) {
  return s[x] * sz[y] < s[y] * sz[x];
}

int main() {
  int n, x, d;
  cin >> n >> x >> d;
  scanf("%d", &w[1]);
  for(int i = 2, y; i <= n; ++i) {
    scanf("%d%d", &w[i], &y);
    add(y, i);
  }
  dfs(1, 0);
  int mx = min(n, d), tot = n * n * n;
  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  int pos = 1, now = mx, res = 0;
  for(; ; pos <<= 1) {
    if(now <= pos) {
      c[++res] = now;
      break;
    } else {
      c[++res] = pos;
      now -= pos;
    }
  }
  for(int i = 1; i <= n; ++i) 
   for(int o = 1; o <= res; ++o) {
    int nm = c[o];
    for(int j = tot; j >= sz[i] * nm; --j) {
      f[j] = min(f[j], f[j - sz[i] * nm] + s[i] * nm);
    } 
  }
  for(int i = 1; i <= n; ++i) p[i] = i;
  sort(p + 1, p + 1 + n, cmp);
  ll ans = 0;
  for(int o = 0; o <= tot; ++o) {
//    if(f[o] != f[100]) printf("%d %lld\n", o, f[o]); 
    if(f[o] > x) continue;
    ll pos = x - f[o];
    ll tmp = o;
    for(int i = 1; i <= n; ++i) {
      if(!pos) break;
      int u = p[i];
      ll num;
      if(u == 1) num = pos;
      else num = d - mx;
      ll Ad = min(pos / s[u], num);
      tmp += Ad * sz[u], pos -= s[u] * Ad;
    }
    ans = max(ans, tmp);
  }
  printf("%lld\n", ans);  
  return 0;
}

Measured memory_bytes: 63744
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N;
	cin >> N;
	vector<LL> A(N);
	int pos = 0;
	LL absMAX = 0;
	for(int i=0;i<N;++i){
		cin >> A[i];
		if( abs(A[i]) >= abs(absMAX) ){
			pos = i;
			absMAX = A[i];
		}
	}
	vector< pair<int,int> > ans;
	pair<int,int> temp;
	if( absMAX < 0 ){
		for(int i=0;i<N;++i){
			if( A[i] > 0 ){
				A[i] += absMAX;
				temp.first = pos+1;
				temp.second = i+1;
				ans.push_back( temp );
			}
		}
		for(int i=N-1;i>0;--i){
			if( A[i-1] > A[i] ){
				A[i-1] += A[i];
				temp.first = i+1;
				temp.second = i-1+1;
				ans.push_back( temp );
			}
		}
	}else{
		for(int i=0;i<N;++i){
			if( A[i] < 0 ){
				A[i] += absMAX;
				temp.first = pos+1;
				temp.second = i+1;
				ans.push_back( temp );
			}
		}
		for(int i=0;i<N-1;++i){
			if( A[i] > A[i+1] ){
				A[i+1] += A[i];
				temp.first = i+1;
				temp.second = i+1+1;
				ans.push_back( temp );
			}
		}
	}
	int size = ans.size();
	cout << size << endl;
	for(int i=0;i<size;++i){
		cout << ans[i].first << ' ' << ans[i].second <<'\n';
	}
	cout << flush;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

S = input()
size = len(S)
if len(S) % 2 == 0:
    ans = size // 2
    base = S[size // 2]
    for i in range(size // 2):
        if S[size // 2 - 1 - i] == S[size // 2 + i] == base:
            ans += 1
        else:
            break
    print(ans)
else:
    ans = size // 2 + 1
    base = S[size // 2]
    for i in range(size // 2):
        if S[size // 2 - 1 - i] == S[size // 2 + 1 + i] == base:
            ans += 1
        else:
            break
    print(ans)
    


Measured memory_bytes: 5968