루미 알고리즘

#1487플래티넘Gruppindelning

PO 2020 결선코딩출제 Mattias Akke스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Matteläraren Maria tänker dela in sina elever i två grupper under nästa lektion. Därför ställs hon nu inför ett vanligt problem: hur delar man in elever i två grupper på ett vettigt sätt? Det finns n elever i klassen, och klassrummet har n stolar, numrerade från 1 till n. När en elev anländer till klassrummet så sätter den sig alltid på den lediga stolen som är längst till vänster. Så om totalt k personer dyker upp en viss dag så kommer de alltid att sitta på stolarna 1,2,...,k.

För att dela in eleverna i två grupper har Maria en viss strategi som hon vill använda. Innan lektionen börjar väljer hon en sekvens s av n st ettor och tvåor. När lektionen har börjat så går hon till varje elev och låter eleven som sitter på stol i hamna i grupp s_i. För att gruppindelningen ska bli vettig så finns det två krav som s måste uppfylla:

  1. Maria vet inte hur många elever som kommer, men oavsett hur många som dyker upp så ska skillnaden i storlek mellan de två grupperna vara högst 1.
  2. Det finns m par av stolar som har samma färg. Om det sitter elever på ett sådant par av stolar så måste de hamna i samma grupp.

Din uppgift är att, givet n,m och de m paren av stolar, hitta den sekvens s som kommer först i alfabetisk ordning och uppfyller kraven ovan. Om det inte finns något giltigt s ska ditt program skriva ut -1.

Med alfabetisk ordning menas att man jämför två sekvenser genom att primärt kolla på det första tecknet, om det är samma kollar man på det andra, o.s.v. T.ex. kommer sekvensen 1122 före 1211, men efter 1112.

Indata

Den första raden innehåller två heltal n och m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ n/2), antalet stolar i klassrummet och antalet stolpar med samma färg. Därefter följer m rader som vardera innehåller två heltal s_1, s_2 (1 ≤ s_1, s_2 ≤ N, s_1 ≠ s_2), vilket betyder att stol s_1 och s_2 har samma färg. Varje stol har samma färg som högst en annan.

Utdata

Skriv ut en sekvens med n ettor eller tvåor (utan mellanslag), alternativt -1 om det saknas en giltig lösning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
112n ≤ 15
223n ≤ 40
325Stol i kan bara ha samma färg som stol i± 1.
440Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Om det bara kommer två personer så måste de vara i olika grupper. Alltså måste stol 1 och stol 2 vara i olika grupp, men vi vet också att stol 3 måste vara i samma grupp som stol 2. Om det kommer fyra personer måste därför stol 4 vara i samma grupp som stol 1 för att grupperna ska bli lika stora. Men stol 4 måste vara i samma grupp som stol 5. Om vi fortsätter på samma sätt får vi att stol 1, 4 och 5 måste vara i samma grupp, medan stol 2, 3, 6 och 7 är i den andra gruppen. Det finns alltså två lösningar: 1221122 och 2112211. Den alfabetiskt minsta av dessa är 1221122.

예제

예제 1

입력
7 3
2 3
4 5
6 7
출력
1221122

예제 2

입력
8 3
1 3
2 5
4 7
출력
12122121

예제 3

입력
6 3
1 3
5 2
4 6
출력
-1

출처 표기

출처: Programmeringsolympiaden 2020년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.