Codeforces/1850/index.html

1346 lines
89 KiB
HTML
Raw Permalink Normal View History

<!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'>&nbsp;</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;">&times;</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 &quot;<span class="tex-font-style-tt">YES</span>&quot; if there is such a pair, and &quot;<span class="tex-font-style-tt">NO</span>&quot; 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 &quot;<span class="tex-font-style-tt">YES</span>&quot; if such a pair exists, and &quot;<span class="tex-font-style-tt">NO</span>&quot; otherwise.</p><p>You can output the answer in any case (for example, the strings &quot;<span class="tex-font-style-tt">yEs</span>&quot;, &quot;<span class="tex-font-style-tt">yes</span>&quot;, &quot;<span class="tex-font-style-tt">Yes</span>&quot; and &quot;<span class="tex-font-style-tt">YES</span>&quot; 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 &quot;<span class="tex-font-style-tt">YES</span>&quot;.</p><p>For the second test case, any combination of chosen digits won't be at least $$$10$$$, thus the output should be &quot;<span class="tex-font-style-tt">NO</span>&quot; (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 &quot;<span class="tex-font-style-tt">YES</span>&quot;.</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;">&times;</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 &quot;Ten Words of Wisdom&quot;, 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;">&times;</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-ex
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;">&times;</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;">&times;</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;">&times;</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;">&times;</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
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;">&times;</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 &lt; 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 &quot;<span class="tex-font-style-tt">YES</span>&quot; if there is a partition of the $$$n$$$ soldiers that satisfies <span class="tex-font-style-bf">all</span> of the $$$m$$$ conditions and &quot;<span class="tex-font-style-tt">NO</span>&quot; 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 &quot;<span class="tex-font-style-tt">YES</span>&quot; if there is an arrangement of the $$$n$$$ soldiers that satisfies <span class="tex-font-style-bf">all</span> of the $$$m$$$ conditions and &quot;<span class="tex-font-style-tt">NO</span>&quot; 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
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>