contoh soal simulasi acm-icpc

7/25/2019 Contoh Soal Simulasi ACM-ICPC

1/25

Three Lines [Brian Dean, 2012]

Farmer John wants to monitor his N cows (1 se%arate& inte!er i an& $i !i"in! the #ocation o cow i'

?87/L6 :N/;T

@1 A0 01 22 01 9

:N/;T D6T8:L?

There are @ cows, at %ositions (1,A), (0,0), (1,2), (2,0), (1,), an& (9,)'

;T/;T F478T

Line 1 /#ease ot%t 1 i it is %ossi-#e to monitor a## N cows with three cameras, or 0 i not'

?87/L6 ;T/;T

1

;T/;T D6T8:L?

The #ines $=0, =1, an& $= are each either hori.onta# or "ertica#, an&co##ecti"e#$ the$ contain a## N o the cow #ocations'


2/25

4Lay T3Xt 6En3Rat0rAnda diminta membuatkan sebuah program yang bernama, "ALAY TEXT

GENERATOR" dimana memudahkan orang-orang aay seperti anda untuk

memakainya!

Tet aay dihasikan meaui penggantian beberapa karakter men#adi angka, dan

menggunakan seed untuk menghasikan huru$ besar yang a%ak!

&erubahan karakter men#adi angka berdasarkan tabe diba'ah ini(

Karakter Angka

o )

i *

+

e

a .

s /

g 0

# 1

b 2

3 4

5edangkan huru$ besar dihasikan meaui seed-seed biangan, untuk tiap indeks-

i6muai dari *7 karakter 8a8!!8+8 diakukan perhitungan yaitu #ika pada i mempunyai

#umah keipatan seed-seed biangan gan#i maka karakter diganti men#adi huru$ besar,

#ika tidak maka huru$ tetap huru$ ke%i! 9ntuk karakter seain 8a8!!8+8, karakter tidak

dimanipulasi.

Spesifikasi Masukan

:asukan terdiri dari baris yaitu(

;aris pertama terdiri dari * buah biangan yaitu 6*


3/25

karakter 8a8!!8+8, titik6!7, koma6,7, dan spasi6 7!

&an#ang kata tidak meebihi )) karakter!

Spesifikasi Keluaran

5atu baris keuaran yaitu Tet Aay yang dihasikan!

!nt!" Masukan

9 A 19 2Cthe 3ic -rown o m%s o"er the #a.$ &o!'

!nt!" Keluaran

th9 C;1cE 40GN 0 A;m/5 0H94 tI9 L2$ &0@'

#en$elasan

>arakter 8a8!!8+8 yang diakukan perubahan upper ? o'er %ase hanya pada karakter

yang tidak bisa direpa%e dengan angka!

inde% karakter 3 & '3 () $umla" status

' t 0 genap

( " 0 genap

3 e @ ' gan$il4 0 genap

* + 0 genap

6 u @ ' gan$il

& i @ ' gan$il

, - 0 genap

) k @ ' gan$il

'0 0 genap

'' 0 genap

'( r @ ' gan$il'3 ! @ ' gan$il

'4 / @ ' gan$il

'* n @ ' gan$il

'6 0 genap

'& f 0 genap

', ! @ ' gan$il


4/25

') % 0 genap

(0 0 genap

(' $ @ @ ( genap

(( u 0 genap

(3 m 0 genap(4 p @ ' gan$il

(* s 0 genap

(6 @ ' gan$il

(& ! @ ' gan$il

(, @ ' gan$il

() e @ ' gan$il

30 r @ ' gan$il

3' 0 genap

3( t 0 genap33 " @ ' gan$il

34 e 0 genap

3* @ ' gan$il

36 l @ ' gan$il

3& a 0 genap

3, 1 0 genap

3) y @ @ ( genap

40 0 genap

4' d 0 genap

4( ! @ @ ( genap

43 g 0 genap

44 . 0 genap


5/25

Ba#ance& ow ?-sets [Nea# G, 2012]

Farmer John+s owns N cows (2


6/25

Booshe# [Nea# G Tra&itiona#, 2012]

Ghen Farmer John isn+t mi#in! cows, stacin! ha$-a#es, #inin! % his cows,or -i#&in! ences, he eno$s sittin! &own with a !oo& -oo' "er the$ears, he has co##ecte& N -oos (1 se%arate& inte!ers I(i) an& G(i)' (1


7/25

There are 9 she#"es, the irst containin! st -oo 1 (hei!ht 5, wi&th A),the secon& containin! -oos 2'' (hei!ht 19, wi&th C), an& the thir&containin! -oo 5 (hei!ht 9, wi&th )'


8/25

Booshe# [Nea# G Tra&itiona#, 2012]

Ghen Farmer John isn+t mi#in! cows, stacin! ha$-a#es, #inin! % his cows,or -i#&in! ences, he eno$s sittin! &own with a !oo& -oo' "er the$ears, he has co##ecte& N -oos (1 se%arate& inte!ers I(i) an& G(i)' (1


9/25

ows in a 4ow [Brian Dean, 2012]

Farmer John+s N cows (1


10/25

Doorsmeer

Pada suatu tempat cuci motor yang sederhana :)) pelanggan harus

dengan sabar menunggu karena motor hanya dapat dicuci satu per

satu

Motor yang kotor harus dicuci lebih lama dari motor yang lebih

bersih.

Pemilik Doorsmeer pusing untuk mengatur motor mana yg harus

dicuci terlebih dahulu agar total waktu yang ditunggu tiap

pelanggan seminimal mungkin.

Sebagai contoh terdapat 3 motor untuk dicuci

dengan lama waktu cuci 10 !0 30 menit.

penyusunan 10 !0 30 maka pelanggan 1 menunggu 10 menit

pelanggan " menunggu 10#!0 pelanggan 3 menunggu 10#!0#30.maka totalnya adalah $10)#$10#!0)#$10#!0#30) % 1!0 menit.

&ika penyusunan !0 10 30 maka total lama waktu adalah 1'0

menit.

(antulah pemiliknya untuk menghitung total lama waktu yang

ditunggu tiap pelanggan seminimal mungkin.

Input

(aris pertama berisi $1 *% *% "0000).(aris "..#1 berisi lama pencucian motor ke i $tidak lebih dari 300).

Output

+otal lama waktu yang ditunggu tiap pelanggan seminimal

mungkin.

Sample Input

!

10!0

"0

10


11/25

Sample Output

1,0

Problem setter: tiok-cek


12/25

6m%t$ ?ta##s [Brian Dean, 2019]

Farmer John+s new -arn consists o a h!e circ#e o N sta##s (2 1 -ein! a&acent to sta## 0'

8t the en& o each &a$, FJ+s cows arri"e -ac at the -arn one -$ one, eachwith a %reerre& sta## the$ wo#& #ie to occ%$' Iowe"er, i a cow+s%reerre& sta## is a#rea&$ occ%ie& -$ another cow, she scans orwar&se3entia##$ rom this sta## nti# she in&s the irst nocc%ie& sta##,which she then c#aims' : she scans %ast sta## N>1, she contines scannin!rom sta## 0'

Oi"en the %reerre& sta## o each cow, %#ease &etermine the sma##est in&eo a sta## that remains nocc%ie& ater a## the cows ha"e retrne& to the-arn' Notice that the answer to this 3estion &oes not &e%en& on the or&erin which the cows retrn to the -arn'

:n or&er to a"oi& isses with rea&in! h!e amonts o in%t, the in%t tothis %ro-#em is s%eciie& in a concise ormat sin! E #ines (1 se%arate& inte!ers N an& E'

Lines 2''1E 6ach #ine contains inte!ers P Q 8 B, inter%rete& as a-o"e' The tota# nm-er o cows s%eciie& -$ a## these #ines wi## -e at most N>1' ows can -e a&&e& to the same sta## -$ se"era# o these #ines'

?87/L6 :N/;T

10 99 2 2 2 1 0 11 1 1 A

:N/;T D6T8:L?

There are 10 sta##s in the -arn, nm-ere& 0''C' The secon& #ine o in%tstates that 9 cows %reer sta## (21) mo& 10 = @, an& 9 cows %reer sta##(22) mo& 10 = ' The thir& #ine states that 2 cows %reer sta## (011)mo& 10 = 1' Line or s%eciies that 1 cow %reers sta## (11A) mo& 10 = (so a tota# o cows %reer this sta##)'

;T/;T F478T


13/25

Line 1 The minimm in&e o an nocc%ie& sta##'

?87/L6 ;T/;T

5

;T/;T D6T8:L?

8## sta##s wi## en& % occ%ie& ece%t sta## 5'


14/25

Islands [Brian Dean, 2012]

Problem 3:

heneBer it rains, Carmer Dohn8s $ied a'ays ends up $ooding! o'eBer, sin%e the

$ied isn8t per$e%ty eBe, it $is up 'ith 'ater in a non-uni$orm $ashion, eaBing anumber o$ "isands" separated by epanses o$ 'ater!

CD8s $ied is des%ribed as a one-dimensiona ands%ape spe%i$ied by N 6*


15/25

29

:N/;T D6T8:L?

The sam%#e in%t matches the i!re a-o"e'

;T/;T F478T

Line 1 8 sin!#e inte!er !i"in! the maimm nm-er o is#an&s that a%%ear at an$ one %oint in time o"er the corse o the rainstorm'

?87/L6 ;T/;T (i#e is#an&s'ot)


16/25

#EA2A

&ada pea#aran matematika kai ini, &eter bea#ar menyederhanakan pe%ahan!

Fiberikan sebuah pe%ahan, &eter diminta untuk menyederhanakan pe%ahan ke bentukpaing sederhana! &eter merasa soa ini tidakah semudah yang dibayangkan, karena

mungkin sa#a gurunya men#ebaknya meaui soa-soa yang unik!

Spesifikasi masukan

:asukan terdiri dari beberapa kasus, input berhenti ketika End O$ Cie! Tiap kasus

terdiri dari satu baris yaitu berisi dua buah integer dipisah 88! Fi#amin bah'a masukan

adaah Baid 6tidak akan menimbukan error7!

Spesifikasi keluaran

>euaran berupa beberapa baris berupa pe%ahan paing sederhana!

N;( &astikan program anda bisa ber#aan pada kasus-kasus ekstrimH

!nt!" masukan

2

*/0

02

44*))////

!nt!" keluaran

.

*

.

44*))

*


17/25

*)/! A ay To Cind &rimes

Time Limit(*!) 5e%onds :emory Limit(0//0>

es-ripti!n

GiBen a integer p I *, i$ p %an be deBided ony by * and itse$, 'e say that p is a prime

number! Cor eampe, * %an ony be deBided by * and *, so * is a prime numberJ

* %an be deBided by si numbers( *, , , ., 0, *, so * is not a prime number! The

smaest ten prime number is , , /, 1, **, *, *1, *4, , 4!

Eratosthenes 'as a Greek mathemati%ian, astronomer, and geographer! e inBented a

method $or $inding prime numbers that is sti used today! This method is %aed

Eratosthenes85ieBe! A sieBe has hoes in it and is used to $iter out the #ui%e!Eratosthenes8s sieBe $iters out numbers to $ind the prime numbers!

Eratosthenes8s sieBe %an be used as $oo's to $ind a prime numbers smaer than or

e3ua to a giBen number n(

5tep* ( &ut a integers bet'een and n 6in%ude and n7 on Eratosthenes8s sieBe!

5tep ( 5ee%t the smaest number on the sieBe, suppose it is m, then m must be a

prime!

5tep ( Citer out a the integers 'hi%h %an be deBided by m $rom Eratosthenes8s

sieBe!

5tep. ( K$ m @ m


18/25

?e##ect the sma##est nm-er, it+s 5, so it is a#so a %rime' Then i#ter ota## inte!ers can -e &e"i&e& -$ 5

?ie"e A, 11, 19, 1A, 1C/rime -in 2, 9, 5

Becase 5 5 = 25 R 20, so a## nm-ers remains on 6ratosthenes+s sie"e are%rime, %t a## o them into %rime -in

?ie"e /rime -in 2, 9, 5, A, 11, 19, 1A, 1C

No' the task is, giBen a number k, output the k-th smaest prime number! 6You may

use any 'ay you 'ant to soBe this probem as it is %orre%t7

5nput

The $irst ine is an integer n, the number o$ test %ases, n %ases $oo's! Cor Ea%h test

%ase has an singe integer k 6k I *7!

utput

A singe integer per ine, the k-th prime number! Kt is guaranted that the %orre%t ans'er

is smaer than *)))))!

Sample 5nput

110

1001000

Sample utput

22C51AC1C

2int

K$ you 'ant to use an arge arrays, &ease de$ine them as goba Bariabes! Cor

eampe, i$ K 'ant to use an array named arrM(

Sinc#&e '''''''''

int arr[1000000]*


19/25

int main () ''''''M


20/25

4nnin! La%s [Brian Dean, 2012]

Bore& with horse racin!, Farmer John &eci&es to in"esti!ate the easi-i#it$o cow racin! as a s%ort' Ie sets % his N cows (1


21/25

Silap

&eter sedang bea#ar angka, gurunya FaBid sedang menga#arkan dia dengan %ara yang

unik! &ak FaBid menuiskan sebanyak n-* angka 6semua angka berbeda muai dari*!!n dengan a%ak7, au &eter disuruh untuk men%ari angka yang hiang dari kumpuan

angka *!!n! &eter muai bingung %ara men%arinya au dia meminta bantuan kaian

untuk membuatkan program pen%ari angka hiang!

Spesifikasi masukan

;aris pertama berisi integer 6*


22/25

Tied Down [Brian Dean, 2012]

As 'e a kno', ;essie the %o' ikes nothing more than %ausing mis%hie$ on the $arm!

To keep her $rom %ausing too mu%h troube, Carmer Dohn de%ides to tie ;essie do'n

to a $en%e 'ith a ong rope! hen Bie'ed $rom aboBe, the $en%e %onsists o$ N posts 6*

se%arate& an& $ coor&inates o ence %ost i'

Lines 2N''2N7 6ach o these 71 #ines contains, in se3ence, the s%ace>se%arate& an& $ coor&inates o a %oint a#on! the ro%e' The irst an& #ast %oints are a#wa$s the same as Bessie+s


23/25

#ocation (-, -$)'

?87/L6 :N/;T

2 10 @ 12 92 1@ 12 1 12 09 11 95 9 00 19 2@ 1

:N/;T D6T8:L?

There are two %osts at (2,9) an& (2,1)' Bessie is at (@,1)' The ro%e !oesrom (@,1) to (2,) to (1,1), an& so on, en&in! ina##$ at (@,1)' The sha%eo the ro%e is the same as in the i!re a-o"e'

;T/;T F478T

Line 1 The minimm nm-er o %osts that nee& to -e remo"e& in or&er or Bessie to esca%e -$ rnnin! to the ri!ht'

?87/L6 ;T/;T

1

;T/;T D6T8:L?

4emo"in! either %ost 1 or %ost 2 wi## a##ow Bessie to esca%e'


24/25

Unlocking Blocks (Silver) [Brian Dean, 2012]

A itte-kno'n $a%t about %o's is that they oBe pu++esH Cor ;essie8s birthday, Carmer

Dohn giBes her an interesting me%hani%a pu++e $or her to soBe! The pu++e %onsists

o$ three soid ob#e%ts, ea%h o$ 'hi%h is buit $rom ** unit s3uares gued together!

Ea%h o$ these ob#e%ts is a "%onne%ted" shape, in the sense that you %an get $rom one

s3uare on the ob#e%t to any other s3uare on the ob#e%t by stepping north, south, east, or

'est, through s3uares on the ob#e%t!

An ob#e%t %an be moBed by repeatedy siding it either north, south, east, or 'est one

unit! The goa o$ the pu++e is to moBe the ob#e%ts so that they are separated -- 'here

their bounding boes no onger share any positiBe oBerap 'ith ea%h-other! GiBen the

shapes and o%ations o$ the three ob#e%ts, your task is to hep ;essie de%ide 'hat is the

minimum number o$ indiBidua sides re3uired to separate the ob#e%ts!

/4BL67 N876 n#oc

:N/;T F478T

Line 1 Three s%ace>se%arate& inte!ers N1, N2, an& N9, &escri-in! res%ecti"e#$ the nm-er o nit s3ares main! % o-ects 1, 2, an& 9'

Lines 2''1N1 6ach o these #ines &escri-es the (,$) #ocation o the soth>west corner o sin!#e s3are that is %art o o-ect 1' 8## coor&inates #ie in the ran!e 0''C'

Lines 2N1''1N1N2 6ach o these #ines &escri-es the (,$) #ocation o the soth>west corner o sin!#e s3are that is %art o o-ect 2' 8## coor&inates #ie in the ran!e 0''C'

Lines 2N1N2''1N1N2N9 6ach o these #ines &escri-es the (,$) #ocation o the soth>west corner o sin!#e s3are that is

%art o o-ect 9' 8## coor&inates #ie in the ran!e 0''C'

?87/L6 :N/;T

12 9 50 01 02 09 0


25/25

9 10 10 20 90 1 2 9 2 12 21 22 99 9 9 2

:N/;T D6T8:L?

-ect 1 is ma&e rom 12 s3ares, o-ect 2 is ma&e rom 9 s3ares, an&

o-ect 9 is ma&e rom 5 s3ares' The sha%es o the o-ects are those inthe i!re a-o"e'

;T/;T F478T

Line 1 The minimm nm-er o mo"es necessar$ to se%arate the threeo-ects, or >1 i the o-ects cannot -e se%arate&'

?87/L6 ;T/;T

5

;T/;T D6T8:L?

: we s#i&e o-ect 9 to the east -$ one %osition, then s#i&e o-ect 2north -$ one %osition, then s#i&e o-ect 1 west -$ three %ositions,then the -on&in! -oes o the three o-ects wi## no #on!er share an$o"er#a% in common'

contoh soal simulasi acm-icpc

Documents