|
|
The problem can be reduced to a matching problem. It can be solved by Dinic's algorithm. Some useful tests for WA3: 3 3 2 2 3 answer: NO 4 3 2 2 3 answer: YES No these won't help for WA at 3. Actually, you can solve it as a graph problem, where numbers 0, 1, ..., n are vertices, which connected like: 0-1, 1-2, ... Please, tell me what is in Test4??????? I also got WA for test 4.....so I started to try some self made test cases.....and I came across this one : 5 4 2 0 1 3 My output : NO. Correct Output should be YES. I will have to rethink my approach.....maybe you have the same problem as well. case 3 3 1 2 3 helped me in test 4. But anyway it's better to write your own test case generator. Edited by author 18.04.2020 04:47 Here is my solution and used test cases. I don't understand why I always get WA. 8-( Test 1. 5 4 2 0 1 2: NO Test 2.5 4 2 0 1 5: YES Test 3. 5 4 2 0 3 5: YES Test 4. 5 4 2 0 3 4: YES Test 5. 5 5 2 0 3 4 5: YES Test 6. 5 5 2 0 2 4 5: YES Test 7. 5 6 2 1 2 4 5 0: NO Test 8. 5 4 1 2 2 3: YES Test 9. 5 5 1 2 3 4 3: YES Test 10. 5 5 1 1 0 3 4: NO Test 11. 5 3 0 0 1: NO Test 12. 5 3 0 1 1: NO Test 13. 5 3 1 2 2: YES Test 14. 5 3 1 1 2: YES Test 15. 5 3 4 4 5: NO Test 16. 5 3 3 4 4: YES Test 17. 5 3 4 5 5: NO Test 18. 5 3 3 4 5: YES Test 19. 2 2 1 1: YES Test 20. 2 2 2 2: NO Source code: [code deleted] Edited by moderator 13.02.2007 20:57 If the num of cards is lower than m i think that the asnwer should be NO 2.5 4 2 0 1 5 YES? Edited by author 19.01.2007 12:34 I'm not very good in C, and i don't undrstand your source) But my idea is very simple. Store in array number of repeats, increment a[0] and a[n] (because it's only one card with this numbers) and find in array sequence 2 1 1 .. 1 1 2 that's all) Edited by author 22.04.2009 22:45 Is test 9 right? i think so.i think that test#9 may be wrong.or i made mistake while reading the problem... tell the truth,i don't really understand the problem .. I don't understand Test 5. 5 5 2 0 3 4 5: YES Why? first 5 so take 5 or 6 second 5 so take 5 or 6 so take 5 and 6 ... last 5 so take 5 or 6 again, but 5 and 6 were taken, so NO help me, please for the 1st and the 2nd 5 means n and m without meaning the number which was took. here are test right Edited by author 31.12.2012 02:08 Edited by author 31.12.2012 02:08 Edited by author 31.12.2012 02:08 There is my code: Program t1134; Const MaxN=1000; Var Card : array[1..MaxN]of boolean; Numb : array[1..MaxN]of integer; Use : array[1..MaxN]of boolean; M,N,i,j : integer; ex : boolean; begin Read(N,M); if (M>N)or(m=0) then begin writeln('NO'); halt(0); end; for i:=1 to N do Card[i]:=false; for i:=1 to M do Use[i]:=false; for i:=1 to M do begin read(Numb[i]); if (Numb[i]<0)or(Numb[i]>n) then begin writeln('NO'); halt(0); end; end; for i:=1 to M do if Numb[i]=0 then begin Use[i]:=true; if Card[1] then begin writeln('NO'); halt(0); end; Card[1]:=true; end else if Numb[i]=n then begin Use[i]:=true; if Card[n] then begin writeln('NO'); halt(0); end; Card[n]:=true; end; for i:=1 to m-1 do if not(use[i]) then for j:=i+1 to m do if not(use[j]) then if numb[i]=numb[j] then begin if (card[numb[i]])or(card[numb[j]-1]) then begin writeln('NO'); halt(0); end; card[numb[i]-1]:=true; card[numb[i]]:=true; use[i]:=true; use[j]:=true; end; repeat ex:=true; for i:=1 to m do if not(use[i]) then if (card[numb[i]])or(card[numb[i]-1]) then begin if (card[numb[i]])and(card[numb[i]-1]) then begin writeln('NO'); halt(0); end; if card[numb[i]] then begin card[numb[i]-1]:=true; use[i]:=true; end else begin card[numb[i]-1]:=true; use[i]:=true; end; end; until ex; Writeln('YES'); end. 3 3 2 2 3 Maybe you forgot something, because the output of your program for this test case is 'YES'; hope this will help Good luck! > 3 3 > 2 2 3 > Maybe you forgot something, because the output of your program for > this test case is 'YES'; > hope this will help > Good luck! > i suppose the answer should be NO for that 2 2 means the 2nd and the 3rd had been taken, so the third number 3 is uncorrect 3 3 2 2 3 Maybe you forgot something, because the output of your program for this test case is 'YES'; hope this will help Good luck! Sorry for my bad english I'm see all exists tests, and I'm get a correct result on these tests(according comments). Let <ms> is init array, <flag> is (answer is YES?). 1. I do check that (the number in <ms>) is not greater than <n> 2. I'm sorted <ms>. 3. I'm create a <isFills> = new Array[Boolean](n+1) And then I use the following code: if (m>1 && ms(1) == 0) return false // (ms(0)==ms(1)==0) => "NO" if (m>1 && ms(m-2)==n) return false // (ms(m-2)==ms(m-1)==n) => "NO"
isFills(max(ms(0)-1, 0)) = true for (i <- 1 until m) { if (!isFills(ms(i)-1) || !isFills(ms(i))) { if (!isFills(ms(i)-1)) isFills(ms(i)-1) = true else isFills(ms(i)) = true } else return false } return flag Console.println(if (getFlag==true) "YES" else "NO") Full code: object Main { import java.util.Scanner import math._
val scan = new Scanner(System.in) val n = scan.nextInt() val m = scan.nextInt() val ms = new Array[Int](max(m,1)) for (i <- 0 until m) ms(i) = scan.nextInt() scan.close()
def getFlag: Boolean = { var flag = true
for (i <- 0 until m) flag &&= ms(i)<=n if (!flag) return flag
java.util.Arrays.sort(ms) val isFills = new Array[Boolean](n+1)
if (m>1 && ms(1) == 0) return false if (m>1 && ms(m-2)==n) return false
isFills(max(ms(0)-1, 0)) = true for (i <- 1 until m) { if (!isFills(ms(i)-1) || !isFills(ms(i))) { if (!isFills(ms(i)-1)) isFills(ms(i)-1) = true else isFills(ms(i)) = true } else return false } flag } Console.println(if (getFlag==true) "YES" else "NO")
def main(args: Array[String]){} } Edited by author 26.12.2015 23:56 Edited by author 26.12.2015 23:57 please tell me how 1 1 2 2 can be YES.Because if Nick take cards for example that 0 1 reads 1 1 2 reads 1 2 3 reads 2 and he can't write 1 2 and 2 3 and answer must be NO i think Sorry I understnd all :) Edited by author 17.08.2008 04:31 Edited by author 17.08.2008 04:32 i don't understand why it can be YES Edited by author 22.04.2014 12:25 linear time input + O(nlogn) time sorting + O(n)time availability checking gives ac in .015 sec and 150 kb. I think better solution is possible. Please, let me know. Use Hash Sort which is O(n) i tryed all possible tests but i am still getting mistake on the fifth test. can somebody give me some tricky tests to help me? i have got this test too=( in this problem,sorting and greedy approach works.after sorting given card outcomes, we must iterate through these numbers and serve that card which has smallest possible number.using this,we make more chance to the next card to serve for the next outcome, i.e outcomes are ordered. The new compiler supports regex and thus the problem can be solved with 12 lines of real code (263 chars) and a 5-line header (include, ...). 1. 2 2 1 1 - YES This is such a sequence: (1;2) and (1;0) 2. 2 2 2 2 - NO This is impossible because number 2 is written only on one card (2;1) so it couldn't appear twice. Good luck! > 1. 2 2 1 1 - YES > This is such a sequence: > (1;2) and (1;0) > 2. 2 2 2 2 - NO > This is impossible because number 2 is written only on one card (2;1) > so it couldn't appear twice. > > Good luck! > please tell me how 2 2 1 1 can be YES.Because if Nick take cards for example that 0 1 reads 1 1 2 reads 1 2 3 reads 2 and he can't write 1 2 and 2 3 and answer must be NO i think Here the first two numbers are N and M I use n^4 algorythm and works for 0.015 secs. :P m positive integer numbers are listed in sample there is number 0. So 'positive' should be replaced by 'non-negative'. Remember, that (0,1) belong to the FIRST Card. If your get RE - check, that after Sorting every number < nCards =) Subj. PS Im sorry for my english. Same in Russian: Сколько раз Ник может ошибиться? Ok, here are some: Test 1: 8 6 1 2 2 3 4 4 ANSWER: NO Test 2: 8 4 0 1 2 2 ANSWER: NO My code works fine with the test cases discussed here ... But still am getting wrong answer for test case #11 Can anyone give a tricky test case tat would help me ?? don't think about the minus and you will find it so easy...think about it as if all numbers are written positive.:) I got WA on test 12. please give me some test. thank you. |
|
|