mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-12-21 15:11:26 +01:00
Matej Focko
7a2374a1c6
Signed-off-by: Matej Focko <me@mfocko.xyz> diff --git a/734/a.cpp b/734/a.cpp new file mode 100644 index 0000000..8b7aa0e --- /dev/null +++ b/734/a.cpp @@ -0,0 +1,111 @@ +#include <algorithm> +#include <cassert> +#include <cctype> +#include <cstdint> +#include <functional> +#include <iostream> +#include <optional> +#include <sstream> +#include <string> +#include <vector> + +namespace helpers { + +using namespace std; + +long pow(long base, long exp) { + if (exp == 0) return 1; + long half = pow(base, exp / 2); + if (exp % 2 == 0) return half * half; + return half * half * base; +} + +template <typename T> +inline void answer(const T &ans) { + cout << ans << "\n"; +} + +inline void yes() { cout << "YES\n"; } +inline void no() { cout << "NO\n"; } + +} // namespace helpers + +namespace { + +using namespace std; +using namespace helpers; + +enum result { anton, danik, tie }; + +result who_won(const std::string &results) { + auto a = std::count(results.begin(), results.end(), 'A'); + auto d = std::count(results.begin(), results.end(), 'D'); + + if (a == d) { + return result::tie; + } + + return (a > d) ? result::anton : result::danik; +} + +void solve() { + int N; + cin >> N; + + std::string results; + cin >> results; + + switch (who_won(results)) { + case result::anton: + answer("Anton"); + break; + case result::danik: + answer("Danik"); + break; + case result::tie: + answer("Friendship"); + break; + default: + assert(false); + } +} + +} // namespace + +// for single test case, comment out for ‹N› test cases +#define SINGLE + +#ifdef TEST + +#include "../.common/cpp/catch_amalgamated.hpp" + +TEST_CASE("examples") { + CHECK(who_won("ADAAAA") == result::anton); + CHECK(who_won("DDDAADA") == result::danik); + CHECK(who_won("DADADA") == result::tie); +} + +#else + +int main(void) { + +#ifdef SINGLE + + solve(); + +#else + + // for multiple test cases + int N; + std::cin >> N >> std::ws; + + for (auto i = 0; i < N; ++i) { + solve(); + } + +#endif + + return 0; +} + +#endif diff --git a/734/index.html b/734/index.html new file mode 100644 index 0000000..94e78a7 --- /dev/null +++ b/734/index.html @@ -0,0 +1,1113 @@ + +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"> +<html lang="en"> +<head> + <meta http-equiv="content-type" content="text/html; charset=UTF-8"> + <meta name="X-Csrf-Token" content="3c369c9e05a5c47b3bedccce421411f2"/> + <meta id="viewport" name="viewport" content="width=device-width, initial-scale=0.01"/> + + + <script type="text/javascript" src="//codeforces.org/s/0/js/jquery-1.8.3.js"></script> + <script type="application/javascript"> + window.locale = "en"; + window.standaloneContest = false; + function adjustViewport() { + var screenWidthPx = Math.min($(window).width(), window.screen.width); + var siteWidthPx = 1100; // min width of site + var ratio = Math.min(screenWidthPx / siteWidthPx, 1.0); + var viewport = "width=device-width, initial-scale=" + ratio; + $('#viewport').attr('content', viewport); + var style = $('<style>html * { max-height: 1000000px; }</style>'); + $('html > head').append(style); + } + + if ( /Android|webOS|iPhone|iPad|iPod|BlackBerry/i.test(navigator.userAgent) ) { + adjustViewport(); + } + + /* Protection against trailing dot in domain. */ + let hostLength = window.location.host.length; + if (hostLength > 1 && window.location.host[hostLength - 1] === '.') { + window.location = window.location.protocol + "//" + window.location.host.substring(0, hostLength - 1); + } + </script> + <meta http-equiv="pragma" content="no-cache"> + <meta http-equiv="expires" content="-1"> + <meta http-equiv="profileName" content="f1"> + <meta name="google-site-verification" content="OTd2dN5x4nS4OPknPI9JFg36fKxjqY0i1PSfFPv_J90"/> + <meta property="fb:admins" content="100001352546622" /> + <meta property="og:image" content="//codeforces.org/s/0/images/codeforces-sponsored-by-ton.png" /> + <link rel="image_src" href="//codeforces.org/s/0/images/codeforces-sponsored-by-ton.png" /> + <meta property="og:title" content="Problems - Codeforces"/> + <meta property="og:description" content=""/> + + <meta property="og:site_name" content="Codeforces"/> + + + + + + + <meta name="utc_offset" content="+03:00"/> + <meta name="verify-reformal" content="f56f99fd7e087fb6ccb48ef2" /> + <title>Problems - Codeforces</title> + <meta name="description" content="Codeforces. Programming competitions and contests, programming community" /> + <meta name="keywords" content="programming algorithm contest competition informatics olympiads c++ java graphs vkcup" /> + <meta name="robots" content="index, follow" /> + + <link rel="stylesheet" href="//codeforces.org/s/62837/css/font-awesome.min.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/line-awesome.min.css" type="text/css" charset="utf-8" /> + + <link href='//fonts.googleapis.com/css?family=PT+Sans+Narrow:400,700&subset=latin,cyrillic' rel='stylesheet' type='text/css'> + <link href='//fonts.googleapis.com/css?family=Cuprum&subset=latin,cyrillic' rel='stylesheet' type='text/css'> + + + <link rel="apple-touch-icon" sizes="57x57" href="//codeforces.org/s/0/apple-icon-57x57.png"> + <link rel="apple-touch-icon" sizes="60x60" href="//codeforces.org/s/0/apple-icon-60x60.png"> + <link rel="apple-touch-icon" sizes="72x72" href="//codeforces.org/s/0/apple-icon-72x72.png"> + <link rel="apple-touch-icon" sizes="76x76" href="//codeforces.org/s/0/apple-icon-76x76.png"> + <link rel="apple-touch-icon" sizes="114x114" href="//codeforces.org/s/0/apple-icon-114x114.png"> + <link rel="apple-touch-icon" sizes="120x120" href="//codeforces.org/s/0/apple-icon-120x120.png"> + <link rel="apple-touch-icon" sizes="144x144" href="//codeforces.org/s/0/apple-icon-144x144.png"> + <link rel="apple-touch-icon" sizes="152x152" href="//codeforces.org/s/0/apple-icon-152x152.png"> + <link rel="apple-touch-icon" sizes="180x180" href="//codeforces.org/s/0/apple-icon-180x180.png"> + <link rel="icon" type="image/png" sizes="192x192" href="//codeforces.org/s/0/android-icon-192x192.png"> + <link rel="icon" type="image/png" sizes="32x32" href="//codeforces.org/s/0/favicon-32x32.png"> + <link rel="icon" type="image/png" sizes="96x96" href="//codeforces.org/s/0/favicon-96x96.png"> + <link rel="icon" type="image/png" sizes="16x16" href="//codeforces.org/s/0/favicon-16x16.png"> + <link rel="manifest" href="/manifest.json"> + <meta name="msapplication-TileColor" content="#ffffff"> + <meta name="msapplication-TileImage" content="//codeforces.org/s/0/ms-icon-144x144.png"> + <meta name="theme-color" content="#ffffff"> + + <!--CombineResourcesFilter--> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/prettify.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/clear.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/style.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/ttypography.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/problem-statement.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/second-level-menu.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/roundbox.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/datatable.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/table-form.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/topic.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/jquery.jgrowl.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/facebox.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/jquery.wysiwyg.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/jquery.autocomplete.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/codeforces.datepick.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/colorbox.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/jquery.drafts.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/community.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/css/sidebar-menu.css" type="text/css" charset="utf-8" /> + + <!-- MathJax --> + <script type="text/x-mathjax-config"> + MathJax.Hub.Config({ + tex2jax: {inlineMath: [['$$$','$$$']], displayMath: [['$$$$$$','$$$$$$']]} + }); + MathJax.Hub.Register.StartupHook("End", function () { + Codeforces.runMathJaxListeners(); + }); + </script> + <script type="text/javascript" async + src="https://cdn-mathjax.codeforces.com/MathJax.js?config=TeX-AMS_HTML-full" + > + </script> + <!-- /MathJax --> + + <script type="text/javascript" src="//codeforces.org/s/62837/js/prettify/prettify.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/moment-with-locales.min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/pushstream.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.easing.min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.lavalamp.min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.jgrowl.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.swipe.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.hotkeys.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/facebox.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.wysiwyg.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/controls/wysiwyg.colorpicker.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/controls/wysiwyg.table.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/controls/wysiwyg.image.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/controls/wysiwyg.link.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.autocomplete.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.datepick.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.ie6blocker.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.colorbox-min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.ba-bbq.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/jquery.drafts.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/clipboard.min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/autosize.min.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/sjcl.js"></script> + <script type="text/javascript" src="/scripts/7524722dd28773e2987937a750cd80cd/en/codeforces-options.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/codeforces.js?v=20160131"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/EventCatcher.js?v=20160131"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/preparedVerdictFormats-en.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/js/confetti.min.js"></script> + <!--/CombineResourcesFilter--> + + <link rel="stylesheet" href="//codeforces.org/s/62837/markitup/skins/markitup/style.css" type="text/css" charset="utf-8" /> + <link rel="stylesheet" href="//codeforces.org/s/62837/markitup/sets/markdown/style.css" type="text/css" charset="utf-8" /> + + + <script type="text/javascript" src="//codeforces.org/s/62837/markitup/jquery.markitup.js"></script> + <script type="text/javascript" src="//codeforces.org/s/62837/markitup/sets/markdown/set.js"></script> + + <!--[if IE]> + <style> + #sidebar { + padding-left: 1em; + margin: 1em 1em 1em 0; + } + </style> + <![endif]--> + + + + +</head> +<body class=" "><span style='display:none;' class='csrf-token' data-csrf='3c369c9e05a5c47b3bedccce421411f2'> </span> + +<!-- .notificationTextCleaner used in Codeforces.showAnnouncements() --> +<div class="notificationTextCleaner" style="font-size: 0"></div> +<div class="button-up" style="display: none; opacity: 0.7; width: 50px; height:100%; position: fixed; left: 0; top: 0; cursor: pointer; text-align: center; line-height: 35px; color: #d3dbe4; font-weight: bold; font-size: 3.0rem;"><i class="icon-circle-arrow-up"></i></div> +<div class="verdictPrototypeDiv" style="display: none;"></div> + +<!-- Codeforces JavaScripts. --> +<script type="text/javascript"> + String.prototype.hashCode = function() { + var hash = 0, i, chr; + if (this.length === 0) return hash; + for (i = 0; i < this.length; i++) { + chr = this.charCodeAt(i); + hash = ((hash << 5) - hash) + chr; + hash |= 0; // Convert to 32bit integer + } + return hash; + }; + + var queryMobile = Codeforces.queryString.mobile; + if (queryMobile === "true" || queryMobile === "false") { + Codeforces.putToStorage("useMobile", queryMobile === "true"); + } else { + var useMobile = Codeforces.getFromStorage("useMobile"); + if (useMobile === true || useMobile === false) { + if (useMobile != false) { + Codeforces.redirect(Codeforces.updateUrlParameter(document.location.href, "mobile", useMobile)); + } + } + } +</script> + +<script type="text/javascript"> + if (window.parent.frames.length > 0) { + window.stop(); + } +</script> + + + + + + <script type="text/javascript"> + $(document).ready(function () { + (function () { + jQuery.expr[':'].containsCI = function(elem, index, match) { + return !match || !match.length || match.length < 4 || !match[3] || ( + elem.textContent || elem.innerText || jQuery(elem).text() || '' + ).toLowerCase().indexOf(match[3].toLowerCase()) >= 0; + } + }(jQuery)); + + $.ajaxPrefilter(function(options, originalOptions, xhr) { + var csrf = Codeforces.getCsrfToken(); + + if (csrf) { + var data = originalOptions.data; + if (originalOptions.data !== undefined) { + if (Object.prototype.toString.call(originalOptions.data) === '[object String]') { + data = $.deparam(originalOptions.data); + } + } else { + data = {}; + } + options.data = $.param($.extend(data, { csrf_token: csrf })); + } + }); + + window.getCodeforcesServerTime = function(callback) { + $.post("/data/time", {}, callback, "json"); + } + + window.updateTypography = function () { + $("div.ttypography code").addClass("tt"); + $("div.ttypography pre>code").addClass("prettyprint").removeClass("tt"); + $("div.ttypography table").addClass("bordertable"); + prettyPrint(); + } + + $.ajaxSetup({ scriptCharset: "utf-8" ,contentType: "application/x-www-form-urlencoded; charset=UTF-8", headers: { + 'X-Csrf-Token': Codeforces.getCsrfToken() + }}); + + window.updateTypography(); + + Codeforces.signForms(); + + setTimeout(function() { + $(".second-level-menu-list").lavaLamp({ + fx: "backout", + speed: 700 + }); + }, 100); + + + Codeforces.countdown(); + $("a[rel='photobox']").colorbox(); + + + function showAnnouncements(json) { + //info("j=" + JSON.stringify(json)); + + if (json.t != "a") { + return; + } + + setTimeout(function() { + Codeforces.showAnnouncements(json.d, "en"); + }, Math.random() * 500); + } + + function showEventCatcherUserMessage(json) { + if (json.t == "s") { + var points = json.d[5]; + var passedTestCount = json.d[7]; + var judgedTestCount = json.d[8]; + var verdict = preparedVerdictFormats[json.d[12]]; + var verdictPrototypeDiv = $(".verdictPrototypeDiv"); + verdictPrototypeDiv.html(verdict); + if (judgedTestCount != null && judgedTestCount != undefined) { + verdictPrototypeDiv.find(".verdict-format-judged").text(judgedTestCount); + } + if (passedTestCount != null && passedTestCount != undefined) { + verdictPrototypeDiv.find(".verdict-format-passed").text(passedTestCount); + } + if (points != null && points != undefined) { + verdictPrototypeDiv.find(".verdict-format-points").text(points); + } + Codeforces.showMessage(verdictPrototypeDiv.text()); + } + } + + $(".clickable-title").each(function() { + var title = $(this).attr("data-title"); + if (title) { + var tmp = document.createElement("DIV"); + tmp.innerHTML = title; + $(this).attr("title", tmp.textContent || tmp.innerText || ""); + } + }); + + $(".clickable-title").click(function() { + var title = $(this).attr("data-title"); + if (title) { + Codeforces.alert(title); + } else { + Codeforces.alert($(this).attr("title")); + } + }).css("position", "relative").css("bottom", "3px"); + + Codeforces.showDelayedMessage(); + + Codeforces.reformatTimes(); + + //Codeforces.initializePubSub(); + if (window.codeforcesOptions.subscribeServerUrl) { + window.eventCatcher = new EventCatcher( + window.codeforcesOptions.subscribeServerUrl, + [ + Codeforces.getGlobalChannel(), + Codeforces.getUserChannel(), + Codeforces.getUserShowMessageChannel(), + Codeforces.getContestChannel(), + Codeforces.getParticipantChannel(), + Codeforces.getTalkChannel() + ] + ); + + if (Codeforces.getParticipantChannel()) { + window.eventCatcher.subscribe(Codeforces.getParticipantChannel(), function(json) { + showAnnouncements(json); + }); + } + + if (Codeforces.getContestChannel()) { + window.eventCatcher.subscribe(Codeforces.getContestChannel(), function(json) { + showAnnouncements(json); + }); + } + + if (Codeforces.getGlobalChannel()) { + window.eventCatcher.subscribe(Codeforces.getGlobalChannel(), function(json) { + showAnnouncements(json); + }); + } + + if (Codeforces.getUserChannel()) { + window.eventCatcher.subscribe(Codeforces.getUserChannel(), function(json) { + showAnnouncements(json); + }); + } + + if (Codeforces.getUserShowMessageChannel()) { + window.eventCatcher.subscribe(Codeforces.getUserShowMessageChannel(), function(json) { + showEventCatcherUserMessage(json); + }); + } + } + + Codeforces.setupContestTimes("/data/contests"); + Codeforces.setupSpoilers(); + Codeforces.setupTutorials("/data/problemTutorial"); + }); + </script> + +<script type="text/javascript"> + var _gaq = _gaq || []; + _gaq.push(['_setAccount', 'UA-743380-5']); + _gaq.push(['_trackPageview']); + + (function () { + var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; + ga.src = (document.location.protocol == 'https:' ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; + var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); + })(); +</script> + + +<div id="body"> +<div style="width: 950px; margin: 0 auto;" class="compact-problemset"> + <div id="header" style="position: relative; margin: 0;"> + <div style="float:left;"> + <a href="/"><img height="65" style="height: 65px;" src="//codeforces.org/s/14919/images/codeforces-sponsored-by-ton.png" alt="Codeforces"/></a> + </div> + <div class="lang"> + <div style="text-align: right;"> + <a href="?locale=en"><img src="//codeforces.org/s/14919/images/flags/24/gb.png" title="In English" alt="In English"/></a> + <a href="?locale=ru"><img src="//codeforces.org/s/14919/images/flags/24/ru.png" title="По-русски" alt="По-русски"/></a> + </div> + </div> + <br style="clear: both;"/> + </div> + + <br style="clear: both;"/> + + <div style="text-align: center; font-size: 1.8rem; margin-bottom: 0.5em;" + class="caption">Codeforces Round 379 (Div. 2)</div> + <div style="border-top: 1px solid #ccc; height: 1em;"></div> + + <div class="problem-frames"> + <div + style="margin-bottom: 2em;" + > + + <style> + #facebox .content:has(.diff-popup) { + width: 90vw; + max-width: 120rem !important; + } + + .testCaseMarker { + position: absolute; + font-weight: bold; + font-size: 1rem; + } + + .diff-popup { + width: 90vw; + max-width: 120rem !important; + display: none; + overflow: auto; + } + + .input-output-copier { + font-size: 1.2rem; + float: right; + color: #888 !important; + cursor: pointer; + border: 1px solid rgb(185, 185, 185); + padding: 3px; + margin: 1px; + line-height: 1.1rem; + text-transform: none; + } + + .input-output-copier:hover { + background-color: #def; + } + + .test-explanation textarea { + width: 100%; + height: 1.5em; + } + + .pending-submission-message { + color: darkorange !important; + } + </style> + <script> + const OPENING_SPACE = String.fromCharCode(1001); + const CLOSING_SPACE = String.fromCharCode(1002); + + const nodeToText = function (node, pre) { + let result = []; + + if (node.tagName === "SCRIPT" || node.tagName === "math" + || (node.classList && node.classList.contains("input-output-copier"))) + return []; + + if (node.tagName === "NOBR") { + result.push(OPENING_SPACE); + } + + if (node.nodeType === Node.TEXT_NODE) { + let s = node.textContent; + if (!pre) { + s = s.replace(/\s+/g, " "); + } + if (s.length > 0) { + result.push(s); + } + } + + if (pre && node.tagName === "BR") { + result.push("\n"); + } + + node.childNodes.forEach(function (child) { + result.push(nodeToText(child, node.tagName === "PRE").join("")); + }); + + if (node.tagName === "DIV" + || node.tagName === "P" + || node.tagName === "PRE" + || node.tagName === "UL" + || node.tagName === "LI" + ) { + result.push("\n"); + } + + if (node.tagName === "NOBR") { + result.push(CLOSING_SPACE); + } + + return result; + } + + const isSpecial = function (c) { + return c === ',' || c === '.' || c === ';' || c === ')' || c === ' '; + } + + const convertStatementToText = function(statmentNode) { + const text = nodeToText(statmentNode, false).join("").replace(/ +/g, " ").replace(/\n\n+/g, "\n\n"); + let result = []; + for (let i = 0; i < text.length; i++) { + const c = text.charAt(i); + if (c === OPENING_SPACE) { + if (!((i > 0 && text.charAt(i - 1) === '(') || (result.length > 0 && result[result.length - 1] === ' '))) { + result.push('+'); + } + } else if (c === CLOSING_SPACE) { + if (!(i + 1 < text.length && isSpecial(text.charAt(i + 1)))) { + result.push('-'); + } + } else { + result.push(c); + } + } + return result.join("").split("\n").map(value => value.trim()).join("\n"); + }; + </script> + <div class="diff-popup"> + </div> + +<div class="problemindexholder" problemindex="A" data-uuid="ps_65c305c3b8dcc001f8771428683e810346182fe9"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">A. Anton and Danik</div><div class="time-limit"><div class="property-title">time limit per test</div>1 second</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Anton likes to play chess, and so does his friend Danik.</p><p>Once they have played <span class="tex-span"><i>n</i></span> games in a row. For each game it's known who was the winner — Anton or Danik. None of the games ended with a tie.</p><p>Now Anton wonders, who won more games, he or Danik? Help him determine this.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains a single integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 100 000</span>) — the number of games played.</p><p>The second line contains a string <span class="tex-span"><i>s</i></span>, consisting of <span class="tex-span"><i>n</i></span> uppercase English letters '<span class="tex-font-style-tt">A</span>' and '<span class="tex-font-style-tt">D</span>' — the outcome of each of the games. The <span class="tex-span"><i>i</i></span>-th character of the string is equal to '<span class="tex-font-style-tt">A</span>' if the Anton won the <span class="tex-span"><i>i</i></span>-th game and '<span class="tex-font-style-tt">D</span>' if Danik won the <span class="tex-span"><i>i</i></span>-th game.</p></div><div class="output-specification"><div class="section-title">Output</div><p>If Anton won more games than Danik, print "<span class="tex-font-style-tt">Anton</span>" (without quotes) in the only line of the output.</p><p>If Danik won more games than Anton, print "<span class="tex-font-style-tt">Danik</span>" (without quotes) in the only line of the output.</p><p>If Anton and Danik won the same number of games, print "<span class="tex-font-style-tt">Friendship</span>" (without quotes).</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>6<br />ADAAAA<br /></pre></div><div class="output"><div class="title">Output</div><pre>Anton<br /></pre></div><div class="input"><div class="title">Input</div><pre>7<br />DDDAADA<br /></pre></div><div class="output"><div class="title">Output</div><pre>Danik<br /></pre></div><div class="input"><div class="title">Input</div><pre>6<br />DADADA<br /></pre></div><div class="output"><div class="title">Output</div><pre>Friendship<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, Anton won <span class="tex-span">6</span> games, while Danik — only <span class="tex-span">1</span>. Hence, the answer is "<span class="tex-font-style-tt">Anton</span>".</p><p>In the second sample, Anton won <span class="tex-span">3</span> games and Danik won <span class="tex-span">4</span> games, so the answer is "<span class="tex-font-style-tt">Danik</span>".</p><p>In the third sample, both Anton and Danik won <span class="tex-span">3</span> games and the answer is "<span class="tex-font-style-tt">Friendship</span>".</p></div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=A]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + window.changedTests = new Set(); + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + String.prototype.replaceAll = function (search, replace) { + return this.split(search).join(replace); + }; + + $(".sample-test .title").each(function () { + const preId = ("id" + Math.random()).replaceAll(".", "0"); + const cpyId = ("id" + Math.random()).replaceAll(".", "0"); + + $(this).parent().find("pre").attr("id", preId); + const $copy = $("<div title='Copy' data-clipboard-target='#" + preId + "' id='" + cpyId + "' class='input-output-copier'>Copy</div>"); + $(this).append($copy); + + const clipboard = new Clipboard('#' + cpyId, { + text: function (trigger) { + const pre = document.querySelector('#' + preId); + const lines = pre.querySelectorAll(".test-example-line"); + return Codeforces.filterClipboardText(pre.innerText, lines.length); + } + }); + + const isInput = $(this).parent().hasClass("input"); + + clipboard.on('success', function (e) { + if (isInput) { + Codeforces.showMessage("The example input has been copied into the clipboard"); + } else { + Codeforces.showMessage("The example output has been copied into the clipboard"); + } + e.clearSelection(); + }); + }); + + $(".test-form-item input").change(function () { + addPendingSubmissionMessage($($(this).closest("form")), "You changed the answer, do not forget to submit it if you want to save the changes"); + const index = $(this).closest(".problemindexholder").attr("problemindex"); + let test = ""; + $(this).closest("form input").each(function () { + const test_ = $(this).attr("name"); + if (test_ && test_.substring(0, 4) === "test") { + test = test_; + } + }); + if (index.length > 0 && test.length > 0) { + const indexTest = index + "::" + test; + window.changedTests.add(indexTest); + } + }); + + $(window).on('beforeunload', function () { + if (window.changedTests.size > 0) { + return 'Dialog text here'; + } + }); + + autosize($('.test-explanation textarea')); + + $(".test-example-line").hover(function() { + $(this).attr("class").split(" ").forEach((clazz) => { + if (clazz.substr(0, "test-example-line-".length) === "test-example-line-") { + let end = clazz.substr("test-example-line-".length); + if (end !== "even" && end !== "odd" && end !== "0") { + let top = 1E20; + let left = 1E20; + let problem = $(this).closest(".problemindexholder"); + $(this).closest(".input").find("." + clazz).css("background-color", "#FFFDE7").each(function() { + top = Math.min(top, $(this).offset().top); + left = Math.min(left, $(this).offset().left); + }); + let testCaseMarker = problem.find(".testCaseMarker_" + end); + if (testCaseMarker.length === 0) { + const html = "<div class=\"testCaseMarker testCaseMarker_" + end + " notice\"></div>"; + problem.append($(html)); + testCaseMarker = problem.find(".testCaseMarker_" + end); + } + if (testCaseMarker) { + testCaseMarker.show() + .offset({top, left: left - 20}) + .text(end); + } + } + } + }); + }, function() { + $(this).attr("class").split(" ").forEach((clazz) => { + if (clazz.substr(0, "test-example-line-".length) === "test-example-line-") { + let end = clazz.substr("test-example-line-".length); + if (end !== "even" && end !== "odd" && end !== "0") { + $("." + clazz).css("background-color", ""); + $(this).closest(".problemindexholder").find(".testCaseMarker_" + end).hide(); + } + } + }); + }); + + }); +</script> + </div> + <div + style="margin-bottom: 2em;" + > + + +<div class="problemindexholder" problemindex="B" data-uuid="ps_1a8ff0f1cb45201a295b026df7d726c0eaee5592"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">B. Anton and Digits</div><div class="time-limit"><div class="property-title">time limit per test</div>1 second</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Recently Anton found a box with digits in his room. There are <span class="tex-span"><i>k</i><sub class="lower-index">2</sub></span> digits <span class="tex-span">2</span>, <span class="tex-span"><i>k</i><sub class="lower-index">3</sub></span> digits <span class="tex-span">3</span>, <span class="tex-span"><i>k</i><sub class="lower-index">5</sub></span> digits <span class="tex-span">5</span> and <span class="tex-span"><i>k</i><sub class="lower-index">6</sub></span> digits <span class="tex-span">6</span>.</p><p>Anton's favorite integers are <span class="tex-span">32</span> and <span class="tex-span">256</span>. He decided to compose this integers from digits he has. He wants to make the sum of these integers as large as possible. Help him solve this task!</p><p>Each digit can be used no more than once, i.e. the composed integers should contain no more than <span class="tex-span"><i>k</i><sub class="lower-index">2</sub></span> digits <span class="tex-span">2</span>, <span class="tex-span"><i>k</i><sub class="lower-index">3</sub></span> digits <span class="tex-span">3</span> and so on. Of course, unused digits are not counted in the sum.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The only line of the input contains four integers <span class="tex-span"><i>k</i><sub class="lower-index">2</sub></span>, <span class="tex-span"><i>k</i><sub class="lower-index">3</sub></span>, <span class="tex-span"><i>k</i><sub class="lower-index">5</sub></span> and <span class="tex-span"><i>k</i><sub class="lower-index">6</sub></span> — the number of digits <span class="tex-span">2</span>, <span class="tex-span">3</span>, <span class="tex-span">5</span> and <span class="tex-span">6</span> respectively (<span class="tex-span">0 ≤ <i>k</i><sub class="lower-index">2</sub>, <i>k</i><sub class="lower-index">3</sub>, <i>k</i><sub class="lower-index">5</sub>, <i>k</i><sub class="lower-index">6</sub> ≤ 5·10<sup class="upper-index">6</sup></span>).</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer — maximum possible sum of Anton's favorite integers that can be composed using digits from the box.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>5 1 3 4<br /></pre></div><div class="output"><div class="title">Output</div><pre>800<br /></pre></div><div class="input"><div class="title">Input</div><pre>1 1 1 1<br /></pre></div><div class="output"><div class="title">Output</div><pre>256<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, there are five digits <span class="tex-span">2</span>, one digit <span class="tex-span">3</span>, three digits <span class="tex-span">5</span> and four digits <span class="tex-span">6</span>. Anton can compose three integers <span class="tex-span">256</span> and one integer <span class="tex-span">32</span> to achieve the value <span class="tex-span">256 + 256 + 256 + 32 = 800</span>. Note, that there is one unused integer <span class="tex-span">2</span> and one unused integer <span class="tex-span">6</span>. They are not counted in the answer.</p><p>In the second sample, the optimal answer is to create on integer <span class="tex-span">256</span>, thus the answer is <span class="tex-span">256</span>.</p></div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=B]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + + }); +</script> + </div> + <div + style="margin-bottom: 2em;" + > + + +<div class="problemindexholder" problemindex="C" data-uuid="ps_b077555a1e4cdfa7a82efaaafb94648f66976a53"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">C. Anton and Making Potions</div><div class="time-limit"><div class="property-title">time limit per test</div>4 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare <span class="tex-span"><i>n</i></span> potions.</p><p>Anton has a special kettle, that can prepare one potions in <span class="tex-span"><i>x</i></span> seconds. Also, he knows spells of two types that can faster the process of preparing potions.</p><ol> <li> Spells of this type speed up the preparation time of one potion. There are <span class="tex-span"><i>m</i></span> spells of this type, the <span class="tex-span"><i>i</i></span>-th of them costs <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> manapoints and changes the preparation time of each potion to <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> instead of <span class="tex-span"><i>x</i></span>. </li><li> Spells of this type immediately prepare some number of potions. There are <span class="tex-span"><i>k</i></span> such spells, the <span class="tex-span"><i>i</i></span>-th of them costs <span class="tex-span"><i>d</i><sub class="lower-index"><i>i</i></sub></span> manapoints and instantly create <span class="tex-span"><i>c</i><sub class="lower-index"><i>i</i></sub></span> potions. </li></ol><p>Anton can use <span class="tex-font-style-bf">no more than one</span> spell of the first type and <span class="tex-font-style-bf">no more than one</span> spell of the second type, and the total number of manapoints spent should not exceed <span class="tex-span"><i>s</i></span>. Consider that all spells are used instantly and right before Anton starts to prepare potions.</p><p>Anton wants to get to the next level as fast as possible, so he is interested in the minimum number of time he needs to spent in order to prepare at least <span class="tex-span"><i>n</i></span> potions.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains three integers <span class="tex-span"><i>n</i></span>, <span class="tex-span"><i>m</i></span>, <span class="tex-span"><i>k</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 2·10<sup class="upper-index">9</sup>, 1 ≤ <i>m</i>, <i>k</i> ≤ 2·10<sup class="upper-index">5</sup></span>) — the number of potions, Anton has to make, the number of spells of the first type and the number of spells of the second type.</p><p>The second line of the input contains two integers <span class="tex-span"><i>x</i></span> and <span class="tex-span"><i>s</i></span> (<span class="tex-span">2 ≤ <i>x</i> ≤ 2·10<sup class="upper-index">9</sup>, 1 ≤ <i>s</i> ≤ 2·10<sup class="upper-index">9</sup></span>) — the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.</p><p>The third line contains <span class="tex-span"><i>m</i></span> integers <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> < <i>x</i></span>) — the number of seconds it will take to prepare one potion if the <span class="tex-span"><i>i</i></span>-th spell of the first type is used.</p><p>The fourth line contains <span class="tex-span"><i>m</i></span> integers <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>b</i><sub class="lower-index"><i>i</i></sub> ≤ 2·10<sup class="upper-index">9</sup></span>) — the number of manapoints to use the <span class="tex-span"><i>i</i></span>-th spell of the first type.</p><p>There are <span class="tex-span"><i>k</i></span> integers <span class="tex-span"><i>c</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>c</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>) in the fifth line — the number of potions that will be immediately created if the <span class="tex-span"><i>i</i></span>-th spell of the second type is used. It's guaranteed that <span class="tex-span"><i>c</i><sub class="lower-index"><i>i</i></sub></span> are <span class="tex-font-style-bf">not decreasing</span>, i.e. <span class="tex-span"><i>c</i><sub class="lower-index"><i>i</i></sub> ≤ <i>c</i><sub class="lower-index"><i>j</i></sub></span> if <span class="tex-span"><i>i</i> < <i>j</i></span>.</p><p>The sixth line contains <span class="tex-span"><i>k</i></span> integers <span class="tex-span"><i>d</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>d</i><sub class="lower-index"><i>i</i></sub> ≤ 2·10<sup class="upper-index">9</sup></span>) — the number of manapoints required to use the <span class="tex-span"><i>i</i></span>-th spell of the second type. It's guaranteed that <span class="tex-span"><i>d</i><sub class="lower-index"><i>i</i></sub></span> are <span class="tex-font-style-bf">not decreasing</span>, i.e. <span class="tex-span"><i>d</i><sub class="lower-index"><i>i</i></sub> ≤ <i>d</i><sub class="lower-index"><i>j</i></sub></span> if <span class="tex-span"><i>i</i> < <i>j</i></span>.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer — the minimum time one has to spent in order to prepare <span class="tex-span"><i>n</i></span> potions.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>20 3 2<br />10 99<br />2 4 3<br />20 10 40<br />4 15<br />10 80<br /></pre></div><div class="output"><div class="title">Output</div><pre>20<br /></pre></div><div class="input"><div class="title">Input</div><pre>20 3 2<br />10 99<br />2 4 3<br />200 100 400<br />4 15<br />100 800<br /></pre></div><div class="output"><div class="title">Output</div><pre>200<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, the optimum answer is to use the second spell of the first type that costs <span class="tex-span">10</span> manapoints. Thus, the preparation time of each potion changes to <span class="tex-span">4</span> seconds. Also, Anton should use the second spell of the second type to instantly prepare <span class="tex-span">15</span> potions spending <span class="tex-span">80</span> manapoints. The total number of manapoints used is <span class="tex-span">10 + 80 = 90</span>, and the preparation time is <span class="tex-span">4·5 = 20</span> seconds (<span class="tex-span">15</span> potions were prepared instantly, and the remaining <span class="tex-span">5</span> will take <span class="tex-span">4</span> seconds each).</p><p>In the second sample, Anton can't use any of the spells, so he just prepares <span class="tex-span">20</span> potions, spending <span class="tex-span">10</span> seconds on each of them and the answer is <span class="tex-span">20·10 = 200</span>.</p></div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=C]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + + }); +</script> + </div> + <div + style="margin-bottom: 2em;" + > + + +<div class="problemindexholder" problemindex="D" data-uuid="ps_279de45d108c7cb50845c790fc216a4e6b3df74d"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">D. Anton and Chess</div><div class="time-limit"><div class="property-title">time limit per test</div>4 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Anton likes to play chess. Also, he likes to do programming. That is why he decided to write the program that plays chess. However, he finds the game on <span class="tex-span">8</span> to <span class="tex-span">8</span> board to too simple, he uses an infinite one instead.</p><p>The first task he faced is to check whether the king is in check. Anton doesn't know how to implement this so he asks you to help.</p><p>Consider that an infinite chess board contains one white king and the number of black pieces. There are only rooks, bishops and queens, as the other pieces are not supported yet. The white king is said to be in check if at least one black piece can reach the cell with the king in one move. </p><p>Help Anton and write the program that for the given position determines whether the white king is in check.</p><p>Remainder, on how do chess pieces move: </p><ul> <li> Bishop moves any number of cells diagonally, but it can't "leap" over the occupied cells. </li><li> Rook moves any number of cells horizontally or vertically, but it also can't "leap" over the occupied cells. </li><li> Queen is able to move any number of cells horizontally, vertically or diagonally, but it also can't "leap". </li></ul></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains a single integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 500 000</span>) — the number of black pieces.</p><p>The second line contains two integers <span class="tex-span"><i>x</i><sub class="lower-index">0</sub></span> and <span class="tex-span"><i>y</i><sub class="lower-index">0</sub></span> (<span class="tex-span"> - 10<sup class="upper-index">9</sup> ≤ <i>x</i><sub class="lower-index">0</sub>, <i>y</i><sub class="lower-index">0</sub> ≤ 10<sup class="upper-index">9</sup></span>) — coordinates of the white king.</p><p>Then follow <span class="tex-span"><i>n</i></span> lines, each of them contains a character and two integers <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>y</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span"> - 10<sup class="upper-index">9</sup> ≤ <i>x</i><sub class="lower-index"><i>i</i></sub>, <i>y</i><sub class="lower-index"><i>i</i></sub> ≤ 10<sup class="upper-index">9</sup></span>) — type of the <span class="tex-span"><i>i</i></span>-th piece and its position. Character '<span class="tex-font-style-tt">B</span>' stands for the bishop, '<span class="tex-font-style-tt">R</span>' for the rook and '<span class="tex-font-style-tt">Q</span>' for the queen. It's guaranteed that no two pieces occupy the same position.</p></div><div class="output-specification"><div class="section-title">Output</div><p>The only line of the output should contains "<span class="tex-font-style-tt">YES</span>" (without quotes) if the white king is in check and "<span class="tex-font-style-tt">NO</span>" (without quotes) otherwise.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>2<br />4 2<br />R 1 1<br />B 1 5<br /></pre></div><div class="output"><div class="title">Output</div><pre>YES<br /></pre></div><div class="input"><div class="title">Input</div><pre>2<br />4 2<br />R 3 3<br />B 1 5<br /></pre></div><div class="output"><div class="title">Output</div><pre>NO<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>Picture for the first sample: </p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/87d71a7f8b5f6bb4dfe1569981172f27df5f3c25.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center> White king is in check, because the black bishop can reach the cell with the white king in one move. The answer is "<span class="tex-font-style-tt">YES</span>".<p>Picture for the second sample: </p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/ffe9233c1153ab298f9beb299795f320e53990b3.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center> Here bishop can't reach the cell with the white king, because his path is blocked by the rook, and the bishop cant "leap" over it. Rook can't reach the white king, because it can't move diagonally. Hence, the king is not in check and the answer is "<span class="tex-font-style-tt">NO</span>".</div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=D]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + + }); +</script> + </div> + <div + style="margin-bottom: 2em;" + > + + +<div class="problemindexholder" problemindex="E" data-uuid="ps_c50327ce34f24c017be721b8fc9d2638e843bf1e"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">E. Anton and Tree</div><div class="time-limit"><div class="property-title">time limit per test</div>3 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.</p><p>There are <span class="tex-span"><i>n</i></span> vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).</p><p>To change the colors Anton can use only operations of one type. We denote it as <span class="tex-span"><i>paint</i>(<i>v</i>)</span>, where <span class="tex-span"><i>v</i></span> is some vertex of the tree. This operation changes the color of all vertices <span class="tex-span"><i>u</i></span> such that all vertices on the shortest path from <span class="tex-span"><i>v</i></span> to <span class="tex-span"><i>u</i></span> have the same color (including <span class="tex-span"><i>v</i></span> and <span class="tex-span"><i>u</i></span>). For example, consider the tree</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/743d98b529ef7a6cc1ef00db0d15c89abcd4fa68.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center><p>and apply operation <span class="tex-span"><i>paint</i>(3)</span> to get the following:</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/c70da7466118eb36e82383380d75e7da5755bbe6.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center><p>Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains a single integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 200 000</span>) — the number of vertices in the tree.</p><p>The second line contains <span class="tex-span"><i>n</i></span> integers <span class="tex-span"><i>color</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">0 ≤ <i>color</i><sub class="lower-index"><i>i</i></sub> ≤ 1</span>) — colors of the vertices. <span class="tex-span"><i>color</i><sub class="lower-index"><i>i</i></sub> = 0</span> means that the <span class="tex-span"><i>i</i></span>-th vertex is initially painted white, while <span class="tex-span"><i>color</i><sub class="lower-index"><i>i</i></sub> = 1</span> means it's initially painted black.</p><p>Then follow <span class="tex-span"><i>n</i> - 1</span> line, each of them contains a pair of integers <span class="tex-span"><i>u</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>v</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>u</i><sub class="lower-index"><i>i</i></sub>, <i>v</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i>, <i>u</i><sub class="lower-index"><i>i</i></sub> ≠ <i>v</i><sub class="lower-index"><i>i</i></sub></span>) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs <span class="tex-span">(<i>u</i><sub class="lower-index"><i>i</i></sub>, <i>v</i><sub class="lower-index"><i>i</i></sub>)</span> are distinct, i.e. there are no multiple edges.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>11<br />0 0 0 1 1 0 1 0 0 1 1<br />1 2<br />1 3<br />2 4<br />2 5<br />5 6<br />5 7<br />3 8<br />3 9<br />3 10<br />9 11<br /></pre></div><div class="output"><div class="title">Output</div><pre>2<br /></pre></div><div class="input"><div class="title">Input</div><pre>4<br />0 0 0 0<br />1 2<br />2 3<br />3 4<br /></pre></div><div class="output"><div class="title">Output</div><pre>0<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, the tree is the same as on the picture. If we first apply operation <span class="tex-span"><i>paint</i>(3)</span> and then apply <span class="tex-span"><i>paint</i>(6)</span>, the tree will become completely black, so the answer is <span class="tex-span">2</span>.</p><p>In the second sample, the tree is already white, so there is no need to apply any operations and the answer is <span class="tex-span">0</span>.</p></div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=E]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + + }); +</script> + </div> + <div + style="margin-bottom: 1em;" + > + + +<div class="problemindexholder" problemindex="F" data-uuid="ps_7402a79896f1810c56f7bfb63e86e9da8fb5567e"> + <div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier"> + <div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div> + <span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span> + </div> + <div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">F. Anton and School</div><div class="time-limit"><div class="property-title">time limit per test</div>2 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays <span class="tex-span"><i>b</i></span> and <span class="tex-span"><i>c</i></span> of length <span class="tex-span"><i>n</i></span>, find array <span class="tex-span"><i>a</i></span>, such that:</p><p><img align="middle" class="tex-formula" src="https://espresso.codeforces.com/740a8e062ff019090dccc22c683a81ee764fd5b3.png" style="max-width: 100.0%;max-height: 100.0%;" /></p><p>where <span class="tex-span"><i>a</i> <i>and</i> <i>b</i></span> means bitwise AND, while <span class="tex-span"><i>a</i> <i>or</i> <i>b</i></span> means bitwise OR.</p><p>Usually Anton is good in arraystudying, but this problem is too hard, so Anton asks you to help.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains a single integers <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 200 000</span>) — the size of arrays <span class="tex-span"><i>b</i></span> and <span class="tex-span"><i>c</i></span>.</p><p>The second line contains <span class="tex-span"><i>n</i></span> integers <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">0 ≤ <i>b</i><sub class="lower-index"><i>i</i></sub> ≤ 10<sup class="upper-index">9</sup></span>) — elements of the array <span class="tex-span"><i>b</i></span>.</p><p>Third line contains <span class="tex-span"><i>n</i></span> integers <span class="tex-span"><i>c</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">0 ≤ <i>c</i><sub class="lower-index"><i>i</i></sub> ≤ 10<sup class="upper-index">9</sup></span>) — elements of the array <span class="tex-span"><i>c</i></span>.</p></div><div class="output-specification"><div class="section-title">Output</div><p>If there is no solution, print <span class="tex-span"> - 1</span>.</p><p>Otherwise, the only line of the output should contain <span class="tex-span"><i>n</i></span> non-negative integers <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> — elements of the array <span class="tex-span"><i>a</i></span>. If there are multiple possible solutions, you may print any of them.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>4<br />6 8 4 4<br />16 22 10 10<br /></pre></div><div class="output"><div class="title">Output</div><pre>3 5 1 1 <br /></pre></div><div class="input"><div class="title">Input</div><pre>5<br />8 25 14 7 16<br />19 6 9 4 25<br /></pre></div><div class="output"><div class="title">Output</div><pre>-1<br /></pre></div></div></div></div><p> </p></div> +</div> + + <script> + $(function () { + Codeforces.addMathJaxListener(function () { + let $problem = $("div[problemindex=F]"); + let uuid = $problem.attr("data-uuid"); + let statementText = convertStatementToText($problem.find(".ttypography").get(0)); + + let previousStatementText = Codeforces.getFromStorage(uuid); + if (previousStatementText) { + if (previousStatementText !== statementText) { + $problem.find(".diff-notifier").show(); + + $problem.find(".diff-notifier-close").click(function() { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + $problem.find(".diff-notifier").hide(); + }); + + $problem.find("a.view-changes").click(function() { + $.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) { + if (result["success"] === "true") { + Codeforces.facebox(".diff-popup", "//codeforces.org/s/14919"); + $("#facebox .diff-popup").html(result["diff"]); + } + }, "json"); + }); + } + } else { + Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60); + } + }); + }); + </script> + + +<script type="text/javascript"> + $(document).ready(function () { + + function endsWith(string, suffix) { + return string.indexOf(suffix, string.length - suffix.length) !== -1; + } + + const inputFileDiv = $("div.input-file"); + const inputFile = inputFileDiv.text(); + const outputFileDiv = $("div.output-file"); + const outputFile = outputFileDiv.text(); + + + if (!endsWith(inputFile, "standard input") + && !endsWith(inputFile, "standard input")) { + inputFileDiv.attr("style", "font-weight: bold"); + } + + if (!endsWith(outputFile, "standard output") + && !endsWith(outputFile, "standard output")) { + outputFileDiv.attr("style", "font-weight: bold"); + } + + const titleDiv = $("div.header div.title"); + + + + + }); +</script> + </div> + </div> + + <div id="footer"> + <div><a href="https://codeforces.com/">Codeforces</a> (c) Copyright 2010-2023 Mike Mirzayanov</div> + <div>The only programming contests Web 2.0 platform</div> + + </div> + +</div> +</div> + <script type="application/javascript"> + if ('serviceWorker' in navigator && 'fetch' in window && 'caches' in window) { + navigator.serviceWorker.register('/service-worker-14919.js') + .then(function (registration) { + console.log('Service worker registered: ', registration); + }) + .catch(function (error) { + console.log('Registration failed: ', error); + }); + } + </script> +<script>(function(){var js = "window['__CF$cv$params']={r:'7e4a78eed8c1b329',m:'KWHTr9lOsrfm1MbjttTaixc4ApSiMqGw9beQiHm8YEw-1689009574-0-AeGABAk9pPXXMvzmhUp5AjYnotHtl02UYaTzpfyDNyBN'};_cpo=document.createElement('script');_cpo.nonce='',_cpo.src='/cdn-cgi/challenge-platform/scripts/invisible.js',document.getElementsByTagName('head')[0].appendChild(_cpo);";var _0xh = document.createElement('iframe');_0xh.height = 1;_0xh.width = 1;_0xh.style.position = 'absolute';_0xh.style.top = 0;_0xh.style.left = 0;_0xh.style.border = 'none';_0xh.style.visibility = 'hidden';document.body.appendChild(_0xh);function handler() {var _0xi = _0xh.contentDocument || _0xh.contentWindow.document;if (_0xi) {var _0xj = _0xi.createElement('script');_0xj.nonce = '';_0xj.innerHTML = js;_0xi.getElementsByTagName('head')[0].appendChild(_0xj);}}if (document.readyState !== 'loading') {handler();} else if (window.addEventListener) {document.addEventListener('DOMContentLoaded', handler);} else {var prev = document.onreadystatechange || function () {};document.onreadystatechange = function (e) {prev(e);if (document.readyState !== 'loading') {document.onreadystatechange = prev;handler();}};}})();</script></body> +</html> |
||
---|---|---|
.. | ||
a.cpp | ||
index.html |