codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1373.md (9564B)


      1 Source: https://codeforces.com/blog/entry/79376
      2 
      3 [1373A - Donut Shops](/contest/1373/problem/A "Educational Codeforces Round 90 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (pikmike)**
     12 
     13 ```
     14 for tc in range(int(input())):
     15 	a, b, c = map(int, input().split())
     16 	print(1 if a < c else -1, end=" ")
     17 	print(b if c < a * b else -1)
     18 ```
     19 
     20 [1373B - 01 Game](/contest/1373/problem/B "Educational Codeforces Round 90 (Rated for Div. 2)")
     21 
     22 Idea: [Roms](/profile/Roms "Master Roms")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (Roms)**
     29 
     30 ```
     31 for _ in range(int(input())):
     32     s = input()
     33     print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET')
     34 ```
     35 
     36 [1373C - Pluses and Minuses](/contest/1373/problem/C "Educational Codeforces Round 90 (Rated for Div. 2)")
     37 
     38 Idea: [Roms](/profile/Roms "Master Roms")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (Roms)**
     45 
     46 ```
     47 for _ in range(int(input())):
     48     s = input()
     49     cur, mn, res = 0, 0, len(s)
     50     for i in range(len(s)):
     51         cur += 1 if s[i] == '+' else -1
     52         if cur < mn:
     53             mn = cur
     54             res += i + 1
     55         
     56     print(res)
     57 ```
     58 
     59 [1373D - Maximum Sum on Even Positions](/contest/1373/problem/D "Educational Codeforces Round 90 (Rated for Div. 2)")
     60 
     61 Idea: [vovuh](/profile/vovuh "Master vovuh")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution (vovuh)**
     68 
     69 ```
     70 #include <bits/stdc++.h>
     71 
     72 using namespace std;
     73 
     74 int main() {
     75 #ifdef _DEBUG
     76 	freopen("input.txt", "r", stdin);
     77 //	freopen("output.txt", "w", stdout);
     78 #endif
     79 	
     80 	int t;
     81 	cin >> t;
     82 	while (t--) {
     83 		int n;
     84 		cin >> n;
     85 		vector<int> a(n);
     86 		for (auto &it : a) cin >> it;
     87 		vector<vector<long long>> dp(n + 1, vector<long long>(3));
     88 		for (int i = 0; i < n; ++i) {
     89 			dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + (i & 1 ? 0 : a[i]));
     90 			if (i + 2 <= n) dp[i + 2][1] = max(dp[i + 2][1], max(dp[i][0], dp[i][1]) + (i & 1 ? a[i] : a[i + 1]));
     91 			dp[i + 1][2] = max(dp[i + 1][2], max({dp[i][0], dp[i][1], dp[i][2]}) + (i & 1 ? 0 : a[i]));
     92 		}
     93 		cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
     94 	}
     95 	
     96 	return 0;
     97 }
     98 ```
     99 
    100 [1373E - Sum of Digits](/contest/1373/problem/E "Educational Codeforces Round 90 (Rated for Div. 2)")
    101 
    102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution 1 (BledDest)**
    109 
    110 ```
    111 #include<bits/stdc++.h>
    112 
    113 using namespace std;
    114 
    115 int n, k;
    116 
    117 bool decimalLess(const string& s, const string& t)
    118 {
    119 	if(s.size() != t.size())
    120 		return s.size() < t.size();
    121 	for(int i = 0; i < s.size(); i++)
    122 		if(s[i] != t[i])
    123 			return s[i] < t[i];
    124 	return false;
    125 }
    126 
    127 void upd(string& ans, const string& cur)
    128 {
    129 	if(ans == "-1" || decimalLess(cur, ans))
    130 		ans = cur;
    131 }
    132 
    133 void read()
    134 {
    135 	cin >> n >> k;
    136 }
    137 
    138 void solve()
    139 {
    140 	string ans = "-1";
    141 	for(int i = 0; i <= 9; i++)
    142 	{
    143 		int cnt9 = n / 9;
    144 		if(i + k < 10)
    145 			cnt9 = 0;
    146 		for(int j = 0; j <= cnt9; j++)
    147 		{
    148 		    if(i + k >= 10 && j == 0)
    149 		        continue;
    150 			int curSum = (i + (i + k)) * (k + 1) / 2;
    151 			if(j != 0)
    152 			{
    153 				int cntBefore = 10 - i;
    154 				int cntAfter = k + 1 - cntBefore;
    155 				curSum = (i + 9) * cntBefore / 2 + cntBefore * 9 * (j - 1) + (1 + cntAfter) * cntAfter / 2;
    156 			}
    157 			curSum = n - curSum;
    158 			if(curSum < 0 || curSum % (k + 1) != 0)
    159 				continue;
    160 			string curNum = {char('0' + i)};
    161 			for(int z = 0; z < j - 1; z++)
    162 				curNum += "9";
    163 			int maxNum = 9;
    164 			if(i + k >= 10)
    165 				maxNum = 8;
    166 			curSum /= (k + 1);
    167 			while(curSum != 0)
    168 			{
    169 				int d = min(curSum, maxNum);
    170 				maxNum = 9;
    171 				curSum -= d;
    172 				curNum.push_back(char('0' + d));
    173 			}
    174 			reverse(curNum.begin(), curNum.end());
    175 			upd(ans, curNum);
    176 		}
    177 	}
    178 	cout << ans << endl;
    179 }
    180 
    181 int main()
    182 {
    183 	int t;
    184 	cin >> t;
    185 	for(int i = 0; i < t; i++)
    186 	{
    187 		read();
    188 		solve();
    189 	}
    190 }
    191 ```
    192 
    193 **Solution 2 (pikmike)**
    194 
    195 ```
    196 def get(s):
    197 	return str(s % 9) + '9' * (s // 9)
    198 
    199 for tc in range(int(input())):
    200 	n, k = map(int, input().split())
    201 	k += 1
    202 	bst = 10**100
    203 	for d in range(10):
    204 		ends = 0
    205 		for i in range(k):
    206 			ends += (d + i) % 10
    207 		if ends > n:
    208 			continue
    209 		if d + k > 10:
    210 			for cnt in range(12):
    211 				s = 9 * cnt * (10 - d)
    212 				if s > n - ends:
    213 					break
    214 				for nd in range(9):
    215 					ns = s + (10 - d) * nd + (k - (10 - d)) * (nd + 1)
    216 					if ns > n - ends:
    217 						break
    218 					if (n - ends - ns) % k == 0:
    219 						bst = min(bst, int(get((n - ends - ns) // k) + str(nd) + '9' * cnt + str(d)))
    220 		elif (n - ends) % k == 0:
    221 			bst = min(bst, int(get((n - ends) // k) + str(d)))
    222 	print(-1 if bst == 10**100 else bst)
    223 ```
    224 
    225 [1373F - Network Coverage](/contest/1373/problem/F "Educational Codeforces Round 90 (Rated for Div. 2)")
    226 
    227 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    228 
    229 **Tutorial**
    230 
    231 Tutorial is loading...
    232 
    233 **Solution 1 (adedalic)**
    234 
    235 ```
    236 #include<bits/stdc++.h>
    237 
    238 using namespace std;
    239 
    240 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    241 #define sz(a) int((a).size())
    242 
    243 #define x first
    244 #define y second
    245 
    246 typedef long long li;
    247 typedef pair<int, int> pt;
    248 
    249 const int INF = int(1e9);
    250 const li INF64 = li(1e18);
    251 
    252 int n;
    253 vector<int> a, b;
    254 
    255 inline bool read() {
    256 	if(!(cin >> n))
    257 		return false;
    258 	a.resize(n);
    259 	fore(i, 0, n)
    260 		cin >> a[i];
    261 	b.resize(n);
    262 	fore(i, 0, n)
    263 		cin >> b[i];
    264 	return true;
    265 }
    266 
    267 struct func {
    268 	int minx, mink, maxk;
    269 	func() : minx(0), mink(0), maxk(0) {}
    270 	func(int minx, int mink, int maxk) : minx(minx), mink(mink), maxk(maxk) {}
    271 };
    272 
    273 func getFunc(int a, int b) {
    274 	if (a <= b)
    275 		return func(0, b - a, b);
    276 	else
    277 		return func(a - b, 0, b);
    278 }
    279 
    280 func merge(func a, func b) {
    281 	if (a.minx == -1 || b.minx == -1)
    282 		return func(-1, -1, -1);
    283 	
    284 	if (a.maxk < b.minx)
    285 		return func(-1, -1, -1);
    286 	if (a.mink >= b.minx)
    287 		return func(a.minx, min(b.maxk, b.mink + (a.mink - b.minx)), min(b.maxk, b.mink + (a.maxk - b.minx)));
    288 	else {
    289 		int add = b.minx - a.mink;
    290 		return func(a.minx + add, b.mink, min(b.maxk, b.mink + (a.maxk - b.minx)));
    291 	}
    292 }
    293 
    294 inline void solve() {
    295 	func total = getFunc(a[0], b[0]);
    296 	fore(i, 1, n)
    297 		total = merge(total, getFunc(a[i], b[i]));
    298 	
    299 	if (total.minx != -1 && total.minx <= total.mink)
    300 		cout << "YES\n";
    301 	else
    302 		cout << "NO\n";
    303 }
    304 
    305 int main() {
    306 #ifdef _DEBUG
    307 	freopen("input.txt", "r", stdin);
    308 	int tt = clock();
    309 #endif
    310 	ios_base::sync_with_stdio(false);
    311 	cin.tie(0), cout.tie(0);
    312 	cout << fixed << setprecision(15);
    313 	
    314 	int tc; cin >> tc;
    315 	
    316 	while(tc--) {
    317 		read();
    318 		solve();
    319 		
    320 #ifdef _DEBUG
    321 		cerr << "TIME = " << clock() - tt << endl;
    322 		tt = clock();
    323 #endif
    324 	}
    325 	return 0;
    326 }
    327 ```
    328 
    329 **Solution 2 (Ne0n25)**
    330 
    331 ```
    332 #include <bits/stdc++.h>
    333  
    334 using namespace std;
    335 
    336 typedef long long li;
    337 const int N = 1000 * 1000 + 13;
    338 
    339 int n;
    340 int a[N], b[N];
    341  
    342 void solve() {
    343 	scanf("%d", &n);
    344 	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    345 	for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
    346 	
    347 	li need = 0, add = 0, extra = 2e9;
    348 	for (int i = n - 1; i >= 0; --i) {
    349 		if (b[i] < need) {
    350 			puts("NO");
    351 			return;
    352 		}
    353 		
    354 		li val = b[i] - a[i];
    355 		li to_add = min(extra, max(0LL, val - need));
    356 		add += to_add;
    357 		extra = min(extra - to_add, b[i] - need - to_add);
    358 		need = max(0LL, need - val);
    359 	}
    360 	
    361 	puts(add >= need ? "YES" : "NO");
    362 }
    363  
    364 int main() {
    365 	int t;
    366 	scanf("%d", &t);
    367 	for (int i = 0; i < t; ++i)
    368 		solve();
    369 }
    370 ```
    371 
    372 [1373G - Pawns](/contest/1373/problem/G "Educational Codeforces Round 90 (Rated for Div. 2)")
    373 
    374 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    375 
    376 **Tutorial**
    377 
    378 Tutorial is loading...
    379 
    380 **Solution (Roms)**
    381 
    382 ```
    383 #include <bits/stdc++.h>
    384 
    385 using namespace std;
    386 
    387 const int N = int(2e5) + 9;
    388 
    389 int n, k;
    390 int m;
    391 int t[8 * N];
    392 int add[8 * N];
    393 int cnt[2 * N];
    394 
    395 void push(int v, int l, int r) {
    396     if (r - l != 1 && add[v] != 0) {
    397         t[v * 2 + 1] += add[v];
    398         t[v * 2 + 2] += add[v];
    399         add[v * 2 + 1] += add[v];
    400         add[v * 2 + 2] += add[v];
    401         add[v] = 0;
    402     }
    403 }
    404 
    405 void upd(int v, int l, int r, int L, int R, int x) {
    406     if (L >= R) return;
    407     if(l == L && r == R) {
    408         t[v] += x;
    409         add[v] += x;
    410         return;
    411     } 
    412     
    413     push(v, l, r);
    414     int mid = (l + r) / 2;
    415     upd(v * 2 + 1, l, mid, L, min(R, mid), x);
    416     upd(v * 2 + 2, mid, r, max(L, mid), R, x);
    417     t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    418 }
    419 
    420 void upd(int l, int r, int x) {
    421     upd(0, 0, n + n, l, r, x);
    422 }
    423 
    424 int get(int v, int l, int r, int L, int R) {
    425     if (L >= R) return 0;
    426     if (l == L && r == R) return t[v];
    427     
    428     push(v, l, r);
    429     int mid = (l + r) >> 1;
    430     return max(get(v * 2 + 1, l, mid, L, min(R, mid))
    431     		 , get(v * 2 + 2, mid, r, max(L, mid), R));
    432 }
    433 
    434 int get(int l, int r) {
    435     return get(0, 0, n + n, l, r);
    436 }
    437 
    438 int getAns(set <int> &smx) {
    439     if (smx.empty()) return 0;
    440     return max(0, get(0, *smx.rbegin() + 1) - n);
    441 }
    442 
    443 void build(int v, int l, int r) {
    444     if (r - l == 1) {
    445         t[v] = l;
    446         return;
    447     }
    448     
    449     int mid = (l + r) >> 1;
    450     build(v * 2 + 1, l, mid);
    451     build(v * 2 + 2, mid, r);
    452     t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    453 }
    454 
    455 int main(){
    456     scanf("%d %d %d", &n, &k, &m);
    457     
    458     build(0, 0, n + n);
    459     set <pair<int, int> > s;
    460     set <int> smx;
    461     for (int i = 0; i < m; ++i) {
    462         int x, y;
    463         scanf("%d %d", &x, &y);
    464         int pos = abs(x - k) + y - 1;
    465         pair <int, int> p = make_pair(x, y);
    466         if (s.count(p)) {
    467             --cnt[pos];
    468             if (cnt[pos] == 0) smx.erase(pos);
    469             upd(0, pos + 1, -1);
    470             s.erase(p);
    471         } else {
    472             ++cnt[pos];
    473             if (cnt[pos] == 1) smx.insert(pos);
    474             upd(0, pos + 1, 1);
    475             s.insert(p);
    476         }
    477         
    478         printf("%d\n", getAns(smx));
    479     }
    480     return 0;
    481 }
    482 ```