CSES - Datatähti 2021 alku - Results
Submission details
Task:2021-luvut
Sender:antti_p
Submission time:2020-10-11 11:52:15 +0300
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED25
#4ACCEPTED50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3, 4details
#2ACCEPTED0.01 s1, 2, 3, 4details
#3ACCEPTED0.01 s1, 2, 3, 4details
#4ACCEPTED0.01 s1, 2, 3, 4details
#5ACCEPTED0.01 s1, 2, 3, 4details
#6ACCEPTED0.01 s1, 2, 3, 4details
#7ACCEPTED0.01 s1, 2, 3, 4details
#8ACCEPTED0.01 s1, 2, 3, 4details
#9ACCEPTED0.01 s1, 2, 3, 4details
#10ACCEPTED0.01 s1, 2, 3, 4details
#11ACCEPTED0.01 s2, 3, 4details
#12ACCEPTED0.01 s2, 3, 4details
#13ACCEPTED0.01 s2, 3, 4details
#14ACCEPTED0.01 s2, 3, 4details
#15ACCEPTED0.01 s2, 3, 4details
#16ACCEPTED0.01 s2, 3, 4details
#17ACCEPTED0.01 s2, 3, 4details
#18ACCEPTED0.01 s2, 3, 4details
#19ACCEPTED0.01 s2, 3, 4details
#20ACCEPTED0.01 s2, 3, 4details
#21ACCEPTED0.01 s3, 4details
#22ACCEPTED0.01 s3, 4details
#23ACCEPTED0.01 s3, 4details
#24ACCEPTED0.01 s3, 4details
#25ACCEPTED0.01 s3, 4details
#26ACCEPTED0.01 s3, 4details
#27ACCEPTED0.01 s3, 4details
#28ACCEPTED0.01 s3, 4details
#29ACCEPTED0.01 s3, 4details
#30ACCEPTED0.01 s3, 4details
#31ACCEPTED0.01 s4details
#32ACCEPTED0.01 s4details
#33ACCEPTED0.01 s4details
#34ACCEPTED0.01 s4details
#35ACCEPTED0.01 s4details
#36ACCEPTED0.01 s4details
#37ACCEPTED0.01 s4details
#38ACCEPTED0.01 s4details
#39ACCEPTED0.01 s4details
#40ACCEPTED0.01 s4details

Code

use std::io;
use std::io::prelude::*;

fn count_len(l: u32, k: u32) -> u128 {
    if l < k {
        panic!();
    }
    if l == k {
        return 1
    }
    if k == 0 {
        return 10u128.pow(l)
    }
    9*count_len(l - 1, k) + count_len(l - 1, k - 1)
}

fn find_nth(n: u128) -> u128 {
    let mut bounding = 4;
    while count_len(bounding, 4) <= n {
        bounding+= 1;
    }
    recursive_find(n, bounding, 4, 0)
}

fn recursive_find(n: u128, l: u32, k: u32, d_i: usize) -> u128 {
    if l < k {
        panic!()
    }
    if l == k {
        return if l == 0 {
            0
        } else if l == 1 {
            1
        } else if l == 2 {
            21
        } else if l == 3 {
            021
        } else {
            2021
        }
    }
    if k == 0 {
        return n
    }
    const DIGITS : [u32; 4] = [2, 0, 2, 1];
    let d = DIGITS[d_i];
    let mut total = 0;
    let step = count_len(l - 1, k);
    let step_d = count_len(l - 1, k - 1);
    let mut first_d = 0;
    while first_d != d {
        if total + step > n {
            return (first_d as u128)*10u128.pow(l - 1) + recursive_find(n - total, l - 1, k, d_i);
        }
        total+= step;
        first_d+= 1;
    }
    if total + step_d > n {
        return (first_d as u128)*10u128.pow(l - 1) + recursive_find(n - total, l - 1, k - 1, d_i + 1);
    }
    total+= step_d;
    first_d+= 1;
    while first_d != 10 {
        if total + step > n {
            return (first_d as u128)*10u128.pow(l - 1) + recursive_find(n - total, l - 1, k, d_i);
        }
        total+= step;
        first_d+= 1;
    }
    panic!()
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    println!("{}", find_nth(lines.next().unwrap().unwrap().parse::<u128>().unwrap() - 1));
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
10

correct output
20214

user output
20214

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
359

correct output
202661

user output
202661

Test 3

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
392

correct output
202819

user output
202819

Test 4

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
715

correct output
230721

user output
230721

Test 5

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
278

correct output
202219

user output
202219

Test 6

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
296

correct output
202318

user output
202318

Test 7

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
427

correct output
203214

user output
203214

Test 8

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
565

correct output
208212

user output
208212

Test 9

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
289

correct output
202311

user output
202311

Test 10

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
342

correct output
202581

user output
202581

Test 11

Group: 2, 3, 4

Verdict: ACCEPTED

input
964486

correct output
182502018

user output
182502018

Test 12

Group: 2, 3, 4

Verdict: ACCEPTED

input
110979

correct output
20296916

user output
20296916

Test 13

Group: 2, 3, 4

Verdict: ACCEPTED

input
759149

correct output
126108721

user output
126108721

Test 14

Group: 2, 3, 4

Verdict: ACCEPTED

input
234934

correct output
25023210

user output
25023210

Test 15

Group: 2, 3, 4

Verdict: ACCEPTED

input
610310

correct output
120288133

user output
120288133

Test 16

Group: 2, 3, 4

Verdict: ACCEPTED

input
956690

correct output
182027419

user output
182027419

Test 17

Group: 2, 3, 4

Verdict: ACCEPTED

input
608459

correct output
120281827

user output
120281827

Test 18

Group: 2, 3, 4

Verdict: ACCEPTED

input
944777

correct output
175260251

user output
175260251

Test 19

Group: 2, 3, 4

Verdict: ACCEPTED

input
880780

correct output
152270421

user output
152270421

Test 20

Group: 2, 3, 4

Verdict: ACCEPTED

input
418357

correct output
68202361

user output
68202361

Test 21

Group: 3, 4

Verdict: ACCEPTED

input
713294506861

correct output
20099206371786

user output
20099206371786

Test 22

Group: 3, 4

Verdict: ACCEPTED

input
191431126351

correct output
4193020274761

user output
4193020274761

Test 23

Group: 3, 4

Verdict: ACCEPTED

input
778422318223

correct output
20247733120134

user output
20247733120134

Test 24

Group: 3, 4

Verdict: ACCEPTED

input
931090767075

correct output
20691282041612

user output
20691282041612

Test 25

Group: 3, 4

Verdict: ACCEPTED

input
198806129726

correct output
4275365802196

user output
4275365802196

Test 26

Group: 3, 4

Verdict: ACCEPTED

input
724343399444

correct output
20128443204610

user output
20128443204610

Test 27

Group: 3, 4

Verdict: ACCEPTED

input
105064053560

correct output
2350677231115

user output
2350677231115

Test 28

Group: 3, 4

Verdict: ACCEPTED

input
236866700902

correct output
5872395029521

user output
5872395029521

Test 29

Group: 3, 4

Verdict: ACCEPTED

input
696349488695

correct output
20034225603103

user output
20034225603103

Test 30

Group: 3, 4

Verdict: ACCEPTED

input
30929267826

correct output
1205256095901

user output
1205256095901

Test 31

Group: 4

Verdict: ACCEPTED

input
576379198814226780

correct output
4185251600926331891

user output
4185251600926331891

Test 32

Group: 4

Verdict: ACCEPTED

input
291698664446913099

correct output
2280132983584730156

user output
2280132983584730156

Test 33

Group: 4

Verdict: ACCEPTED

input
693146378550043345

correct output
5270258230724009910

user output
5270258230724009910

Test 34

Group: 4

Verdict: ACCEPTED

input
685982323362439932

correct output
5236052744416920782

user output
5236052744416920782

Test 35

Group: 4

Verdict: ACCEPTED

input
838865925103308874

correct output
6800200426815679149

user output
6800200426815679149

Test 36

Group: 4

Verdict: ACCEPTED

input
766426223219980635

correct output
6112960212822572807

user output
6112960212822572807

Test 37

Group: 4

Verdict: ACCEPTED

input
652970397451919317

correct output
4923188580186259818

user output
4923188580186259818

Test 38

Group: 4

Verdict: ACCEPTED

input
188458586650539464

correct output
1903508375720755921

user output
1903508375720755921

Test 39

Group: 4

Verdict: ACCEPTED

input
157646989818721527

correct output
1525038392797601315

user output
1525038392797601315

Test 40

Group: 4

Verdict: ACCEPTED

input
898606361978236778

correct output
7326676702587314407

user output
7326676702587314407