akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct rerooting{
	vector<T> dp1;
	vector<T> dp2;
	T E;
	function<T(T, T)> add;
	function<T(T, T)> root;
	void dfs1(vector<vector<pair<int, int>>> &c, int v){
		dp1[v] = E;
		for (auto P : c[v]){
			int w = P.second;
			dfs1(c, w);
			dp1[v] = add(dp1[v], root(dp1[w], P.first));
		}
	}
	void dfs2(vector<vector<pair<int, int>>> &c, int v){
		int deg = c[v].size();
		vector<T> L(deg + 1, E);
		for (int i = 0; i < deg; i++){
			L[i + 1] = add(L[i], root(dp1[c[v][i].second], c[v][i].first));
		}
		vector<T> R(deg + 1, E);
		for (int i = deg - 1; i >= 0; i--){
			R[i] = add(R[i + 1], root(dp1[c[v][i].second], c[v][i].first));
		}
		for (int i = 0; i < deg; i++){
			dp2[c[v][i].second] = root(add(dp2[v], add(L[i], R[i + 1])), c[v][i].first);
			dfs2(c, c[v][i].second);
		}
	}
	rerooting(vector<vector<pair<int, int>>> &c, function<T(T, T)> add, function<T(T, T)> root, T E): add(add), root(root), E(E){
		int N = c.size();
		dp1 = vector<T>(N);
		dfs1(c, 0);
		dp2 = vector<T>(N);
		dfs2(c, 0);
	}
	T operator [](int k){
		return root(add(dp1[k], dp2[k]), 0);
	}
};
int add(int a, int b){
  return max(a, b);
}
int root(int a, int b){
  return a + b;
}
vector<vector<pair<int, int>>> child(vector<vector<pair<int, int>>> E, int r){
	int N = E.size();
	vector<vector<pair<int, int>>> c(N);
	queue<int> Q;
	Q.push(r);
	while (!Q.empty()){
		int v = Q.front();
		Q.pop();
		for (auto P : E[v]){
			int w = P.second;
			if (c[w].empty()){
				c[v].push_back(make_pair(P.first, w));
				Q.push(w);
			}
		}
	}
	return c;
}
int main(){
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> E(n);
  for (int i = 0; i < n - 1; i++){
    int s, t, w;
    cin >> s >> t >> w;
    E[s].push_back(make_pair(w, t));
    E[t].push_back(make_pair(w, s));
  }
  vector<vector<pair<int, int>>> c = child(E, 0);
  rerooting<int> ans(c, add, root, 0);
  for (int i = 0; i < n; i++){
    cout << ans[i] << endl;
  }
}


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

namespace agc030_a
{
    class Program
    {
        static void Main(string[] args)
        {
            var text = Console.ReadLine();
            var list = text.Split(' ').ToList().Select(x => int.Parse(x)).ToList();

            var a = list[0];
            // var b = list[1];

            Console.WriteLine((a - 2) * 180);
        }
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<tuple>
#include<algorithm>

using namespace std;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define RREPS(i, n) for(int i=n;i>0;i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

int r, n, m;
string s;
vector<string> ans;

void dfs(string &s, int i, int used){
	if(i == s.size()){
		ans.pb(s);
		return ;
	}
	if(s[i]=='a' || (1&(used >> (s[i]-'a')))) dfs(s, i+1, used);
	if(s[i] < 'z' && 0 == (1&(used >> (s[i]-'a'+1)))){
		s[i] ++;
		dfs(s, i+1, used | (1 << (s[i]-'a')));
		s[i] --;
	}
}

int main(){
	while(cin >> s, s != "#"){
		n = s.size();
		dfs(s, 0, 0);
		cout << ans.size() << endl;
		if(ans.size() <= 10) for(auto &s : ans) cout << s << endl;
		else{
			REP(i, 5) cout << ans[i] << endl;
			REP(i, 5) cout << ans[ans.size()-5+i] << endl;
		}
		ans.clear();
	}
}

Measured memory_bytes: 2344
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		int c[] = new int[n];
		int a[][] = new int[n][m];

		for (int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
			for (int j = 0; j < m; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < (1 << n); i++) {
			int value = 0;
			int aNow[] = new int[m];
			boolean can = true;
			for (int j = 0; j < n; j++) {
				if ((i >> j & 1) == 1) {
					value += c[j];
					for (int k = 0; k < m; k++) {
						aNow[k] += a[j][k];
					}
				}
			}
			for (int k = 0; k < m; k++) {
				if (aNow[k] < x) can = false;
			}
			if (can) min = Math.min(min, value);
		}

		if (min == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}



		sc.close();

	}

}


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

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

void dijkstra(int s, vector<int> &d, vector<vector<pair<int,int>>> &G, int x){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	d.clear();
	d.resize(G.size(),INF);
	
	d[s] = x;
	q.push(make_pair(x,s));
	
	while(!q.empty()){
		pair<int,int> p = q.top();q.pop();
		int v = p.second;
		
		if(d[v] < p.first) continue;
		
		for(pair<int,int> e : G[v]){
			if(d[e.first] > d[v] + e.second){
				d[e.first] = d[v] + e.second;
				q.push(make_pair(d[e.first],e.first));
			}
		}
	}	
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	int H, W;
	vector<string> s;
	vector<int> d;
	vector<vector<pair<int,int>>> G;
	
	cin>>H>>W;
	
	s.resize(H);
	G.resize(H*W);
	
	for(int i = 0; i < H; i++){
		cin>>s[i];
	}
	
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(i != H-1) {
				if(s[i][j] == '.' && s[i+1][j] == '#') G[i*W+j].push_back({(i+1)*W+j, 1});
				// if(s[i][j] != s[i+1][j]) G[i*W+j].push_back({(i+1)*W+j, 1});
				else G[i*W+j].push_back({(i+1)*W+j, 0});
			}
			if(j != W-1) {
				if(s[i][j] == '.' && s[i][j+1] == '#') G[i*W+j].push_back({i*W+j+1, 1});
				// if(s[i][j] != s[i][j+1]) G[i*W+j].push_back({i*W+j+1, 1});
				else G[i*W+j].push_back({i*W+j+1, 0});
			}
		}
	}
	
	dijkstra(0,d,G, s[0][0] == '#');
	
	cout<<d[(H-1)*W+W-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
	int N;
	cin >> N;
	string ans = "APPROVED";
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		if (A % 2 == 0) {
			if (A % 3 != 0 && A % 5 != 0) ans = "DENIED";
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    long long N;
    string S;
    cin >> N >> S;
    int count = 0;
    string ward = "ABC";
    for (string::size_type pos = 0; (pos = S.find(ward, pos)) != string::npos; pos += ward.size()) {
        ++count;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import math

if __name__ == "__main__":
    num = int(sys.stdin.readline().strip())
    ans = 0
    for i in range(0, num):
        n = int(sys.stdin.readline().strip())
        flag = False
        for j in range(2, int(math.sqrt(n)) + 1):
            if n % j == 0:
                flag = True
                break
        if not flag:
            ans += 1
    print ans

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

namespace abc173_d
{
  class Program
  {
    static void Main(string[] args)
    {
      var N = CIn.ReadInt();
      var A = CIn.ReadIntArray(N);

      Array.Sort(A, (a, b) => b - a);

      var l = new List<int>();
      l.Add(A[0]);

      var ans = 0L;

      for (int i = 0, j = 0; j < N - 1; i++)
      {
        if (i == 0 || N - 1 - j < 2)
        {
          ans += A[i];
          j++;
        }
        else
        {
          ans += A[i] * 2L;
          j += 2;
        }
      }

      /*for (int i = 1; i < N; i++)
      {
        var max = 0;
        var pos = 0;
        for (int j = 0; j < l.Count; j++)
        {
          if (j != l.Count - 1)
          {
            var min = Math.Min(l[j], l[j + 1]);
            if (max < Math.Min(l[j], l[j + 1]))
            {
              max = min;
              pos = j + 1;
            }
          }
          else
          {
            var min = Math.Min(l[j], l[0]);
            if (max < min)
            {
              max = min;
              pos = j + 1;
            }
          }
        }

        l.Insert(pos, A[i]);
        ans += max;
      }*/

      Console.WriteLine(ans);
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


Measured memory_bytes: 50176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h, w, n;
    cin >> h >> w >> n;
    ll m= INF;
    REP(i,h+1){
        REP(j,w+1){
            if(n<=i*w+j*h-2*i*j){
                m= min(m, i+j);
            }
        }
    }
    cout << m << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>
#include <queue>

using namespace std;

vector<string> list;

void Func(string s,int num, array<bool, 26> check){
    if(num >= s.size()){
        list.push_back(s);
        return;
    }
    int c = int(s[num] - 'a');
    if(check[c] || s[num] == 'a'){
        Func(s, num + 1, check);
    }
    if(s[num] != 'z' && !check[c+1]){
        check[c+1] = true;
        s[num] = char(s[num] + 1);
        Func(s, num + 1, check);
    }
}

int main(){
    while(true){
        list.clear();
        string s;
        cin >> s;
        if(s == "#") break;

        array<bool, 26> check;
        for(int i = 0; i < 26; ++i) check[i] = false;
        Func(s, 0, check);
        sort(list.begin(), list.end());
        cout << list.size() << endl;
        if(list.size() <= 10){
            for(const auto& c : list){
                cout << c << endl;
            }
        } else {
            for(int i = 0; i < 5; ++i) cout << list[i] << endl;
            for(int i = list.size()-5; i < list.size(); ++i) cout << list[i] << endl;
        }
    }
}


Measured memory_bytes: 4260
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <climits>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
////////////////////////////////////////////////
struct UnionFind {
  vector<int> par;  // parent
  vector<int> num;  // # of node included in the same group
  UnionFind(int n) : par(n), num(n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      num[i] = 1;
    }
  }
  int root(int x) {
    // if (num[x] <= num[par[x]]) {
    //   num[x] = num[par[x]];
    // } else {
    //   num[par[x]] = num[x];
    // }
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) return;
    par[min(rx, ry)] = max(rx, ry);
    num[rx] += num[ry];
    num[ry] = num[rx];
  }
  bool same(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
  int size(int x) { return num[root(x)]; }
};
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  int n;
  int m;
  cin >> n >> m;
  vector<P> a(m);
  REPe(e, a) {
    cin >> e.first >> e.second;
    e.first--;
    e.second--;
  }
  reverse(all(a));
  vecll ans(m + 1, 0);
  UnionFind uf(n);
  REP(i, m) {
    if (uf.same(a[i].first, a[i].second)) {
      // cout << a[i].first << "," << a[i].second << ": "
      //      << (ll)uf.size(a[i].first) << " " << (ll)uf.size(a[i].second)
      //      << "->";
      ans[i + 1] = ans[i];
      uf.unite(a[i].first, a[i].second);
      // cout << (ll)uf.size(a[i].first) << " " << (ll)uf.size(a[i].second)
      //      << endl;
    } else {
      // cout << a[i].first << "," << a[i].second << ": "
      //      << (ll)uf.size(a[i].first) << " " << (ll)uf.size(a[i].second)
      //      << "->";
      ans[i + 1] = ans[i] + (ll)uf.size(a[i].first) * (ll)uf.size(a[i].second);
      uf.unite(a[i].first, a[i].second);
      // cout << (ll)uf.size(a[i].first) << " " << (ll)uf.size(a[i].second)
      //      << endl;
    }
  }
  reverse(all(ans));
  // REP(i, n) { cout << uf.size(i) << endl; }
  ll tot = (ll)n * (ll)(n - 1) / 2;
  // cout << tot << endl;
  FOR(i, 1, m + 1) { cout << tot - ans[i] << endl; }
}
//////////////////////////////////////////////


Measured memory_bytes: 3712
#include <iostream>
#include <queue>
#include <vector>
#include <limits>
#include <cstring>

#define FOR(i,b,n) for(int i=b;i<n; i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))

using namespace std;

int w, h, sx, sy;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
char field[30][30] = {0};
bool visit[30][30] = {0};

int solve();
void solve_rec(int, int);

int solve()
{
	int res = 0;
	CLR(visit);
	solve_rec(sx, sy);
	
	FOR(j,0,h)
		FOR(i,0,w)
		{
			if( visit[j][i] == true	)
			{
				res++;
			}
		}
	
	return res;
}

void solve_rec(int x, int y)
{
	if( !(x < 0 || x >= w || y < 0 || y >= h
	|| field[y][x] == '#' || visit[y][x] == true ) )
	{
		visit[y][x] = true;
		
		FOR(i, 0, 4)
		{
			solve_rec(x+dx[i], y+dy[i]);
		}
	}
	
	return;
}
	
int main()
{
	while(cin >> w >> h, (w||h))
	{
		FOR(j,0,h)
			FOR(i,0,w)
			{
				cin >> field[j][i];
				
				if( field[j][i] == '@')
				{
					sx = i; sy = j;
				}
			}
			
		cout << solve() << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 0
def main():
    n = int(input())
    x = list(map(int,input().split()))
    s = sorted(x)
    m1 = s[n//2-1]
    m2 = s[n//2]

    for i in x:
        if i<=m1:
            print(m2)
        else:
            print(m1)

if __name__ == '__main__':
    main()



Measured memory_bytes: 93652
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int N;
string S;


int main()
{

	cin >> N;
	cin >> S;

	int ans = 0;

	for (int k = 0; k < N - 1; k++) {
		vector<int> A(N);
		int c = k;
		for (int i = k + 1; i < N; i++) {
			if (i + A[i - c + k] < c + A[c]) {
				A[i] = A[i - c + k];
			}
			else {
				int j = max(0, c + A[c] - i);
				while (i + j < N && S[k + j] == S[i + j]) ++j;
				A[i] = j;
				c = i;
			}

			ans = max(ans, min(A[i], i - k));
		}
	}


	cout << ans << endl;

	return 0;
}


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

C = []
A = []
for i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])

result = -1
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)


Measured memory_bytes: 9068
#include <iostream>
#include <cstdio>
using namespace std;
#define N 200010
int k;
int n;
int a[N];
int fun(int k, int x) {
    return x>k-x?k-x:x;
}
int main(){
    while (scanf("%d %d",&k,&n)!=EOF) {
        for (int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int ans = 0,dis=0;
        for (int i=0;i<n;i++) {
            if (i==0)
                dis= k-a[n-1]+a[0];
            else
                dis = a[i]-a[i-1];
            if (ans < dis)
                ans = dis;
        }
        printf("%d\n",k-ans);
    }
    return 0;
}


Measured memory_bytes: 1152
import math
N = int(input())

l = [i for i in range(55556)]
l[1] = 0
for i in l[1:]:
    if i > math.sqrt(55556): break
    if i == 0 :continue
    for j in range(2*i,55556,i): l[j] = 0

prime = [i for i in l if (l != 0 and (i - 3)%10 == 0)]
print(" ".join(map(str,prime[:N])))


Measured memory_bytes: 5784
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int H, W;
int d[100][100];

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

using Pii = pair<int, int>;

void bfs(int x, int y) {
  queue<pair<Pii, int>> que;
  que.push(make_pair(Pii(x, y), 0));

  while (!que.empty()) {
    auto elem = que.front();
    que.pop();

    int cx = elem.first.first;
    int cy = elem.first.second;
    int cdist = elem.second;

    if (d[cx][cy] != 0) {
      continue;
    }

    d[cx][cy] = cdist;

    rep(i, 0, 4) {
      int nx = cx + dx[i];
      int ny = cy + dy[i];

      if (d[nx][ny] == 0 && !(nx == 1 && ny == 1)) {
        que.push(make_pair(Pii(nx, ny), cdist + 1));
      }
    }
  }
}

void trace_route(int x, int y) {
  int cx = x;
  int cy = y;

  while (!(cx == 1 && cy == 1)) {
    int cdist = d[cx][cy];
    d[cx][cy] = -1;

    rep(i, 0, 4) {
      int nx = cx + dx[i];
      int ny = cy + dy[i];
      if (d[nx][ny] == cdist - 1) {
        cx = nx;
        cy = ny;
        break;
      }
    }
  }

  d[1][1] = -1;
}

int main() {
  cin >> H >> W;
  rep(i, 0, H) {
    string s;
    cin >> s;
    d[i + 1][0] = -1;
    d[i + 1][W + 1] = -1;
    rep(j, 0, W) {
      if (s[j] == '.') {
        d[i + 1][j + 1] = 0;
      } else {
        d[i + 1][j + 1] = -1;
      }
    }
  }
  rep(i, 0, W + 2) {
    d[0][i] = -1;
    d[H + 1][i] = -1;
  }

  bfs(1, 1);

  if (d[H][W] == 0) {
    cout << -1 << endl;
    return 0;
  }

  trace_route(H, W);

  int ans = 0;
  repe(i, 1, H) {
    repe(j, 1, W) {
      if (d[i][j] != -1) ++ans;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
from decimal import *
import math
a,b,x=map(int,input().split())
height=Decimal(x)/Decimal(a*a)

y1=Decimal(2*a*height)/Decimal(b)   #これってbを固定した時の高さじゃ
if y1>a:#a*height=(b+y)*a/2<=>y=2height-b
    y1=b-(2*height-b)
    print(math.degrees(math.atan(y1/a)))
else:#a*height=b*y/2なるy<=>y=2*a*height/b
    print(math.degrees(math.atan(b/y1)))

Measured memory_bytes: 59500
N, Q = map(int, input().split())
s = input()
TD = [input().split() for i in range(Q)]


def check(i):
    """どっちに落ちるかを返す
    -1,0,1

    Args:
        i ([type]): [description]
    """

    if i == -1:
        return -1
    if i == N:
        return 1

    for q in range(Q):
        t, d = TD[q]
        if t == s[i]:
            if d == "L":
                i -= 1
            else:
                i += 1

            if i == -1:
                return -1
            if i == N:
                return 1
    return 0


s_index = -1  # include
e_index = N  # include
while s_index+1 < e_index:
    c_index = (s_index+e_index)//2
    if check(c_index) == -1:
        s_index = c_index
    else:
        e_index = c_index
left = s_index

s_index = -1  # include
e_index = N  # include
while s_index+1 < e_index:
    c_index = (s_index+e_index)//2
    if check(c_index) == 1:
        e_index = c_index
    else:
        s_index = c_index
right = e_index


print(right-left-1)


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

using namespace std;

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

int main() {
    REP(i, 3) {
        int h1, m1, s1, h2, m2, s2;
        cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;
        int tmp = 3600 * (h2 - h1) + 60 * (m2 - m1) + s2 - s1;

        int h = tmp / 3600;
        tmp %= 3600;
        int m = tmp / 60;
        int s = tmp % 60;

        cout << h << " " << m << " " << s << endl;
    }
    return 0;
}



Measured memory_bytes: 3084
while true do
    h, w = gets.split(" ").map(&:to_i)
    if h && w == 0
        break
    end
    a = h - 2
    b = w - 2

    puts "#" * w 
    i = 0
    while i < a do
        puts ("#" + "." * b + "#")
        i = i + 1
    end
    puts "#" * w
    
    print "\n"
end

Measured memory_bytes: 8748
#include<bits/stdc++.h>
using namespace std;
 
long long n, cnt, jumlah, selisih;
map<long long, long long>sum, idx;
long long a[200003], b[200003];
 
int main(){
	cin>>n;
	for(long long i=1; i<=n; i++){
		cin>>a[i];
		b[i]=i;
	}
	for(long long i=1; i<=n; i++){
		jumlah=a[i]+b[i];
		selisih=b[i]-a[i];
		sum[jumlah]++;
		idx[selisih]++;
	}
	for(long long i=1; i<=n; i++){
		jumlah=a[i]+b[i];
		selisih=b[i]-a[i];
		sum[jumlah]--;
		idx[selisih]--;
		cnt=cnt+sum[selisih]+idx[jumlah];
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 52164
#include <stdio.h>

int main(void){
	int a,b,c,d,e;
	scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
	if (a == 0){
		printf("%d\n", 1);
	}
	if (b == 0){
		printf("%d\n", 2);
	}
	if (c == 0){
		printf("%d\n", 3);
	}
	if (d == 0){
		printf("%d\n", 4);
	}
	if (e == 0){
		printf("%d\n", 5);
	}
	return 0;
}

Measured memory_bytes: 1724
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    if((A==B&&B!=C) || (B==C&&C!=A) || (C==A&&A!=B)){
        cout << "Yes" << endl; 
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

namespace AtCoderCs
{
    class Program
    {
        static void Main()
        {

            var Num = int.Parse(Console.ReadLine());
            List<KeyValuePair<string, int>> Songs = new List<KeyValuePair<string, int>>(Num);
            int Sum = 0;

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

                var Buf = Console.ReadLine().Split(' ');
                int Second = int.Parse(Buf[1]);
                Songs.Add(new KeyValuePair<string, int>(Buf[0], Second));

                Sum += Second;
            }

            string LastSong = Console.ReadLine();
            int Index = Songs.FindIndex(x => x.Key == LastSong);

            // 就寝位置が後半の場合
            if (Index > Songs.Count / 2)
            {

                Sum = 0;

                for (int i = Index + 1; i < Songs.Count; i++)
                {

                    Sum += Songs[i].Value;

                }

            }
            else
            {

                for (int i = 0; i < Index + 1; i++)
                {

                    Sum -= Songs[i].Value;

                }

            }

            Console.WriteLine(Sum);

        }


    }
}


Measured memory_bytes: 13268
#include<stdio.h>

int f[1000][1000];
int p[1000][1000];
int did[10000];
int max= -1<<30;


void search(int d[],int n){
  int i,j,s=0,m=0;
  int a[1000];

  for(i=0;i<10;i++){
    m*=2;
    m+=d[i];
  }
  if(did[m]==1) return;
  did[m]=1;

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

  for(i=0;i<n;i++){
    for(j=0;j<10;j++){
      if(d[j]==1&&f[i][j]==1)
        a[i]++;
    }
  }
  if(m!=0){
    for(i=0;i<n;i++){
      s+=p[i][a[i]];
    }
    if(s>max) max=s;
  }

  for(i=0;i<10;i++){
    if(d[i]==0){
     d[i]=1;
      search(d,n);
    }
    else{
      d[i]=0;
      search(d,n);
    }
  }

}




int main(void){
  int i,j,n;
  int d[1000];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<10;j++){
    scanf("%d",&f[i][j]);
    }
  }

  for(i=0;i<10000;i++)
    did[i]=0;

  for(i=0;i<n;i++){
    for(j=0;j<11;j++){
      scanf("%d",&p[i][j]);
    }
  }

  for(i=0;i<10;i++)
    d[i]=0;

  search(d,n);

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

  return 0;
}


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

int main() {
  string S;
  cin >> S;
  int N = S.size();
  vector<int> ans(N, 0);
  int count = 1;
  for(int i = 0; i < N - 1; i++) {
    if(S.at(i) == S.at(i + 1)) {
      count++;
    }
    else if(S.at(i) == 'R') {
      ans.at(i) += (count + 1) / 2;
      ans.at(i + 1) += count / 2;
      count = 1;
    }
    else {
      ans.at(i - count + 1) += (count + 1) / 2;
      ans.at(i - count) += count / 2;
      count = 1;
    }
  }
  ans.at(N - 1 - count) += count / 2;
  ans.at(N - 1 - count + 1) += (count + 1) / 2;
  for(int i = 0; i < N; i++) {
    cout << ans.at(i) << " ";
  }
  cout << endl;
}

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N;
  cin >> N;
  
  ll ans_total = 1;
  ll ans_odd   = 1;

  rep(i, N){
    int a;
    cin >> a;
    ans_total = ans_total * 3;
    if(a%2==0){
      ans_odd *= 2;
    }
  }

  cout << ans_total - ans_odd << endl;



  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,x,a[101]={0},i,tmp,s=0,y=0;
	scanf("%d%d%d",&n,&m,&x);
	for(i=0;i<m;i++)
	{
		scanf("%d",&tmp);
		a[tmp]=1;
	}
	for(i=1;i<=x;i++)
	{
		if(a[i])
			s++;
	}
	for(i=x;i<=n;i++)
	{
		if(a[i])
			y++;
	}
	printf("%d",min(y,s));
	return 0;
}

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

void solve( int case_i, int W, int N ) {
	vector<int> v( N+1 ), w( N+1 );
	for( int i = 1; i <= N; ++i ) {
		char c;
		cin >> v[i] >> c >> w[i];
	}

	vector<vector<int>> dp( N+1, vector<int>( W+1 ) );
	for( int i = 1; i <= N; ++i ) {
		for( int j = 1; j <= W; ++j ) {
			if( j >= w[i] ) {
				int x = dp[i-1][j - w[i]] + v[i];
				int y = dp[i-1][j];
				dp[i][j] = max( x, y );
			}
			else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}

	int rv = dp[N][W];
	int rw = W;
	for( int i = W-1; i > 0; --i ) {
		if( dp[N][i] == rv ) {
			rw = i;
		}
	}

	cout << "Case " << case_i << ":\n";
	cout << rv << '\n' << rw << '\n';
}

int main() {
	ios_base::sync_with_stdio( false );

	int W, N;
	for( int i = 1; cin >> W >> N; ++i ) {
		if( W == 0 ) {
			break;
		}

		solve( i, W, N );
	}

	return 0;
}



Measured memory_bytes: 6752
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0 for _ in range(lenT+1)] for _ in range(lenS+1)]

for i in range(lenS):
  for j in range(lenT):
    if S[i] == T[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      if dp[i+1][j] >= dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
         dp[i+1][j+1] = dp[i][j+1]

ans = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] >= dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m -= 1
print(ans[::-1])

Measured memory_bytes: 120924
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    double x[n] = {0};
    double y[n] = {0};
    for (int i = 0; i < n; i++) {
        scanf("%lf", &x[i]);
    }
    
    for (int j = 0; j < n; j++) {
        scanf("%lf", &y[j]);
    }
    
    double p_1 = 0;
    double p_2 = 0;
    double p_3 = 0;
    double p_inf = 0;
    for (int k = 0; k < n; k++) {
        p_1 += abs(x[k] - y[k]);
        p_2 += pow(abs(x[k] - y[k]), 2.0);
        p_3 += pow(abs(x[k] - y[k]), 3.0);
        if (p_inf < abs(x[k] - y[k])) {
            p_inf = abs(x[k] - y[k]);
        }
    }
    printf("%lf\n", p_1);
    printf("%lf\n", sqrt(p_2));
    printf("%lf\n", pow(p_3, 1.0/3));
    printf("%lf\n", p_inf);
}


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

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> broken(N+1);
  
  for (int i=0;i<M;i++){
    int a;
    cin >> a;
    broken[a] = 1;
  }
  
  vector<int> dp(N+2);
  const int mod =1000000007;
  dp[N]=1;
  for (int i=N-1;i>=0;i--){
    if (broken[i]){
      dp[i]=0;
      continue;
    }
    dp[i] = (dp[i+1]+dp[i+2])%mod;
  }
  cout << dp[0] <<endl;
}
  
  
  


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

int main() {

	int n, k, c;
	cin >> n >> k >> c;
	string s;
	cin >> s;

	vector<int> ans1, ans2;

	for (int i = 0; i < n; i++) {
		if (s[i] == 'o') {
			ans1.push_back(i);
			i += c;
		}
	}

	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'o') {
			ans2.push_back(i);
			i -= c;
		}
	}

	if (ans1.size() == k) {
		for (auto n : ans1) {
			if (binary_search(ans2.rbegin(), ans2.rend(), n)) {
				cout << n + 1 << endl;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3448
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
int main()
{
    // std::cout << std::fixed << std::setprecision(10);
    int n, d; std::cin >> n >> d;
    int ans = (n+d*2)/(d*2+1);
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int r; cin >> r;
  cout << r*r << endl;
  return 0;
}


Measured memory_bytes: 256
S1 = []
S2= []
sum = 0
for i, s in enumerate(input()):
    if s == "\\":
        S1.append(i)
    elif s == "/" and len(S1) > 0:
        j = S1.pop()
        sum += i - j
        a = i - j
        while len(S2) > 0 and S2[-1][0] > j:
            a += S2.pop()[1]
        S2.append((j, a))
print(sum)
sum2 = [str(len(S2))]
for s in S2:
    sum2.append(str(s[1]))
print(" ".join(sum2))



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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b != c) cout << "Yes" << endl;
    else if (b == c && c != a) cout << "Yes" << endl;
    else if (c == a && a != b) cout << "Yes" << endl;
    else cout << "No" << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<int> d(n+1, 0);
    for (int x = 1; x < 100; x++)
        for (int y = 1; y < 100; y++)
            for (int z = 1; z < 100; z++) {
                int t = x * x + y * y + z * z + x * y + y * z + z * x;
                if (t < n+1)
                    d[t]++;
            }
    
    for (int i = 1; i <= n; i++)
        cout << d[i] << endl;
    
    return 0;
}


Measured memory_bytes: 3564
#include<stdio.h>
#include<stdlib.h>

int compare_int(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}

int main(){
	int n,i,d[100000];
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&d[i]);
	qsort(d,n,sizeof(int),compare_int);
	printf("%d\n",d[n/2]-d[n/2-1]);
	return 0;
}

Measured memory_bytes: 892
import Foundation
class Node {
  var val: Int64
  var next: Node?
  init(val: Int64) {
    self.val = val
  }
}

class Queue {
  var head: Node?
  var tail: Node?
  init(){}
  func enqueue(val: Int64) {
    let node = Node(val: val)
    if head == nil {
      head = node
      tail = head
    } else {
      tail!.next = node
      tail = node
    }
  }
  func dequeue() -> Int64 {
    let val = self.head!.val
    self.head = self.head!.next
    if self.head == nil {
      self.tail = nil
    }
    return val
  }
}
func solve(K: Int64) -> Int64 {
  if K < 10 {
    return K
  }
  let queue = Queue()
  for i in 1...9 {
    queue.enqueue(Int64(i))
  }
  var count: Int64 = 9
  var result: Int64 = -1
  while count < K {
    let top = queue.dequeue()
    let last = top % 10
    for start in last-1...last+1 {
      if start < 0 || start > 9 {
        continue
      }
      let next = top * 10 + start
      queue.enqueue(next)
      count += 1
      if count == K {
        result = next
        break
      }
    }
  }
  return result
}

let input = readLine()!
let info = input.componentsSeparatedByString(" ")
let K = Int64(info[0])!

print(solve(K))


Measured memory_bytes: 7780
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    cin >> N;
    vector<pair<int, int>> p(N);
    for(int i = 0; i < N; i++){
        cin >> p[i].first;
        p[i].second = i + 1;
    }
    sort(p.begin(), p.end());
    for(int i = 0; i < N; i++){
        cout << p[i].second << (i == N - 1 ? "\n" : " ");
    }
    return 0;
}


Measured memory_bytes: 1536
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	while(true) {
		auto np = readInts();
		auto n = np[0];
		auto p = np[1];
		if(n == 0 && p == 0) {
			return;
		}
		auto stone = new int[n];
		int m = 0;
		int wan = p;
		while(true) {
			if(wan == 1 && stone[m] == p-1) {
				writeln(m);
				break;
			}
			if(wan > 0) {
				++stone[m];
				--wan;
			} else {
				wan = stone[m];
				stone[m] = 0;
			}
			m = (m+1)%n;
		}
	}
}

Measured memory_bytes: 2472
n,m=map(int,input().split())
ans=[0 for _ in range(n+1)]
cnt=[1 for _ in range(n+1)]
ans[1]=1
for i in range(m):
  a,b=map(int,input().split())
  if ans[a]==1:
    ans[b]=1
    if cnt[a]==1:
      ans[a]=0
  cnt[a]-=1
  cnt[b]+=1
print(sum(ans))

Measured memory_bytes: 4752
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define ff first
#define ss second
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }	
using namespace std;

string s;
int m=2019,resl=0;
int arr[200005];
unordered_map<int,int> mp;

int power(int x, unsigned int y, int p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)  
    {    
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}  
int main(){
	cin>>s;
	mp[0]=1;
	int n=s.size();
	arr[n]=0;
	for(int i=n-1;i>=0;i--){
		arr[i]=(arr[i+1]+((s[i]-'0')%m)*power(10,n-i-1,m))%m;
		//cout<<arr[i+1]<<endl;
		resl+=mp[arr[i]];
		mp[arr[i]]++;	
	}
	cout<<resl<<endl;
}

Measured memory_bytes: 4500
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
struct mint {
    int x;
    mint(int x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(int t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

mint dp[100010][110][2];
string K;
int D;



signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> K;
    cin >> D;
    dp[0][0][0] = 1;
    rep(i, K.length()) {
        rep(j, D) {
            rep(d, 10) {
                int next_d = (j + d) % D;
                dp[i + 1][next_d][1] += dp[i][j][1];
            }
            int num = K[i] - '0';
            int next_d = (j + num) % D;
            dp[i + 1][next_d][0] += dp[i][j][0];
            rep(d, num) {
                next_d = (j + d) % D;
                dp[i + 1][next_d][1] += dp[i][j][0];
            }
        }
    }

    cout << (dp[K.length()][0][0] + dp[K.length()][0][1] - 1).x << endl;

    return 0;
}


Measured memory_bytes: 175576
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> ii;
 
const int N = 2e5 + 5;
char s[N];
int dp[N], nxt[N][26];
 
int main() {
  scanf("%s", s);
  int n = strlen(s);
 
  dp[n] = 1;
  for (int i = 0; i < 26; ++i) nxt[n][i] = n;
  for (int i = n - 1; i >= 0; --i) {
    dp[i] = 1e9;
    for (int j = 0; j < 26; ++j) {
      dp[i] = min(dp[i], dp[nxt[i + 1][j]] + 1);
      nxt[i][j] = nxt[i + 1][j];
    }
    nxt[i][s[i] - 'a'] = i;
  }
 
  int len = 1e9, pos, c;
  for(int i = 0; i < 26; ++i) {
    if (dp[nxt[0][i]] < len) {
      len = dp[nxt[0][i]]; 
      pos = nxt[0][i]; 
      c = i; 
    }
  }
 
  printf("%c", char('a' + c));
  while (pos < n) {
    --len;
    for (int i = 0; i < 26; ++i) {
      if (dp[nxt[pos + 1][i]] == len) {
        c = i;
        break;
      }
    }
    printf("%c", char('a' + c));
    pos = nxt[pos + 1][c];
  }
  puts("");
}


Measured memory_bytes: 21504
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n;i>=0;i--)
#define For(i,m,n) for(int i=m;i<n;i++)
#define Forr(i,m,n) for(int i=m;i>n;i--)
#define Sort(a) sort(a.begin(),a.end())
#define pb push_back
#define vl vector<ll>
#define vll vector<vector<ll>>
#define INF 999999999999

int main(){
  int N;
  cin>>N;
  if(N%2==0) cout<<fixed<<setprecision(10)<<1.0/2.0<<endl;
  else cout<<fixed<<setprecision(10)<<((N+1.0)/2.0)/N<<endl;
  return 0;
}


Measured memory_bytes: 256
N=int(input())
a=[]
for i in range(N):
    a.append(input())

import numpy as np
s=np.zeros(5)

for i in a:
    if i[0]=="M":
        s[0]+=1
    elif i[0]=="A":
        s[1]+=1
    elif i[0]=="R":
        s[2]+=1
    elif i[0]=="C":
        s[3]+=1
    elif i[0]=="H":
        s[4]+=1
    else:
        continue
c=0

for i in range(5):
    for j in range(i+1,5):
        for k in range(j+1,5):
            c+=s[i]*s[j]*s[k]
print(int(c))
    


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

using namespace std;

int main() {
  int N;
  cin >> N;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}

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

int main(void) {
  string s;
  cin >> s;
  bool ok = true;
  rep (i, 3) {
    if (s[i] == s[i + 1]) ok = false;
  }
  cout << (ok ? "Good" : "Bad") << 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;

int main() {
    cin.tie(0)->sync_with_stdio(false);

	int n, k; cin >> n >> k;
	vector<ll> x(n);
	REP(i, n) cin >> x[i];

	ll res = 1e18;
	REP(i, n - k + 1) {
		ll l = abs(x[i]) + abs(x[k-1+i] - x[i]);
		ll r = abs(x[k-1+i]) + abs(x[k-1+i] - x[i]);
		res = min(res, min(l, r));
	}
	if (n == 1) res = abs(x[0]);
	cout << res << '\n';
    return 0;
}


Measured memory_bytes: 3924
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    int d[N];
    for(int i=0;i<N;i++)cin>>d[i];
    int cnt=0;
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++)cnt+=d[i]*d[j];
    }
    cout<<cnt<<endl;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int A, B;

    cin >> A >> B;

    if (A * B * 1 % 2 == 1 || A * B * 2 % 2 == 1 || A * B * 3 % 2 == 1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main() {
  string s1, s2; cin >> s1 >> s2;
  if(s1[0]==s2[2] && s1[1]==s2[1] && s1[2]==s2[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();
        if(N<=K) System.out.println(X*N);
        else System.out.println(X*K+Y*(N-K));
    }
}

Measured memory_bytes: 23124
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int mod = 1000000007;
const int INF = 1001001001;

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

#define rep(i, n)  for(int i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 100, 0), b(n + 100, 0);
    rep(i, n) cin >> a[i+1];
    int ansCnt = 0;
    string ans = "";
    for(int i = n; i >= 1; --i) {
        int index = 0;
        for(int s = 1; i * s <= n; s++) {
            index += b[s*i];
        }

        if((a[i]+index) % 2 == 1) {
            ansCnt += 1;
            b[i] = 1;
            ans += to_string(i) + " ";
        }
    }

    cout << ansCnt << endl;
    cout << ans << endl;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    lint S;
    cin >> S;
    lint X1 = 0, Y1 = 0, X2 = 1e9, Y2 = 1, X3, Y3;
    Y3 = (S + (lint)1e9 - 1) / (lint)1e9;
    X3 = (lint)1e9 * Y3 - S;
    cout << 0 << ' ' << 0 << ' ';
    cout << (lint)1e9 << ' ' << 1 << ' ';
    cout << X3 << ' ' << Y3 << ' ';

    return 0;
}

Measured memory_bytes: 3596