mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-09-16 15:46:56 +02:00
1035 lines
60 KiB
HTML
1035 lines
60 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="3c3c7bca397c50607911f55c0c18b4f8"/>
|
||
<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="h2">
|
||
<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/27731/css/font-awesome.min.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/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/27731/css/prettify.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/clear.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/ttypography.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/problem-statement.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/second-level-menu.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/roundbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/datatable.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/table-form.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/topic.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/jquery.jgrowl.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/facebox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/jquery.wysiwyg.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/jquery.autocomplete.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/codeforces.datepick.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/colorbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/jquery.drafts.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/css/community.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/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/27731/js/prettify/prettify.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/moment-with-locales.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/pushstream.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.easing.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.lavalamp.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.jgrowl.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.swipe.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.hotkeys.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/facebox.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.wysiwyg.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/controls/wysiwyg.colorpicker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/controls/wysiwyg.table.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/controls/wysiwyg.image.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/controls/wysiwyg.link.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.autocomplete.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.datepick.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.ie6blocker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.colorbox-min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.ba-bbq.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/jquery.drafts.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/clipboard.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/autosize.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/sjcl.js"></script>
|
||
<script type="text/javascript" src="/scripts/a61a038b2c1ac31d2efeffe05ea088a2/en/codeforces-options.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/codeforces.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/EventCatcher.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/preparedVerdictFormats-en.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/js/confetti.min.js"></script>
|
||
<!--/CombineResourcesFilter-->
|
||
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/markitup/skins/markitup/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/27731/markitup/sets/markdown/style.css" type="text/css" charset="utf-8" />
|
||
|
||
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/markitup/jquery.markitup.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/27731/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='3c3c7bca397c50607911f55c0c18b4f8'> </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/50788/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/50788/images/flags/24/gb.png" title="In English" alt="In English"/></a>
|
||
<a href="?locale=ru"><img src="//codeforces.org/s/50788/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 304 (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_3649a41323b6bb0d978e26cc0025cb7edee6c42f">
|
||
<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. Soldier and Bananas</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>A soldier wants to buy <span class="tex-span"><i>w</i></span> bananas in the shop. He has to pay <span class="tex-span"><i>k</i></span> dollars for the first banana, <span class="tex-span">2<i>k</i></span> dollars for the second one and so on (in other words, he has to pay <span class="tex-span"><i>i</i>·<i>k</i></span> dollars for the <span class="tex-span"><i>i</i></span>-th banana). </p><p>He has <span class="tex-span"><i>n</i></span> dollars. How many dollars does he have to borrow from his friend soldier to buy <span class="tex-span"><i>w</i></span> bananas?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains three positive integers <span class="tex-span"><i>k</i>, <i>n</i>, <i>w</i></span> (<span class="tex-span">1 ≤ <i>k</i>, <i>w</i> ≤ 1000</span>, <span class="tex-span">0 ≤ <i>n</i> ≤ 10<sup class="upper-index">9</sup></span>), the cost of the first banana, initial number of dollars the soldier has and number of bananas he wants. </p></div><div class="output-specification"><div class="section-title">Output</div><p>Output one integer — the amount of dollars that the soldier must borrow from his friend. If he doesn't have to borrow money, output <span class="tex-span">0</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>3 17 4<br /></pre></div><div class="output"><div class="title">Output</div><pre>13</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/50788");
|
||
$("#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_d55b4b515a92da5926e4977e6670e78a1e7d466d">
|
||
<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. Soldier and Badges</div><div class="time-limit"><div class="property-title">time limit per test</div>3 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Colonel has <span class="tex-span"><i>n</i></span> badges. He wants to give one badge to every of his <span class="tex-span"><i>n</i></span> soldiers. Each badge has a <span class="tex-font-style-it">coolness factor</span>, which shows how much it's owner reached. Coolness factor can be increased by one for the cost of one coin. </p><p>For every pair of soldiers one of them should get a badge with strictly higher factor than the second one. Exact values of their factors aren't important, they just need to have distinct factors. </p><p>Colonel knows, which soldier is supposed to get which badge initially, but there is a problem. Some of badges may have the same factor of coolness. Help him and calculate how much money has to be paid for making all badges have different factors of coolness.</p></div><div class="input-specification"><div class="section-title">Input</div><p>First line of input consists of one integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 3000</span>).</p><p>Next line consists of <span class="tex-span"><i>n</i></span> integers <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>), which stand for coolness factor of each badge.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Output single integer — minimum amount of coins the colonel has to pay.</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 />1 3 1 4<br /></pre></div><div class="output"><div class="title">Output</div><pre>1</pre></div><div class="input"><div class="title">Input</div><pre>5<br />1 2 3 2 5<br /></pre></div><div class="output"><div class="title">Output</div><pre>2</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In first sample test we can increase factor of first badge by <span class="tex-span">1</span>.</p><p>In second sample test we can increase factors of the second and the third badge by <span class="tex-span">1</span>.</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/50788");
|
||
$("#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_f0dff181c4d8a9ba7e5cbaca5982ed1eee23254f">
|
||
<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. Soldier and Cards</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>Two bored soldiers are playing card war. Their card deck consists of exactly <span class="tex-span"><i>n</i></span> cards, numbered from <span class="tex-span">1</span> to <span class="tex-span"><i>n</i></span>, <span class="tex-font-style-bf">all values are different</span>. They divide cards between them in some manner, it's possible that they have different number of cards. Then they play a "war"-like card game. </p><p>The rules are following. On each turn a <span class="tex-font-style-it">fight</span> happens. Each of them picks card from the top of his stack and puts on the table. The one whose card value is bigger wins this <span class="tex-font-style-it">fight</span> and takes both cards from the table to the bottom of his stack. More precisely, he first takes his opponent's card and puts to the bottom of his stack, and then he puts his card to the bottom of his stack. If after some turn one of the player's stack becomes empty, he loses and the other one wins. </p><p>You have to calculate how many <span class="tex-font-style-it">fights</span> will happen and who will win the game, or state that game won't end.</p></div><div class="input-specification"><div class="section-title">Input</div><p>First line contains a single integer <span class="tex-span"><i>n</i></span> (<span class="tex-span">2 ≤ <i>n</i> ≤ 10</span>), the number of cards.</p><p>Second line contains integer <span class="tex-span"><i>k</i><sub class="lower-index">1</sub></span> (<span class="tex-span">1 ≤ <i>k</i><sub class="lower-index">1</sub> ≤ <i>n</i> - 1</span>), the number of the first soldier's cards. Then follow <span class="tex-span"><i>k</i><sub class="lower-index">1</sub></span> integers that are the values on the first soldier's cards, from top to bottom of his stack.</p><p>Third line contains integer <span class="tex-span"><i>k</i><sub class="lower-index">2</sub></span> (<span class="tex-span"><i>k</i><sub class="lower-index">1</sub> + <i>k</i><sub class="lower-index">2</sub> = <i>n</i></span>), the number of the second soldier's cards. Then follow <span class="tex-span"><i>k</i><sub class="lower-index">2</sub></span> integers that are the values on the second soldier's cards, from top to bottom of his stack.</p><p><span class="tex-font-style-bf">All card values are different.</span></p></div><div class="output-specification"><div class="section-title">Output</div><p>If somebody wins in this game, print <span class="tex-span">2</span> integers where the first one stands for the number of <span class="tex-font-style-it">fights</span> before end of game and the second one is <span class="tex-span">1</span> or <span class="tex-span">2</span> showing which player has won.</p><p>If the game won't end and will continue forever output <span class="tex-span"> - 1</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 />2 1 3<br />2 4 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>6 2</pre></div><div class="input"><div class="title">Input</div><pre>3<br />1 2<br />2 1 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>-1</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>First sample: </p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/290aae4aaf31a0db96a319a356dc896e0ae7573a.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center><p>Second sample: </p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/64d6acc04bdd6ae24b03493ff0ddc4bbcf0750d9.png" style="max-width: 100.0%;max-height: 100.0%;" /> </center></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/50788");
|
||
$("#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_fb57dc7ce817af20ffac2ac629eda922ca124b85">
|
||
<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. Soldier and Number Game</div><div class="time-limit"><div class="property-title">time limit per test</div>3 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>Two soldiers are playing a game. At the beginning first of them chooses a positive integer <span class="tex-span"><i>n</i></span> and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer <span class="tex-span"><i>x</i> > 1</span>, such that <span class="tex-span"><i>n</i></span> is divisible by <span class="tex-span"><i>x</i></span> and replacing <span class="tex-span"><i>n</i></span> with <span class="tex-span"><i>n</i> / <i>x</i></span>. When <span class="tex-span"><i>n</i></span> becomes equal to <span class="tex-span">1</span> and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.</p><p>To make the game more interesting, first soldier chooses <span class="tex-span"><i>n</i></span> of form <span class="tex-span"><i>a</i>! / <i>b</i>!</span> for some positive integer <span class="tex-span"><i>a</i></span> and <span class="tex-span"><i>b</i></span> (<span class="tex-span"><i>a</i> ≥ <i>b</i></span>). Here by <span class="tex-span"><i>k</i>!</span> we denote the <span class="tex-font-style-it">factorial</span> of <span class="tex-span"><i>k</i></span> that is defined as a product of all positive integers not large than <span class="tex-span"><i>k</i></span>.</p><p>What is the maximum possible score of the second soldier?</p></div><div class="input-specification"><div class="section-title">Input</div><p>First line of input consists of single integer <span class="tex-span"><i>t</i></span> (<span class="tex-span">1 ≤ <i>t</i> ≤ 1 000 000</span>) denoting number of games soldiers play.</p><p>Then follow <span class="tex-span"><i>t</i></span> lines, each contains pair of integers <span class="tex-span"><i>a</i></span> and <span class="tex-span"><i>b</i></span> (<span class="tex-span">1 ≤ <i>b</i> ≤ <i>a</i> ≤ 5 000 000</span>) defining the value of <span class="tex-span"><i>n</i></span> for a game.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each game output a maximum score that the second soldier can get.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>2<br />3 1<br />6 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>2<br />5<br /></pre></div></div></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/50788");
|
||
$("#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_3f0ff2c70fedf1924004289a712e9c4b73f28e43">
|
||
<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. Soldier and Traveling</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 country there are <span class="tex-span"><i>n</i></span> cities and <span class="tex-span"><i>m</i></span> bidirectional roads between them. Each city has an army. Army of the <span class="tex-span"><i>i</i></span>-th city consists of <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> soldiers. Now soldiers roam. After roaming each soldier has to either stay in his city or to go to the one of neighboring cities by at <span class="tex-font-style-bf">moving along at most one road</span>.</p><p>Check if is it possible that after roaming there will be exactly <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> soldiers in the <span class="tex-span"><i>i</i></span>-th city.</p></div><div class="input-specification"><div class="section-title">Input</div><p>First line of input consists of 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> ≤ 100</span>, <span class="tex-span">0 ≤ <i>m</i> ≤ 200</span>).</p><p>Next line contains <span class="tex-span"><i>n</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>n</i></sub></span> (<span class="tex-span">0 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub> ≤ 100</span>).</p><p>Next line contains <span class="tex-span"><i>n</i></span> integers <span class="tex-span"><i>b</i><sub class="lower-index">1</sub>, <i>b</i><sub class="lower-index">2</sub>, ..., <i>b</i><sub class="lower-index"><i>n</i></sub></span> (<span class="tex-span">0 ≤ <i>b</i><sub class="lower-index"><i>i</i></sub> ≤ 100</span>).</p><p>Then <span class="tex-span"><i>m</i></span> lines follow, each of them consists of two integers <span class="tex-span"><i>p</i></span> and <span class="tex-span"><i>q</i></span> (<span class="tex-span">1 ≤ <i>p</i>, <i>q</i> ≤ <i>n</i></span>, <span class="tex-span"><i>p</i> ≠ <i>q</i></span>) denoting that there is an undirected road between cities <span class="tex-span"><i>p</i></span> and <span class="tex-span"><i>q</i></span>. </p><p>It is guaranteed that there is at most one road between each pair of cities.</p></div><div class="output-specification"><div class="section-title">Output</div><p>If the conditions can not be met output single word "<span class="tex-font-style-tt">NO</span>".</p><p>Otherwise output word "<span class="tex-font-style-tt">YES</span>" and then <span class="tex-span"><i>n</i></span> lines, each of them consisting of <span class="tex-span"><i>n</i></span> integers. Number in the <span class="tex-span"><i>i</i></span>-th line in the <span class="tex-span"><i>j</i></span>-th column should denote how many soldiers should road from city <span class="tex-span"><i>i</i></span> to city <span class="tex-span"><i>j</i></span> (if <span class="tex-span"><i>i</i> ≠ <i>j</i></span>) or how many soldiers should stay in city <span class="tex-span"><i>i</i></span> (if <span class="tex-span"><i>i</i> = <i>j</i></span>).</p><p>If there are several possible answers you may output any of them.</p></div><div class="sample-tests"><div class="section-title">Examples</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>4 4<br />1 2 6 3<br />3 5 3 1<br />1 2<br />2 3<br />3 4<br />4 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>YES<br />1 0 0 0 <br />2 0 0 0 <br />0 5 1 0 <br />0 0 2 1 <br /></pre></div><div class="input"><div class="title">Input</div><pre>2 0<br />1 2<br />2 1<br /></pre></div><div class="output"><div class="title">Output</div><pre>NO</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/50788");
|
||
$("#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-50788.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:'7e47d0721973b359',m:'F6VjiD5GnmwRdE_n_zhyLKuYxtDwpwtNu0KcQyZwn.M-1688981701-0-AeovY+Gzqocx4T3FZqumNiZKB5o9GIJNV1TCNBDAZgeE'};_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>
|