mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-09-19 17:16:55 +02:00
1035 lines
64 KiB
HTML
1035 lines
64 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="ae204dff4eb79ba50ee56efba5d33b4e"/>
|
||
<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/19903/css/font-awesome.min.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/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/19903/css/prettify.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/clear.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/ttypography.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/problem-statement.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/second-level-menu.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/roundbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/datatable.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/table-form.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/topic.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/jquery.jgrowl.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/facebox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/jquery.wysiwyg.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/jquery.autocomplete.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/codeforces.datepick.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/colorbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/jquery.drafts.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/css/community.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/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/19903/js/prettify/prettify.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/moment-with-locales.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/pushstream.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.easing.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.lavalamp.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.jgrowl.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.swipe.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.hotkeys.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/facebox.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.wysiwyg.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/controls/wysiwyg.colorpicker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/controls/wysiwyg.table.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/controls/wysiwyg.image.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/controls/wysiwyg.link.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.autocomplete.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.datepick.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.ie6blocker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.colorbox-min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.ba-bbq.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/jquery.drafts.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/clipboard.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/autosize.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/sjcl.js"></script>
|
||
<script type="text/javascript" src="/scripts/3dccf1f9f8cb4969b151d97264ecfd48/en/codeforces-options.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/codeforces.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/EventCatcher.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/preparedVerdictFormats-en.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/js/confetti.min.js"></script>
|
||
<!--/CombineResourcesFilter-->
|
||
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/markitup/skins/markitup/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/19903/markitup/sets/markdown/style.css" type="text/css" charset="utf-8" />
|
||
|
||
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/markitup/jquery.markitup.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/19903/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='ae204dff4eb79ba50ee56efba5d33b4e'> </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/34323/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/34323/images/flags/24/gb.png" title="In English" alt="In English"/></a>
|
||
<a href="?locale=ru"><img src="//codeforces.org/s/34323/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 197 (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_cf4d9170f9a9a109549df2f821a3c410687a5e97">
|
||
<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. Helpful Maths</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>Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation.</p><p>The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that isn't enough for Xenia. She is only beginning to count, so she can calculate a sum only if the summands follow in non-decreasing order. For example, she can't calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3.</p><p>You've got the sum that was written on the board. Rearrange the summans and print the sum in such a way that Xenia can calculate the sum.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a non-empty string <span class="tex-span"><i>s</i></span> — the sum Xenia needs to count. String <span class="tex-span"><i>s</i></span> contains no spaces. It only contains digits and characters "<span class="tex-font-style-tt">+</span>". Besides, string <span class="tex-span"><i>s</i></span> is a correct sum of numbers 1, 2 and 3. String <span class="tex-span"><i>s</i></span> is at most 100 characters long.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print the new sum that Xenia can count.</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>3+2+1<br /></pre></div><div class="output"><div class="title">Output</div><pre>1+2+3<br /></pre></div><div class="input"><div class="title">Input</div><pre>1+1+3+1+3<br /></pre></div><div class="output"><div class="title">Output</div><pre>1+1+1+3+3<br /></pre></div><div class="input"><div class="title">Input</div><pre>2<br /></pre></div><div class="output"><div class="title">Output</div><pre>2<br /></pre></div></div></div></div></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/34323");
|
||
$("#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_a2af5cad2c836a87dd32ba339a24a525aeacd059">
|
||
<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. Xenia and Ringroad</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>Xenia lives in a city that has <span class="tex-span"><i>n</i></span> houses built along the main ringroad. The ringroad houses are numbered 1 through <span class="tex-span"><i>n</i></span> in the clockwise order. The ringroad traffic is one way and also is clockwise.</p><p>Xenia has recently moved into the ringroad house number 1. As a result, she's got <span class="tex-span"><i>m</i></span> things to do. In order to complete the <span class="tex-span"><i>i</i></span>-th task, she needs to be in the house number <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and complete all tasks with numbers less than <span class="tex-span"><i>i</i></span>. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>m</i></span> <span class="tex-span">(2 ≤ <i>n</i> ≤ 10<sup class="upper-index">5</sup>, 1 ≤ <i>m</i> ≤ 10<sup class="upper-index">5</sup>)</span>. The second line contains <span class="tex-span"><i>m</i></span> integers <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>m</i></sub></span> <span class="tex-span">(1 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i>)</span>. Note that Xenia can have multiple consecutive tasks in one house.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print a single integer — the time Xenia needs to complete all tasks.</p><p>Please, do not use the <span class="tex-font-style-tt">%lld</span> specifier to read or write 64-bit integers in С++. It is preferred to use the <span class="tex-font-style-tt">cin</span>, <span class="tex-font-style-tt">cout</span> streams or the <span class="tex-font-style-tt">%I64d</span> specifier.</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 />3 2 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>6<br /></pre></div><div class="input"><div class="title">Input</div><pre>4 3<br />2 3 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>2<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first test example the sequence of Xenia's moves along the ringroad looks as follows: <span class="tex-span">1 → 2 → 3 → 4 → 1 → 2 → 3</span>. This is optimal sequence. So, she needs 6 time units.</p></div></div></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/34323");
|
||
$("#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_e3fdb6df78cc169c706ae04187420223165a228c">
|
||
<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. Xenia and Weights</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>Xenia has a set of weights and pan scales. Each weight has an integer weight from 1 to 10 kilos. Xenia is going to play with scales and weights a little. For this, she puts weights on the scalepans, one by one. The first weight goes on the left scalepan, the second weight goes on the right scalepan, the third one goes on the left scalepan, the fourth one goes on the right scalepan and so on. Xenia wants to put the total of <span class="tex-span"><i>m</i></span> weights on the scalepans.</p><p>Simply putting weights on the scales is not interesting, so Xenia has set some rules. First, she does not put on the scales two consecutive weights of the same weight. That is, the weight that goes <span class="tex-span"><i>i</i></span>-th should be different from the <span class="tex-span">(<i>i</i> + 1)</span>-th weight for any <span class="tex-span"><i>i</i></span> <span class="tex-span">(1 ≤ <i>i</i> < <i>m</i>)</span>. Second, every time Xenia puts a weight on some scalepan, she wants this scalepan to outweigh the other one. That is, the sum of the weights on the corresponding scalepan must be strictly greater than the sum on the other pan.</p><p>You are given all types of weights available for Xenia. You can assume that the girl has an infinite number of weights of each specified type. Your task is to help Xenia lay <span class="tex-span"><i>m</i></span> weights on the scales or to say that it can't be done.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a string consisting of exactly ten zeroes and ones: the <span class="tex-span"><i>i</i></span>-th <span class="tex-span">(<i>i</i> ≥ 1)</span> character in the line equals "<span class="tex-font-style-tt">1</span>" if Xenia has <span class="tex-span"><i>i</i></span> kilo weights, otherwise the character equals "<span class="tex-font-style-tt">0</span>". The second line contains integer <span class="tex-span"><i>m</i></span> <span class="tex-span">(1 ≤ <i>m</i> ≤ 1000)</span>.</p></div><div class="output-specification"><div class="section-title">Output</div><p>In the first line print "<span class="tex-font-style-tt">YES</span>", if there is a way to put <span class="tex-span"><i>m</i></span> weights on the scales by all rules. Otherwise, print in the first line "<span class="tex-font-style-tt">NO</span>". If you can put <span class="tex-span"><i>m</i></span> weights on the scales, then print in the next line <span class="tex-span"><i>m</i></span> integers — the weights' weights in the order you put them on the scales.</p><p>If there are multiple solutions, you can 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>0000000101<br />3<br /></pre></div><div class="output"><div class="title">Output</div><pre>YES<br />8 10 8<br /></pre></div><div class="input"><div class="title">Input</div><pre>1000000000<br />2<br /></pre></div><div class="output"><div class="title">Output</div><pre>NO<br /></pre></div></div></div></div></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/34323");
|
||
$("#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_7e75f00efca4038935fb486b1584e765177f3cc5">
|
||
<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. Xenia and Bit Operations</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>Xenia the beginner programmer has a sequence <span class="tex-span"><i>a</i></span>, consisting of <span class="tex-span">2<sup class="upper-index"><i>n</i></sup></span> non-negative integers: <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index">2<sup class="upper-index"><i>n</i></sup></sub></span>. Xenia is currently studying bit operations. To better understand how they work, Xenia decided to calculate some value <span class="tex-span"><i>v</i></span> for <span class="tex-span"><i>a</i></span>.</p><p>Namely, it takes several iterations to calculate value <span class="tex-span"><i>v</i></span>. At the first iteration, Xenia writes a new sequence <span class="tex-span"><i>a</i><sub class="lower-index">1</sub> <i>or</i> <i>a</i><sub class="lower-index">2</sub>, <i>a</i><sub class="lower-index">3</sub> <i>or</i> <i>a</i><sub class="lower-index">4</sub>, ..., <i>a</i><sub class="lower-index">2<sup class="upper-index"><i>n</i></sup> - 1</sub> <i>or</i> <i>a</i><sub class="lower-index">2<sup class="upper-index"><i>n</i></sup></sub></span>, consisting of <span class="tex-span">2<sup class="upper-index"><i>n</i> - 1</sup></span> elements. In other words, she writes down the bit-wise OR of adjacent elements of sequence <span class="tex-span"><i>a</i></span>. At the second iteration, Xenia writes the bitwise <span class="tex-font-style-bf">exclusive</span> OR of adjacent elements of the sequence obtained after the first iteration. At the third iteration Xenia writes the bitwise OR of the adjacent elements of the sequence obtained after the second iteration. And so on; the operations of bitwise exclusive OR and bitwise OR alternate. In the end, she obtains a sequence consisting of one element, and that element is <span class="tex-span"><i>v</i></span>.</p><p>Let's consider an example. Suppose that sequence <span class="tex-span"><i>a</i> = (1, 2, 3, 4)</span>. Then let's write down all the transformations <span class="tex-span">(1, 2, 3, 4)</span> <span class="tex-span"> → </span> <span class="tex-span">(1 <i>or</i> 2 = 3, 3 <i>or</i> 4 = 7)</span> <span class="tex-span"> → </span> <span class="tex-span">(3 <i>xor</i> 7 = 4)</span>. The result is <span class="tex-span"><i>v</i> = 4</span>.</p><p>You are given Xenia's initial sequence. But to calculate value <span class="tex-span"><i>v</i></span> for a given sequence would be too easy, so you are given additional <span class="tex-span"><i>m</i></span> queries. Each query is a pair of integers <span class="tex-span"><i>p</i>, <i>b</i></span>. Query <span class="tex-span"><i>p</i>, <i>b</i></span> means that you need to perform the assignment <span class="tex-span"><i>a</i><sub class="lower-index"><i>p</i></sub> = <i>b</i></span>. After each query, you need to print the new value <span class="tex-span"><i>v</i></span> for the new sequence <span class="tex-span"><i>a</i></span>.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>m</i></span> <span class="tex-span">(1 ≤ <i>n</i> ≤ 17, 1 ≤ <i>m</i> ≤ 10<sup class="upper-index">5</sup>)</span>. The next line contains <span class="tex-span">2<sup class="upper-index"><i>n</i></sup></span> integers <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index">2<sup class="upper-index"><i>n</i></sup></sub></span> <span class="tex-span">(0 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> < 2<sup class="upper-index">30</sup>)</span>. Each of the next <span class="tex-span"><i>m</i></span> lines contains queries. The <span class="tex-span"><i>i</i></span>-th line contains integers <span class="tex-span"><i>p</i><sub class="lower-index"><i>i</i></sub>, <i>b</i><sub class="lower-index"><i>i</i></sub></span> <span class="tex-span">(1 ≤ <i>p</i><sub class="lower-index"><i>i</i></sub> ≤ 2<sup class="upper-index"><i>n</i></sup>, 0 ≤ <i>b</i><sub class="lower-index"><i>i</i></sub> < 2<sup class="upper-index">30</sup>)</span> — the <span class="tex-span"><i>i</i></span>-th query.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print <span class="tex-span"><i>m</i></span> integers — the <span class="tex-span"><i>i</i></span>-th integer denotes value <span class="tex-span"><i>v</i></span> for sequence <span class="tex-span"><i>a</i></span> after the <span class="tex-span"><i>i</i></span>-th query.</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 4<br />1 6 3 5<br />1 4<br />3 4<br />1 2<br />1 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>1<br />3<br />3<br />3<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>For more information on the bit operations, you can follow this link: <span class="tex-font-style-tt">http://en.wikipedia.org/wiki/Bitwise_operation</span></p></div></div></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/34323");
|
||
$("#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_2f85d85ecf436c049de44abe421920424ef981ba">
|
||
<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. Three Swaps</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>Xenia the horse breeder has <span class="tex-span"><i>n</i></span> <span class="tex-span">(<i>n</i> > 1)</span> horses that stand in a row. Each horse has its own unique number. Initially, the <span class="tex-span"><i>i</i></span>-th left horse has number <span class="tex-span"><i>i</i></span>. That is, the sequence of numbers of horses in a row looks as follows (from left to right): 1, 2, 3, <span class="tex-span">...</span>, <span class="tex-span"><i>n</i></span>.</p><p>Xenia trains horses before the performance. During the practice sessions, she consistently gives them commands. Each command is a pair of numbers <span class="tex-span"><i>l</i>, <i>r</i></span> <span class="tex-span">(1 ≤ <i>l</i> < <i>r</i> ≤ <i>n</i>)</span>. The command <span class="tex-span"><i>l</i>, <i>r</i></span> means that the horses that are on the <span class="tex-span"><i>l</i></span>-th, <span class="tex-span">(<i>l</i> + 1)</span>-th, <span class="tex-span">(<i>l</i> + 2)</span>-th, <span class="tex-span">...</span>, <span class="tex-span"><i>r</i></span>-th places from the left must be rearranged. The horses that initially stand on the <span class="tex-span"><i>l</i></span>-th and <span class="tex-span"><i>r</i></span>-th places will swap. The horses on the <span class="tex-span">(<i>l</i> + 1)</span>-th and <span class="tex-span">(<i>r</i> - 1)</span>-th places will swap. The horses on the <span class="tex-span">(<i>l</i> + 2)</span>-th and <span class="tex-span">(<i>r</i> - 2)</span>-th places will swap and so on. In other words, the horses that were on the segment <span class="tex-span">[<i>l</i>, <i>r</i>]</span> change their order to the reverse one.</p><p>For example, if Xenia commanded <span class="tex-span"><i>l</i> = 2, <i>r</i> = 5</span>, and the sequence of numbers of horses before the command looked as (2, 1, 3, 4, 5, 6), then after the command the sequence will be (2, 5, 4, 3, 1, 6).</p><p>We know that during the practice Xenia gave at most three commands of the described form. You have got the final sequence of numbers of horses by the end of the practice. Find what commands Xenia gave during the practice. Note that you do not need to minimize the number of commands in the solution, find any valid sequence of at most three commands.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains an integer <span class="tex-span"><i>n</i></span> <span class="tex-span">(2 ≤ <i>n</i> ≤ 1000)</span> — the number of horses in the row. The second line contains <span class="tex-span"><i>n</i></span> distinct integers <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>n</i></sub></span> <span class="tex-span">(1 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i>)</span>, where <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> is the number of the <span class="tex-span"><i>i</i></span>-th left horse in the row after the practice.</p></div><div class="output-specification"><div class="section-title">Output</div><p>The first line should contain integer <span class="tex-span"><i>k</i></span> <span class="tex-span">(0 ≤ <i>k</i> ≤ 3)</span> — the number of commads Xenia gave during the practice. In each of the next <span class="tex-span"><i>k</i></span> lines print two integers. In the <span class="tex-span"><i>i</i></span>-th line print numbers <span class="tex-span"><i>l</i><sub class="lower-index"><i>i</i></sub>, <i>r</i><sub class="lower-index"><i>i</i></sub></span> <span class="tex-span">(1 ≤ <i>l</i><sub class="lower-index"><i>i</i></sub> < <i>r</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i>)</span> — Xenia's <span class="tex-span"><i>i</i></span>-th command during the practice.</p><p>It is guaranteed that a solution exists. If there are several solutions, you are allowed to 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>5<br />1 4 3 2 5<br /></pre></div><div class="output"><div class="title">Output</div><pre>1<br />2 4<br /></pre></div><div class="input"><div class="title">Input</div><pre>6<br />2 1 4 3 6 5<br /></pre></div><div class="output"><div class="title">Output</div><pre>3<br />1 2<br />3 4<br />5 6<br /></pre></div></div></div></div></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/34323");
|
||
$("#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-34323.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:'7e43897a1e47b365',m:'V6PMnoPZksgzBGBxvPa7gM0TeV4kViAbgxE9_KFuHcA-1688936851-0-AY8/ACugG/2xMqFTcQm6mNIQKc7zfq5r+wQbEDcMM1rC'};_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>
|