Task: | Kortit I |
Sender: | wolruso |
Submission time: | 2024-11-09 14:30:06 +0200 |
Language: | Rust (2021) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 15 |
#3 | ACCEPTED | 73 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.00 s | 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 3 | details |
#4 | ACCEPTED | 0.01 s | 3 | details |
#5 | ACCEPTED | 0.01 s | 3 | details |
#6 | ACCEPTED | 0.01 s | 3 | details |
#7 | ACCEPTED | 0.01 s | 3 | details |
#8 | ACCEPTED | 0.01 s | 3 | details |
#9 | ACCEPTED | 0.01 s | 3 | details |
#10 | ACCEPTED | 0.01 s | 3 | details |
#11 | ACCEPTED | 0.01 s | 3 | details |
#12 | ACCEPTED | 0.01 s | 3 | details |
#13 | ACCEPTED | 0.01 s | 3 | details |
#14 | ACCEPTED | 0.01 s | 3 | details |
#15 | ACCEPTED | 0.01 s | 3 | details |
#16 | ACCEPTED | 0.01 s | 3 | details |
#17 | ACCEPTED | 0.01 s | 3 | details |
#18 | ACCEPTED | 0.01 s | 3 | details |
#19 | ACCEPTED | 0.01 s | 3 | details |
#20 | ACCEPTED | 0.01 s | 3 | details |
Code
use std::io::stdin;pub struct TestInfo {pub num_cards: usize,pub p1_points: usize,pub p2_points: usize,}pub fn initial_method(num_cards: usize,num_points_p1: usize,num_points_p2: usize,) -> Option<(Vec<usize>, Vec<usize>)> {// 5 4 3 2 1// 5 -> just reduces the problem to (n - 1)// anything else -> means that card can not be played against the enemy's such card, meaning a// tie won't result there, meaning one player will win there, meaning p2 will win there, as// their going to have a n to place there// -> Thus it is not possible to have a (n - 1) tie. Instead, an n or (n - 2) tie is the best// possible, and in the latter case, both players will have to get one point//// In fact, all ties, a count k of them, just cause the problem to become (n - k) instead// (regardless of the place of the ties)// 5 4 3 2 1 4, 1// 1 5 4 3 2//// 5 4 3 2 1 3, 2// 1 3 5 4 2//// 5 4 3 2 1 1, 4// 4 3 2 1 5//// 5 4 3 2 1// 4 5 1 3 2//// I.e.: neither 1, nor (n - 1), is ALWAYS a valid option//// Picking 1 < x < n - 1 as the first card signifies:// - that card is no more available to be picked for e(x - 1)// - that card is no more available to be picked for e(x + 1)//// 5 4 3 2 1// 3 5 4 1 2//// 5 4 3 2 1// 2 5 4 3 1//// Whenever a card y(a > b) is picked as a response to e(b), it reduces the amount of cards// y(x >= a) available to win against all cards e(x <= a - 2).// It does not affact the ability for winning against cards e(x >= a - 2)// 1// b//// Actually, a better way to represent this would be by saying that:// Whenever a card y(a > b + 1) is picked as a response to e(b), it makes the card y(b + 1)// useless. Or, actually, if b > 1 (as would generally be the case), it causes a chain// reaction, where yes, the card y(b + 1) can be played against cards e(x < b), but now there's// b + 1 (of which one is the card 1, which can not be used to win, so really, there's only b// cards that matter in this sense) cards of player Y available to be played against b - 1 cards// of the enemy. There is a mismatch, and thus one of those cards will inevitable go to waste,// i.e. be unable to be used to win an exchange, and must thus be used to lose instead.//// 5 4 3 2 1// 1 2 5 4 3//// 5 4 3 2 1// 1 2 4 3 5//// And along with the effect mentioned in the previous paragraph, there is also the effect that// there will now be one card fewer for winning against cards e(x > b), one card less than// there are those cards of the enemy. Thus the one card y(x > b + 1) that doesn't exist will// instead be replaced by the wasted card y(x <= b).//// Actually, the previous paragraph mentioned in the previous paragraph is entirely incorrect.//// When a card y(a > b) is picked to win against a card e(b), the cards e(e) are split into two// groups: e(x > b) and e(x <= b). The former group doesn't get any smaller as a result of the// exchange, but the latter does, as e(b) is included in it. If a == b + 1, then the group of// cards y(c > b + 1) that can be played against the group of cards e(x > b) does not get any// smaller. But if a > b + 1, the group y(c > b + 1) does get smaller by one card. This means// that the amount of times it is possible to win against cards e(x > b) is reduced by one.// The same applies for picking a card y(a < b) against a card e(b), except the relations are// reversed.//// 5 4 3 2 1// 1 3 2 4 5//// 5 4 3 2 1// 4 3 2 1 5//// 5 4 3 2 1// 3 5 2 1 4//// e(b) => y(a < b)// e(c < a <=> c < b - 1) can be won against with the cards y(d >= a). That group e(c) of cards does// not get any smaller but the group y(d) does.////// Formal Approach://// The game can be thought of as a sequence of exchanges. The game will then have a separate,// distinct state at each such element of the sequence: a state consisting of the set of cards// e(x) and y(x).// Since in the first part of the exercise, the particular game doesn't matter as long as// it ends up with the right score totals, it doesn't matter in which order the cards are// represented. Thus it would be helpful to use a convention where the exchanges are ordered// based on cards e(x) in descending order.// The above inferences can be formulated thusly. At each element of the sequence of// exchanges, S(n), regardless of how the game has been played by both players up to this// point, regardless of which elements the sets E(n) and Y(n) hold, the following holds true.// The set E(n) can be split into two sets, e(a > o(n)) and e(b <= o(n)). In S(n + 1), if such// a state exists, i.e. n < N, e(a) will be equally large, while e(b) will have decreased in// size by one, compared to the state S(n), as that set includes the element e(o(n)).// It is relevant to define one more set, this time for Y(n): y(a > o(n) + 1). This set// describes the elements of Y(n) that can be played against e(a) to win. If t(n) == o(n) + 1, then// the set y(a) does not decrease in size, and thus will remain as equal with e(a) as it was in// the previous state S(n - 1), provided of course, that n > 0. If, on the other hand, t(n) > o(n) + 1,// then it does belong in the set y(a), and thus the size of that set decreases. This means that one// fewer card in e(a) can be won against.// But what is the effect on the possibilities for losing against E(a > n)? The only// elements E(n) that might possibly be affected by this are e(c > o(n) + 1). Of course the// size of e(c) remains constant across state boundaries, and the number of elements y(c <=// o(n) + 1)//// The algorithm:// It would generate the game state, one exchange at a time, starting from the previously// described order. Before continuing with producing an exchange sequence for the wins and// losses though, the algorithm would calculate the number of ties and produce the appropriate// sequence of the appropriate length to describe the tie exchanges. At the end the algorithm// could then preprend that sequence to the generated one.// At each exchange, the algorithm would produce such an exchange, that it produced a win// for p2 if there are still wins needed to be obtained for that player, and otherwise one// for p1. The exhange would be made such, that it would not lower the maximum amount of points// each player can still obtain beyond the point total they are to acquire. The algorithm would// only need to consider the point maximums separately for each player, as there is no link// between them.//// Thus the only problems remaining are:// - Edge cases at cards n and 1// - 1 is the only card that can not be used for winning, and thus choosing that card// for a losing option does not atually reduce My(n)// - n is the only card that can not be used to lose, and thus choosing that card for a// winning option does not actually reduce Me(n)// - How to avoid accidentally causing a tie, as that is illegal now that the ties have already// been taken care of before?// - As E(0) == Y(0), and each exchange is either a win or a loss, which means o(n) !=// t(n), - no nvm: S(1) = (1, 2), S(2) = (2, 1), then S(3) must be (3, 3).// IMPORTANT: e(m) and e(l) here are for the state at the start of the next exchange, S(n + 1)!// - How does choosing a winning card affect maximum losing plays left?// - If t(n) < e(m), then Me(n) decreases// - If t(n) >= e(m), then Me(n) does not change// - How does choosing a losing card affect maximum winning playes left?// - If t(n) > e(l), then My(n) decreases// - If t(n) <= e(l), then My(n) does not change//// So basically, in the above two cases, if the card t(n) could not be used for winning or// losing in S(n + 1) anyway, then there would naturally be no reduction in My(n + 1) or Me(n// + 1)// (Could consider the above 2 by considering every possible state + exchange combination and// then finding regularities in the effect)//// The algoritm proceeds in descending order from e(m) towards e(l). At S(1), there are 2// options: t(1) = n - 1 (if p1 = n - 1) or t(1) = 1 (if p2 = n - 1). If neither, t(1) can be// either.// S(2): If pc2 < p2, then t(2) = n - 1 + 1 = n. Else, t(2) = n - 1 - 1 = n - 2.// S(3): If pc2 < p2, then t(3) = n - 2 + 1 = n - 1. Except, this card might've been selected// for S(1) before. In that case, it is not possible anymore to win this. Nvm, if t(1) = n - 1,// then p1 = n - 1, which means S(2) should be a loss anyway, and the only win should be at// S(n).// Thus n - 1 is actually a secure choice here. If instead pc1 < p1, then t(3) = n - 2 - 1// = n - 3.////// General rule//// The cases of p1 = n - 1 and p2 = n - 1 can be thought of as a special case for which its own logic exists.// p1 case: t(i) = n - i, for every case i != n. t(n) = n.// p2 case: t(i) = n - i + 2, for every case i != 1. t(1) = 1.//// For every other case, the wins will be generated first, and then the losses. (Apart from// S(1) of course.) For each win, t(i) = n - i + 2. For each loss, t(i) = n - i.// E: 7 6 5 4 3 2 1// Y: 1 7 6 3 2 5 4// Me: 6 4 3 2 1 0 0 0// My: 6 6 5 4 3 2 1 0// Note: The "base" M() reduction comes into play only if that exchange was indeed winnable or// losable//// Note: At S(6) and S(7), the order of the 5 and 4 don't matter.//// Walkthrough:// c = 7, p1 = 3, p2 = 4// t(1) = 1, as p1 < n - 1 and p2 < n - 1// t(2) = n - 2 + 2 = n, as pc2 < p2 - 2, the winning logic// t(3) = n - 3 + 2 = n - 1, as pc2 < p2 - 2, the winning logic//// Normally, the winning would continue here, with t(4) = n - 2. But since pc2 = 2, and both S(n -// 1) and S(n) must be wins, pc2 < p2 - 2 must hold for another win to be generated. Since p2 -// 2 = 4, and 2 == 2, the algorithm must switch to losses here.//// t(4) = n - 4 as pc2 == p2 - 2, the losing logic// t(5) = n - 5, the losing logic// The logic switches here. The lost 2 exchanges can be nothing else apart from a win, so the// last two cards should just be played here in an arbitrary order. The two cards remaining are// always those that would've been played in the first two exchanges that grant a loss (after// S(1) of course) to generate a win instead. In this case, 5 and 4.// t(6) = 5, ending logic// t(7) = 4, ending logic//// p1 = 5, p2 = 4// 9 8 7 6 5 4 3 2 1// 1 9 8 5 4 3 2 7 6// w(n) = l(n - 2)//// p1 = 9, p2 = 3// 12 11 10 9 8 7 6 5 4 3 2 1// 1 12 9 8 7 6 5 4 3 2 11 10// Note: S(n) is a guaranteed win, as it can't be a tie, and no card is less than 1. Thus it is// necessary to compare pc2 to p2 - 1, not just p2.if num_points_p1 > (num_cards - 1)|| num_points_p2 > (num_cards - 1)|| (num_points_p1 + num_points_p2) > num_cards{return None;}let num_ties = num_cards - num_points_p1 - num_points_p2;let mut p2_cards = Vec::new();// let mut maximum_p1_points = num_cards - 1;// let mut maximum_p2_points = num_cards - 1;let mut current_p1_points = 0;let mut current_p2_points = 0;let mut cards = Vec::new();for i in (1..=num_cards).rev() {cards.push(i);}if num_points_p1 == 0 && num_points_p2 == 0 {return Some((cards.clone(), cards));} else if num_points_p1 == 0 || num_points_p2 == 0 {return None;}// means that p2 = c - ties - p1if num_points_p2 == 1 {// i = num_ties is still a tie, and i = num_ties + 1 is S(n)for i in ((num_ties + 2)..=num_cards).rev() {p2_cards.push(i - 1);}p2_cards.push(num_cards);for i in (1..=num_ties).rev() {p2_cards.push(i);}return Some((cards, p2_cards));} else {p2_cards.push(num_ties + 1);current_p1_points += 1;}// This is relevant in the case of c = 3, p1 = 1, p2 = 2let mut switch_to_losses = 2;let mut switch_to_losses_happened = false;// Two problematic cases: middle losses = 1 and middle losses = 0.// For the latter one, special logic can be written very easily.// In the middle losses = 1 case, the next exchange already includes the switch_to_losses as// t(n - 1). Thus it isn't problematic to also have switch_to_losses + 1 as t(n)if num_points_p1 == 1 {for i in ((num_ties + 1)..num_cards).rev() {p2_cards.push(i + 1);}for i in (1..=num_ties).rev() {p2_cards.push(i);}return Some((cards, p2_cards));}for i in ((num_ties + 3)..num_cards).rev() {if current_p2_points < (num_points_p2 - 2) {p2_cards.push(i + 1);current_p2_points += 1;} else if current_p1_points < num_points_p1 {if !switch_to_losses_happened {switch_to_losses = i;switch_to_losses_happened = true;}p2_cards.push(i - 1);current_p1_points += 1;} else {return None;}// maximum_p1_points -= 1;// maximum_p2_points -= 1;// if maximum_p1_points < (num_points_p1 - current_p1_points) {// return None;// }// if maximum_p2_points < (num_points_p2 - current_p2_points) {// return None;// }}// There will always be at least two wins for p2, because otherwise the answer is already// generated before and this logic is never reached. If there are only two wins, they will both happen// herep2_cards.push(switch_to_losses + 1);p2_cards.push(switch_to_losses);for i in (1..=num_ties).rev() {p2_cards.push(i);}Some((cards, p2_cards))}fn main() {let mut l = String::new();stdin().read_line(&mut l).unwrap();let num_tests: usize = l.trim().parse().unwrap();let mut tests: Vec<TestInfo> = Vec::with_capacity(num_tests);for _ in 0..num_tests {let mut tl = String::new();stdin().read_line(&mut tl).unwrap();let mut nums = tl.trim().split(' ');let c: usize = nums.next().unwrap().parse().unwrap();let p1: usize = nums.next().unwrap().parse().unwrap();let p2: usize = nums.next().unwrap().parse().unwrap();tests.push(TestInfo {num_cards: c,p1_points: p1,p2_points: p2,});}for i in 0..num_tests {let t = &tests[i];let answer_tmp = initial_method(t.num_cards, t.p1_points, t.p2_points);let answer = match answer_tmp {None => {println!("NO");continue;}Some(a) => {println!("YES");a}};let p1_cards = answer.0.into_iter().map(|c| c.to_string()).collect::<Vec<String>>().join(" ");let p2_cards = answer.1.into_iter().map(|c| c.to_string()).collect::<Vec<String>>().join(" ");println!("{}", p1_cards);println!("{}", p2_cards);}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
54 4 4 0 3 1 3 3 2 2 4 0 4 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... |
Test 2
Group: 2, 3
Verdict: ACCEPTED
input |
---|
284 6 1 0 5 0 2 7 1 5 7 7 5 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 2 3 4 5 6 1 7 ... |
user output |
---|
NO NO YES 7 6 5 4 3 2 1 2 7 6 5 4 3 1 ... |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
955 14 2 10 12 2 5 10 4 9 14 1 13 ... |
correct output |
---|
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 14 13 12 11 10 9 8 7 6 5 4 3 2... |
Test 4
Group: 3
Verdict: ACCEPTED
input |
---|
869 17 12 9 16 8 4 15 9 9 17 11 15 ... |
correct output |
---|
NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO YES 16 15 14 13 12 11 10 9 8 7 6 5... |
Test 5
Group: 3
Verdict: ACCEPTED
input |
---|
761 18 3 15 19 1 15 18 8 1 19 19 17 ... |
correct output |
---|
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 18 17 16 15 14 13 12 11 10 9 8... |
Test 6
Group: 3
Verdict: ACCEPTED
input |
---|
925 21 14 21 20 18 18 20 7 6 21 14 9 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO NO YES 20 19 18 17 16 15 14 13 12 11 ... |
Test 7
Group: 3
Verdict: ACCEPTED
input |
---|
529 22 3 3 22 17 5 22 6 15 22 22 20 ... |
correct output |
---|
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 22 21 20 19 18 17 16 15 14 13 ... |
Test 8
Group: 3
Verdict: ACCEPTED
input |
---|
576 23 18 9 23 16 8 23 16 13 23 16 22 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... |
Test 9
Group: 3
Verdict: ACCEPTED
input |
---|
625 24 2 22 24 15 21 24 6 3 24 21 1 ... |
correct output |
---|
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 24 23 22 21 20 19 18 17 16 15 ... |
Test 10
Group: 3
Verdict: ACCEPTED
input |
---|
676 25 16 25 25 15 2 25 15 7 25 15 16 ... |
correct output |
---|
NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO YES 25 24 23 22 21 20 19 18 17 16 ... |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
729 26 2 18 26 14 18 26 5 18 26 19 13 ... |
correct output |
---|
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 26 25 24 23 22 21 20 19 18 17 ... |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
784 27 26 7 27 14 0 27 14 5 27 14 14 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO NO YES 27 26 25 24 23 22 21 20 19 18 ... |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
841 28 26 16 28 13 19 28 5 8 28 26 4 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO NO YES 28 27 26 25 24 23 22 21 20 19 ... |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
900 29 24 15 29 13 2 29 13 7 29 13 16 ... |
correct output |
---|
NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO YES 29 28 27 26 25 24 23 22 21 20 ... |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
961 30 24 26 30 12 24 30 4 29 30 24 14 ... |
correct output |
---|
NO NO NO NO YES ... |
user output |
---|
NO NO NO NO YES ... |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
1000 15 12 6 33 18 30 44 4 26 6 6 5 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO NO YES 44 43 42 41 40 39 38 37 36 35 ... |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
1000 45 32 30 4 0 3 46 23 10 71 19 46 ... |
correct output |
---|
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
NO NO YES 46 45 44 43 42 41 40 39 38 37 ... |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
1000 51 29 37 75 11 72 5 2 4 31 8 26 ... |
correct output |
---|
NO NO NO NO YES ... |
user output |
---|
NO NO NO NO YES ... |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
1000 50 20 37 99 45 58 86 79 73 85 70 54 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
1000 26 23 5 73 53 59 64 47 41 80 75 55 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... |