mirror of
https://gitlab.com/mfocko/Codeforces.git
synced 2024-09-16 15:46:56 +02:00
Matej Focko
7ec83aafc4
* “A. To My Critics” * “B. Ten Words of Wisdom” * “C. Word on the Paper” * “D. Balanced Round” * “E. Cardboard for Pictures” * “F. We Were Both Children” * “G. The Morning Star” * “H. The Third Letter” Signed-off-by: Matej Focko <me@mfocko.xyz>
1345 lines
89 KiB
HTML
1345 lines
89 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="f3d06b09c22b4d447e4963b06b1539d9"/>
|
||
<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/86650/css/font-awesome.min.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/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/86650/css/prettify.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/clear.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/ttypography.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/problem-statement.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/second-level-menu.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/roundbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/datatable.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/table-form.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/topic.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/jquery.jgrowl.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/facebox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/jquery.wysiwyg.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/jquery.autocomplete.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/codeforces.datepick.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/colorbox.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/jquery.drafts.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/css/community.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/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/86650/js/prettify/prettify.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/moment-with-locales.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/pushstream.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.easing.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.lavalamp.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.jgrowl.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.swipe.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.hotkeys.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/facebox.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.wysiwyg.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/controls/wysiwyg.colorpicker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/controls/wysiwyg.table.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/controls/wysiwyg.image.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/controls/wysiwyg.link.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.autocomplete.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.datepick.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.ie6blocker.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.colorbox-min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.ba-bbq.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/jquery.drafts.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/clipboard.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/autosize.min.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/sjcl.js"></script>
|
||
<script type="text/javascript" src="/scripts/548970f070d7a877b85d5c43a40403d1/en/codeforces-options.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/codeforces.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/EventCatcher.js?v=20160131"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/preparedVerdictFormats-en.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/js/confetti.min.js"></script>
|
||
<!--/CombineResourcesFilter-->
|
||
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/markitup/skins/markitup/style.css" type="text/css" charset="utf-8" />
|
||
<link rel="stylesheet" href="//codeforces.org/s/86650/markitup/sets/markdown/style.css" type="text/css" charset="utf-8" />
|
||
|
||
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/markitup/jquery.markitup.js"></script>
|
||
<script type="text/javascript" src="//codeforces.org/s/86650/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='f3d06b09c22b4d447e4963b06b1539d9'> </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/67929/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/67929/images/flags/24/gb.png" title="In English" alt="In English"/></a>
|
||
<a href="?locale=ru"><img src="//codeforces.org/s/67929/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 886 (Div. 4)</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_6957176af89d1186911501f682ed590f7ce03d6d">
|
||
<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. To My Critics</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>Suneet has three digits $$$a$$$, $$$b$$$, and $$$c$$$. </p><p>Since math isn't his strongest point, he asks you to determine if you can choose any two digits to make a sum greater or equal to $$$10$$$.</p><p>Output "<span class="tex-font-style-tt">YES</span>" if there is such a pair, and "<span class="tex-font-style-tt">NO</span>" otherwise.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.</p><p>The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a, b, c \leq 9$$$).</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output "<span class="tex-font-style-tt">YES</span>" if such a pair exists, and "<span class="tex-font-style-tt">NO</span>" otherwise.</p><p>You can output the answer in any case (for example, the strings "<span class="tex-font-style-tt">yEs</span>", "<span class="tex-font-style-tt">yes</span>", "<span class="tex-font-style-tt">Yes</span>" and "<span class="tex-font-style-tt">YES</span>" will be recognized as a positive answer).</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">5</div><div class="test-example-line test-example-line-odd test-example-line-1">8 1 2</div><div class="test-example-line test-example-line-even test-example-line-2">4 4 5</div><div class="test-example-line test-example-line-odd test-example-line-3">9 9 9</div><div class="test-example-line test-example-line-even test-example-line-4">0 0 0</div><div class="test-example-line test-example-line-odd test-example-line-5">8 5 3</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
YES
|
||
NO
|
||
YES
|
||
NO
|
||
YES
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>For the first test case, by choosing the digits $$$8$$$ and $$$2$$$ we can obtain a sum of $$$8 + 2 = 10$$$ which satisfies the condition, thus the output should be "<span class="tex-font-style-tt">YES</span>".</p><p>For the second test case, any combination of chosen digits won't be at least $$$10$$$, thus the output should be "<span class="tex-font-style-tt">NO</span>" (note that we can not choose the digit on the same position twice).</p><p>For the third test case, any combination of chosen digits will have a sum equal to $$$18$$$, thus the output should be "<span class="tex-font-style-tt">YES</span>".</p></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=A]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#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_1b2b81cf3586d894936f0cba2daad3a728158274">
|
||
<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. Ten Words of Wisdom</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 game show "Ten Words of Wisdom", there are $$$n$$$ participants numbered from $$$1$$$ to $$$n$$$, each of whom submits one response. The $$$i$$$-th response is $$$a_i$$$ words long and has quality $$$b_i$$$. No two responses have the same quality, and at least one response has length at most $$$10$$$.</p><p>The winner of the show is the response which has the highest quality out of all responses that are not longer than $$$10$$$ words. Which response is the winner?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.</p><p>The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the number of responses.</p><p>Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 50$$$) — the number of words and the quality of the $$$i$$$-th response, respectively. </p><p><span class="tex-font-style-bf">Additional constraints on the input:</span> in each test case, at least one value of $$$i$$$ satisfies $$$a_i \leq 10$$$, and all values of $$$b_i$$$ are distinct.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output a single line containing one integer $$$x$$$ ($$$1 \leq x \leq n$$$) — the winner of the show, according to the rules given in the statement.</p><p>It can be shown that, according to the constraints in the statement, exactly one winner exists for each test case.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">3</div><div class="test-example-line test-example-line-odd test-example-line-1">5</div><div class="test-example-line test-example-line-odd test-example-line-1">7 2</div><div class="test-example-line test-example-line-odd test-example-line-1">12 5</div><div class="test-example-line test-example-line-odd test-example-line-1">9 3</div><div class="test-example-line test-example-line-odd test-example-line-1">9 4</div><div class="test-example-line test-example-line-odd test-example-line-1">10 1</div><div class="test-example-line test-example-line-even test-example-line-2">3</div><div class="test-example-line test-example-line-even test-example-line-2">1 2</div><div class="test-example-line test-example-line-even test-example-line-2">3 4</div><div class="test-example-line test-example-line-even test-example-line-2">5 6</div><div class="test-example-line test-example-line-odd test-example-line-3">1</div><div class="test-example-line test-example-line-odd test-example-line-3">1 43</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
4
|
||
3
|
||
1
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first test case, the responses provided are as follows:</p><ul> <li> Response 1: $$$7$$$ words, quality $$$2$$$ </li><li> Response 2: $$$12$$$ words, quality $$$5$$$ </li><li> Response 3: $$$9$$$ words, quality $$$3$$$ </li><li> Response 4: $$$9$$$ words, quality $$$4$$$ </li><li> Response 5: $$$10$$$ words, quality $$$1$$$ </li></ul><p>We can see that the responses with indices $$$1$$$, $$$3$$$, $$$4$$$, and $$$5$$$ have lengths not exceeding $$$10$$$ words. Out of these responses, the winner is the one with the highest quality.</p><p>Comparing the qualities, we find that: </p><ul> <li> Response 1 has quality $$$2$$$. </li><li> Response 3 has quality $$$3$$$. </li><li> Response 4 has quality $$$4$$$. </li><li> Response 5 has quality $$$1$$$. </li></ul><p>Among these responses, Response 4 has the highest quality.</p></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=B]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#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_57ae383e69507a89692382ee0a2d0ef5495cc449">
|
||
<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. Word on the Paper</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>On an $$$8 \times 8$$$ grid of dots, a word consisting of lowercase Latin letters is written vertically in one column, from top to bottom. What is it?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The input consists of multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.</p><p>Each test case consists of $$$8$$$ lines, each containing $$$8$$$ characters. Each character in the grid is either $$$\texttt{.}$$$ (representing a dot) or a lowercase Latin letter ($$$\texttt{a}$$$–$$$\texttt{z}$$$). </p><p>The word lies entirely in a single column and is continuous from the beginning to the ending (without gaps). See the sample input for better understanding.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output a single line containing the word made up of lowercase Latin letters ($$$\texttt{a}$$$–$$$\texttt{z}$$$) that is written vertically in one column from top to bottom.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">5</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">...i....</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-odd test-example-line-1">........</div><div class="test-example-line test-example-line-even test-example-line-2">........</div><div class="test-example-line test-example-line-even test-example-line-2">.l......</div><div class="test-example-line test-example-line-even test-example-line-2">.o......</div><div class="test-example-line test-example-line-even test-example-line-2">.s......</div><div class="test-example-line test-example-line-even test-example-line-2">.t......</div><div class="test-example-line test-example-line-even test-example-line-2">........</div><div class="test-example-line test-example-line-even test-example-line-2">........</div><div class="test-example-line test-example-line-even test-example-line-2">........</div><div class="test-example-line test-example-line-odd test-example-line-3">........</div><div class="test-example-line test-example-line-odd test-example-line-3">........</div><div class="test-example-line test-example-line-odd test-example-line-3">........</div><div class="test-example-line test-example-line-odd test-example-line-3">........</div><div class="test-example-line test-example-line-odd test-example-line-3">......t.</div><div class="test-example-line test-example-line-odd test-example-line-3">......h.</div><div class="test-example-line test-example-line-odd test-example-line-3">......e.</div><div class="test-example-line test-example-line-odd test-example-line-3">........</div><div class="test-example-line test-example-line-even test-example-line-4">........</div><div class="test-example-line test-example-line-even test-example-line-4">........</div><div class="test-example-line test-example-line-even test-example-line-4">........</div><div class="test-example-line test-example-line-even test-example-line-4">........</div><div class="test-example-line test-example-line-even test-example-line-4">.......g</div><div class="test-example-line test-example-line-even test-example-line-4">.......a</div><div class="test-example-line test-example-line-even test-example-line-4">.......m</div><div class="test-example-line test-example-line-even test-example-line-4">.......e</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div><div class="test-example-line test-example-line-odd test-example-line-5">a.......</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
i
|
||
lost
|
||
the
|
||
game
|
||
aaaaaaaa
|
||
</pre></div></div></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=C]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#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_01f11e52686f736b5bb4fb27bbcf3fb2cbbc95e1">
|
||
<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. Balanced Round</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 the author of a Codeforces round and have prepared $$$n$$$ problems you are going to set, problem $$$i$$$ having difficulty $$$a_i$$$. You will do the following process: </p><ul> <li> remove some (possibly zero) problems from the list; </li><li> rearrange the remaining problems in any order you wish. </li></ul><p>A round is considered <span class="tex-font-style-it">balanced</span> if and only if the absolute difference between the difficulty of any two consecutive problems is at most $$$k$$$ (less or equal than $$$k$$$).</p><p>What is the minimum number of problems you have to remove so that an arrangement of problems is balanced?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.</p><p>The first line of each test case contains two positive integers $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq 10^9$$$) — the number of problems, and the maximum allowed absolute difference between consecutive problems.</p><p>The second line of each test case contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the difficulty of each problem.</p><p>Note that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output a single integer — the minimum number of problems you have to remove so that an arrangement of problems is balanced.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">7</div><div class="test-example-line test-example-line-odd test-example-line-1">5 1</div><div class="test-example-line test-example-line-odd test-example-line-1">1 2 4 5 6</div><div class="test-example-line test-example-line-even test-example-line-2">1 2</div><div class="test-example-line test-example-line-even test-example-line-2">10</div><div class="test-example-line test-example-line-odd test-example-line-3">8 3</div><div class="test-example-line test-example-line-odd test-example-line-3">17 3 1 20 12 5 17 12</div><div class="test-example-line test-example-line-even test-example-line-4">4 2</div><div class="test-example-line test-example-line-even test-example-line-4">2 4 6 8</div><div class="test-example-line test-example-line-odd test-example-line-5">5 3</div><div class="test-example-line test-example-line-odd test-example-line-5">2 3 19 10 8</div><div class="test-example-line test-example-line-even test-example-line-6">3 4</div><div class="test-example-line test-example-line-even test-example-line-6">1 10 5</div><div class="test-example-line test-example-line-odd test-example-line-7">8 1</div><div class="test-example-line test-example-line-odd test-example-line-7">8 3 1 4 5 10 7 3</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
2
|
||
0
|
||
5
|
||
0
|
||
3
|
||
1
|
||
4
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>For the first test case, we can remove the first $$$2$$$ problems and construct a set using problems with the difficulties $$$[4, 5, 6]$$$, with difficulties between adjacent problems equal to $$$|5 - 4| = 1 \leq 1$$$ and $$$|6 - 5| = 1 \leq 1$$$.</p><p>For the second test case, we can take the single problem and compose a round using the problem with difficulty $$$10$$$.</p></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=D]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#facebox .diff-popup").html(result["diff"]);
|
||
}
|
||
}, "json");
|
||
});
|
||
}
|
||
} else {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
}
|
||
});
|
||
});
|
||
</script>
|
||
|
||
|
||
<script type="text/javascript">
|
||
$(document).ready(function () {
|
||
|
||
function endsWith(string, suffix) {
|
||
return string.indexOf(suffix, string.length - suffix.length) !== -1;
|
||
}
|
||
|
||
const inputFileDiv = $("div.input-file");
|
||
const inputFile = inputFileDiv.text();
|
||
const outputFileDiv = $("div.output-file");
|
||
const outputFile = outputFileDiv.text();
|
||
|
||
|
||
if (!endsWith(inputFile, "standard input")
|
||
&& !endsWith(inputFile, "standard input")) {
|
||
inputFileDiv.attr("style", "font-weight: bold");
|
||
}
|
||
|
||
if (!endsWith(outputFile, "standard output")
|
||
&& !endsWith(outputFile, "standard output")) {
|
||
outputFileDiv.attr("style", "font-weight: bold");
|
||
}
|
||
|
||
const titleDiv = $("div.header div.title");
|
||
|
||
|
||
|
||
|
||
});
|
||
</script>
|
||
</div>
|
||
<div
|
||
style="margin-bottom: 2em;"
|
||
>
|
||
|
||
|
||
<div class="problemindexholder" problemindex="E" data-uuid="ps_52a3359871a6d4b192463ae17206c6ef8fa54de7">
|
||
<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. Cardboard for Pictures</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>Mircea has $$$n$$$ pictures. The $$$i$$$-th picture is a square with a side length of $$$s_i$$$ centimeters. </p><p>He mounted each picture on a square piece of cardboard so that each picture has a border of $$$w$$$ centimeters of cardboard on all sides. In total, he used $$$c$$$ square centimeters of cardboard. Given the picture sizes and the value $$$c$$$, can you find the value of $$$w$$$?</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/9cc8c6f9c246d2c264aeb25fb11e193fda6b8f96.png" style="max-width: 100.0%;max-height: 100.0%;" /> <span class="tex-font-size-small">A picture of the first test case. Here $$$c = 50 = 5^2 + 4^2 + 3^2$$$, so $$$w=1$$$ is the answer.</span> </center><p>Please note that the piece of cardboard goes behind each picture, not just the border.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.</p><p>The first line of each test case contains two positive integers $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) and $$$c$$$ ($$$1 \leq c \leq 10^{18}$$$) — the number of paintings, and the amount of used square centimeters of cardboard.</p><p>The second line of each test case contains $$$n$$$ space-separated integers $$$s_i$$$ ($$$1 \leq s_i \leq 10^4$$$) — the sizes of the paintings.</p><p>The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.</p><p><span class="tex-font-style-bf">Additional constraint on the input:</span> Such an integer $$$w$$$ exists for each test case.</p><p>Please note, that some of the input for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like <span class="tex-font-style-tt">long long</span> for C++).</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output a single integer — the value of $$$w$$$ ($$$w \geq 1$$$) which was used to use exactly $$$c$$$ squared centimeters of cardboard.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre>
|
||
10
|
||
3 50
|
||
3 2 1
|
||
1 100
|
||
6
|
||
5 500
|
||
2 2 2 2 2
|
||
2 365
|
||
3 4
|
||
2 469077255466389
|
||
10000 2023
|
||
10 635472106413848880
|
||
9181 4243 7777 1859 2017 4397 14 9390 2245 7225
|
||
7 176345687772781240
|
||
9202 9407 9229 6257 7743 5738 7966
|
||
14 865563946464579627
|
||
3654 5483 1657 7571 1639 9815 122 9468 3079 2666 5498 4540 7861 5384
|
||
19 977162053008871403
|
||
9169 9520 9209 9013 9300 9843 9933 9454 9960 9167 9964 9701 9251 9404 9462 9277 9661 9164 9161
|
||
18 886531871815571953
|
||
2609 10 5098 9591 949 8485 6385 4586 1064 5412 6564 8460 2245 6552 5089 8353 3803 3764
|
||
</pre></div><div class="output"><div class="title">Output</div><pre>
|
||
1
|
||
2
|
||
4
|
||
5
|
||
7654321
|
||
126040443
|
||
79356352
|
||
124321725
|
||
113385729
|
||
110961227
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>The first test case is explained in the statement.</p><p>For the second test case, the chosen $$$w$$$ was $$$2$$$, thus the only cardboard covers an area of $$$c = (2 \cdot 2 + 6)^2 = 10^2 = 100$$$ squared centimeters.</p><p>For the third test case, the chosen $$$w$$$ was $$$4$$$, which obtains the covered area $$$c = (2 \cdot 4 + 2)^2 \times 5 = 10^2 \times 5 = 100 \times 5 = 500$$$ squared centimeters.</p></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=E]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#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="F" data-uuid="ps_17a039f3a529f2311946694ad01ddf32ee75d249">
|
||
<div style="display: none; margin:1em 0;text-align: center; position: relative;" class="alert alert-info diff-notifier">
|
||
<div>The problem statement has recently been changed. <a class="view-changes" href="#">View the changes.</a></div>
|
||
<span class="diff-notifier-close" style="position: absolute; top: 0.2em; right: 0.3em; cursor: pointer; font-size: 1.4em;">×</span>
|
||
</div>
|
||
<div class="ttypography"><div class="problem-statement"><div class="header"><div class="title">F. We Were Both Children</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>Mihai and Slavic were looking at a group of $$$n$$$ frogs, numbered from $$$1$$$ to $$$n$$$, all initially located at point $$$0$$$. Frog $$$i$$$ has a hop length of $$$a_i$$$. </p><p>Each second, frog $$$i$$$ hops $$$a_i$$$ units forward. Before any frogs start hopping, Slavic and Mihai can place <span class="tex-font-style-bf">exactly one</span> trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.</p><p>However, the children can't go far away from their home so they can only place a trap in the first $$$n$$$ points (that is, in a point with a coordinate between $$$1$$$ and $$$n$$$) and the children can't place a trap in point $$$0$$$ since they are scared of frogs.</p><p>Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.</p><p>The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.</p><p>The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the lengths of the hops of the corresponding frogs.</p><p>It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">7</div><div class="test-example-line test-example-line-odd test-example-line-1">5</div><div class="test-example-line test-example-line-odd test-example-line-1">1 2 3 4 5</div><div class="test-example-line test-example-line-even test-example-line-2">3</div><div class="test-example-line test-example-line-even test-example-line-2">2 2 2</div><div class="test-example-line test-example-line-odd test-example-line-3">6</div><div class="test-example-line test-example-line-odd test-example-line-3">3 1 3 4 9 10</div><div class="test-example-line test-example-line-even test-example-line-4">9</div><div class="test-example-line test-example-line-even test-example-line-4">1 3 2 4 2 3 7 8 5</div><div class="test-example-line test-example-line-odd test-example-line-5">1</div><div class="test-example-line test-example-line-odd test-example-line-5">10</div><div class="test-example-line test-example-line-even test-example-line-6">8</div><div class="test-example-line test-example-line-even test-example-line-6">7 11 6 8 12 4 4 8</div><div class="test-example-line test-example-line-odd test-example-line-7">10</div><div class="test-example-line test-example-line-odd test-example-line-7">9 11 9 12 1 7 2 5 8 10</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
3
|
||
3
|
||
3
|
||
5
|
||
0
|
||
4
|
||
4
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first test case, the frogs will hop as follows: </p><ul> <li> Frog 1: $$$0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$$$ </li><li> Frog 2: $$$0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$$$ </li><li> Frog 3: $$$0 \to 3 \to 6 \to 9 \to 12 \to \cdots$$$ </li><li> Frog 4: $$$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$$$ </li><li> Frog 5: $$$0 \to 5 \to 10 \to 15 \to 20 \to \cdots$$$ </li></ul> Therefore, if Slavic and Mihai put a trap at coordinate $$$4$$$, they can catch three frogs: frogs 1, 2, and 4. It can be proven that they can't catch any more frogs.<p>In the second test case, Slavic and Mihai can put a trap at coordinate $$$2$$$ and catch all three frogs instantly.</p></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=F]");
|
||
let uuid = $problem.attr("data-uuid");
|
||
let statementText = convertStatementToText($problem.find(".ttypography").get(0));
|
||
|
||
let previousStatementText = Codeforces.getFromStorage(uuid);
|
||
if (previousStatementText) {
|
||
if (previousStatementText !== statementText) {
|
||
$problem.find(".diff-notifier").show();
|
||
|
||
$problem.find(".diff-notifier-close").click(function() {
|
||
Codeforces.putToStorageTtl(uuid, statementText, 6 * 60 * 60);
|
||
$problem.find(".diff-notifier").hide();
|
||
});
|
||
|
||
$problem.find("a.view-changes").click(function() {
|
||
$.post("/data/diff", {action: "getDiff", a: previousStatementText, b: statementText}, function (result) {
|
||
if (result["success"] === "true") {
|
||
Codeforces.facebox(".diff-popup", "//codeforces.org/s/67929");
|
||
$("#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="G" data-uuid="ps_a875be440a97b7722205bfbea3e8416a03714171">
|
||
<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">G. The Morning Star</div><div class="time-limit"><div class="property-title">time limit per test</div>2 seconds</div><div class="memory-limit"><div class="property-title">memory limit per test</div>256 megabytes</div><div class="input-file"><div class="property-title">input</div>standard input</div><div class="output-file"><div class="property-title">output</div>standard output</div></div><div><p>A compass points directly toward the morning star. It can only point in one of eight directions: the four cardinal directions (N, S, E, W) or some combination (NW, NE, SW, SE). Otherwise, it will break.</p><center> <img class="tex-graphics" src="https://espresso.codeforces.com/d4bc950948a1049d2c81071966d4259748cb892a.png" style="max-width: 100.0%;max-height: 100.0%;" /> <span class="tex-font-size-small">The directions the compass can point.</span> </center><p>There are $$$n$$$ distinct points with integer coordinates on a plane. How many ways can you put a compass at one point and the morning star at another so that the compass does not break?</p></div><div class="input-specification"><div class="section-title">Input</div><p>Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.</p><p>The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of points.</p><p>Then $$$n$$$ lines follow, each line containing two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of each point, all points have distinct coordinates.</p><p>It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output a single integer — the number of pairs of points that don't break the compass.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">5</div><div class="test-example-line test-example-line-odd test-example-line-1">3</div><div class="test-example-line test-example-line-odd test-example-line-1">0 0</div><div class="test-example-line test-example-line-odd test-example-line-1">-1 -1</div><div class="test-example-line test-example-line-odd test-example-line-1">1 1</div><div class="test-example-line test-example-line-even test-example-line-2">4</div><div class="test-example-line test-example-line-even test-example-line-2">4 5</div><div class="test-example-line test-example-line-even test-example-line-2">5 7</div><div class="test-example-line test-example-line-even test-example-line-2">6 9</div><div class="test-example-line test-example-line-even test-example-line-2">10 13</div><div class="test-example-line test-example-line-odd test-example-line-3">3</div><div class="test-example-line test-example-line-odd test-example-line-3">-1000000000 1000000000</div><div class="test-example-line test-example-line-odd test-example-line-3">0 0</div><div class="test-example-line test-example-line-odd test-example-line-3">1000000000 -1000000000</div><div class="test-example-line test-example-line-even test-example-line-4">5</div><div class="test-example-line test-example-line-even test-example-line-4">0 0</div><div class="test-example-line test-example-line-even test-example-line-4">2 2</div><div class="test-example-line test-example-line-even test-example-line-4">-1 5</div><div class="test-example-line test-example-line-even test-example-line-4">-1 10</div><div class="test-example-line test-example-line-even test-example-line-4">2 11</div><div class="test-example-line test-example-line-odd test-example-line-5">3</div><div class="test-example-line test-example-line-odd test-example-line-5">0 0</div><div class="test-example-line test-example-line-odd test-example-line-5">-1 2</div><div class="test-example-line test-example-line-odd test-example-line-5">1 -2</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
6
|
||
2
|
||
6
|
||
8
|
||
0
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>In the first test case, any pair of points won't break the compass: </p><ul> <li> The compass is at $$$(0,0)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$. </li><li> The compass is at $$$(0,0)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$. </li><li> The compass is at $$$(-1,-1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{NE}$$$. </li><li> The compass is at $$$(-1,-1)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$. </li><li> The compass is at $$$(1,1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{SW}$$$. </li><li> The compass is at $$$(1,1)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$. </li></ul><p>In the second test case, only two pairs of points won't break the compass: </p><ul> <li> The compass is at $$$(6,9)$$$, the morning star is at $$$(10,13)$$$: the compass will point $$$\text{NE}$$$. </li><li> The compass is at $$$(10,13)$$$, the morning star is at $$$(6,9)$$$: the compass will point $$$\text{SW}$$$. </li></ul></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=G]");
|
||
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/67929");
|
||
$("#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="H" data-uuid="ps_5aaab802536a92918df89dfc81448c450f2c8bfc">
|
||
<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">H. The Third Letter</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>In order to win his toughest battle, Mircea came up with a great strategy for his army. He has $$$n$$$ soldiers and decided to arrange them in a certain way in camps. Each soldier has to belong to exactly one camp, and there is one camp at each integer point on the $$$x$$$-axis (at points $$$\cdots, -2, -1, 0, 1, 2, \cdots$$$).</p><p>The strategy consists of $$$m$$$ conditions. Condition $$$i$$$ tells that soldier $$$a_i$$$ should belong to a camp that is situated $$$d_i$$$ meters in front of the camp that person $$$b_i$$$ belongs to. (If $$$d_i < 0$$$, then $$$a_i$$$'s camp should be $$$-d_i$$$ meters behind $$$b_i$$$'s camp.)</p><p>Now, Mircea wonders if there exists a partition of soldiers that respects the condition and he asks for your help! Answer "<span class="tex-font-style-tt">YES</span>" if there is a partition of the $$$n$$$ soldiers that satisfies <span class="tex-font-style-bf">all</span> of the $$$m$$$ conditions and "<span class="tex-font-style-tt">NO</span>" otherwise.</p><p>Note that two different soldiers <span class="tex-font-style-bf">may</span> be placed in the same camp.</p></div><div class="input-specification"><div class="section-title">Input</div><p>The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.</p><p>The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq m \leq n$$$) — the number of soldiers, and the number of conditions respectively.</p><p>Then $$$m$$$ lines follow, each of them containing $$$3$$$ integers: $$$a_i$$$, $$$b_i$$$, $$$d_i$$$ ($$$a_i \neq b_i$$$; $$$1 \leq a_i, b_i \leq n$$$; $$$-10^9 \leq d_i \leq 10^9$$$) — denoting the conditions explained in the statement. Note that if $$$d_i$$$ is positive, $$$a_i$$$ should be $$$d_i$$$ meters in front of $$$b_i$$$ and if it is negative, $$$a_i$$$ should be $$$-d_i$$$ meters behind $$$b_i$$$.</p><p>Note that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.</p></div><div class="output-specification"><div class="section-title">Output</div><p>For each test case, output "<span class="tex-font-style-tt">YES</span>" if there is an arrangement of the $$$n$$$ soldiers that satisfies <span class="tex-font-style-bf">all</span> of the $$$m$$$ conditions and "<span class="tex-font-style-tt">NO</span>" otherwise.</p></div><div class="sample-tests"><div class="section-title">Example</div><div class="sample-test"><div class="input"><div class="title">Input</div><pre><div class="test-example-line test-example-line-even test-example-line-0">4</div><div class="test-example-line test-example-line-odd test-example-line-1">5 3</div><div class="test-example-line test-example-line-odd test-example-line-1">1 2 2</div><div class="test-example-line test-example-line-odd test-example-line-1">2 3 4</div><div class="test-example-line test-example-line-odd test-example-line-1">4 2 -6</div><div class="test-example-line test-example-line-even test-example-line-2">6 5</div><div class="test-example-line test-example-line-even test-example-line-2">1 2 2</div><div class="test-example-line test-example-line-even test-example-line-2">2 3 4</div><div class="test-example-line test-example-line-even test-example-line-2">4 2 -6</div><div class="test-example-line test-example-line-even test-example-line-2">5 4 4</div><div class="test-example-line test-example-line-even test-example-line-2">3 5 100</div><div class="test-example-line test-example-line-odd test-example-line-3">2 2</div><div class="test-example-line test-example-line-odd test-example-line-3">1 2 5</div><div class="test-example-line test-example-line-odd test-example-line-3">1 2 4</div><div class="test-example-line test-example-line-even test-example-line-4">4 1</div><div class="test-example-line test-example-line-even test-example-line-4">1 2 3</div></pre></div><div class="output"><div class="title">Output</div><pre>
|
||
YES
|
||
NO
|
||
NO
|
||
YES
|
||
</pre></div></div></div><div class="note"><div class="section-title">Note</div><p>For the first test case, we can partition the soldiers into camps in the following way: soldier:</p><ul> <li> Soldier $$$1$$$ in the camp with the coordinate $$$x = 3$$$. </li><li> Soldier $$$2$$$ in the camp with the coordinate $$$x = 5$$$. </li><li> Soldier $$$3$$$ in the camp with the coordinate $$$x = 9$$$. </li><li> Soldier $$$4$$$ in the camp with the coordinate $$$x = 11$$$. </li></ul><p>For the second test case, there is no partition that can satisfy all the constraints at the same time.</p><p>For the third test case, there is no partition that satisfies all the constraints since we get contradictory information about the same pair.</p><p>For the fourth test case, in order to satisfy the only condition, a possible partition is:</p><ul> <li> Soldier $$$1$$$ in the camp with the coordinate $$$x = 10$$$. </li><li> Soldier $$$2$$$ in the camp with the coordinate $$$x = 13$$$. </li><li> Soldier $$$3$$$ in the camp with the coordinate $$$x = -2023$$$. </li><li> Soldier $$$4$$$ in the camp with the coordinate $$$x = -2023$$$. </li></ul></div></div><p> </p></div>
|
||
</div>
|
||
|
||
<script>
|
||
$(function () {
|
||
Codeforces.addMathJaxListener(function () {
|
||
let $problem = $("div[problemindex=H]");
|
||
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/67929");
|
||
$("#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-67929.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:'7eb6509a89e6b36b'};_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.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>
|