akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
//macros
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)

int main(){
    ll N,res = 1;
    vector<ll> H;
    cin >> N;
    H.resize(N);
    vector<ll> dp(N);

    rep(i,0,N){
        ll temp;
        cin >> temp;
        H[i] = temp;
        dp[i] = 1;
        //cout << H[i] << endl;
    }
    rep(i,0,N-1){
        
        if (H[i] >= H[i + 1]){
            dp[i + 1] += dp[i];
        }
        else dp[i+1] = 1;
        res = max(res, dp[i+1]);
        //cout << H[i] <<  H[i+1]<< dp[i+1]<<endl;
    }

    cout << res - 1<< endl;
}

Measured memory_bytes: 1792
N, K = map(int,input().split())

if K > (N-1) * (N-2) // 2:
    print(-1)
    exit()

M = N-1 + (N-1)*(N-2)//2 - K
print(M)

for i in range(2,N+1):
    print("{0} {1}".format(1,i))
    
cnt = N-1
for i in range(2,N+1):
    for j in range(i+1,N+1):
        if cnt == M: exit()
        
        print("{0} {1}".format(i,j))
        cnt += 1

        

Measured memory_bytes: 9144
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//#include<set>
#include<algorithm>
//#include<math.h>
//#include<iostream>
//#include<time.h>
using namespace std;

#define LL long long
int qread()
{
	char c; int s=0,t=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (t=-1);
	do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*t;
}

//Pay attention to read!

int n;
#define maxn 200011
int a[maxn],p[maxn];
int main()
{
	n=qread(); for (int i=1;i<=n;i++) a[i]=qread();
	for (int i=1;i<=n;i++) p[a[i]]=p[a[i]-1]+1;
	int ans=0; for (int i=1;i<=n;i++) ans=max(ans,p[i]);
	printf("%d\n",n-ans);
	return 0;
}

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

int main()
{
    int x,y;cin>>x>>y;
    int ans=0;
    if(x==1)ans+=3;
    else if(x==2)ans+=2;
    else if(x==3)ans++;
    if(y==1)ans+=3;
    else if(y==2)ans+=2;
    else if(y==3)ans++;
    if(x==1&&y==1)ans+=4;
    cout<<ans*100000<<endl;
}


Measured memory_bytes: 256
D, G = map(int, input().split())
p = []
c = []
for _ in range(D):
    p_i, c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)
answer = 10000000

for bit in range(2 ** D):
    s, num, rest_max = 0, 0, 0
    for i in range(D):
        if bit & (1 << i):
            s += 100 * (i + 1) * p[i] + c[i]
            num += p[i]
        else:
            rest_max = i
    if s < G:
        s1 = 100 * (rest_max + 1)
        if (G - s) % s1 == 0:
            need = (G - s) // s1
        else:
            need = (G - s) // s1 + 1
        if need >= p[rest_max]:
            continue
        num += need
    answer = min(answer, num)
print(answer)


Measured memory_bytes: 9236
#include<stdio.h>
#define S(type,x) fscanf(stdin,"%"#type,&x)
#define N (int)1e6
#define MIN(a,b) a<b?a:b
int dp[N + 1],
	odd[N + 1];
int main() {
	int i;
	for (i = 0; i <= N; i++) dp[i] = odd[i] = i;
	int p = 4, n = 3;
	for (; p <= N; n++) {
		for (i = 0; i+p <= N; i++) {
			dp[i + p] = MIN(dp[i + p], dp[i] + 1);
			if (p & 1) odd[i + p] = MIN(odd[i + p], odd[i] + 1);
		}
		p = n*(n + 1)*(n + 2) / 6;
	}
	while (S(d, n), n)fprintf(stdout, "%d %d\n", dp[n], odd[n]);
	return 0;
}

Measured memory_bytes: 8416
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
int main() {
  cout << fixed << setprecision(30);
  ll a,b;
  cin>>a>>b;
cout<<a*b<<" ";
putout(2*(a+b));
}


Measured memory_bytes: 3084
N = int(input())
T = list(map(int, input().split()))
M = int(input())
P = [0]*M
X = [0]*M
for i in range(M):
    P[i], X[i] = map(int, input().split())

def Main(N, T, M, P, X):
    ans = [0]*M
    for i in range(M):
        TT = T.copy()
        TT[P[i]-1] = X[i]
        ans[i] = sum(TT)
    return ans

res = Main(N, T, M, P, X)
for e in res:
    print(e)

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

using P = pair<string, int>;

int main() {
  int N; cin >> N;
  map<string, int> m;
  for (int i{}; i < N; ++i) {
    string S; cin >> S;
    ++m[S];
  }
  vector<P> m2;
  for (const auto &p : m) {
    m2.push_back(p);
  }
  sort(m2.begin(), m2.end(), [](P l, P r) {
    if (l.second == r.second)
      return l.first < r.first;
    return l.second > r.second;
  });

  auto it = m2.begin();
  int count = it->second;
  do {
    cout << it->first << endl;
  } while (++it != m2.end() && it->second == count);
  return 0;
}


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

using namespace std;

int main() {
  int N, X, Y;
  cin >> N >> X >> Y;
  vector<vector<int>> v(N , vector<int>(N ));
  vector<int> ans(N - 1);

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      v[i][j] = min(j - i, abs(Y - j - 1) + 1 + abs(X - i - 1));
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (v[i][j] > 0) {
        int ind = v[i][j] - 1;
        ans[ind] += 1;
      }
    }
  }

  for (int x : ans) {
    cout << x << endl;
  }
}


Measured memory_bytes: 16000
package main

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

type vertexId int

type vertex struct {
	id vertexId
	visitedAt int
	adjs []vertexId
}

func createVertex(id int, adjsInt []int) vertex {
	adjs := make([]vertexId, len(adjsInt))
	for i := 0; i < len(adjs); i++ {
		adjs[i] = vertexId(adjsInt[i])
	}
	return vertex{
		id: vertexId(id),
		visitedAt: -1,
		adjs: adjs,
	}
}

func (v *vertex) isVisited() bool {
	return v.visitedAt >= 0
}

func bfs(id vertexId, vqueue []vertexId, vertices []vertex) {
	vertex := &vertices[id-1]
	for _, vid := range vertex.adjs {
		if !vertices[vid-1].isVisited() {
			(&vertices[vid-1]).visitedAt = vertex.visitedAt+1
			vqueue = append(vqueue, vid)
		}
	}
	if len(vqueue) > 0 {
		nextId := vqueue[0]
		nextVqueue := vqueue[1:]
		bfs(nextId, nextVqueue, vertices)
	}
}

func solveBfs(vertices []vertex) {
	vertex := &vertices[0]
	vertex.visitedAt = 0
	vqueue := make([]vertexId, 0)
	bfs(vertex.id, vqueue, vertices)
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	vertices := make([]vertex, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		adjN, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		adjs := make([]int, adjN)
		for j := 0; j < adjN; j++ {
			adjId, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjs[j] = adjId
		}
		vertices[i] = createVertex(id, adjs)
	}

	solveBfs(vertices)

	for i := 0; i < n; i++ {
		fmt.Printf("%d %d\n", vertices[i].id, vertices[i].visitedAt)
	}
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	return strconv.Atoi(nextText(sc))
}



Measured memory_bytes: 1192
#include <stdio.h>
using namespace std;
int main(void){
    int m,f,r;
    
    while(1){
        scanf("%d%d%d",&m,&f,&r);
        if(m==-1&&f==-1&&r==-1)break;
        if(m==-1||f==-1){
            printf("F\n");
        }
        else if(m+f>=80){
            printf("A\n");
        }else if(m+f>=65){
            printf("B\n");
        }else if(m+f>=50){
            printf("C\n");
        }else if(m+f>=30&&r>=50){
            printf("C\n");
        }else if(m+f>=30&&r<50){
            printf("D\n");
        }else{
            printf("F\n");
        }
    }
}



Measured memory_bytes: 2596
#include <iostream>
#include <cmath>
#include <iomanip>
int main() {
  int a, b, h, m;
  std::cin >> a >> b >> h >> m;
  m += h * 60;
  const double PH = 0.5;
  const double PM = 6;
  const double th = PH * m, tm = PM * m;
  std::cout << std::fixed << std::setprecision(20)
            << sqrt(a * a + b * b -
                    2 * a * b * cos((th - tm) / 180 * acos(-1)));

  return 0;
}

Measured memory_bytes: 4228
#include <stdio.h>

int main(void) {
	int A, B;
	scanf("%d%d", &A, &B);
	if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0) {
		printf("Possible\n");
	}
	else {
		printf("Impossible\n");
	}

	return 0;

}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		sc.close();
		
		long l = 0L;
		long p = 2L;
		long q = 1L;
		if(N == 1){
			System.out.println(q);
			return;
		}
		for(int i = 0;i < N-1;i++){
			l = p + q;
			p = q;
			q = l;
		}
		System.out.println(l);
	}
}

Measured memory_bytes: 23380
/*
lakshaygpt28
Lakshay Gupta
*/

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

const double PI = acos(-1);
const long long LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

struct points {
    int x, y;
};

int main() {
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector<points> a(n);
    int mn_x = INT_MAX, mn_y = INT_MAX;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        mn_x = min(mn_x, a[i].x);
        mn_y = min(mn_y, a[i].y);
    }
    int mn1 = INT_MAX, mx1 = INT_MIN;
    int mn2 = INT_MAX, mx2 = INT_MIN;
    for (int i = 0; i < n; i++) {
        a[i].x -= mn_x;
        a[i].y -= mn_y;
        mn1 = min(a[i].x + a[i].y, mn1);
        mx1 = max(a[i].x + a[i].y, mx1);
        mn2 = min(a[i].x - a[i].y, mn2);
        mx2 = max(a[i].x - a[i].y, mx2);
    }
    cout << max(mx1 - mn1, mx2 - mn2) << "\n";
    return 0;
}


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

using namespace std;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define PB push_back
#define PF push_front

typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;

const ll mod = 1e9+7;
const ll INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

int main(){
  string s;
  cin>>s;
  vector<int> a(26);
  
  rep(i,s.size()){
    a[s[i]-'a']++;
  }
  
  rep(i,26){
    if(a[i]==0){
      cout<<(char)(i+'a')<<endl;
      return 0;
    }
  }
  
  cout<<"None"<<endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    bool can = false;
    for (int i = 1; i < B;i++){
        if(A*i%B==C){
            can = true;
            break;
        }
    }
        puts(can ? "YES" : "NO");
 }

Measured memory_bytes: 256
#include<iostream>
#define LEN 100005
using namespace std;
 
struct Queue{
  int Q[LEN];
  int tail,head;
 
  void initialize(){
    head=tail=0;
  }
 
  bool empty(){
    return head==tail;
  }
   
  void inqueue(int x){
    Q[tail]=x;
    tail++;
    tail%=LEN;
  }
 
  int dequeue(){
    if(empty()){
        return 0;
    }
    int res=Q[head];
    head++;
    head%=LEN;
    return res;
  }
};
 
int main(){
  Queue queue,queue2;
  int n,q,number;
  string Q[LEN];
  cin>>n>>q;
  queue.initialize();
  queue2.initialize();
  for(int i=0;i<n;i++){
    cin>>Q[i]>>number;
    queue.inqueue(number);
    queue2.inqueue(i);
  }
   
  int p=0,A,B;
  while(!queue.empty()){
    A=queue.dequeue();
    B=queue2.dequeue();
    if(A<=q){
      p+=A;
      cout<<Q[B]<<' '<<p<<endl;
    }else{
      p+=q;
      A-=q;
      queue.inqueue(A);
      queue2.inqueue(B);
    }
  }
   
  return 0;
}



Measured memory_bytes: 7036
import java.io.*;

public class Main{
    public static void main(String[]args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
       while(true){
           String str =br.readLine();
           if(str.equals("0")){
               break;
           }
           int sum=0;
           for(int i=0;i<str.length();i++){
               sum+=Character.getNumericValue(str.charAt(i));
           }
           System.out.println(sum);
       } 
        
        
    }

        
}

Measured memory_bytes: 17076
import java.io.{BufferedReader, InputStreamReader}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val Array(n, m) = in.readLine().split("\\s+").map(_.toInt)

    System.out.println(
      if (n == m) {
        "Yes"
      } else {
        "No"
      }
    )
  }
}


Measured memory_bytes: 27200
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

int n, m;
priority_queue<int> pq;

int main()
{
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> n >> m;
    forn(i, n)
    {
        int x;
        cin >> x;
        pq.push(x);
    }
    forn(i, m)
    {
        int temp = pq.top();
        pq.pop();
        pq.push(temp/2);
    }
    ll ans = 0;
    while(!pq.empty())
    {
        ans += pq.top();
        pq.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 892
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val s = readLine()!!

    val check = (1..m).joinToString("") { "1" }
    if (s.contains(check)) {
        println(-1)
        return
    }

    var cur = n
    val ansList = mutableListOf<Int>()
    while(cur!=0){
        if(cur<=m){
            ansList.add(0,cur)
            break
        }
        for(move in m downTo 1){
            val next =  cur - move
            if(s[next]=='0'){
                ansList.add(0,move)
                cur = next
                break
            }
        }
    }
    println(ansList.joinToString(" "))
}

Measured memory_bytes: 39764
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))

    for i in range(K + 1, N + 1): # K + 1 から N までのループ
        if (A[i - K - 1] < A[i - 1]):
            print("Yes")
        else:
            print("No")
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 31604
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {

	static long MOD = 1_000_000_007;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		//int N = Integer.parseInt(sc.next());
		//long L = Long.parseLong(sc.next());

		Scanner sc = new Scanner(System.in);
		//char[] c = sc.next().toCharArray();
		long A = Long.parseLong(sc.next());
		long B = Long.parseLong(sc.next());
		long C = Long.parseLong(sc.next());
		long D = Long.parseLong(sc.next());
		int INF = Integer.MAX_VALUE;
		int INF_MIN = -1000;//Integer.MIN_VALUE;
		
		long C_mal = B/C - (A-1)/C;
		
		long D_mal = B/D - (A-1)/D;
		
		long CD_mal = B/lcm(C,D) - (A-1)/lcm(C,D);
		
		
		

		System.out.println(B - A + 1 - (C_mal + D_mal - CD_mal));
		
		
	
		
		
	}
	static long lcm (long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return (c/b);
	}
}



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

using namespace std;

#define N 300000
#define INF 0x3f3f3f3f

int n,x,y,rt,ans,sum,a[N],c[N],d[N],head[N],tot,vis[N],fa[N],f[N],g[N];
char s[N];
struct edge{int v,nxt;}e[N];

void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}

void dfs(int u){
	vis[u]=c[u]; d[u]=0;
	for (int i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u]){
			fa[v]=u; dfs(v);
			if (!vis[v]){++d[v]; ++d[u];}
			vis[u]&=vis[v];
		}
}

void dp(int u){
	sum+=d[u];
	if ((c[u]+d[u])&1) a[u]=0;
	else{++sum; a[u]=2;}
	int mx1=0,mx2=0; bool fl=0;
	for (int i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u]&&!vis[v]){
			fl=1; dp(v);
			ans=max(ans,f[v]+mx2+a[u]);
			ans=max(ans,g[v]+mx1+a[u]);
			mx1=max(mx1,f[v]); mx2=max(mx2,g[v]);
		}
	f[u]=mx1+a[u];
	g[u]=fl?mx2+a[u]:-INF;
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%s",s+1);
	for (int i=1;i<=n;++i) c[i]=s[i]=='B';
	for (int i=1;i<=n;++i) if (!c[i]) rt=i;
	dfs(rt);
	if (rt) dp(rt);
	else{puts("0"); return 0;}
	printf("%d\n",sum-ans);
	
	return 0;
}
			

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

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int n, tmp;
  cin >> n;
  int a[n];
  for(int i=0; i<n; i++) {
    cin >> a[i];
  }

  int min=a[0];
  int max=a[0];
  long int sum=0;


  for(int i=0; i<n; i++) {
    sum += a[i];
    if(a[i] < min) min = a[i];
    if(a[i] > max) max = a[i];
  }

  printf("%d %d %ld\n",min, max, sum);

}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#define MOD ((int)1e9+7)
 
using namespace std;

string s;
int n,k;

const int N=2e6+6;

long long fac[N],infac[N];

long long nck(int x,int y)
{
	return (((fac[x]*infac[y])%MOD)*infac[x-y])%MOD;
}

long long poww(long long x,int y)
{
	if(y==0) return 1;
	if(y&1) return (x*poww(x,y-1))%MOD;
	return poww((x*x)%MOD,y/2);
}

int main()
{
	cin >> k >> s;
	n=s.size();
	fac[0]=infac[0]=1;
	for(int i=1;i<N;i++)
	{
		fac[i]=(i*fac[i-1])%MOD;
		infac[i]=poww(fac[i],MOD-2);
	}
	long long ans=0;
	for(int i=n;i<=n+k;i++)
	{
		long long x=poww(25,i-n)*nck(i-1,n-1);
		x%=MOD;
		x*=poww(26,n+k-i);
		x%=MOD; ans+=x; ans%=MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 35596
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    a[0] = a[0]%m
    for i in range(1, n):
        a[i] += a[i-1]
        a[i] %= m
    a.sort()
    target = 0
    cnt = 1
    for i in a:
        if i == target:
            ans += cnt
            cnt += 1
        else:
            target = i
            cnt = 1
    print(ans)

if __name__ == "__main__":
    main()

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define ALLTRUE(xs) all_of(ALL(xs),[](bool x){return x;})
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define ANYTRUE(xs) any_of(ALL(xs),[](bool x){return x;})
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

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

struct edge { int to,cost; };
const int MOD=1e9+7;

ll gcd(ll a, ll b) {
  if (!b) return a;
  return gcd(b,a%b);
}
vector<ll> factorize(ll n) {
  vector<ll> res;
  FOR(i,2,(ll)(sqrt(n))+1) {
    if (n%i==0) {
      while (n%i==0) n /= i;
      res.push_back(i);
    }
  }
  if (n > 1) res.push_back(n);
  return res;
}

int main() {
  ll A,B;cin>>A>>B;
  // 答えに必ず1が入る
  // dsの中に含まれている素数+1が答え
  vector<ll> ds = factorize(gcd(A,B));
  OUT(ds.size()+1);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = INF;
    chmin(ans, abs(a + b - c - d));
    chmin(ans, abs(a - b + c - d));
    chmin(ans, abs(-a + b + c - d));
    chmin(ans, abs(a - b - c + d));
    chmin(ans, abs(-a + b - c + d));
    chmin(ans, abs(-a - b + c + d));
    cout << ans << endl;
}



Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
main()
{
	int i,n;
	string s;
	map<string,int>m;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>s;
		m[s]++;
	}
	cout<<m.size()<<endl;
	
	
}


Measured memory_bytes: 19264
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;

  if(a%3==0 || b%3==0 || (a+b)%3==0)
    cout << "Possible" << endl; 
  else cout << "Impossible" << endl; 

}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<double> p(N);
    REP(i,N) cin >> p[i];
    double ans = 0;
    double tmp = 0;
    REP(i,K) tmp += (p[i] * (1 + p[i])) / (2 * p[i]);
    chmax(ans, tmp);
    for(int i=K;i<N;i++){
        tmp -= (p[i-K] * (1 + p[i-K])) / (2 * p[i-K]);
        tmp += (p[i] * (1 + p[i])) / (2 * p[i]);
        chmax(ans, tmp);
    }
    printf("%.12lf\n", ans);
}


Measured memory_bytes: 1792
import numpy as np
import sys

X = int(input())
def P(n):
  if n == 2:
    return True
  for p in range(2, int(np.sqrt(n))+1):
      if n % p == 0:
        return False
  return True

for i in range (X,110000):
  if P(i)==True:
    print(i)
    sys.exit()

Measured memory_bytes: 12480
#include<stdio.h>

int main(){
	int n,a,b,p[100],i,j;
	scanf("%d%d%d",&n,&a,&b);
	for(i=0;i<n;i++)scanf("%d",&p[i]);
	int ans,numa=0,numb=0,numc=0;
	for(i=0;i<n;i++){
		if(p[i]<=a)numa++;
		else if(p[i]<=b)numb++;
		else numc++;
	}
	ans=numa;
	if(ans>numb)ans=numb;
	if(ans>numc)ans=numc;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
#define diup(v,a,k) distance((v).begin(),(k)+upper_bound((v).begin(),(v).end(),(a)))
#define dilo(v,a,k) distance((v).begin(),(k)+lower_bound((v).begin(),(v).end(),(a)))
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(v.size())o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const double eps = 1e-6;
const ll LINF = 100200300400500600ll;
const int INF = 1001001001;
//--------------------------------------------------------
#define fastio cin.tie(nullptr); std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
#define myloopset int loop = 1; if(argc>2) loop =stoi(argv[2]); rep(i,loop)
//--------------------------------------------------------------
template <class T> T chmin(T &a,T b){if(a>b){a=b; return 1;}else return 0;}
template <class T> T chmax(T &a,T b){if(a<b){a=b; return 1;}else return 0;}
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};

struct D21{
  int is,js;
  D21(int isize,int jsize){
    is = isize;
    js = jsize;
  }
  int operator()(int i,int j){
    return i*js+j;
  }
};


void Main(){
  int h,n;
  cin>>h>>n;
  vi a(n),b(n);
  rep(i,n){
    cin>>a[i]>>b[i];
  }
  int p = 10000;
  vvi dp(n+1,vi(h+p,INF));
  rep(i,n+1) dp[i][0] = 0;
  rep(i,n) rep(j,h+p){
    dp[i+1][j] = min( dp[i+1][j] ,dp[i][j]);
    if( j >= a[i] )
      dp[i+1][j] = min( dp[i+1][j] ,dp[i+1][j - a[i]] + b[i] );
  }
  int ans = dp[n][h];
  srep(i,h+1,h+p){
    chmin(ans,dp[n][i]);
  }
  cout<<ans<<endl;
} int main(int argc,char** argv)
{fastio; myio; myloopset Main();}


Measured memory_bytes: 78592
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(h)]

    dd = defaultdict(list)
    for i in range(h):
        for j in range(w):
            dd[a[i][j]] = [i,j]

    d2 = defaultdict(int)
    for i in range(d):
        n = 1 + i
        v = 0
        x,y = dd[n]
        while n <= h * w - d:
            n += d
            xx,yy = dd[n]
            v += abs(xx - x) + abs(yy - y)
            x = xx
            y = yy
            d2[n] = v
            
    q = int(input())
    for i in range(q):
        l, r = map(int, input().split())
        print(d2[r] - d2[l])
        

if __name__ == '__main__':
    main()


Measured memory_bytes: 42176
s=input()
n=len(s)

ans=[0]*n

cnt=0
index=0

for i in range(n-1):
  
  if s[i]=="R" and s[i+1]=="L":
    ans[i]+=1+cnt//2
    ans[i+1]+=1+cnt-cnt//2
    cnt=0
    index=i
  elif s[i]=="L" and s[i+1]=="R":
    pass
  elif s[i]=="R":
    cnt+=1
  else:
    if (i-index)%2==1:
      ans[index]+=1
    else:
      ans[index+1]+=1

print(*ans)
    
    
    

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

using namespace std;

const int MAXN = 100001;
const int MAXK = 101;

int N,H[MAXN],dp[MAXN],K;

int main(){
	#ifdef EVAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	cin >> N >> K;
	for(int i = 0; i < N; i++){
		cin >> H[i];
	}
	dp[1] = abs(H[1] - H[0]);
	for(int i = 2; i < N; i++){
		dp[i] = INT_MAX;
		for(int j = i - 1; j >= 0 && j >= i  - K; j--){
			dp[i] = min(dp[i],abs(H[i] - H[j]) + dp[j]);
		}
	}
	cout << dp[N - 1];
}

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

struct P{
    int begin;
    int end;
    string str;

    P(int b, int e, string s){
        begin = b;
        end = e;
        str = s;
    }

    bool operator < (const P& p)const{
        return begin < p.begin;
    }
};

int main(void){
    int N, Q;
    while(cin >> N >> Q, N | Q){
    vector< P > v;
    for(int i = 0; i < N; i++){
        string str; int base, east;
        cin >> str >> base >> east;
        v.push_back( P(east - base + 1, east, str) );
    }
    sort(v.begin(), v.end());

    for(int i = 0; i < Q; i++){
        int y; cin >> y;
        int ans = -1;
        string str;
        for(int j = v.size() - 1; j >= 0; j--){
            if(v[j].begin <= y && y <= v[j].end){
                ans = y - v[j].begin + 1;
                str = v[j].str;
                break;
            }
        }
        if(ans == -1) cout << "Unknown" << endl;
        else cout << str << " " << ans << endl;
    }
    }
    return 0;
}

Measured memory_bytes: 3224
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        var nab = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var n = nab[0];
        var a = nab[1];
        var b = nab[2];
        var diff = Abs(a - b);
        if (diff % 2 == 0)
        {
            Console.WriteLine(diff / 2);
            return;
        }
        Console.WriteLine(Min(Solve(a - 1, b - 1), Solve(n - a, n - b)));
    }
    static long Solve(long a, long b)
    {
        if (a > b)
        {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var min = a;
        a -= min;
        b -= min;
        b -= 1;
        return min + 1 + b / 2;
    }
}


Measured memory_bytes: 13268
import sys

# sys.stdin = open('c1.in')


def f(x):
    for n in range(0, 10 ** 9):
        s = n * (n + 1) / 2
        if s >= x:
            return n


def f2(x):
    a = 0
    b = 10 ** 5
    while b - a > 1:
        n = (a + b) // 2
        s = n * (n + 1) // 2
        if s >= x:
            b = n
        else:
            a = n
    return b

x = int(input())
print(f2(x))

# for x in range(10 ** 9, 1, -10 ** 5):
#     if f(x) != f2(x):
#         print(x, f(x), f2(x))
#         break


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

int main(void)
{
	int a,b,c;
	int i;
	int num=0;
	
	cin >> a >> b >> c;
	
	for(i = a; i <= b; i++)
	{
		if(c % i == 0)
		{
			num++;
		}
	}
	cout << num << endl;
	
	return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <unordered_set>
#include <algorithm>

int main() {
	std::unordered_set<int> penkis;
	for (int i = 0; i < 3; i++) {
		int v;
		std::cin >> v;
		penkis.insert(v);
	}

	std::cout << penkis.size() << std::endl;
}


Measured memory_bytes: 256
s = gets.chomp

words = ['dream', 'dreamer', 'erase', 'eraser']



until s.empty? do
  reduced = false
  words.map do |w|
    if s[-w.size, w.size] == w
      s = s[0..-w.size-1]
      reduced = true
      break
    end
  end

  unless reduced
    puts 'NO'
    exit 0

  end

end

puts 'YES'


Measured memory_bytes: 56268
import math
x = int(input())

def Is_prime(a):
	flag = 0
	for k in range(2,int(math.sqrt(a))+1):
		if a%k == 0:
			flag = 1
	if flag == 0:
		return True
	else:
		return False

while not Is_prime(x):
	x += 1
print(x)


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



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

  ll S, c; cin >> S >> c;

  if(2*S > c){
    cout << c/2 << endl;
    return 0;
  }
  
  c-=(2*S);
  c/=4;
  ll ans = S + c; 
  cout << ans << endl;
  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


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

long fact(int n);

int main(void)
{
    int n;
    
    cin >> n;
    cout << fact(n) << endl;
    
    return 0;
}

long fact(int n)
{
    if(n == 1) return 1;
    else return fact(n-1) * n;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e3+3;
char s[maxN], t[maxN], x[maxN];
int f[maxN][maxN];
int N, M;
int main() {
    scanf("%s", s+1);
    scanf("%s", t+1);
    N = strlen(s+1);
    M = strlen(t+1);
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if (s[i]==t[j]) f[i][j] = f[i-1][j-1]+1;
                else f[i][j] = max(f[i-1][j], f[i][j-1]);
    int i = N, j = M;
    while (i > 0 && j > 0) {
        if (s[i] == t[j] && f[i][j] == f[i-1][j-1]+1) {
            x[f[i][j]] = s[i];
            --i; --j;
        } else if (f[i][j] == f[i-1][j]) --i;
          else if (f[i][j] == f[i][j-1]) --j;
    }
    for(int i = 1; i <= f[N][M]; ++i) putchar(x[i]);
    if (f[N][M] == 0) cout << " ";
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define srt(i) sort(i.begin(), i.end())
#define rvt(i) sort(i.begin(), i.end(), greater<int>())


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

    vector<int> ans(10001);
    for(int i=1; i<=100; i++)
    for(int j=1; j<=100; j++)
    for(int k=1; k<=100; k++){
      int t = i*i + j*j + k*k + i*j + j*k + k*i;
      if(t<=10000){
        ans.at(t)++;
      }
    }

    for(int i=1; i<=n; i++)
      cout << ans.at(i) << endl;
}


Measured memory_bytes: 3624
#include <stdio.h>

int main(){
    
    char s_a[100], s_b[100], s_c[100], turn = 'a';
    int c_a=0, c_b=0, c_c=0;
    
    scanf("%s", s_a);
    scanf("%s", s_b);
    scanf("%s", s_c);
    
    do{
        switch (turn) {
            case 'a':
                if ((turn = s_a[c_a++]) == 0){
                    printf("A\n");
                    return 0;
                }
                break;
                
            case 'b':
                if ((turn = s_b[c_b++]) == 0){
                    printf("B\n");
                    return 0;
                }
                break;
                
            case 'c':
                if ((turn = s_c[c_c++]) == 0){
                    printf("C\n");
                    return 0;
                }
                break;
        }
    } while (1);
    
    return 0;
}

Measured memory_bytes: 128
module Main where

import Control.Applicative
import Numeric
import Data.Char
import Data.List
import Data.Ord

main :: IO ()
main = do
  { cs <- getContents
  ; putStr $ unlines
           $ map showCharCount
           $ mergeCharCounts
           $ charCounts
           $ alphas cs
  }
  
alphas :: String -> String
alphas = map toLower . filter isAlpha

charCounts :: String -> [(Char, Int)]
charCounts = map count . group . sort

count :: String -> (Char, Int)
count s = (head s, length s) 

initCharCounts :: [(Char, Int)]
initCharCounts = zip ['a' .. 'z'] (repeat 0)

mergeCharCounts :: [(Char, Int)] -> [(Char, Int)]
mergeCharCounts = merge initCharCounts

merge :: [(Char, Int)] -> [(Char, Int)] -> [(Char, Int)]
merge [] [] = []
merge xs [] = xs
merge (x:xs) (y:ys) = case (comparing fst) x y of
  LT -> x : merge xs (y:ys)
  EQ -> y : merge xs ys
  _  -> error "Henn!"
  
showCharCount :: (Char, Int) -> String
showCharCount (c, n) = [c] ++ " : " ++ show n

--

getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""



Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
int main(){
    ll k,a,b;
    cin>>k>>a>>b;
    
    if(b<a+2 || a-1>k) cout<<k+1<<endl;
    else{
        ll x=(k-a+1)/2;
        cout<<1+(k-2*x)+x*(b-a)<<endl;
    }
}



Measured memory_bytes: 256
n, $k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
f = gets.split.map(&:to_i).sort.reverse
$cost = []
n.times do |i|
  $cost << [a[i], f[i], a[i] * f[i]]
end
$cost.sort_by! { |c| -c[2] }

def check(x) # x以下のコストにできるか
  cnt = 0
  $cost.each do |c|
    if c[2] > x
      cnt += (c[0] - x / c[1])
    end
  end
  cnt <= $k
end

ok = 10**18
ng = -1
while (ok - ng).abs > 1
  mid = (ok + ng) / 2
  if check(mid)
    ok = mid
  else
    ng = mid
  end
end
p ok


Measured memory_bytes: 47288
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			int N=in.nextInt();
			int T=in.nextInt();//best
			int E=in.nextInt();//誤差
			boolean judge=false;
			int ans=-1;
			int s[]=new int[N];
			for(int i=0;i<N;i++)
				s[i]=in.nextInt();
			for(int i=0;i<N;i++)
			{
				for(int j=0;;j++)
				{
					if(Math.abs(s[i]*j-T)<=E)
					{
						judge=true;
						ans=i+1;
					}
					if(s[i]*j>T+E)
						break;
				}
				if(judge)
					break;
			}
			System.out.println(judge ? ans:-1);
		}
	}
}

Measured memory_bytes: 12000
<?php
error_reporting(0);
//$N = explode(" ",trim(fgets(STDIN)));
list($N,$M,$X) = explode(" ",trim(fgets(STDIN)));
$A  = explode(" ",trim(fgets(STDIN)));

$p1 = 0;
for($i=$X;$i<=$N;$i++) {
  if (in_array($i,$A)) {
    $p1++;
  }
}
$p2=0;
for($i=$X;$i>0;$i--) {
  if (in_array($i,$A)) {
    $p2++;
  }
}
printf("%d\n",min($p1,$p2));


Measured memory_bytes: 3576
#include <stdio.h>
#define max(X, Y) ((X) > (Y) ? (X) : (Y))

int main()
{
    int a, b, c;

    scanf("%d %d %d", &a, &b, &c);

    printf("%d\n", max(a * 10 + b + c, max(a + b * 10 + c, a + b + c * 10)));

    return 0;
}


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

using namespace std;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
#define INF             1000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

void init() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	init();
	ll n, a, b;
	cin >> n >> a >> b;
	cout << (((n / (a + b)) * a) + min(n % (a + b), a));
	return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/08  Problem: ABC 092 C / Link: http://abc092.contest.atcoder.jp/tasks/abc092_c  ----- */


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

	LL N; cin >> N;
	vector<LL> a(N + 3);
	for (int i = 0; i < N; ++i) {
		cin >> a[i + 1];
	}

	VL minus(N + 2);
	LL ans = 0;
	FOR(i, 1, N + 2) {
		ans += abs(a[i] - a[i - 1]);
		LL dx1 = a[i] - a[i - 1];
		LL dx2 = a[i + 1] - a[i];
		if (dx1*dx2 < 0) {
			minus[i - 1] = 2 * min(abs(dx1), abs(dx2));
		}
	}
	FOR(i, 0, N) {
		cout << ans - minus[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>

int main()
{
	int k;
	long long int a[200010];
	std::cin >> k;
	
	for (int i = 0; i < k; ++i)
	{
		std::cin >> a[i];
		if (i == k - 1 && a[i] != 2)
		{
			std::cout << -1;
			return 0;
		}
	}
	
	long long int max = 3, min = 2;
	for (int i = k - 2; i >= 0; --i)
	{
		long long int check = (max / a[i]) * a[i];
		if (check >= min && check <= max)
		{
			if (min % a[i] == 0)
				min = min;
			else
				min = ((min / a[i]) + 1) * a[i];
			
			max = (((max / a[i]) * a[i]) + a[i]) - 1;
		}
		else
		{
			std::cout << -1;
			return 0;
		}
		
//		std::cout << min << " " << max << "\n";
	}
	
	std::cout << min << " " << max;
}

Measured memory_bytes: 1024
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,q = list(map(int, input().split()))

### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1
bit = [0]*(n+1)    
init(bit, list(map(int, input().split())))
for i in range(q):
    t,u,v = map(int, input().split())
    if t==0:
        add(bit, u+1, v)
    else:
        print(query(bit, v) - query(bit, u))

Measured memory_bytes: 133040
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

bool max_bipartite_match(const vector<vector<bool>>&adj, vector<bool>&vis, vector<int>&match, 
	const int& u, const int& n){
	for(int v=0;v<n;v++){
		if(adj[u][v] && !vis[v]){
			vis[v]=true;
			if(match[v]==-1 || max_bipartite_match(adj,vis,match,match[v],n)){
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}
int main(){
	int n; cin>>n;
	vector<ii>red(n), blue(n);
	for(int i=0;i<n;i++){
		int a,b; scanf("%d %d", &a,&b);
		red[i]={a,b};
	}
	for(int i=0;i<n;i++){
		int c,d;  scanf("%d %d", &c,&d);
		blue[i]={c,d};
	}
	vector<vector<bool>>adj(n,vector<bool>(n,false));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(red[i].first<blue[j].first && 
				red[i].second<blue[j].second){
				adj[i][j]=true;
			}
		}
	}
	int ret=0;
	vector<int>match(n,-1);
	for(int u=0;u<n;u++){
		vector<bool>vis(n,false);
		if(max_bipartite_match(adj,vis,match,u,n)){
			ret++;
		}
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] input = sc.nextLine().split("[\\s]+");
    int A = Integer.parseInt(input[0]);
    int B = Integer.parseInt(input[1]);
    System.out.println((A-1) * (B-1));
  }
}

Measured memory_bytes: 21716
#include<stdio.h>
#include<math.h>
#include<string.h>



int main(void){
char a[15],b[15];
int ia,ib;
scanf("%s%s",a,b);
ia=a[0]-'0';
ib=b[0]-'0';
int i;
//printf("%d%d",ia,ib);
if(ia>ib){
  for(i=0;i<ia;i++){
    b[i]=b[0];
  }
  b[ia]='\0';
  printf("%s",b);
  return 0;
}
else{
  for(i=0;i<ib;i++){
    a[i]=a[0];
}
a[ib]='\0';
printf("%s",a);
return 0;
}


  return 0;
}


Measured memory_bytes: 128
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


a, b, n = LI()
if b - 1 <= n:
    x = b - 1
else:
    x = n
print(a * x // b - a * (x // b))

Measured memory_bytes: 81332