AtCoder Beginner Contest 196

AtCoder Beginner Contest 196 Solutions with Golang

問題名	実行時間制限	メモリ制限
A	Difference Max	2 sec	1024 MB	提出
B	Round Down	2 sec	1024 MB	提出
C	Doubled	2 sec	1024 MB	提出
D	Hanjo	2 sec	1024 MB	提出
E	Filters	2 sec	1024 MB	提出
F	Substring 2	3 sec	1024 MB	提出

A. Difference Max

A – Difference Max Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 100100 points

Problem Statement

Given are integers aa, bb, cc, and dd.
We will choose integers xx and yy such that a≤x≤ba≤x≤b and c≤y≤dc≤y≤d. Find the maximum possible value of x−yx−y here.

Constraints

All values in input are integers.
−100≤a≤b≤100−100≤a≤b≤100
−100≤c≤d≤100−100≤c≤d≤100

Solution

package main

import (
  "fmt"
)

func main(){
  var a,b,c,d int
  fmt.Scan(&a, &b, &c, &d)
  fmt.Println(c-b)
}

B.Round Down

B – Round Down Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200200 points

Problem Statement

Given an integer or a decimal XX, round it down to an integer and print the result.

Constraints

0≤X≤101000≤X≤10100
XX is an integer or a decimal with at most 100100 digits after the decimal point, without unnecessary leading zeros.

solution

package main

import (
	"fmt"
)

func main(){
	var s string
	fmt.Scan(&s)
	var t string
	for i := 0; i < len(s); i++ {
		if(s[i] == '.') {
			break
		} else {
			t = t+string(s[i])
		}
	}
	fmt.Println(t)
}

C.Doubled

C – Doubled Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

Given is an integer NN.
How many integers xx between 11 and NN (inclusive) satisfy the following condition?

The decimal representation (without leading zeros) of xx has an even number of digits, and its first and second halves are equal as strings.

Constraints

NN is an integer.
1≤N<10121≤N<1012

solution

package main

import (
	"fmt"
	"math"
)

func main(){
	var ans int64
	var n int64
	fmt.Scan(&n)
	var i int64
	for i = 1; i <= 1000000; i++ {
		var t int64 = i
		d := 0
		for ; t >= 1;{
			t = t/10
			d++
		}
		 t = i+i*(int64)(math.Pow(10.0, (float64)(d)))
		 if t <= n {
			 ans++
		 }else{
			 break
		 }
	}
	fmt.Println(ans)
}

D.Hanjo

D – Hanjo Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

We have a rectangular room that is HH meters long and WW meters wide.
We will cover this room with AA indistinguishable 22 meters ×× 11 meters rectangular tatami mats and BB indistinguishable 11 meter ×× 11 meter square tatami mats. The rectangular mats can be used in either direction: they can be 22 meters long and 11 meter wide, or 11 meter long and 22 meters wide.
How many ways are there to do this?
Here, it is guaranteed that 2A+B=HW2A+B=HW, and two ways are distinguished if they match only after rotation, reflection, or both.

Constraints

All values in input are integers.
1≤H,W1≤H,W
HW≤16HW≤16
0≤A,B0≤A,B
2A+B=HW2A+B=HW

Solution

package main

import (
	"fmt"
)

var h,w int
var d[16][16] int

func dfs(i int, j int, a int, b int) int{
	res := 0
	if a < 0 || b < 0{
		return 0
	}
	if j == w {
		j = 0
		i = i+1
	}
	if i == h {
		return 1
	}
	if d[i][j] == 1{
		return dfs(i,j+1, a,b)
	}
	d[i][j] = 1
	res = res + dfs(i,j+1,a,b-1)
	if j+1 < w && d[i][j+1] == 0 {
		d[i][j+1] = 1
		res = res + dfs(i,j+1, a-1, b)
		d[i][j+1] = 0
	}
	if i+1 < h && d[i+1][j] == 0 {
		d[i+1][j] = 1
		res = res + dfs(i,j+1,a-1,b)
		d[i+1][j] = 0
	}
	d[i][j] = 0
	return res
}

func main(){
	var a, b int
	fmt.Scan(&h,&w,&a,&b)
	fmt.Println(dfs(0,0,a,b))
}

E.Filters

E – Filters Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

Given are integer sequences A=(a1,a2,…,aN)A=(a1,a2,…,aN), T=(t1,t2,…,tN)T=(t1,t2,…,tN), and X=(x1,x2,…,xQ)X=(x1,x2,…,xQ).
Let us define NN functions f1(x),f2(x),…,fN(x)f1(x),f2(x),…,fN(x) as follows:

fi(x)=⎧⎨⎩x+ai(ti=1)max(x,ai)(ti=2)min(x,ai)(ti=3)fi(x)={x+ai(ti=1)max(x,ai)(ti=2)min(x,ai)(ti=3)

For each i=1,2,…,Qi=1,2,…,Q, find fN(…f2(f1(xi))…)fN(…f2(f1(xi))…).

Constraints

All values in input are integers.
1≤N≤2×1051≤N≤2×105
1≤Q≤2×1051≤Q≤2×105
|ai|≤109|ai|≤109
1≤ti≤31≤ti≤3
|xi|≤109

solution

This Go code was not accepted, because methods(fmt.scan, fmt.print) were too slow.
Instead of using fmt, you should use buffer methods.
But I don’t know much about it, I show you C++ solutions too.

package main

import (
	"fmt"
)

func main(){
	var n, q int64
	fmt.Scan(&n)
	a := make([]int64, n)
	t := make([]int64, n)

	var low, high, add int64
	low = (int64)(-1e18)
	high = (int64)(1e18)
	var i int64
	for i = 0; i < n; i++ {
		fmt.Scan(&a[i])
		fmt.Scan(&t[i])
		if t[i] == 1 {
			low = low + a[i]
			high = high + a[i]
			add = add + a[i]
		}else if t[i] == 2{
			if low < a[i] {
				low = a[i]
			}
			if high < a[i] {
				high = a[i]
			}
		} else {
			if low > a[i]{
				low = a[i]
			}
			if high > a[i]{
				high = a[i]
			}
		}
	}

	fmt.Scan(&q)
	for i = 0; i < q; i++ {
		var x int64
		fmt.Scan(&x)
		if x + add < low {
			fmt.Println(low)
		}else if x+add > high {
			fmt.Println(high)
		}else {
			fmt.Println(x+add)
		}
	}
}

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

void chmin(ll &a, ll b){if(a > b) a = b;}
void chmax(ll &a, ll b){if(a < b) a = b;}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n;
  vector<int> a(n), t(n);
  for(int i = 0; i < n; ++i) cin >> a[i] >> t[i];
  cin >> q;
  vector<int> x(q);
  for(int i = 0; i < q; ++i) cin >> x[i];
  ll low = -1e18, high = 1e18, add = 0;
  for(ll i = 0; i < n; ++i){
    if(t[i] == 1){
      low += a[i];
      high += a[i];
      add += a[i];
    }else if (t[i] == 2){
      chmax(low,a[i]);
      chmax(high,a[i]);
    }else{
      chmin(low,a[i]);
      chmin(high,a[i]);
    }
  }
  for(ll i = 0; i < q; ++i){
    if(x[i]+add < low) cout << low << endl;
    else if(x[i]+add > high) cout << high << endl;
    else cout << x[i]+add << endl;
  }
  return 0;
}

Search