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; }