mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-09-16 15:46:56 +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="a1c473fcd7c2fb023bb378a6d38e06d4"/>
|
||
<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='a1c473fcd7c2fb023bb378a6d38e06d4'> </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 Beta Round 47</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_d13030ecde43fed8ecf0117970d49fbf80fa55b9">
|
||
<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. Domino piling</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>You are given a rectangular board of <span class="tex-span"><i>M</i> × <i>N</i></span> squares. Also you are given an unlimited number of standard domino pieces of <span class="tex-span">2 × 1</span> squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:</p><p>1. Each domino completely covers two squares.</p><p>2. No two dominoes overlap.</p><p>3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.</p><p>Find the maximum number of dominoes, which can be placed under these restrictions.</p></div><div class="input-specification"><div class="section-title">Input</div><p>In a single line you are given two integers <span class="tex-span"><i>M</i></span> and <span class="tex-span"><i>N</i></span> — board sizes in squares (<span class="tex-span">1 ≤ <i>M</i> ≤ <i>N</i> ≤ 16</span>).</p></div><div class="output-specification"><div class="section-title">Output</div><p>Output one number — the maximal number of dominoes, which can be placed.</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 /></pre></div><div class="output"><div class="title">Output</div><pre>4<br /></pre></div><div class="input"><div class="title">Input</div><pre>3 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>4<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_f7f3f5c68c61e51c53dee95bb965df0b6d0dbdf4">
|
||
<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. Choosing Symbol Pairs</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>There is a given string <span class="tex-span"><i>S</i></span> consisting of <span class="tex-span"><i>N</i></span> symbols. Your task is to find the number of ordered pairs of integers <span class="tex-span"><i>i</i></span> and <span class="tex-span"><i>j</i></span> such that</p><p>1. <span class="tex-span">1 ≤ <i>i</i>, <i>j</i> ≤ <i>N</i></span></p><p>2. <span class="tex-span"><i>S</i>[<i>i</i>] = <i>S</i>[<i>j</i>]</span>, that is the <span class="tex-span"><i>i</i></span>-th symbol of string <span class="tex-span"><i>S</i></span> is equal to the <span class="tex-span"><i>j</i></span>-th.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The single input line contains <span class="tex-span"><i>S</i></span>, consisting of lowercase Latin letters and digits. It is guaranteed that string <span class="tex-span"><i>S</i></span> in not empty and its length does not exceed <span class="tex-span">10<sup class="upper-index">5</sup></span>.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print a single number which represents the number of pairs <span class="tex-span"><i>i</i></span> and <span class="tex-span"><i>j</i></span> with the needed property. Pairs <span class="tex-span">(<i>x</i>, <i>y</i>)</span> and <span class="tex-span">(<i>y</i>, <i>x</i>)</span> should be considered different, i.e. the ordered pairs 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>great10<br /></pre></div><div class="output"><div class="title">Output</div><pre>7<br /></pre></div><div class="input"><div class="title">Input</div><pre>aaaaaaaaaa<br /></pre></div><div class="output"><div class="title">Output</div><pre>100<br /></pre></div></div></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_77dae4fb934aa217d1e378073101f6f94c505865">
|
||
<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. Happy Farm 5</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>The Happy Farm 5 creators decided to invent the mechanism of cow grazing. The cows in the game are very slow and they move very slowly, it can even be considered that they stand still. However, carnivores should always be chased off them. </p><p>For that a young player Vasya decided to make the shepherd run round the cows along one and the same closed path. It is very important that the cows stayed strictly inside the area limited by the path, as otherwise some cows will sooner or later be eaten. To be absolutely sure in the cows' safety, Vasya wants the path completion time to be minimum.</p><p>The new game is launched for different devices, including mobile phones. That's why the developers decided to quit using the arithmetics with the floating decimal point and use only the arithmetics of integers. The cows and the shepherd in the game are represented as points on the plane with integer coordinates. The playing time is modeled by the turns. During every turn the shepherd can either stay where he stands or step in one of eight directions: horizontally, vertically, or diagonally. As the coordinates should always remain integer, then the length of a horizontal and vertical step is equal to <span class="tex-span">1</span>, and the length of a diagonal step is equal to <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/bfe16f27ebc966df6f10ba356a1547b6e7242dd7.png" style="max-width: 100.0%;max-height: 100.0%;" />. The cows do not move. You have to minimize the number of moves the shepherd needs to run round the whole herd.</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> which represents the number of cows in the herd (<span class="tex-span">1 ≤ <i>N</i> ≤ 10<sup class="upper-index">5</sup></span>). Each of the next <span class="tex-span"><i>N</i></span> lines contains two integers <span class="tex-span"><i>X</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>Y</i><sub class="lower-index"><i>i</i></sub></span> which represent the coordinates of one cow of (<span class="tex-span">|<i>X</i><sub class="lower-index"><i>i</i></sub>|, |<i>Y</i><sub class="lower-index"><i>i</i></sub>| ≤ 10<sup class="upper-index">6</sup></span>). Several cows can stand on one point.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print the single number — the minimum number of moves in the sought path.</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 1<br />5 1<br />5 3<br />1 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>16<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>Picture for the example test: The coordinate grid is painted grey, the coordinates axes are painted black, the cows are painted red and the sought route is painted green.</p><center> <img class="tex-graphics" height="113px" src="https://espresso.codeforces.com/fc4ddd52fc95b53d2e72248c928d0d62dea6c1db.png" style="max-width: 100.0%;max-height: 100.0%;" width="151px" /> </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/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_d601140f4a93d1fcfec74a939c0bd827c64e6061">
|
||
<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. Bombing</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>The commanding officers decided to drop a nuclear bomb on the enemy's forces. You are ordered to determine the power of the warhead that needs to be used.</p><p>The enemy has <span class="tex-span"><i>N</i></span> strategically important objects. Their positions are known due to the intelligence service. The aim of the strike is to deactivate at least <span class="tex-span"><i>K</i></span> important objects of the enemy. The bombing impact point is already determined and has coordinates of <span class="tex-span">[<i>X</i><sub class="lower-index">0</sub>; <i>Y</i><sub class="lower-index">0</sub>]</span>.</p><p>The nuclear warhead is marked by the estimated impact radius <span class="tex-span"><i>R</i> ≥ 0</span>. All the buildings that are located closer than <span class="tex-span"><i>R</i></span> to the bombing epicentre will be destroyed. All the buildings that are located further than <span class="tex-span"><i>R</i></span> from the epicentre, can also be deactivated with some degree of probability. Let's assume that <span class="tex-span"><i>D</i></span> is the distance between a building and the epicentre. This building's deactivation probability <span class="tex-span"><i>P</i>(<i>D</i>, <i>R</i>)</span> is calculated according to the following formula: </p><center class="tex-equation"><img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6a47db42daca2851e527aeb9e0299a54dbdbb14e.png" style="max-width: 100.0%;max-height: 100.0%;" /></center> We should regard <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/41aacee1a62f5625b89e49dc310098043aaab520.png" style="max-width: 100.0%;max-height: 100.0%;" /> as <span class="tex-span"><i>e</i><sup class="upper-index"><i>a</i></sup></span>, where <span class="tex-span"><i>e</i> ≈ 2.7182818284590452353602874713527</span><p>If the estimated impact radius of the warhead is equal to zero, then all the buildings located in the impact point will be completely demolished and all the rest of important objects will not be damaged.</p><p>The commanding officers want the probability of failing the task to be no more than <span class="tex-span">ε</span>. Nuclear warheads are too expensive a luxury, that's why you have to minimise the estimated impact radius of the warhead. </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> which represents the number of the enemy's objects (<span class="tex-span">1 ≤ <i>N</i> ≤ 100</span>). The second line contains two integers: <span class="tex-span"><i>K</i></span> is the required number of deactivated objects, and <span class="tex-span">ε</span> is the maximally permitted probability of not completing the task, given in per mils (<span class="tex-span">1 ≤ <i>K</i> ≤ <i>N</i></span>, <span class="tex-span">1 ≤ ε ≤ 999</span>). The third line contains <span class="tex-span"><i>X</i><sub class="lower-index">0</sub></span> and <span class="tex-span"><i>Y</i><sub class="lower-index">0</sub></span> which are the coordinates of the strike impact point. The next <span class="tex-span"><i>N</i></span> lines contain two numbers <span class="tex-span"><i>X</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>Y</i><sub class="lower-index"><i>i</i></sub></span> each which are the coordinates of every strategically important object. All the coordinates are integer, their absolute values do not exceed <span class="tex-span">1000</span>.</p><p>Let us remind you that there are a thousand per mils in unity (number one).</p><p>There can be several objects in one point.</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print the sought estimated impact radius of the warhead. The absolute or relative measure of the inaccuracy of your answer should not exceed <span class="tex-span">10<sup class="upper-index"> - 6</sup></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>1<br />1 500<br />5 5<br />1 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>3.84257761518762740<br /></pre></div><div class="input"><div class="title">Input</div><pre>5<br />3 100<br />0 0<br />3 4<br />60 70<br />100 100<br />10 10<br />5 12<br /></pre></div><div class="output"><div class="title">Output</div><pre>13.45126176453737600<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/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_784496a6ea8029d1910e9cf632be332a199c94bd">
|
||
<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. Square Equation Roots</div><div class="time-limit"><div class="property-title">time limit per test</div>5 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>A schoolboy Petya studies square equations. The equations that are included in the school curriculum, usually look simple: </p><center class="tex-equation"><span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>bx</i> + <i>c</i> = 0</span></center> where <span class="tex-span"><i>b</i></span>, <span class="tex-span"><i>c</i></span> are natural numbers.<p>Petya noticed that some equations have two real roots, some of them have only one root and some equations don't have real roots at all. Moreover it turned out that several different square equations can have a common root.</p><p>Petya is interested in how many different real roots have all the equations of the type described above for all the possible pairs of numbers <span class="tex-span"><i>b</i></span> and <span class="tex-span"><i>c</i></span> such that <span class="tex-span">1 ≤ <i>b</i> ≤ <i>n</i></span>, <span class="tex-span">1 ≤ <i>c</i> ≤ <i>m</i></span>. Help Petya find that number.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The single 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>, <i>m</i> ≤ 5000000</span>).</p></div><div class="output-specification"><div class="section-title">Output</div><p>Print a single number which is the number of real roots of the described set of equations.</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 3<br /></pre></div><div class="output"><div class="title">Output</div><pre>12<br /></pre></div><div class="input"><div class="title">Input</div><pre>1 2<br /></pre></div><div class="output"><div class="title">Output</div><pre>1<br /></pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the second test from the statement the following equations are analysed:</p><p> <span class="tex-span"><i>b</i> = 1</span>, <span class="tex-span"><i>c</i> = 1</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>x</i> + 1 = 0</span>; The root is <span class="tex-span"><i>x</i> = - 1</span></p><p> <span class="tex-span"><i>b</i> = 1</span>, <span class="tex-span"><i>c</i> = 2</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>x</i> + 2 = 0</span>; No roots</p><p> Overall there's one root</p><p>In the second test the following equations are analysed:</p><p> <span class="tex-span"><i>b</i> = 1</span>, <span class="tex-span"><i>c</i> = 1</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>x</i> + 1 = 0</span>; The root is <span class="tex-span"><i>x</i> = - 1</span></p><p> <span class="tex-span"><i>b</i> = 1</span>, <span class="tex-span"><i>c</i> = 2</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>x</i> + 2 = 0</span>; No roots</p><p> <span class="tex-span"><i>b</i> = 1</span>, <span class="tex-span"><i>c</i> = 3</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 2<i>x</i> + 3 = 0</span>; No roots</p><p> <span class="tex-span"><i>b</i> = 2</span>, <span class="tex-span"><i>c</i> = 1</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 4<i>x</i> + 1 = 0</span>; The roots are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/d9d9178e998a736dbbe847a1ce187d086a88bbf9.png" style="max-width: 100.0%;max-height: 100.0%;" /></p><p> <span class="tex-span"><i>b</i> = 2</span>, <span class="tex-span"><i>c</i> = 2</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 4<i>x</i> + 2 = 0</span>; The roots are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/5333195e873a6fc26a7646deed470a771d731f15.png" style="max-width: 100.0%;max-height: 100.0%;" /></p><p> <span class="tex-span"><i>b</i> = 2</span>, <span class="tex-span"><i>c</i> = 3</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 4<i>x</i> + 3 = 0</span>; The roots are <span class="tex-span"><i>x</i><sub class="lower-index">1</sub> = - 3, <i>x</i><sub class="lower-index">2</sub> = - 1</span></p><p> <span class="tex-span"><i>b</i> = 3</span>, <span class="tex-span"><i>c</i> = 1</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 6<i>x</i> + 1 = 0</span>; The roots are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2f6d171c4838713ef8224fd6ebc2744bea54f33e.png" style="max-width: 100.0%;max-height: 100.0%;" /></p><p> <span class="tex-span"><i>b</i> = 3</span>, <span class="tex-span"><i>c</i> = 2</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 6<i>x</i> + 2 = 0</span>; The roots are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/0448361df88c70bcd0ae858432e1c1eca7248165.png" style="max-width: 100.0%;max-height: 100.0%;" /></p><p> <span class="tex-span"><i>b</i> = 3</span>, <span class="tex-span"><i>c</i> = 3</span>: <span class="tex-span"><i>x</i><sup class="upper-index">2</sup> + 6<i>x</i> + 3 = 0</span>; The roots are <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6d4b99328193cd25b1099bc7885851919959a826.png" style="max-width: 100.0%;max-height: 100.0%;" /> Overall there are <span class="tex-span">13</span> roots and as the root <span class="tex-span"> - 1</span> is repeated twice, that means there are <span class="tex-span">12</span> different roots.</p></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:'7e42e4d539d24138',m:'Lu5nkSLjzpSezLo5CIwXQx9.5thhU1y7PzxNn8YZKT0-1688930108-0-AUrPHmBis4BCkMEuT1v9+Z5Ix1WuNqKZ3GKl4jOio72z'};_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>
|