akhauriyash/Code-Regression huggingface dataset:
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace atcoder;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main(){
    int n,q; cin>>n>>q;
    dsu unionfind(n);
    rep(i,q){
        int t,u,v; cin>>t>>u>>v;
        if(t==0){
            unionfind.merge(u,v);
        }else if(t==1){
            cout << unionfind.same(u,v) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 4004
while True:
    h,w = map(int,input().split())
    
    if h==0 and w==0:
        break
    
    print('#'*w)
    for _ in range(h-2):
        print('#',end='')
        print('.'*(w-2), end='')
        print('#')
    print('#'*w)
    
    print('')
    
    


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

typedef long long ll;
typedef std::pair<int, int> P;

const int maxn = 50050;

int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	int ans = 1;
	while (N / K) {
		ans++;
		N /= K;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end() 
using namespace std;

typedef long long ll;

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   int init = 1;
   for(int i=0; i<n; ++i) {
       int x;
       cin >> x;
       if(x == init) ++init;
   }
   --init;
   if(n == init) {
       cout << 0 << "\n";
       return 0;
   }
   if(init >= 1 && n - init >= 1)
       cout << n - init << "\n";
   else
       cout << -1 << "\n";
   return 0;
} 


Measured memory_bytes: 256
N, X = map(int, input().split())

count_p = [1] * (N+1) # パティの数
for i in range(1, N+1):
    count_p[i] += count_p[i-1] * 2

length = [1] * (N+1) # バーガーの長さ
for i in range(1, N+1) :
    length[i] += (length[i-1] + 1) * 2

def F(n, x): # レベルnバーガーの下x層のあるパティの数
    if n == 0:
        return min(1, x)
    if x == length[n] // 2 + 1:
        return count_p[n-1] + 1
    elif x > length[n] // 2 + 1:
        return count_p[n-1] + 1 + F(n-1, x-(length[n]//2+1))
    else:
        return F(n-1, max(0, x-1))
print(F(N, X))


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_H = 1005;
int H, W, A, B;
int ans[MAX_H][MAX_H];

int HH[MAX_H], WW[MAX_H];

signed main()
{
  cin >> H >> W >> A >> B;

  int a = A;
  A = W-A;
  int b = B;
  B = H-B;

  set<II> S;
  int k = 0;
  while(true) {
    if(a*H+k*(A-a) > A*H) {
      break;
    }
    S.insert(II(a*H+k*(A-a), A*H-k*(A-a)));
    // cerr << a*H+k*(A-a) << "," << A*H-k*(A-a) << endl;
    if(A == a) {
      break;
    }
    k++;
  }

  k = 0;
  while(true) {
    if(b*W+k*(B-b) > B*W) {
      break;
    }
    auto it = S.find(II(b*W+k*(B-b), B*W-k*(B-b)));
    if(S.end() == it) {
      if(B == b) break;
      k++;
      continue;
    } else {
      int zero = (*it).first, one = (*it).second;
      int k2 = 0;
      while(true) {
        if(a*H+k2*(A-a) == zero) {
          break;
        }
        k2++;
      }

      REP(i,W) {
        if(i < k) WW[i] = b;
        else WW[i] = B;
      }
      REP(i,H) {
        if(i<k2) HH[i] = a;
        else HH[i] = A;
      }

      REP(h,H) {
        REP(w,W) {
          if(HH[h] > 0 && WW[w] > 0) {
            cout << 1;
            HH[h]--; WW[w]--;
          } else {
            cout << 0;
          }
        }
        cout << endl;
      }

      return 0;
    }
  }

  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 1280
from fractions import gcd
A,B=map(int, raw_input().split())

n=gcd(A,B)
K=int(n**0.5)+2

s=set()
s.add(1)

for i in range(2,K):
		while n%i==0:
			s.add(i)
			n/=i
else:
	s.add(n)

print len(s)

Measured memory_bytes: 34792
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#include <set>
#include <queue>

using namespace std;

int main()
{
    string s; cin >> s;
    int k; cin >> k;
    set<string> ranking;
    priority_queue<pair<string,int>,
                   vector<pair<string,int>>,
                   greater<pair<string,int>>> q;
    for (int i = 0; i < s.size(); i++) {
        q.push(make_pair(s.substr(i, 1), i));
    }

    while (true) {
        string ss;
        int ii;
        tie(ss, ii) = q.top();
        q.pop();
        ranking.insert(ss);

        if (ranking.size() >= k)
            break;

        if (ii + ss.size() + 1 <= s.size()) {
            q.push(
                make_pair(s.substr(ii, ss.size()+1), ii));
        }
    }
    auto it = ranking.begin();
    for (int i = 0; i < k - 1; i++)
        it++;
    cout << *it << endl;
    return 0;
}

Measured memory_bytes: 640
import math

A, B, H, M = map(int, input().split())

a = abs(30 * H - 11/2 * M)
if a>180:
    a = 360 - a

a = math.radians(a)

b = A*A + B*B -2 * A * B * math.cos(a)
print(b**(1/2))

Measured memory_bytes: 9504
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

 
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n){ cin >> a[i]; a[i]--;}
  int cnt=0;
  int on=0;
  while(cnt<=n && on!=1){
    on = a[on];
    cnt++;
  }
  if(cnt>n){ cout << -1 <<endl; return 0;}
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

//0305
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int r = sc.nextInt();
            int t = sc.nextInt();
            boolean fr = r % 100 == 0;
            boolean ft = t % 30 == 0;
            int a = r / 100 + t / 30 * 5;
            System.out.print(a);
            if (fr && ft) {
                System.out.println();
            } else if (fr) {
                System.out.println(" " + (a + 5));
            } else if (ft) {
                System.out.println(" " + (a + 1));
            } else {
                System.out.println(" " + (a + 1) + " " + (a + 5) + " " + (a + 6));
            }
        }

    }
}


Measured memory_bytes: 26488
n, m = gets.chomp.split.map(&:to_i)

base, prev = nil, nil
h = Hash.new(0)
gets.chomp.split.map(&:to_i).each{|x|
    base = x - 1 if base.nil?
    h[x - prev] += 1 if prev
    prev = x
}
h[n + 1 - prev] += 1

arr = Array.new(h.keys.max, base)
arr.length.times{|i| h.each{|k, v| arr[i] += [(k - i - 1), 0].max * v}}

q = gets.to_i
gets.chomp.split.map(&:to_i).each{|query|
    i = arr.bsearch_index{|x| x <= query}
    puts i.nil? ? -1 : i + 1
}


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

int main(){
  int n,N,i,sum = 0;
  cin >> N;
  n = N;
  while(n!=0){
    sum += n%10;
    n /= 10; 
  }
  if(N%sum==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

class Program
{
    static void Main(string[] args)
    {
        List<int> XYABC = Console.ReadLine().Split(' ').Select(o => int.Parse(o)).ToList();
        int X = XYABC[0], Y = XYABC[1];
        List<int> p = Console.ReadLine().Split(' ').Select(o => int.Parse(o)).ToList();
        List<int> q = Console.ReadLine().Split(' ').Select(o => int.Parse(o)).ToList();
        List<int> r = Console.ReadLine().Split(' ').Select(o => int.Parse(o)).ToList();

        r.AddRange(p.OrderByDescending(o => o).Take(X));
        r.AddRange(q.OrderByDescending(o => o).Take(Y));

        Console.WriteLine(r.OrderByDescending(o => o).Take(X + Y).Select(o => (long)o).Sum());
    }
}

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

namespace AtCoderConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            // 標準入力から1行取得
            string input = Console.ReadLine();

            // 時計の数nを取得する
            int n = int.Parse(input);

            // 時計の針が一周する時間を格納する配列
            List<ulong> times = new List<ulong>();

            // 格納
            for(int i = 0; i < n; i++)
            {
                times.Add(ulong.Parse(Console.ReadLine()));
            }

            // 最小公倍数を求める
            while (times.Count != 1u)
            {
                ulong tmp = Lcm(times[0], times[1]);
                times.RemoveAt(1);
                times.RemoveAt(0);
                times.Add(tmp);
            }

            // 標準出力に出力
            Console.WriteLine(times[0]);
        }

        // 最小公倍数
        static ulong Lcm(ulong a, ulong b)
        {
            return a / Gcd(a, b) * b;
        }

        // ユークリッドの互除法
        static ulong Gcd(ulong a, ulong b)
        {
            return (a < b) ? Gcd(b, a)
                : (b > 0) ? Gcd(b, a % b)
                : a;
        }
    }
}


Measured memory_bytes: 13268
#include <stdio.h>

int main()
{
    char c;
    scanf("%c", &c);

    switch(c)
    {
    	case 'a':
    		printf("vowel\n");
    	break;

    	case 'i':
    		printf("vowel\n");
    	break;

    	case 'u':
    		printf("vowel\n");
    	break;

    	case 'e':
    		printf("vowel\n");
    	break;

    	case 'o':
    		printf("vowel\n");
    	break;

    	default:
    		printf("consonant\n");

    }

	return 0;
}

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

using namespace std;

int main ()
{
    long long n;
    cin >> n;
    vector <long long> nums;
    nums.push_back(0);
    for (long long i = 1; i < n; i++)
    {
        nums.push_back(0);
        long long a;
        cin >> a;
        nums[a - 1]++;
    }
    for (long long i = 0; i < n; i++)
    {
        cout << nums[i] << endl;
    }
}

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

using namespace std;
map<int, bool>one, non;
int main()
{
    int n, m, x, y;
    cin >> n >> m;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        if(x==1) one[y]=true;
        if(y==1) one[x]=true;
        if(x==n) non[y]=true;
        if(y==n) non[x]=true;
    }
    for(auto i: one) if(non[i.first]) puts("POSSIBLE"), exit(0);
    puts("IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 14336
N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
ans = ddict(int)
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        ans[min(p1,p2,p3)] += 1
for n in range(1,N):
    print(ans[n])

Measured memory_bytes: 50908
#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(a < b) swap(a,b);
    if(b == 0) return a;
    else return gcd(b, a%b);
}
long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b;
    cin >> a >> b;
    cout << lcm(a,b) << endl;
    return 0;
}

Measured memory_bytes: 3604
// doot diddly donger cuckerino Hahahahahah


#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vi = vector<int>;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = acos(-1);

template <typename T> inline T mini(T& x, T y) { return x = min(x, y); }
template <typename T> inline T maxi(T& x, T y) { return x = max(x, y); }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

class DModSum {
public:
  
  void solve(std::istream& cin, std::ostream& cout) {
    ll n;
    cin >> n;
    ll ans = n * (n - 1) / 2;
    
    cout << ans << endl;
  }
};

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
	DModSum solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

class PaizaSample
{

    public class Team
    {
        public int index;
        public string name;
        public int point;

        public Team(int index, string name, int point)
        {
            this.index = index;
            this.name = name;
            this.point = point;
        }
    }

    static void Main()
    {

        bool first = true;
        while (true)
        {
            int n = int.Parse(Console.ReadLine());
            if (n == 0)
            {
                break;
            }

            if (!first)
            {
                Console.WriteLine();
            }

            List<Team> list = new List<Team>();

            for (int i = 0; i < n; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                list.Add(new Team(i, input[0], int.Parse(input[1]) * 3 + int.Parse(input[3])));

            }

            //list.Sort((a, b) => b.point - a.point);
            list = list.OrderByDescending(a => a.point).ThenBy(a => a.index).ToList();

            foreach (Team t in list)
            {
                Console.WriteLine("{0},{1}", t.name, t.point);
            }

            first = false;
        }

       // Console.ReadKey();

    }
}

Measured memory_bytes: 10076
#流れ
#ソートして、探索の方向を一方向にするという方法だけだと、O(n^3)となりアウトとなる。
#小さい2辺a,b(a < b)を固定すると最後の1辺cはc < a + bを満たす必要があることを踏まえる。
#取得した配列をソートし、bの右側にはa,b以上の長さの辺が並ぶようになる。
#bの右隣から、三角形をなす条件を一々チェックしていくとTLEになる
#そこで、bより右側にある数のなす列に対し、三角形の条件を満たさなくなる最初の値(のインデックス)を求める。
#bsearchを使うと、これにかかる時間はO(logn)でいける。
#求めたインデックスと、bのインデックスの差がaとbを固定したときの三角形をなすパターン数になる。
n = gets.to_i
arr = gets.chomp.split(' ').map(&:to_i).sort
i = 0
count = 0
while i < n-2
  j = i + 1
  while j < n-1
    sub_arr = arr[(j+1)..(n-1)]#3つ目の辺の候補リスト
    over_id = sub_arr.bsearch_index {|e| e >= arr[i] + arr[j]} || sub_arr.size#三角形を作れなくなる最初のindexを取得
    count += over_id
    j += 1
  end
  i += 1
end
puts count

Measured memory_bytes: 14264
import std,core.bitop;int l,n;void q(int[]a...){a.writefln!"%(%s %)";}void main(){l.readf!"%d";for(q(n=l.bsr+1,l.popcnt+n*2-3);l>1;q(n-1,n,0),q(n-1,n--,l/=2))l%2&&q(1,n,l-1);}

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

int main(){
    int64_t n;
    cin >> n;
    int64_t a[111000];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int64_t ans = a[0];
    for(int i=0; i<n; i++){
        if(a[i] == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    
    for(int i=1; i<n; i++){
        if(ans > 1000000000000000000ll / a[i]){
            ans = -1;
            break;
        }else{
            ans *= a[i];
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4412
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 ll a[100002][3];
 ll r[100002][3];
 ll n;
 ll res(ll b,ll c)
 {
     ll i;
     if(b==n)
        return 0;
     if(r[b][c]==-1)
     {
         ll ma=INT_MIN;
         for(i=0;i<3;i++)
         {
             if(i==c)
                continue;
             ma=max(ma,a[b][i]+res(b+1,i));

         }
         r[b][c]=ma;
     }
     return r[b][c];
 }
int main()
{
    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     ll t,i,j,k,x,y,c=0,m;
     cin>>n;
     for(i=0;i<n;i++)
     {
         cin>>a[i][0]>>a[i][1]>>a[i][2];

     }
 memset(r,-1,sizeof(r));
     ll mi=max(res(0,0),max(res(0,1),res(0,2)));
     cout<<mi<<"\n";

}


Measured memory_bytes: 12800
# Your code here!
n,k=gets.split
n=n.to_i
k=k.to_i

array2=[]

n.times{
    
    a,b=gets.split
    
    
    a=a.to_i
    b=b.to_i
    array2<<[a,b]
    
    
    
}



array2=array2.sort
answer=0
i=0
loop{
    answer+=array2[i][1]
    if answer>=k
        break
    else 
        i+=1
    end
    
    
    
    
    
}





puts   array2[i][0]


Measured memory_bytes: 11152
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int> pque;
	int h;

	for(int i=0; i<10; i++){
		cin >> h; 
		pque.push(h);
	}

	for(int i=0; i<3; i++){
		cout << pque.top() << endl;
		pque.pop();
	}

	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
#define ll          long long int
#define lld          long double
#define pb          push_back
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define vec         vector<ll>
#define all(a)     (a).begin(),(a).end()
#define F           first
#define S           second
#define mod         1000000007
#define nmod         -1000000007
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repi(i,a,b)	for(ll  i=a;i<=b;i++)
#define per(i,a,b)  for(ll i=a;i>=b;i--)
#define mp          make_pair
#define mit         map<ll,ll>::iterator
#define sit         set<ll>::iterator
#define pit         pair<ll,ll>::iterator
#define xxx         exit(0);
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;
ll xo(ll x, ll y) 
{ 
   return (x | y) & (~x | ~y); 
}  
ll bin_Expo(ll x,ll n)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return bin_Expo(x*x,n/2);
    else                             //n is odd
        return x*bin_Expo(x*x,(n-1)/2);
}
ll mod_Expo(ll x,ll n,ll M)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return mod_Expo((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*mod_Expo((x*x)%M,(n-1)/2,M))%M;
 
}
bool prime_check(ll x)
{
    bool prime = (x >= 2);
    for (ll i = 2; i * i <= x; i++) 
    {
        if (x % i == 0) 
        {
            prime = false;
            break;
        }
    }
    return prime;
}
ll logg(ll base,ll x) 
{
    return (ll)(log(x)/log(base));
}
ll n,k,dp[100005][2][2][2],a[100005], b[100005],c[100005];
ll cc(ll ind,ll p,ll q, ll r)
{
	if(ind==n) return 0;
	if(dp[ind][p][q][r]!=-1) return dp[ind][p][q][r];
	ll ans = 0;
	if(p==1)
	{
		ans=max(ans,b[ind]+cc(ind+1,0,1,0));
		ans=max(ans,c[ind]+cc(ind+1,0,0,1));
	}
	else if(q==1)
	{
		ans=max(ans,a[ind]+cc(ind+1,1,0,0));
		ans=max(ans,c[ind]+cc(ind+1,0,0,1));
	}
	else if(r==1)
	{
		ans=max(ans,b[ind]+cc(ind+1,0,1,0));
		ans=max(ans,a[ind]+cc(ind+1,1,0,0));
	}
	else
	{
		ans=max(ans,a[ind]+cc(ind+1,1,0,0));
		ans=max(ans,b[ind]+cc(ind+1,0,1,0));
		ans=max(ans,c[ind]+cc(ind+1,0,0,1));
	}
	return dp[ind][p][q][r]=ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS; 
    while(TESTS--)
    {
    	ll i,l,j,x1,y1,ans,x,y,q;
    	cin>>n;
    	rep(i,0,n) cin>>a[i]>>b[i]>>c[i];
		repi(i,0,n){
			rep(p,0,2){
				rep(q,0,2){
					rep(r,0,2)
					dp[i][p][q][r]=-1;
				}
			}
		}
		cout<<cc(0,0,0,0);
	}
	return 0;
}














Measured memory_bytes: 21604
var input = '';
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  input += chunk;
});

readable.on( 'end', function() {
  var data = input.split( "\n" );
  var rc = data[0].split( " " ).map( Number );
  var r = rc[0];
  var c = rc[1]; 
  var t = Array( c+1 );
  for( var i=0; i<c+1; i++ ) { t[i] = 0; }
  var output = [];
  var len = r+1;
  for( var index=1; index<len; index++ ) {
    var nums = data[index].split( ' ' ).map( Number );
    var sum = 0;
    for( var j=0; j<c; j++ ) {
      sum += nums[j];
      t[j] += nums[j];
    }
    t[c] += sum;
    nums.push( sum );
    output.push( nums.join( " " ) );
  }
  output.push( t.join( " " ) );
  console.log( output.join( "\n" ) );
});

Measured memory_bytes: 10160
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>v(n,vector<int>(m));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char element;
            cin>>element;
            if(element=='#')
            {
                v[i][j]=-1;
            }
            else
            {
                v[i][j]=0;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(v[i][j]==-1)
            {
                if(i>0&&v[i-1][j]!=-1)
                {
                    v[i-1][j]++;
                }
                if(i<n-1&&v[i+1][j]!=-1)
                {
                    v[i+1][j]++;
                }
                if(j<m-1&&v[i][j+1]!=-1)
                {
                    v[i][j+1]++;
                }
                if(j>0&&v[i][j-1]!=-1)
                {
                    v[i][j-1]++;
                }
                if(i>0&&j>0&&v[i-1][j-1]!=-1)
                {
                    v[i-1][j-1]++;
                }
                if(i>0&&j<m-1&&v[i-1][j+1]!=-1)
                {
                    v[i-1][j+1]++;
                }
                if(i<n-1&&j>0&&v[i+1][j-1]!=-1)
                {
                    v[i+1][j-1]++;
                }
                if(i<n-1&&j<m-1&&v[i+1][j+1]!=-1)
                {
                    v[i+1][j+1]++;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(v[i][j]==-1)
            {
                cout<<"#";
                continue;
            }
            cout<<v[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 3596
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

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




/******************************************************************************************/

ll sum[200005];


int main() {

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

	int n;
	cin >> n;
	vector<int> a(n);
	int mini = 0;
	int mini_idx = 0;
	int maxi = 0;
	int maxi_idx = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i] >= 0) {
			if (maxi < a[i]) {
				maxi = a[i];
				maxi_idx = i + 1;
			}
		}
		else
		{
			if (mini > a[i]) {
				mini = a[i];
				mini_idx = i + 1;
			}
		}
	}

	int cnt = 0;
	vector<pii> ans;
	//cout << maxi << " " << mini << endl;
	if (abs(maxi) > abs(mini)) {
		cnt = maxi;

		//正にする
		for (int i = 0; i < n; i++)
		{
			if (a[i] < 0) {
				a[i] += cnt;
				ans.push_back(pii(maxi_idx, i + 1));
			}
		}

		//累積和の感じ

		for (int i = 0; i < n - 1; i++)
		{
			ans.push_back(pii(i + 1, i + 2));
		}

	}
	else
	{
		cnt = mini;
		//負にする
		for (int i = 0; i < n; i++)
		{
			if (a[i] > 0) {
				a[i] += cnt;
				ans.push_back(pii(mini_idx, i + 1));
			}
		}

		for (int i = n - 1; i > 0; i--)
		{
			ans.push_back(pii(i + 1, i));
		}
	}
	

	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i].first << " " << ans[i].second << endl;
	}

	return 0;
}


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

const char ROCK = 'g';
const char PAPER = 'p';

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

    string s;
    cin >> s;

    int n = s.length();

    const int maxRockCount = (n >> 1) + (n & 1);

    int rockCount = 0;
    int paperCount = 0;
    int score = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == PAPER) {
            if (rockCount == maxRockCount) {
                ++paperCount;
            } else {
                --score;
                ++rockCount;
            }
        } else {
            if (paperCount < rockCount) {
                ++score;
                ++paperCount;
            } else {
                ++rockCount;
            }
        }
    }

    cout << score << endl;

    return 0;
}


Measured memory_bytes: 512
n = int(input())
a_lst = list(map(int,input().split()))
b_lst = list(map(int,input().split()))
monster = 0

for i in range(n):
    a1 = a_lst[i]
    a2 = a_lst[i+1]
    b1 = b_lst[i]
    tmp = b1-a1

    monster += min(a1,b1)
    if tmp>0:
        if a2-tmp<=0:
            monster += a2
            a_lst[i+1] = 0
        else:
            monster += tmp
            a_lst[i+1] -= tmp

print(monster)

Measured memory_bytes: 19244
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int check(const vector<int> &v, int cp){
	int lp = cp, rp = cp + 1;
	while(lp > 0){
		int c = v[lp];
		int tl, tr;
		for(tl = lp; v[tl] == c; --tl);
		for(tr = rp; v[tr] == c; ++tr);
		if((lp - tl) + (tr - rp) < 4){
			break;
		}
		lp = tl;
		rp = tr;
	}
	return lp + (v.size() - 1 - rp);
}

int main(){
	int n;
	while(scanf("%d", &n), n){
		vector<int> v(n + 2);
		for(int i = 1; i <= n; ++i){
			scanf("%d", &v[i]);
		}

		int ans = n;
		for(int i = 1; i <= n; ++i){
			int c = v[i];
			for(int j = 1; j <= 2; ++j){
				int t = (c + j) % 3;
				if(!t){ t = 3; }
				v[i] = t;
				ans = min(ans, check(v, i));
			}
			v[i] = c;
		}
		
		printf("%d\n", ans);
	}
}

Measured memory_bytes: 1072
import math


def sieve_of_eratosthenes(n):
    if n == 1:
        return []
    limit = int(math.sqrt(n))
    targets = [i for i in range(2, n + 1)]
    primes = []
    while targets[0] <= limit:
        p = targets[0]
        primes.append(p)
        targets = [i for i in targets if i % p != 0]
    return primes + targets


n = int(input())
p = sieve_of_eratosthenes(n)
ans = 1
for i in p:
    cnt = 0
    for j in range(2, n + 1):
        while j % i == 0:
            j //= i
            cnt += 1
    ans *= cnt + 1
    ans %= 10 ** 9 + 7
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

using Pii = pair<int, int>;

int solve(int n, int q) {
    vector<Pii> max_points(n, {0, 0}), min_points(n, {0, 0});
    for(int i=0;i<n;++i) {
        max_points[i].second = i;
        min_points[i].second = i;
    }
    int s, k, player;
    for(int i=0;i<q;++i) {
        cin >> s >> k;
        for(int j=0;j<k;++j) {
            cin >> player;
            max_points[player-1].first += s;
            if(k == 1) min_points[player-1].first += s;
        }
    }

    sort(max_points.rbegin(), max_points.rend());
    sort(min_points.begin(), min_points.end());
    if(max_points[0].second != min_points[0].second) {
        return max_points[0].first+1-min_points[0].first;
    }
    int ret1 = max_points[1].first+1-min_points[0].first;
    int ret2 = max_points[0].first+1-min_points[1].first;
    return max(ret1, ret2);
    
}

int main() {
    int n,m;
    while(cin >> n >> m && n) {
        cout << solve(n, m) << endl;
    }
}


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

using ll = long long;

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

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

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

    int N, K; cin >> N >> K;
    vector<int> A(N); cin >> A;

    vector<ll> sum;
    ll all_or = 0;
    rep(i, N) {
        ll s = 0;
        for (int j = i; j < N; j++) {
            s += A[j];
            sum.push_back(s);
            all_or |= s;
        }
    }

    vector<int> idx;
    rep(i, sum.size()) idx.push_back(i);

    ll ans = 0;
    for (ll b = (1LL << 41); b > 0; b >>= 1) {
        if (!(all_or & b)) continue;
        vector<int> on;
        for (const int& i : idx) {
            if (sum[i] & b) {
                on.push_back(i);
            }
        }
        if (on.size() >= K) {
            ans |= b;
            idx = on;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 8300
#include<stdio.h>
int main(){
  int  a,b,c;
  scanf("%d%d%d",&a,&b,&c);
  if ( (a==b && a==5) || (b==c && b==5) || (a==c && a==5) ) {
   	printf("YES\n");  
  } else {
   	puts("NO"); 
  }
 	return 0; 
}


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

char grp(int x){
  if(x == 2)
    return 'c';
  if(x == 4 or x == 6 or x == 9 or x == 11)
    return 'b';
  else
    return 'a';
}

int main() {
  int p, q;
  cin >> p >> q;
  
  cout << ( grp(p) == grp(q) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;

int main()
{
	double r = 0;
	cin >> r;

	cout << fixed;
	cout << setprecision(8) << (M_PI*r*r) << " ";
	cout << setprecision(8) << (2 * M_PI*r) << endl;

	return 0;
}


Measured memory_bytes: 3256
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define infll 1000000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define mod 1000000007
#define N 200009
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;

int B,W,a[N],b[N],fac[N],inv[N],bin[N];
int main(){
	scanf("%d%d",&B,&W);
	int i;
	for (i=fac[0]=1; i<N; i++) fac[i]=(ll)fac[i-1]*i%mod;
	inv[0]=inv[1]=1;
	for (i=2; i<N; i++) inv[i]=mod-(ll)mod/i*inv[mod%i]%mod;
	for (i=3; i<N; i++) inv[i]=(ll)inv[i-1]*inv[i]%mod;
	for (i=bin[0]=1; i<N; i++) bin[i]=(ll)bin[i-1]*(mod+1>>1)%mod;
	for (i=1; i<B+W; i++){
		if (i>=W)
			a[i]=(ll)cbn(i-1,W-1)*bin[i]%mod;
		if (i>=B)
			b[i]=(ll)cbn(i-1,B-1)*bin[i]%mod;
		ad(a[i],a[i-1]);
		ad(b[i],b[i-1]);
	}
	for (i=1; i<=B+W; i++) printf("%lld\n",(ll)(1+a[i-1]+mod-b[i-1])*(mod+1>>1)%mod);
	return 0;
}


Measured memory_bytes: 6144
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int b[][] = new int[N][3];
for(int i = 0; i < N ; i++){
    for(int j = 0; j < 3 ; j++){
      b[i][j] = sc.nextInt();
    }
}
int place = 0;
int chk = 0;
int abs = 0;
for(int i=0; i<N; i++){
  abs = Math.abs(place - (b[i][1] + b[i][2]));
  if(b[i][0] >= place + abs){
    if(b[i][0] % 2 == 0){
      if(Math.abs(place - abs) % 2 != 0){
        chk = 1;
       }
    }else{
      if(Math.abs(place - abs) % 2 == 0){
        chk = 1;
      }
    }
  }else{
     chk = 1;
     break;
  }
   place = b[i][1] + b[i][2];
}
if(chk == 0) System.out.print("Yes");
else         System.out.print("No");
}//main
}//Main

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

int main(){
  vector<int> A(3);
  for(int i=0;i<3;i++){
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());

  if((A.at(0)==5)&&(A.at(1)==5)&&(A.at(2)==7)){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
from math import gcd

def euclid(A,B):
    if B==1:
        return 1,1-A
    else:
        q,r = A//B,A%B
        x1,y1 = euclid(B,r)
        return y1,x1-q*y1

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

N = int(input())
dic = primeFactor(2*N)

data = []
for p in dic:
    data.append(p**dic[p])

n = len(data)
ans = 2*N
for i in range(2**n):
    A = 1
    B = 1
    for j in range(n):
        if i>>j & 1:
            A *= data[j]
        else:
            B *= data[j]

    x0,y0 = euclid(A,B)

    limit1 = (1-y0)//A
    if limit1*A+y0<1:
        limit1+=1

    limit2 = (x0+1)//B
    if limit2*B- x0<1:
        limit2+=1

    limit = max(limit1,limit2)

    tmp = (B*limit-x0)*A
    ans = min(ans,tmp)

print(ans)

Measured memory_bytes: 73716
#!/usr/bin/env python3
def main():
    R, G, B = map(int, input().split())
    K = int(input())

    for i in range(K):
        if R >= G:
            G = G * 2
        else:
            if G >= B:
                B = B * 2
        if B > G > R:
            print("Yes")
            exit()
    print("No")
if __name__  == '__main__':
    main()

Measured memory_bytes: 9008
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-5;
const ll MOD=1e+7;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int main(){
    int h,w,n;cin>>n>>h>>w;
    cout<<(n-h+1)*(n-w+1)<<endl;
}   


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

void solve(long long N, long long K, std::vector<long long> p) {
    vector<double> table;
    vector<double> prob_table;
    table.push_back(0);
    prob_table.push_back(0);

    for (long long i = 0; i < N; i++) {
        double probability = 0.5 * p[i] + 0.5;
        prob_table.push_back(probability);
        double minus_prob = 0;
        if ((long long)table.size() - K >= 0) {
            minus_prob = prob_table[(long long)table.size() - K];
        }
        table.push_back(probability + table[(long long)table.size() - 1] - minus_prob);
    }

    printf("%.12lf\n", *max_element(table.begin(), table.end()));
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can
// remove this line by using your custom template)
int main() {
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> p(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &p[i]);
    }
    solve(N, K, std::move(p));
    return 0;
}


Measured memory_bytes: 5100
#include <iostream>

using namespace std;

int main()
{
    int n,m;
    int a[1001];
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    int sum=0;
    for(int i=0; i<n; i++)
    {
        sum+=a[i];
    }
    int count=0;
    for(int i=0; i<n; i++)
    {
        if(a[i]*4*m>=sum)
            count++;
    }
    if(count>=m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
def check(st):
    for d in range(len(st)):
        if st[d]=="3":
            return True
    return False

num = int(input())
str=""
for d in range(3,num+1):
    s = "%d"%(d)
    if d%3==0 or check(s):
        str+=" %d"%(d)
print(str)

Measured memory_bytes: 5636
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

ll calc1(ll t1, ll t2, ll a1, ll a2, ll b1, ll b2) {
	if (a2 < b2) {
		swap(a2, b2);
		swap(a1, b1);
	}
	ll D = t1 * (b1 - a1) + t2 * (b2 - a2);
	if (D > 0) {
		return 0;
	}
	if (D == 0) {
		return -1;
	}
	else {
		if (b1 - a1 < 0)return 0;
		ll c = -t1 * (b1 - a1);
		if (c % D == 0) {
			return c / D;
		}
		else {
			return c / D + 1;
		}
	}
}

ll calc2(ll t1, ll t2, ll a1, ll a2, ll b1, ll b2) {
	if (a1 < b1) {
		swap(a1, b1);
		swap(a2, b2);
	}
	ll D = t1 * (b1 - a1) + t2 * (b2 - a2);
	if (D > 0) {
		return t1 * (a1 - b1) / D;
	}
	else if (D <= 0) {
		return 0;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll T1, T2, A1, A2, B1, B2;
	cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;
	ll ans = calc1(T1, T2, A1, A2, B1, B2);
	if (ans == -1) {
		cout << "infinity\n";
		return 0;
	}
	ans += calc2(T1, T2, A1, A2, B1, B2);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;
typedef pair<ll,ll> pairs;
vector<pairs> p;


ll gcd(ll A,ll B){
    if (A%B==0)return(B);
    else return(gcd(B,A%B));
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

vector<vector<ll>> combination(ll n, ll r){
    vector<vector<ll>> v(n + 1, vector<ll>(n + 1, 0));
    for(ll i=0;i<v.size();++i){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(ll i=1;i<v.size();++i){
        for(ll j=0;j<i;++j){
            v[i][j] = (v[i - 1][j - 1] + v[i - 1][j]);
        }
    }
    return v;
}

bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

int main(){
    string s;
    cin>>s;
    ll w;
    cin>>w;
    for(ll i=0;i<s.size();i+=w){
        cout<<s[i];
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 256
from sys import stdin

def solve(n, hs):
    ans = 0
    max_height = hs[0]
    for i, height in enumerate(hs):
        if i == 0 or max_height <= height:
            ans = ans + 1
            max_height = height
    return ans


def main():
    lines = stdin.readlines()
    n = int(lines[0])
    hs = [int(n) for n in lines[1].split(' ')]
    ans = solve(n, hs)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
import java.util.Scanner;

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

	public static void main(String[] args) {
		char[] S = sc.next().toCharArray();
		int N = S.length;
		long K = sc.nextLong();
		int[][] minApp = new int[N + 1][N + 1];
		for (int len = 2; len <= N; ++len) {
			for (int i = 0; i + len <= N; ++i) {
				minApp[i][i + len] = Math.min(minApp[i + 1][i + len] + 1, minApp[i][i + len - 1] + 1);
				if (S[i] == S[i + len - 1]) minApp[i][i + len] = Math.min(minApp[i][i + len], minApp[i + 1][i + len - 1]);
			}
		}
		long[][] count = new long[N + 1][N + 1];
		for (int i = 0; i < N; ++i) {
			count[i][i] = 1;
			count[i][i + 1] = 1;
		}
		count[N][N] = 1;
		for (int len = 2; len <= N; ++len) {
			for (int i = 0; i + len <= N; ++i) {
				if (S[i] == S[i + len - 1]) {
					count[i][i + len] = count[i + 1][i + len - 1];
				} else if (minApp[i + 1][i + len] > minApp[i][i + len - 1]) {
					count[i][i + len] = count[i][i + len - 1];
				} else if (minApp[i + 1][i + len] < minApp[i][i + len - 1]) {
					count[i][i + len] = count[i + 1][i + len];
				} else {
					count[i][i + len] = count[i + 1][i + len] + count[i][i + len - 1];
					if (count[i][i + len] > K) count[i][i + len] = K + 1;
				}
			}
		}
		StringBuilder ans = new StringBuilder();
		if (count[0][N] < K) {
			ans.append("NONE");
		} else {
			int left = 0;
			int right = N;
			while (true) {
				if (left == right) {
					ans.append(new StringBuilder(ans).reverse());
					break;
				}
				if (left + 1 == right) {
					StringBuilder rev = new StringBuilder(ans).reverse();
					ans.append(S[left]).append(rev);
					break;
				}
				if (S[left] == S[right - 1]) {
					ans.append(S[left]);
					left++;
					right--;
				} else if (minApp[left + 1][right] > minApp[left][right - 1]) {
					ans.append(S[right - 1]);
					right--;
				} else if (minApp[left + 1][right] < minApp[left][right - 1]) {
					ans.append(S[left]);
					left++;
				} else {
					if (S[left] < S[right - 1]) {
						if (count[left + 1][right] >= K) {
							ans.append(S[left]);
							left++;
						} else {
							K -= count[left + 1][right];
							ans.append(S[right - 1]);
							right--;
						}
					} else {
						if (count[left][right - 1] >= K) {
							ans.append(S[right - 1]);
							right--;
						} else {
							K -= count[left][right - 1];
							ans.append(S[left]);
							left++;
						}
					}
				}
			}
		}
		System.out.println(ans.toString());
	}
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}


string s[305];
int ans[305][305];


int main2() {
  CLR(ans, 0);

  int H = nextInt();
  int W = nextInt();
  int K = nextInt();

  REP(i, H) cin >> s[i];

  int id = 0;
  REP(i, H) {

    bool first = true;
    REP(j, W) {
      if (s[i][j] == '#') {
        first = false;
        id++;
      }
      if (!first) ans[i][j] = id;
    }

    for (int j = W-2; j >= 0; j--) {
      if (ans[i][j] == 0) {
        ans[i][j] = ans[i][j+1];
      }
    }
  }

  for (int i = 1; i < H; i++) {
    REP(j, W) {
      if (ans[i][j] == 0) {
        ans[i][j] = ans[i-1][j];
      }
    }
  }
  for (int i = H-2; i >= 0; i--) {
    REP(j, W) {
      if (ans[i][j] == 0) {
        ans[i][j] = ans[i+1][j];
      }
    }
  }

  REP(i, H) {
    cout << ans[i][0];
    REP(j, W-1) cout << " " << ans[i][j+1];
    cout << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 1280
n = int(input())
v = list(map(int, input().split()))
v.sort()

for i in range(1, n):
    # print(i)
    if i == n - 1:
        print(sum(v) / 2)
        exit()
    v[i] = (v[i] + v[i - 1]) / 2
    v[i-1]=0


Measured memory_bytes: 2940
#include <stdio.h>

int tri[5002][5002];

int max(int a, int b)
{
    return (a > b ? a : b);
}

int main(void)
{
    int i, j;
    int n, m;
    int x, y, size;
    int res;
    
    scanf("%d%d", &n, &m);
    
    for (i = 0; i < m; i++){
        scanf("%d%d%d", &y, &x, &size);
        tri[y][x] = size + 1;
    }
    
    res = 0;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= i; j++){
            tri[i][j] = max(tri[i][j], (max(tri[i - 1][j - 1], tri[i - 1][j]) - 1));
            if (tri[i][j] != 0){
                res++;
            }
        }
    }
    
    printf("%d\n", res);
    
    return (0);
}

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

int main() {
	long long n, a, b; cin >> n >> a >> b;
	vector<int>x(n); for (auto&& xx : x)cin >> xx;
	
	long long ans = 0;
	for (int i = 1; i < n; i++) {
		ans += min((x[i] - x[i - 1]) * a, b);
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

using ll = long long;
using ull = unsigned long long;
template<class T> using v = vector<T>;

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

template<class T> T read() { T x{}; cin >> x; return x; }
template<class T> v<T> read(int N){ v<T> x(N); REP(i, N) cin >> x[i]; return x; }

template<class T>
void write(const T &x){ cout << x << endl; }
void write(double x){ printf("%.15f\n", x); }

const double PI=3.14159265358979323846;

// vars

void input() {
}

void solve() {
}

double kaijo(ll N){
    double ret = 1;
    for(ll i = 1; i <= N; ++i){ ret *= i; }
    return ret;
}

int main() {
    auto N = read<ll>();
    auto xy = read<double>(2 * N);

    v<ll> i(N);
    iota(i.begin(), i.end(), 0);
    double ans = 0;
    do{
        for(int j = 1; j < N; ++j){
            auto xjpre = xy[2 * i[j-1]], xj = xy[2 * i[j]];
            auto yjpre = xy[2 * i[j-1] + 1], yj = xy[2 * i[j] + 1];
            ans += sqrt(pow(xj - xjpre, 2) + pow(yj - yjpre, 2) );
        }
    }while(next_permutation(i.begin(), i.end()));
    ans /= kaijo(N);

    write(ans);

}



Measured memory_bytes: 256
n=int(input())
f=0
ans=7
if n%2==0:
    print(-1)
else:
    count=1
    while(ans<n):
        ans*=10
        ans+=7
        count+=1
    for i in range(count,10**6+1):
        ans=ans%n
        if ans==0:
            print(i)
            f=1
            break
        ans*=10
        ans+=7
    if f==0:
        print(-1)
    

Measured memory_bytes: 63316
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)

    print("second" if all(A[i] % 2 == 0 for i in range(N)) else "first")


if __name__ == '__main__':
    main()


Measured memory_bytes: 43736