mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-09-19 17:16:55 +02:00
1035 lines
70 KiB
HTML
1035 lines
70 KiB
HTML
|
||
<!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="03dd9c8368e59212881c15f2c08dec9a"/>
|
||
<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='03dd9c8368e59212881c15f2c08dec9a'> </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;">
|
||
<div><a href="/vkcup2017"><img src="//assets.codeforces.com/images/star-vkcup-2017-300.png"/></a></div>
|
||
</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 405 (rated, Div. 2, based on VK Cup 2017 Round 1)</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_986ff5673b1a1ff6ee48e7ac79d9370a7e728d3f">
|
||
<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. Bear and Big Brother</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>Bear Limak wants to become the largest of bears, or at least to become larger than his brother Bob.</p><p>Right now, Limak and Bob weigh <span class="tex-span"><i>a</i></span> and <span class="tex-span"><i>b</i></span> respectively. It's guaranteed that Limak's weight is smaller than or equal to his brother's weight.</p><p>Limak eats a lot and his weight is tripled after every year, while Bob's weight is doubled after every year.</p><p>After how many full years will Limak become strictly larger (strictly heavier) than Bob?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The only line of the input contains two integers <span class="tex-span"><i>a</i></span> and <span class="tex-span"><i>b</i></span> (<span class="tex-span">1 ≤ <i>a</i> ≤ <i>b</i> ≤ 10</span>) — the weight of Limak and the weight of Bob respectively.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer, denoting the integer number of years after which Limak will become strictly larger than Bob.</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 7<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 9<br /></pre></div><div class="output"><div class="title">Output</div><pre>3<br /></pre></div><div class="input"><div class="title">Input</div><pre>1 1<br /></pre></div><div class="output"><div class="title">Output</div><pre>1<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, Limak weighs <span class="tex-span">4</span> and Bob weighs <span class="tex-span">7</span> initially. After one year their weights are <span class="tex-span">4·3 = 12</span> and <span class="tex-span">7·2 = 14</span> respectively (one weight is tripled while the other one is doubled). Limak isn't larger than Bob yet. After the second year weights are <span class="tex-span">36</span> and <span class="tex-span">28</span>, so the first weight is greater than the second one. Limak became larger than Bob after two years so you should print <span class="tex-span">2</span>.</p><p>In the second sample, Limak's and Bob's weights in next years are: <span class="tex-span">12</span> and <span class="tex-span">18</span>, then <span class="tex-span">36</span> and <span class="tex-span">36</span>, and finally <span class="tex-span">108</span> and <span class="tex-span">72</span> (after three years). The answer is <span class="tex-span">3</span>. Remember that Limak wants to be larger than Bob and he won't be satisfied with equal weights.</p><p>In the third sample, Limak becomes larger than Bob after the first year. Their weights will be <span class="tex-span">3</span> and <span class="tex-span">2</span> then.</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_8492b6e1a596e7d1925a9cfd2822d1fe12918d57">
|
||
<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. Bear and Friendship Condition</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>Bear Limak examines a social network. Its main functionality is that two members can become friends (then they can talk with each other and share funny pictures).</p><p>There are <span class="tex-span"><i>n</i></span> members, numbered <span class="tex-span">1</span> through <span class="tex-span"><i>n</i></span>. <span class="tex-span"><i>m</i></span> pairs of members are friends. Of course, a member can't be a friend with themselves.</p><p>Let <span class="tex-font-style-tt">A-B</span> denote that members <span class="tex-font-style-tt">A</span> and <span class="tex-font-style-tt">B</span> are friends. Limak thinks that a network is <span class="tex-font-style-it">reasonable</span> if and only if the following condition is satisfied: For every three <span class="tex-font-style-bf">distinct</span> members (<span class="tex-font-style-tt">X</span>, <span class="tex-font-style-tt">Y</span>, <span class="tex-font-style-tt">Z</span>), if <span class="tex-font-style-tt">X-Y</span> and <span class="tex-font-style-tt">Y-Z</span> then also <span class="tex-font-style-tt">X-Z</span>.</p><p>For example: if Alan and Bob are friends, and Bob and Ciri are friends, then Alan and Ciri should be friends as well.</p><p>Can you help Limak and check if the network is reasonable? Print "<span class="tex-font-style-tt">YES</span>" or "<span class="tex-font-style-tt">NO</span>" accordingly, without the quotes.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contain two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>m</i></span> (<span class="tex-span">3 ≤ <i>n</i> ≤ 150 000</span>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b42f66704052fe39dd9de801c578ecf53d48d0fe.png" style="max-width: 100.0%;max-height: 100.0%;" />) — the number of members and the number of pairs of members that are friends.</p><p>The <span class="tex-span"><i>i</i></span>-th of the next <span class="tex-span"><i>m</i></span> lines contains two distinct integers <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>b</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>b</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i>, <i>a</i><sub class="lower-index"><i>i</i></sub> ≠ <i>b</i><sub class="lower-index"><i>i</i></sub></span>). Members <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> are friends with each other. No pair of members will appear more than once in the input.</p></div><div class="output-specification"><div class="section-title">Output</div><p>If the given network is reasonable, print "<span class="tex-font-style-tt">YES</span>" in a single line (without the quotes). Otherwise, print "<span class="tex-font-style-tt">NO</span>" in a single line (without the 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>4 3<br />1 3<br />3 4<br />1 4<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>4 4<br />3 1<br />2 3<br />3 4<br />1 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>NO<br /></pre></div><div class="input"><div class="title">Input</div><pre>10 4<br />4 3<br />5 10<br />8 9<br />1 2<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>3 2<br />1 2<br />2 3<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>The drawings below show the situation in the first sample (on the left) and in the second sample (on the right). Each edge represents two members that are friends. The answer is "<span class="tex-font-style-tt">NO</span>" in the second sample because members <span class="tex-span">(2, 3)</span> are friends and members <span class="tex-span">(3, 4)</span> are friends, while members <span class="tex-span">(2, 4)</span> are not.</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/999abd3a2ce8ac1986b5396a1ab1d24150213635.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center></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_b25c145c435248d253f8ed920f7e79c278820286">
|
||
<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. Bear and Different Names</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>In the army, it isn't easy to form a group of soldiers that will be effective on the battlefield. The communication is crucial and thus no two soldiers should share a name (what would happen if they got an order that Bob is a scouter, if there are two Bobs?).</p><p>A group of soldiers is effective if and only if their names are different. For example, a group (John, Bob, Limak) would be effective, while groups (Gary, Bob, Gary) and (Alice, Alice) wouldn't.</p><p>You are a spy in the enemy's camp. You noticed <span class="tex-span"><i>n</i></span> soldiers standing in a row, numbered <span class="tex-span">1</span> through <span class="tex-span"><i>n</i></span>. The general wants to choose a group of <span class="tex-span"><i>k</i></span> consecutive soldiers. For every <span class="tex-span"><i>k</i></span> consecutive soldiers, the general wrote down whether they would be an effective group or not.</p><p>You managed to steal the general's notes, with <span class="tex-span"><i>n</i> - <i>k</i> + 1</span> strings <span class="tex-span"><i>s</i><sub class="lower-index">1</sub>, <i>s</i><sub class="lower-index">2</sub>, ..., <i>s</i><sub class="lower-index"><i>n</i> - <i>k</i> + 1</sub></span>, each either "<span class="tex-font-style-tt">YES</span>" or "<span class="tex-font-style-tt">NO</span>". </p><ul> <li> The string <span class="tex-span"><i>s</i><sub class="lower-index">1</sub></span> describes a group of soldiers <span class="tex-span">1</span> through <span class="tex-span"><i>k</i></span> ("<span class="tex-font-style-tt">YES</span>" if the group is effective, and "<span class="tex-font-style-tt">NO</span>" otherwise). </li><li> The string <span class="tex-span"><i>s</i><sub class="lower-index">2</sub></span> describes a group of soldiers <span class="tex-span">2</span> through <span class="tex-span"><i>k</i> + 1</span>. </li><li> And so on, till the string <span class="tex-span"><i>s</i><sub class="lower-index"><i>n</i> - <i>k</i> + 1</sub></span> that describes a group of soldiers <span class="tex-span"><i>n</i> - <i>k</i> + 1</span> through <span class="tex-span"><i>n</i></span>. </li></ul><p>Your task is to find possible names of <span class="tex-span"><i>n</i></span> soldiers. Names should match the stolen notes. Each name should be a string that consists of between <span class="tex-span">1</span> and <span class="tex-span">10</span> English letters, inclusive. The first letter should be uppercase, and all other letters should be lowercase. Names don't have to be existing names — it's allowed to print "<span class="tex-font-style-tt">Xyzzzdj</span>" or "<span class="tex-font-style-tt">T</span>" for example.</p><p>Find and print any solution. It can be proved that there always exists at least one solution.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>k</i></span> (<span class="tex-span">2 ≤ <i>k</i> ≤ <i>n</i> ≤ 50</span>) — the number of soldiers and the size of a group respectively.</p><p>The second line contains <span class="tex-span"><i>n</i> - <i>k</i> + 1</span> strings <span class="tex-span"><i>s</i><sub class="lower-index">1</sub>, <i>s</i><sub class="lower-index">2</sub>, ..., <i>s</i><sub class="lower-index"><i>n</i> - <i>k</i> + 1</sub></span>. The string <span class="tex-span"><i>s</i><sub class="lower-index"><i>i</i></sub></span> is "<span class="tex-font-style-tt">YES</span>" if the group of soldiers <span class="tex-span"><i>i</i></span> through <span class="tex-span"><i>i</i> + <i>k</i> - 1</span> is effective, and "<span class="tex-font-style-tt">NO</span>" otherwise.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Find any solution satisfying all given conditions. In one line print <span class="tex-span"><i>n</i></span> space-separated strings, denoting possible names of soldiers in the order. The first letter of each name should be uppercase, while the other letters should be lowercase. Each name should contain English letters only and has length from <span class="tex-span">1</span> to <span class="tex-span">10</span>.</p><p>If there are multiple valid solutions, 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>8 3<br />NO NO YES YES YES NO<br /></pre></div><div class="output"><div class="title">Output</div><pre>Adam Bob Bob Cpqepqwer Limak Adam Bob Adam</pre></div><div class="input"><div class="title">Input</div><pre>9 8<br />YES NO<br /></pre></div><div class="output"><div class="title">Output</div><pre>R Q Ccccccccc Ccocc Ccc So Strong Samples Ccc</pre></div><div class="input"><div class="title">Input</div><pre>3 2<br />NO NO<br /></pre></div><div class="output"><div class="title">Output</div><pre>Na Na Na</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, there are <span class="tex-span">8</span> soldiers. For every <span class="tex-span">3</span> consecutive ones we know whether they would be an effective group. Let's analyze the provided sample output:</p><ul> <li> First three soldiers (i.e. Adam, Bob, Bob) wouldn't be an effective group because there are two Bobs. Indeed, the string <span class="tex-span"><i>s</i><sub class="lower-index">1</sub></span> is "<span class="tex-font-style-tt">NO</span>". </li><li> Soldiers <span class="tex-span">2</span> through <span class="tex-span">4</span> (Bob, Bob, Cpqepqwer) wouldn't be effective either, and the string <span class="tex-span"><i>s</i><sub class="lower-index">2</sub></span> is "<span class="tex-font-style-tt">NO</span>". </li><li> Soldiers <span class="tex-span">3</span> through <span class="tex-span">5</span> (Bob, Cpqepqwer, Limak) would be effective, and the string <span class="tex-span"><i>s</i><sub class="lower-index">3</sub></span> is "<span class="tex-font-style-tt">YES</span>". </li><li> ..., </li><li> Soldiers <span class="tex-span">6</span> through <span class="tex-span">8</span> (Adam, Bob, Adam) wouldn't be effective, and the string <span class="tex-span"><i>s</i><sub class="lower-index">6</sub></span> is "<span class="tex-font-style-tt">NO</span>". </li></ul></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_efd5ea5e92f60da5e871ebc32977ed8057f3cfe2">
|
||
<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. Bear and Tree Jumps</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>A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.</p><p>Limak is a little polar bear. He lives in a tree that consists of <span class="tex-span"><i>n</i></span> vertices, numbered <span class="tex-span">1</span> through <span class="tex-span"><i>n</i></span>.</p><p>Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most <span class="tex-span"><i>k</i></span>.</p><p>For a pair of vertices <span class="tex-span">(<i>s</i>, <i>t</i>)</span> we define <span class="tex-span"><i>f</i>(<i>s</i>, <i>t</i>)</span> as the minimum number of jumps Limak needs to get from <span class="tex-span"><i>s</i></span> to <span class="tex-span"><i>t</i></span>. Your task is to find the sum of <span class="tex-span"><i>f</i>(<i>s</i>, <i>t</i>)</span> over all pairs of vertices <span class="tex-span">(<i>s</i>, <i>t</i>)</span> such that <span class="tex-span"><i>s</i> < <i>t</i></span>.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>k</i></span> (<span class="tex-span">2 ≤ <i>n</i> ≤ 200 000</span>, <span class="tex-span">1 ≤ <i>k</i> ≤ 5</span>) — the number of vertices in the tree and the maximum allowed jump distance respectively.</p><p>The next <span class="tex-span"><i>n</i> - 1</span> lines describe edges in the tree. The <span class="tex-span"><i>i</i></span>-th of those lines contains two integers <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>b</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>b</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>) — the indices on vertices connected with <span class="tex-span"><i>i</i></span>-th edge.</p><p>It's guaranteed that the given edges form a tree.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer, denoting the sum of <span class="tex-span"><i>f</i>(<i>s</i>, <i>t</i>)</span> over all pairs of vertices <span class="tex-span">(<i>s</i>, <i>t</i>)</span> such that <span class="tex-span"><i>s</i> < <i>t</i></span>.</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 2<br />1 2<br />1 3<br />2 4<br />2 5<br />4 6<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>13 3<br />1 2<br />3 2<br />4 2<br />5 2<br />3 6<br />10 6<br />6 7<br />6 13<br />5 8<br />5 9<br />9 11<br />11 12<br /></pre></div><div class="output"><div class="title">Output</div><pre>114<br /></pre></div><div class="input"><div class="title">Input</div><pre>3 5<br />2 1<br />3 1<br /></pre></div><div class="output"><div class="title">Output</div><pre>3<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first sample, the given tree has <span class="tex-span">6</span> vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most <span class="tex-span">2</span>. For example, from the vertex <span class="tex-span">5</span> he can jump to any of vertices: <span class="tex-span">1</span>, <span class="tex-span">2</span> and <span class="tex-span">4</span> (well, he can also jump to the vertex <span class="tex-span">5</span> itself).</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/2f64f096f9b26ecb178744d255b0b317185ae82b.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center><p>There are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/c0295201207e28a36e641d8cf599f45986059e71.png" style="max-width: 100.0%;max-height: 100.0%;" /> pairs of vertices <span class="tex-span">(<i>s</i>, <i>t</i>)</span> such that <span class="tex-span"><i>s</i> < <i>t</i></span>. For <span class="tex-span">5</span> of those pairs Limak would need two jumps: <span class="tex-span">(1, 6), (3, 4), (3, 5), (3, 6), (5, 6)</span>. For other <span class="tex-span">10</span> pairs one jump is enough. So, the answer is <span class="tex-span">5·2 + 10·1 = 20</span>.</p><p>In the third sample, Limak can jump between every two vertices directly. There are <span class="tex-span">3</span> pairs of vertices <span class="tex-span">(<i>s</i> < <i>t</i>)</span>, so the answer is <span class="tex-span">3·1 = 3</span>.</p></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: 1em;"
|
||
>
|
||
|
||
|
||
<div class="problemindexholder" problemindex="E" data-uuid="ps_121e4c40dc78bf0e69fd33df864b1cfd9eca9a3a">
|
||
<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. Bear and Company</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>Bear Limak prepares problems for a programming competition. Of course, it would be unprofessional to mention the sponsor name in the statement. Limak takes it seriously and he is going to change some words. To make it still possible to read, he will try to modify each word as little as possible.</p><p>Limak has a string <span class="tex-span"><i>s</i></span> that consists of uppercase English letters. In one move he can swap two <span class="tex-font-style-bf">adjacent</span> letters of the string. For example, he can transform a string "<span class="tex-font-style-tt">ABBC</span>" into "<span class="tex-font-style-tt">BABC</span>" or "<span class="tex-font-style-tt">ABCB</span>" in one move.</p><p>Limak wants to obtain a string without a substring "<span class="tex-font-style-tt">VK</span>" (i.e. there should be no letter '<span class="tex-font-style-tt">V</span>' immediately followed by letter '<span class="tex-font-style-tt">K</span>'). It can be easily proved that it's possible for any initial string <span class="tex-span"><i>s</i></span>.</p><p>What is the minimum possible number of moves Limak can do?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains an integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 75</span>) — the length of the string.</p><p>The second line contains a string <span class="tex-span"><i>s</i></span>, consisting of uppercase English letters. The length of the string is equal to <span class="tex-span"><i>n</i></span>.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print one integer, denoting the minimum possible number of moves Limak can do, in order to obtain a string without a substring "<span class="tex-font-style-tt">VK</span>".</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 />VKVK<br /></pre></div><div class="output"><div class="title">Output</div><pre>3<br /></pre></div><div class="input"><div class="title">Input</div><pre>5<br />BVVKV<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>7<br />VVKEVKK<br /></pre></div><div class="output"><div class="title">Output</div><pre>3<br /></pre></div><div class="input"><div class="title">Input</div><pre>20<br />VKVKVVVKVOVKVQKKKVVK<br /></pre></div><div class="output"><div class="title">Output</div><pre>8<br /></pre></div><div class="input"><div class="title">Input</div><pre>5<br />LIMAK<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 initial string is "<span class="tex-font-style-tt">VKVK</span>". The minimum possible number of moves is <span class="tex-span">3</span>. One optimal sequence of moves is:</p><ol><li> Swap two last letters. The string becomes "<span class="tex-font-style-tt">VKKV</span>".</li><li> Swap first two letters. The string becomes "<span class="tex-font-style-tt">KVKV</span>".</li><li> Swap the second and the third letter. The string becomes "<span class="tex-font-style-tt">KKVV</span>". Indeed, this string doesn't have a substring "<span class="tex-font-style-tt">VK</span>".</li></ol><p>In the second sample, there are two optimal sequences of moves. One is "<span class="tex-font-style-tt">BVVKV</span>"<span class="tex-span"> → </span>"<span class="tex-font-style-tt">VBVKV</span>"<span class="tex-span"> → </span>"<span class="tex-font-style-tt">VVBKV</span>". The other is "<span class="tex-font-style-tt">BVVKV</span>"<span class="tex-span"> → </span>"<span class="tex-font-style-tt">BVKVV</span>"<span class="tex-span"> → </span>"<span class="tex-font-style-tt">BKVVV</span>".</p><p>In the fifth sample, no swaps are necessary.</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>
|
||
|
||
<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:'7e47c062bccd4137',m:'eYKvePhWAJQGhbiHujrjiFVmd9cCHO7SfDM6EYqS5VY-1688981043-0-ARz1vI52LhkIa3OmHVL7Xaa3Y2ATwWaaPQ/toHJYqjlq'};_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>
|