akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define max(a, b)	(((a) > (b)) ? (a) : (b))		/* ２個の値の最大値 */
#define min(a, b)	(((a) < (b)) ? (a) : (b))		/* ２個の値の最小値 */
#define ENTER		printf("\n")					/* 改行プリント */
int DBG = 1;										/* デバッグプリント 提出時は0 */
/* main *************************************************************/
int main()
{
	int		a[30],b,c[30],i,j,k,n,m,x,y,ans = 0;
	char	str[256];
	
	scanf("%d", &n);
	a[0] = -1;
	for(i=1;i<=n;i++) scanf("%d", &a[i]);
	for(i=1;i<=n;i++) {
		scanf("%d", &b);
		ans += b;
	}
	for(i=1;i<n;i++) scanf("%d", &c[i]);
	
	for(i=1;i<=n;i++) {
		if (a[i] == (a[i-1] + 1)) {
			ans += c[a[i-1]];
		}
	}

	printf("%d\n",ans);


	return 0;
}


Measured memory_bytes: 128
n=int(input())
a=[i for i in map(int,input().split())]
count=0
answer=0
for i in range(n):
    if count==n:
        break
    if count+1!=a[i]:
        answer+=1
    else:
        count+=1
if count==0:
    print(-1)
else:
    print(answer)

Measured memory_bytes: 24744
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

Vi V;
int n;

int calc(Vi V){
	int c0=0,c1=0;
	for (int i:V) if (i&1) c1++;else c0++;
	if (c0%2==1) return 1;
	if (c0%2==0&&c1>1) return 0;
	int g=0;
	For(i,0,V.size()){
		if (V[i]&1){
			if (V[i]==1) return 0;
			V[i]--;
		}
		g=__gcd(g,V[i]);
	}
	For(i,0,V.size()) V[i]/=g;
	return !calc(V);
}

int main(){
	n=IN();
	For(i,0,n) V.pb(IN());
	puts(calc(V)?"First":"Second");
}

Measured memory_bytes: 10104
#include <bits/stdc++.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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    vector<int> x(N), y(N), h(N);
    for(int i=0; i<N; i++) cin >> x[i] >> y[i] >> h[i];
    int cmpx, cmpy, cmph;
    for(int i=0; i<N; i++){
        if(h[i] > 0){
            cmpx = x[i], cmpy = y[i], cmph = h[i];
        }
    }

    for(int a=0; a<=100; a++){
        for(int b=0; b<=100; b++){
            int height = cmph + abs(a-cmpx) + abs(b-cmpy);
            bool flg = true;
            for(int i=0; i<N; i++) if(max(0, height-abs(a-x[i])-abs(b-y[i])) != h[i]) flg = false;

            if(flg){
                printf("%d %d %d\n", a, b, height);
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n;
	cin >> n;
	long long min = (long long)1e18;
	for(long long i = 1; i <= sqrt(n); i++) {
		if((n % i) == 0 && ((n/i) + i - 2) < min) {
			min = (i + (n/i)) - 2;
		}
	}
	cout <<	min << endl;
	return 0;
}

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

int main(){
    int n,m,c;
    cin >> n >> m >> c;
    int ans=0;
    vector <int> b(m),a(m);
    rep(i,m){
        cin >> b[i];
    }

    int ans2;
    rep(i,n){
        ans2=0;
        rep(i,m){
            cin >> a[i];
            ans2+=a[i]*b[i];
        }
        if((ans2+c)>0){
            ++ans;
        }
    }

    cout << ans << endl;

    

    return 0;
}

Measured memory_bytes: 3568
import sys
c=["light fly", "fly", "bantam", "feather", "light", "light welter",
   "welter", "light middle", "middle", "light heavy", "heavy"]
w=[48,51,54,57,60,64,69,75,81,91]
for s in map(float,sys.stdin):
    i=0;
    for e in w:
        if e<s: i+=1
        else: break
    print c[i]

Measured memory_bytes: 4224
def abc(n:int,lst:list):
    l0=list(filter(lambda x:x[2]==0,lst))
    l=list(filter(lambda x:x[2]!=0,lst))
    if len(l0):
        x0 =l[0][0]
        y0=l[0][1]
        h0 =l[0][2]
        ans=[]
        for x in range(101):
            for y in range(101):
                for i in range(len(l)):
                    if abs(x0-x)+abs(y0-y)-abs(l[i][0]-x)-abs(l[i][1]-y) == l[i][2]-h0:
                        if i ==len(l)-1:
                            for k in range(len(l0)):
                                if abs(l0[k][0]-x)+abs(l0[k][1]-y)>=h0+abs(x0-x)+abs(y0-y):
                                    if k == len(l0)-1:
                                        return x,y,h0+abs(x0-x)+abs(y0-y)
                                else:
                                    break
                    else:
                        break

    else:
        x0 =lst[0][0]
        y0=lst[0][1]
        h0 =lst[0][2]
        for x in range(101):
            for y in range(101):
                for i in range(1,n):
                    if abs(x0-x)+abs(y0-y)-abs(lst[i][0]-x)-abs(lst[i][1]-y) ==lst[i][2]-h0:
                        if i ==n-1:
                            return x,y,h0+abs(x0-x)+abs(y0-y)
                    else:
                        break
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
x,y,h =abc(n,lst)
print(x,y,h)


Measured memory_bytes: 3188
import           Text.Printf

main :: IO ()

isCenter w h x y | x == w / 2 && y == h / 2 = True
                 | otherwise                = False

main = do
    [w, h, x, y] <- map (read :: String -> Double) . words <$> getLine
    let c = isCenter w h x y
    printf "%.6f\n" $ w * h / 2
    if c then print 1 else print 0


Measured memory_bytes: 508
import java.util.Scanner

import scala.io.StdIn._
object Main extends App {

  val Array(a,b,c,k) = scala.io.StdIn.readLine().split(" ").map(_.toInt)

  def solve() = {
    k match {
      case x if x <= a => 1 * x
      case x if x >= a && x <= a+b => a
      case x if x >= a+b && x <= a+b+c => a - (x - a - b)
      case _ => a - c
    }
  }

  println(solve())

}



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

ll inf=1ll<<60;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll h,w,i,j,k=0,n,g[100][100],a[10000];
	cin>>h>>w>>n;
	for (i=0;i<n;i++){
		cin>>a[i];
	}
	for (i=h-1;i>=0;i--){
		if (i%2==0){
			for (j=0;j<w;j++){
				if (a[k]>0){
					g[i][j]=k+1;
					a[k]--;
				}
				else {
					k++;
					a[k]--;
					g[i][j]=k+1;
				}
			}
		}
		else {
			for (j=w-1;j>=0;j--){
				if (a[k]>0){
					g[i][j]=k+1;
					a[k]--;
				}
				else {
					k++;
					a[k]--;
					g[i][j]=k+1;
				}
			}
		}
	}
	for (i=0;i<h;i++){
		for (j=0;j<w;j++){
			cout<<g[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int k= 1;
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("SUN",7);
        hashMap.put("MON",6);
        hashMap.put("TUE",5);
        hashMap.put("WED",4);
        hashMap.put("THU",3);
        hashMap.put("FRI",2);
        hashMap.put("SAT",1);
        String s1;
        String s2;
        int a,b,c;
        double n;
        while(k-->0){
            c=s.nextInt();
            a=s.nextInt();
            b=s.nextInt();
            System.out.println(Math.min(a*c,b));
        }
    }

    private static int binary_search(
            int arr[], int l,
            int h, int x)
    {
        while (l <= h) {
            int mid = (l + h) / 2;
            if (arr[mid] <= x)
                l = mid + 1;
            else
                h = mid - 1;
        }
        return h;
    }
    static int gcd(int a, int b)
    {
        if(b==0) {
            return a;
        }
        return gcd(b,a%b);
    }
    private static boolean isPrime(int n) {
        if (n == 2)
            return true;
        else if ((n % 2 == 0 && n > 2) || n < 2)
            return false;
        else {
            for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }


    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

Measured memory_bytes: 27064
#include <iostream>

int main()
{
    int N, max=0, A;
    long add=0;
    std::cin >> N >> A;
    max = A;
    for (int i = 1; i < N; i++)
    {
        std::cin >> A;
        if (max<A) {
            max = A;
        }
        else {
            add += max - A;
        }
    }
    std::cout << add;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define re register
#define minp(a,b) (dep[a]<dep[b]?(a):(b))
struct eg{int to;eg*nx;}e[200100],*la[100100],*cnt=e;
inline void addE(re int a,re int b)
{
	*++cnt=(eg){b,la[a]};la[a]=cnt;
	*++cnt=(eg){a,la[b]};la[b]=cnt;
}
int va[18][200100],dep[200100],dfn[100100],lg[200100],tot;
void dfs1(re int a,re int fa)
{
	va[0][++tot]=a;dfn[a]=tot;
	for(re eg*i=la[a];i;i=i->nx)if(i->to!=fa)dep[i->to]=dep[a]+1,dfs1(i->to,a),va[0][++tot]=a;
}
int LCA(re int a,re int b)
{
	a=dfn[a];b=dfn[b];
	if(a>b)std::swap(a,b);
	re int c=lg[b-a+1];
	return minp(va[c][a],va[c][b-(1<<c)+1]);
}
int u[100100],v[100100],w[100100],nx[200100],bg[100100],ta[100100],fa[200100],fv[200100];
int ans;
int find(re int a)
{
	if(fa[fa[a]]==fa[a])return fa[a];
	else
	{
		re int b=find(fa[a]);
		fv[a]^=fv[fa[a]];
		return fa[a]=b;
	}
}
void meg(re int a,re int b,re int c)
{
	if(find(a)!=find(b))
	{
		c^=fv[a]^fv[b];
		fv[fa[b]]=c;//printf("**a**%d %d %d %d\n",a,b,fv[b],c);
		fa[fa[b]]=fa[a];
	}//else assert(fv[a]^fv[b]==c);
}
int dfs(re int a,re int fa)
{
	re int mx=1<<30;//printf("**a**%d %d\n",a,bg[a]);
	for(re eg*i=la[a];i;i=i->nx)if(i->to!=fa)
	{
		mx=std::min(mx,dfs(i->to,a));
		if(ta[a])nx[ta[a]]=bg[i->to];
		else bg[a]=bg[i->to];
		if(ta[i->to])ta[a]=ta[i->to];
	}
	if(mx<dep[a]){ans+=2;return mx;}
	while(bg[a]&&dep[w[bg[a]/2]]>=dep[a])bg[a]=nx[bg[a]];
	re int x=bg[a];
	if(x)
	{
		ans++;
		while(nx[x]&&dep[w[nx[x]/2]]>=dep[a])nx[x]=nx[nx[x]];
	}else ta[a]=0;
	re int y=nx[x];
	if(y)
	{
		ans++;
		mx=std::max(dep[w[x/2]],dep[w[y/2]]);
		meg(x/2,y/2,!((x&1)^(y&1)));
	}else ta[a]=x;
	//printf("***%d %d %d %d\n",a,x,y,ans);
	return mx;
}
int main()
{
	re int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(re int i=1;i<n;i++)scanf("%d%d",&x,&y),addE(x,y);
	for(re int i=1;i<=m;i++)fa[i]=i;
	dep[1]=1;dfs1(1,0);
	for(re int i=2;i<=tot;i++)lg[i]=lg[i/2]+1;
	for(re int i=1;(1<<i)<=tot;i++)
	{
		for(re int j=1;j+(1<<i)-1<=tot;j++)va[i][j]=minp(va[i-1][j],va[i-1][j+(1<<i-1)]);
	}
	for(re int i=1;i<=m;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		w[i]=LCA(u[i],v[i]);
		if(ta[u[i]])nx[ta[u[i]]]=i*2;
		else bg[u[i]]=i*2;
		ta[u[i]]=i*2;
		if(ta[v[i]])nx[ta[v[i]]]=i*2+1;
		else bg[v[i]]=i*2+1;
		ta[v[i]]=i*2+1;
	}
	dfs(1,0);
	printf("%d\n",ans);
	for(re int i=1;i<=m;i++)
	{
		find(i);
		if(fv[i])std::swap(u[i],v[i]);
		printf("%d %d\n",u[i],v[i]);
	}
}

Measured memory_bytes: 18816
class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  # (0, i]
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def inversion_number(arr):
    n = len(arr)
    arr = sorted(range(n), key=lambda x: arr[x])
    bit = Bit(n)
    res = n * (n-1) >> 1
    for val in arr:
        res -= bit.sum(val+1)
        bit.add(val+1, 1)
    return res

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N)]
A, B, C = zip(*ABC)
th = N*(N-1)//2 // 2 + 1
def solve(A, B, C):
    # y = (-Ax+C) / B
    if N < 100:
        ok = -1e10
        ng = 1e10
        n_iteration = 70
    else:
        ok = -1e4
        ng = 1e4
        n_iteration = 46
    A, B, C = zip(*sorted(zip(A, B, C), key=lambda x: -x[0]/x[1]))
    for _ in range(n_iteration):
        x = (ok+ng) * 0.5
        Y = [(-a*x+c)/b for a, b, c in zip(A, B, C)]
        inv_num = inversion_number(Y)
        if inv_num >= th:
            ok = x
        else:
            ng = x
    return ok
print(solve(A, B, C), solve(B, A, C))


Measured memory_bytes: 225236
s=input()
lis=[]
for i in range(0,len(s)):
    for j in range(min(i+1,len(s)-1),len(s)+1):
        lis.append(s[i:j])
res=0
#print(lis)
for i in lis:
    if i.count("A") + i.count("C") + i.count("G") + i.count("T") == len(i):
        res=max(res,len(i))
print(res)

Measured memory_bytes: 3060
N,A,B,C = [ int(it) for it in input().split() ]
li = [ int(input()) for i in range(N) ] 

import itertools

w = [0,1,2,3]

ss=1000000000000000
for ci in itertools.product(*([w]*N)):
  cc=[0,0,0,0]
  vc=[0,0,0]
  for i in range(N):
    cc[ci[i]]+=1
    if (ci[i]>0):
      vc[ci[i]-1]+=li[i]
  if ( cc[1]>0 and cc[2]>0 and cc[3]>0 ):
    _ss = abs(vc[0]-A)+abs(vc[1]-B)+abs(vc[2]-C)+(cc[1]+cc[2]+cc[3]-3)*10
    if (_ss<ss):
      ss = _ss
print ( ss )
    
    

Measured memory_bytes: 3064
# ARC081c
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    from collections import Counter
    import heapq

    n = int(input())

    a = list(map(int, input().split()))
    a.sort(reverse=True)

    b = []
    heapq.heapify(b)
    ln = 0
    cou = 0
    for i in a:
        if ln != i:
            ln = i
            cou = 0
        cou += 1
        if cou > 1:
            heapq.heappush(b, -i)
            cou = 0
    try:
        print(heapq.heappop(b)*heapq.heappop(b))
    except:
        print(0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14628
n = gets.strip.to_i

n.times.each do
  h, m = gets.strip.split(':').map{|s| s.to_i}

  dd = (30.0 * h + 0.5 * m - 6 * m).abs
  dd = 360 - dd if dd > 180

  if dd < 30
    puts "alert"
  elsif dd >= 90
    puts "safe"
  else
    puts "warning"
  end
end

Measured memory_bytes: 6136
import math

def cmb(n, r):
  if n == r:
    return 1
  return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

N, K = list(map(int, input().split()))

for i in range(K):
  if (N-K+1) < i + 1:
    print(0)
  else:
  	C = (cmb(K-1, i) * cmb((N-K+1), i+1)) % (10 ** 9 + 7)
  	print(C)

Measured memory_bytes: 3316
/*..............Bismillahir Rahmanir Rahim.............*/
/**
*     => Md. Sajjat Hosen
*     => Department of Computer Science and Engineering
*     => Bangabandhu Sheikh Mujibur Rahman Science and Technology University
**/

/*..................! TRY ONCE MORE !..................*/

/*...Part - 01...*/

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

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

inline int Int(){int x ; scanf("%d",&x) ; return x ;}
inline ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
inline float Float(){float x ; scanf("%f",&x) ; return x ;}
inline double Double(){double x ; scanf("%lf",&x); return x;}

/*...Part - 03...*/
/*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)2e5 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     debug(x)    cerr << #x << " = " << x << '\n' ;
#define     rep(i,b,e)  for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e))  ; i += 1 - 2 * ((b) > (e)))
#define     Int         Int()
#define     Long        Long()
#define     Float       Float()
#define     Double      Double()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     ff          first
#define     ss          second
#define     pb          push_back
#define     eb          emplace_back
#define     mp          make_pair
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)
#define     pie         acos(-1.0)
#define     Fast_Read   ios_base::sync_with_stdio(false); cin.tie(nullptr);  cout.tie(nullptr);

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/



int main(){
    //Fast_Read
    //freopen("input.txt","r",stdin);
    int test = 1 , tc = 0 ;
    ll n, ans = 0;
    while(test--){
        n = Long;
        ans += 1000*(n / 500);
        n %= 500;
        ans += 5*(n / 5);
        printf("%lld\n", ans);
    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/

Measured memory_bytes: 256
#include<stdio.h>
int a[1001401]; 
int main(){
  	int n;
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++) 
		scanf("%d", &a[i]);
  	int p = a[0], sum = 1, flag = 0;
  	for (int i = 1; i < n; i++) {
    	if(p == a[i])
		 	continue;
    	if(p < a[i]){
      		if(flag < 0){
      			sum++;
				flag = 0;
			}
      		else flag = 1;
    	}
    	else {
      		if (flag > 0){
      			sum++;
				flag = 0;
			}
      		else
				flag = -1;
    	}
    	p = a[i];
  	}
  	printf("%d\n", sum);
  	return 0;
}

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

void print_vec(vector<int> vec)
{
  cout << "[";
  for (int i = 0; i < vec.size(); i++)
  {
    cout << vec.at(i) << ", ";
  }
  cout << "]" << endl;
}

int main()
{
  int h, m, s;
  cin >> s;

  h = s / 3600;
  s -= h * 3600;
  m = s / 60;
  s -= m * 60;
  cout << h << ':' << m << ':' << s << endl;
}



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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

int main(void){
  	ll K; cin >> K;
  	ll rem50 = K % 50;
    ll div50 = K / 50;

    if(K == 0){
        cout << 2 << endl << 1 << " " << 1 << endl;
    }
    else{
        ll val = 49 + div50;
        ll ans[50]; rep(i, 50) ans[i] = val;
        rep(i, rem50){
            rep(j, 50){
                if(i == j) ans[j] += 50;
                else ans[j]--;
            }
        }

        cout << 50 << endl;
        rep(i, 50) cout << ans[i] << " "; cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
fun main(arg: Array<String>) {
    val N = nextInt()
    val X = listOfInt().toIntArray()
    val sum = X.sum()
    val av1 = sum / N
    val av2 = av1 + 1
    val ans1 = X.sumBy { (av1 - it) * (av1 - it) }
    val ans2 = X.sumBy { (av2 - it) * (av2 - it) }
    val ans = Math.min(ans1, ans2)
    println(ans)
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }



Measured memory_bytes: 37656
#include <stdio.h>
int n, x, y, k[10], p[10], q[10], t;
int main() {
	scanf("%d", &n);
	k[0] = 1;
	for (int i = 1; i < 10; i++) {
		k[i] = k[i - 1] * i;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", p + i);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", q + i);
	}
	for (int i = 0; i < n; i++) {
		t = 0;
		for (int j = i + 1; j < n; j++) {
			if (p[j] < p[i])t++;
		}
		x += k[n - 1 - i] * t;
	}
	for (int i = 0; i < n; i++) {
		t = 0;
		for (int j = i + 1; j < n; j++) {
			if (q[j] < q[i])t++;
		}
		y += k[n - 1 - i] * t;
	}
	if (y < x) {
		t = y;
		y = x;
		x = t;
	}
	printf("%d\n", y - x);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
#define ll long long
#define ld long double
using namespace std;

int main() {
	int N;
	cin >> N;
	int er=0;
	for(int i=1; i<=N; ++i){
	    int p;
	    cin >> p;
	    if(p!=i) ++er;
	}
	cout << (er<=2 ? "YES" : "NO") << endl;
	return 0;
}


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

template <typename T1, typename T2>
long RoundUp(T1 C, T2 A){
	if(C%A != 0){
		return C/A + 1;
	}else{
		return C/A;
	}
}

int main(){
	long A, B;
	long C;
	cin >> A >> B >> C;

	long OneWeekCoins = 7*A+B;	// 7日間連続ログインした際の獲得コイン数
	long Set1 = C/OneWeekCoins;
	long Set2 = Set1 + 1;
	long rest1 = C - Set1*OneWeekCoins;
	long ans1 = RoundUp(rest1, A) + 7*Set1;
	long ans2 = 7*Set2;

	if(ans1 < ans2){
		cout << ans1 << endl;
	}else{
		cout << ans2 << endl;
	}

}



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

long long dp[101][100001];

long long find(long long w[],long long v[],int n,long long W)
{
	for(int i=0;i<n;i++)
	{
		dp[i][0]=0;
	}

	for(long long j=0;j<=W;j++)
	{

		if(w[0]<=j)
			dp[0][j]=v[0];
		else dp[0][j]=0;
	}

	for(int i=1;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
			if(w[i]<=j)

			{dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);}
		    else dp[i][j]=dp[i-1][j];
		}
	}

	return dp[n-1][W];
}

int main()
{
	int n,W;
	cin>>n>>W;
	long long w[n],v[n];

	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}

	

	long long ans=find(w,v,n,W);
	cout<<ans;

   return 0;

}




Measured memory_bytes: 78336
import itertools

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

arr1 = list(itertools.permutations(range(1, n+1)))

a = arr1.index(p) + 1
b = arr1.index(q) + 1

ans = abs(a - b)
print(ans)


Measured memory_bytes: 8052
//============================================================================
// Name        : abc111b.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;

int main() {
	float N;
	cin >> N;
	for(float i = 111; i <= 999; i += 111){
		if(N / i <= 1){
			cout << i << endl;
			return 0;
		}
	}

	return 0;
}


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

class StronglyConnectedComponents {
private:
  int n;
  vector<vector<int>> dag,rdag,st;
  vector<int> comp,order;
  vector<bool> used;
public:
  StronglyConnectedComponents(const vector<vector<int>>& adj){
    n = adj.size();
    comp.resize(n);
    used.resize(n);
    dag.resize(n);
    rdag.resize(n);
    for(int i=0;i<n;++i){
      for(const auto& x:adj[i]){
        dag[i].emplace_back(x);
        rdag[x].emplace_back(i);
      }
    }
  }

  inline auto operator[](int idx)const{
    return comp[idx];
  }
  void dfs(int now_v){
    if(used[now_v])return;
    used[now_v]=true;
    for(const auto& next_v:dag[now_v]) dfs(next_v);
    order.push_back(now_v);
  }
  auto rdfs(int now_v,int num){
    if(comp[now_v])return false;
    comp[now_v]=num;
    for(const auto& next_v:rdag[now_v]) rdfs(next_v,num);
    return true;
  }
  vector<vector<int>> build(){
    for(int i=0;i<n;++i) dfs(i);
    reverse(order.begin(),order.end());
    int num=1;
    for(const auto& v:order) num+=rdfs(v,num);
    st.resize(num);
    for(int i=0;i<n;++i){
      st[comp[i]].emplace_back(i);
    }
    return st;
  }
  void dump(){
    rep(i,n)cout<<i<<" ";cout<<endl;
    rep(i,n)cout<<comp[i]<<" ";cout<<endl;
  }
};

int main(){

  int n,m;
  cin>>n>>m;
  vector<vector<int>> adj(n);
  vector<int> indeg(n);
  rep(i,m){
    int u,v;
    cin>>u>>v;
    adj[u].emplace_back(v);
    indeg[v]++;
  }

  StronglyConnectedComponents scc(adj);
  auto res = scc.build();
  res.erase(begin(res));
  for(auto& comp:res){
    sort(begin(comp),end(comp),[&indeg](int u,int v){return indeg[u]<indeg[v];});
  }

  cout<<size(res)<<endl;
  for(auto& comp:res){
    cout<<size(comp);
    for(auto& v:comp)cout<<" "<<v;
    cout<<'\n';
  }

}

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

int n;
string s;
int toi(char c){
    return (int)c - '0';
}

int solve(int v){
    int a = v / 100;
    int i = 0;
    int f = 0;
    for(; i < n; i++){
        if(a == toi(s[i])){
            i++;
            f = 1;
            break;
        }
    }
    if(f == 0){
        return 0;
    }
    f = 0;
    a = (v / 10) % 10;
    for(; i < n; i++){
        if(a == toi(s[i])){
            i++;
            f = 1;
            break;
        }
    }
    if(f == 0){
        return 0;
    }
    f = 0;
    a = v % 10;
    for(; i < n; i++){
        if(a == toi(s[i])){
            f = 1;
            break;
        }
    }
    if(f == 0){
        return 0;
    }
    return 1;
}

int main(){
    cin >> n;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < 1000; i++){
        ans += solve(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
    long long N, H[100001], i, judge=1;

    cin >> N;

    for(i=1; i<=N; i++){
        cin >> H[i];
    }

    for(i=N; i>=2; i--){
        if(H[i] == H[i-1] - 1){
            H[i-1]--;
        }

        else if(H[i] < H[i-1] - 1){
            judge = 0;
        }
    }

    if(judge == 1){
        cout << "Yes" << endl;
    }

    else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(int argc, char** argv){
    long long int N, D;
    cin >> N >> D;
    long long D2 = D*D;
    int count = 0;
    for (int i=0; i<N; i++){
        long long int x, y;
        cin >> x >> y;
        if (x*x + y*y <= D2) count++;
    }
    cout << count << "\n";
    return 0;
}


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

const int maxn=25;
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
int h,w,a[maxn][maxn],ans;
int cnt[maxn][maxn];
queue<int> q;

void bfs(int x,int y)
{
	memset(cnt,0,sizeof cnt);
	q.push((x-1)*w+y);
	cnt[x][y]=1;
	while(!q.empty()) {
		int now=q.front();q.pop();
		int nx=(now+w-1)/w,ny=now-(nx-1)*w;
		for(int i=1;i<=4;++i) {
			if(nx+dx[i]>0&&nx+dx[i]<=h&&ny+dy[i]>0&&ny+dy[i]<=w&&
			a[nx+dx[i]][ny+dy[i]]&&!cnt[nx+dx[i]][ny+dy[i]]) {
				cnt[nx+dx[i]][ny+dy[i]]=cnt[nx][ny]+1;
				q.push((nx+dx[i]-1)*w+ny+dy[i]);
			}
		}
	}
	for(int i=1;i<=h;++i)
		for(int j=1;j<=w;++j) ans=max(ans,cnt[i][j]-cnt[x][y]);
}

int main()
{
	scanf("%d %d",&h,&w);
	for(int i=1;i<=h;++i)
		for(int j=1;j<=w;++j) {
			char s=getchar();
			while(s!='#'&&s!='.') s=getchar();
			if(s=='.') a[i][j]=1;
		}
	for(int i=1;i<=h;++i)
		for(int j=1;j<=w;++j) {
			if(a[i][j]) bfs(i,j);
		}
	printf("%d",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    int N,K; cin >> N >> K;
    map<int,int> mp;
    REP(i,N)
    {
        int tmp; cin >> tmp;
        mp[tmp]++;
    }
    VI cnt;

    for(auto p : mp)
    {
        cnt.pb(p.second);
    }
    sort(cnt.begin(), cnt.end());
    LL ans = 0;
    int remain = SZ(cnt) - K;
    if(remain <= 0)
    {
        cout << "0" << endl;
    }
    else
    {
        REP(i,remain) 
        {
           ans += cnt[i];
        }
        cout << ans << endl;
    }




}


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

using namespace std;

constexpr int mod = 1e9 + 7;

int main(void) {
    int N;
    cin >> N;
    int K;
    cin >> K;
    int Q;
    cin >> Q;
    vector<int> A(N, 0);
    int a;
    for (int i = 0; i < Q; i++) {
        cin >> a;
        A[a - 1]++;
    }

    vector<int> cnt(N, K);
    for (int i = 0; i < N; i++) {
        cnt[i] -= (Q - A[i]);
    }

    // for (int i : cnt) cout << i << " ";

    for (int i : cnt) {
        if (i > 0)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

Measured memory_bytes: 1408
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = Integer.parseInt(sc.next());
        int X = Integer.parseInt(sc.next());

        System.out.println(String.join(" ", IntStream.range(X - (K - 1), X + K).mapToObj(String::valueOf).collect(Collectors.toList())));
    }
}


Measured memory_bytes: 28756
def main():
    n, *a = map(int, open(0).read().split())

    b = [cur_a*2 for cur_a in a]

    c = [0]
    for cur_b in b:
        c.append(cur_b - c[-1])
    compensation = c.pop(-1) // 2
    c = [cur_c + compensation * (-1) ** in_i for in_i, cur_c in enumerate(c)]

    ans = c
    print(*ans)
    return()

if __name__ == '__main__':
    main()


Measured memory_bytes: 18988
#pragma GCC optimize("O3")
#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 std;

#define EPS 1e-9
#define INF LLONG_MAX/3LL
#define MOD 1e9+7
#define F first
#define S second
#define pf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(a) ((int)(a).size())
#define all(a) begin(a), end(a)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define F0R(i, a) FOR(i, 0, a)
#define R0F(i, a) ROF(i, a, 0)
#define ITER(i, a) for(auto i : a)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef tree<pi, null_type, less<pi>,
             rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int ls(int x){ return (x)&(-x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll rngr(ll x, ll y) { return (rng()%(y-x+1))+x; }

ll n, a, b, t;
priority_queue<ll> pq;
int main(){
	FAST
	cin >> n;
	F0R(i, n-1){ cin >> t; pq.push(t); }
	t = 0;
	while(!pq.empty()){
		if(t % 2 == 0) a += pq.top();
		else b += pq.top();
		pq.pop(); t++;
	}
	cout << a-b;
}

Measured memory_bytes: 256
def check(n):

    if n <= P-1:
        return True

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)

##開区間
right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Measured memory_bytes: 14964
import math

N, K = map(int, input().split())

ans = 0

if N < K:
    for a in range(N):
        t = math.log2(K)-math.log2(a+1)
        i = math.ceil(t)
        ans += (1/N) * (0.5 ** i)

else:
    for a in range(N):
        if a+1 >= K:
            ans += (1/N)
        else:
            t = math.log2(K)-math.log2(a+1)
            i = math.ceil(t)
            ans += (1/N) * (0.5 ** i)

print(ans)


Measured memory_bytes: 3060
import fractions
from functools import reduce
N,K = map(int,input().split())
A = list(map(int,input().split()))
if max(A) < K:
  print("IMPOSSIBLE")
elif N == 1:
  if A[0] == K:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
else:
  G = fractions.gcd(A[0],A[1])
  for g in range(2,N):
    G = fractions.gcd(G,A[g])
  if K % G != 0:
    print("IMPOSSIBLE")
  else:
    print("POSSIBLE")



Measured memory_bytes: 16244
#11:40
flag = 0
a,b,c,d = map(int,input().split())
if abs(a-c) <= d:
  flag = 1
elif abs(a-b) <= d and abs(b-c) <= d:
  flag = 1
if flag == 1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 2940
#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
#include <map>
//#include <queue>
#include <set>
//#include <sstream>
//#include <stack>
#include <string>
//#include <time.h>
#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
//#include <string.h>
#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
using namespace std;
int main()
{
	int n,a[1000];
	LL ans=1;
	cin>>n;
	for(int i=1;i<=n;i++) a[i-1]=i;
	for(int i=2;i<=n;i++)
	{
		int cnt=0;
		rep(j,n)
		{
			while(a[j]%i==0)
			{
				a[j]/=i;
				cnt++;
			}
		}
		ans=(ans*(cnt+1))%1000000007;
	}
	cout<<ans;
    rt0;
}

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

using namespace std;

int main()
{
    int n,m,sum=0,s,i;
    cin>>n;
    int arr[n];
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    m=*max_element(arr,arr+n);

    for(i=0;i<n;i++)
    {
        sum += arr[i];
    }
    s=sum-m;
    if(s>m)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3536
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<complex<double>>  DFT(vector<complex<double>> a) {
	int n = a.size();
	if (n == 1) return a;
	vector<complex<double>> a0(n / 2), a1(n / 2);
	REP(i, n) {
		if (i % 2 == 0) {
			a0[i / 2] = a[i];
		}
		else {
			a1[i / 2] = a[i];
		}
	}
	vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1);
	vector<complex<double>> inversed_a(n);
	for (int i = 0; i < n; ++i) {
		complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n));
		inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)];
	}
	return inversed_a;
}
vector<complex<double>> IDFT(vector<complex<double>> inversed_a) {
	int n = inversed_a.size();
	vector<complex<double>> now = DFT(inversed_a);
	reverse(now.begin(), now.end());
	for (int q = now.size() - 1; q >= 1; --q) {
		swap(now[q], now[q - 1]);
	}
	REP(i, n) {
		now[i] /= complex<double>(n, 0);
	}
	return now;
}
vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) {
	int deg = a.size() + b.size() - 1;
	int n = 1;
	while (n < deg) n <<= 1;
	a.resize(n);
	b.resize(n);
	vector<complex<double>> inversed_a = DFT(a),inversed_b = DFT(b);
	vector<complex<double>> inversed_c(n);
	REP(i, n) {
		inversed_c[i] = inversed_a[i] * inversed_b[i];
	}
	return IDFT(inversed_c);
}
long long ans[300000];
int main() {
	long long n;
	cin >> n;
	vector<long long> A;
	A.push_back(0);
	REP(i, n) {
		long long a;
		cin >> a;
		A.push_back(a);
	}
	int cnt = 0;
	for (int i = A.size() - 1; i >= 1; --i) {
		long long now = 0;
		for (int q = 2; i * q < A.size(); ++q) {
			now += ans[i * q];
		}
		if (now % 2 != A[i]) {
			ans[i] = 1;
			cnt++;
		}
		else {
			ans[i] = 0;
		}
	}
	cout << cnt << endl;
	REP(i, A.size()) {
		if (ans[i] == 1) {
			cout << i << " ";
		}
	}
	cout << endl;
}

Measured memory_bytes: 4080
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll MOD2=(ll)998244353;
const ll INF=(ll)1e18+10;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

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

//ll add[100010];

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
/*
unordered_map< ll, int > prime_factor(ll n) {
    unordered_map< ll, int > ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}
*/
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}

ll calc_yakusum(ll n,const vector<ll>& ref){
    ll ret=0;
    vector<ll> yaku=divisor(n);
    for(auto i:yaku){
        if(i<n) (ret+=ref[i])%=MOD;
    }
    /*
    unordered_map<ll, int> mp=prime_factor(n);
    ll ret=1ll;
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        ll kou=((ll)pow(itr->first,(ll)itr->second+1)-1ll)/(itr->first-1ll);
        (ret*=kou%MOD)%=MOD;
    }
    return ret;
     */
    return ret;
}

void solve(int ca){
    int N,K; cin>>N>>K;
    vector<ll> add(K+10,0);
    add[1]=1;
    ll ans=modpow(K,N,MOD);
    //cout<<ans<<endl;
    for (int i = 2; i <= K; ++i) {
        ll cnt=K/i;
        ll times=i-calc_yakusum(i,add);
        add[i]=times;
        (ans+=(modpow(cnt,N,MOD)*times)%MOD)%=MOD;
        //cout<<i<<" "<<ans<<endl;
    }
    cout<<ans<<"\n";

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(1);
#endif
    return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t;
    }
    return n*rep_jijo(n,x-1);
}

int main(){
    ll a;
    string b;
    cin >> a >> b;
    ll c=100*(b[0]-'0')+10*(b[2]-'0')+(b[3]-'0');
    ll ans =a*c;
    cout << ans/100 <<endl;
    
    return 0;

}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>

using namespace std;
using ll = long long;
using ull = unsigned long long;


#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)

auto sumdig(ll num) {
	ll dig, sum;
	sum = 0;
	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}

auto mdist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}
int main() {

	int N, K;
	cin >> N >> K;

	double ans = 0;


	int m = min(N+1, K);


	rep(i, 1, m) {
		auto test = ceil(log2(K / (double)i));
		ans += pow(0.5, ceil(log2(K / (double)i)))/(double)N;
	}

	if (K < N) {
		ans += (N-K+1) / (double)N;
	}

	if (ans == 0) {
		ans = 1.0;
	}


	cout << fixed;
	cout << setprecision(10) << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int f(int n){
  return (n%2==0?n/2:3*n+1);
}
int main(){
  int s;
  cin >> s;
  int a[1000000];
  for(int i=0; i<1000000; i++){
    if(i==0) a[i]=s;
    else a[i] = f(a[i-1]);
  }
  for(int i=1; i<1000000-1; i++){
    for(int j=i-1; 0<=j; j--){
      if(a[i]==a[j]){
        cout<<i+1<<endl;
        return 0;
      }
    }
  }
  return 0;
}

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



int main() {
	int n;
	long long A[100];
	cin >> n;
	A[0] = 2;
	A[1] = 1;
	for (int i = 2; i <= n; i++) {
		A[i] = A[i - 1] + A[i - 2];
	}
	cout << A[n] << endl;


	return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;


const int SIZE = 1e5+100;
ll n;
ll a[SIZE];
ll mem,ind;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(mem < abs(a[i])){
            mem = abs(a[i]);
            ind = i;
        }
    }

    cout << n+n-1 << endl;
    for(int i = 0; i < n; i++){
        cout << ind+1 << ' ' << i+1 << endl;
    }

    if(a[ind] < 0){
        for(int i = n-1; i >= 1; i--){
            cout << i+1 << ' ' << i-1+1 << endl;
        }
    }
    else{
        for(int i = 0; i < n-1; i++){
            cout << i+1 << ' ' << i+1+1 << endl;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;

vector<vector<int>> grid, dp;

long long f(int i, int last) {
  if (i == -1) {
    return 0;
  }

  if (dp[i][last] == -1) {
    dp[i][last] = 0;
    for (int act = 0; act < 3; ++act) {
      if (act != last) {
        int happiness = grid[i][act] + f(i - 1, act);
        dp[i][last] = max(dp[i][last], happiness);
      }
    }
  }

  return dp[i][last];
}

int main() { IO;
  int n;
  cin >> n;

  grid.resize(n);
  for (auto &v : grid) {
    v.resize(3);
  }

  dp.resize(n);
  for (auto &v : dp) {
    v.resize(5);
    fill(v.begin(), v.end(), -1);
  }

  for (int i = 0; i < n; ++i) {
    cin >> grid[i][0] >> grid[i][1] >> grid[i][2];
  }

  long long ans = f(n - 1, 3);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 19072
import java.util.Scanner;
public class Main {

    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// 入力
    	int n = sc.nextInt();
    	//String l = sc.next();
    	//int arg[] = new int[n];
    	int tmp = 0;
    	int max = 0;
    	int sum = 0;

    	for(int i = 0; i < n; i++){
    		//arg[n] = sc.nextInt();
    		tmp = sc.nextInt();
    		if (tmp > max){
    			max = tmp;
    		}
    		sum += tmp;

    	}

    	String ans ="";
    	if(max < (sum - max)){
    		ans = "Yes";
    	} else {
    		ans = "No";
    	}
    	// 出力
    	System.out.println(ans);
    }
}

Measured memory_bytes: 21716
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: i64
    }
    let mut m = n;
    let mut ans: i64 = 753;
    while m > 100 {
        let t = (m % 1000 - 753).abs();
        if t < ans {
            ans = t;
        }
        m /= 10;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352