## 178 - Shuffling Patience

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Sorry I post so much on here, but really I'm stuck on this one... see, I don't get the thing about assessed after each card, when a pair play is supposed to be indivisible: I did make a program where a pair was played such that it was reassessed for each time, but that came out wrong. Anyone help? Besides, this produces the right answer for the test case.

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 178 C++ */

// Send to judge@uva.es

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

int totals[16], nfilled;
int tops[16];
int cards[52];

int findcard(int n);

int main() {
char c, d;
int i, j;
int num = 0;

while(ins >> c) {
if(c == '#') break;
ins.putback(c);

for(i = 0; i < 52; i++) {
ins >> c >> d;

if(c == 'T')
cards = 10;
else if(c == 'J')
cards = 11;
else if(c == 'Q')
cards = 12;
else if(c == 'K')
cards = 13;
else if(c == 'A')
cards = 1;
else cards = c - '0';
}

nfilled = 0;

for(i = 0; i < 52; i++) {
for(j = 0; j < nfilled; j++) {
if(tops[j] < 11) {
int f = findcard(11 - tops[j]);

if(f >= 0) {
totals[j]++;
tops[j] = cards[i++];
if(i >= 52) break;
totals[f]++;
tops[f] = cards;
break;
}
} else {
int g, h;

if(tops[j] == 11)
g = findcard(12), h = findcard(13);
if(tops[j] == 12)
g = findcard(11), h = findcard(13);
if(tops[j] == 13)
g = findcard(11), h = findcard(12);

if(g >= 0 && h >= 0) {
totals[j]++;
tops[j] = cards[i++];
if(g < h) {
if(i >= 52) break;
totals[g]++;
tops[g] = cards[i++];

if(i >= 52) break;
totals[h]++;
tops[h] = cards;
} else {
if(i >= 52) break;
totals[h]++;
tops[h] = cards[i++];

if(i >= 52) break;
totals[g]++;
tops[g] = cards;
}

break;
}
}
}

if(i >= 52) break;

if(j >= nfilled) {
if(nfilled >= 16) break;
totals[nfilled] = 1;
tops[nfilled++] = cards;
}
}

outs << ++num << ":";

if(i >= 52) {
for(i = 0; i < nfilled; i++)
outs << setw(3) << totals[i];

outs << endl;
} else {
outs << " Overflowed on card no " << i++ << endl;
}
}

return 0;
}

int findcard(int n) {
int j;

for(j = 0; j < nfilled; j++)
if(tops[j] == n) return j;

return -1;
}

// @END_OF_SOURCE_CODE

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

### 178 error in description

it quite clearly says:
All numbers are to be right justified in a field 3 characters wide
and 'All' has been placed in bold for emphasis and yet when you do this you get PE. To get accepted without PE you need to not right justify the number that is printed in the line 'Overflowed on card no %d'

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
there is no space after the "no", so the description is correct
(format is "... card no%3d")

(that's not to say there wasn't a space there last month, but it's correct now at least...)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark

### 178 - Shuffling Patience

Hi all,

I have been trying to solve problem 178, but with no success. My program fails to give the right solution to the sample input given.

For the input:

TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

my program produces:

1: 8 10 5 1 6 4 6 2 2 4 4

instead of the required sample output:

1: 8 6 7 4 3 5 4 4 2 5 4

I have even tried to solve the problem by hand without reaching the result of the sample output.

It seems that I have misunderstood the rules of the game. The following phrase is central to solving the problem: "Cards are always covered in the same order they were dealt, that is left to right, top to bottom. The first card covered shall be the eligible card nearest the start of play. The second card covered (and also the third for a triple) is its partner nearest the start of play."
I interpret this sentence such that the pair or triplet to be covered is the pair/triplet occupying the 2 or 3 lowest indexed piles. I enumerate the piles of the game like this:

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Consequently I interpret "the start of the play" to be the pile with index 0.

If, with my understanding fo the problem, two pairs exists at positions (2,5) and (3,6) and a triplet at (0,10,11), I choose to cover the piles 0, 10 and 11 in this order. I do NOT consider covering triplets or pairs until the triplet has been covered.

Any idea as to where I am going wrong on this problem???

Kind regards,

Ole Storm.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I'm do it in the same way and I got WA too ....
Maybe someone tell us tricky inputs ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark
Hi Dominik.

Recently I managed to solve P178

If you still get WA I may be able to give you a hint of some kind.

Ole.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Yes, I'm still faced with WA on this problem
Could you tell me something special about it ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark
Hi Dominik,

I finally solved the problem when I relaized that my initial program (which solved the single test-problem OK) would fail on a deck of cards where the final card (card no 52) would be dealt as the first card on pile no. 16. My program would suggest an overflow on card no. 53, which obviously was not the case. When I corected this flaw I got accepted.

Regards,

Ole.

TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D

9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D

TS JS JS JS JS QS QS QS QS KS KS KS KS
AS AS AS AS 2S 2S 2S 2S 3S 3S 3S 3S 4S
4S 4S 4S 5S 5S 5S 5S 6S 6S 6S 6S 7S 7S
7S 7S 8S 8S 8S 8S 9S 9S 9S 9S TS TS TS

4S 4S 4S 5S 5S 5S 5S 6S 6S 6S 6S 7S 7S
TS JS JS JS JS QS QS QS QS KS KS KS KS
AS AS AS AS 2S 2S 2S 2S 3S 3S 3S 3S 4S
7S 7S 8S 8S 8S 8S 9S 9S 9S 9S TS TS TS

QH 2D 3H KH 9H TS QC 8S 8D 2H TH KS KC
2S QS TD 2C 4H 9D JH 7H JD 5H AD 4D 5D
7S JS 8H 3D 8C 6D 4S 9S 5S 3S 4C 6S 9C
KD JC 7D AC 5C AS 7C AH 6H TC QD 6C 3C

3C AS 7C AH 6H 5C TC QD 6C KD JC 7D AC
KC TS QC 8S 8D 9H 2H TH KS QH 2D 3H KH
5D 9D JH 7H JD 4H 5H AD 4D 2S QS TD 2C
9C 6D 4S 9S 5S 8C 3S 4C 6S 7S JS 8H 3D

9C 6D 4S 9S 5S 8C 3S 4C 6S 7S JS 8H 3D
KC TS QC 8S 8D 9H 2H TH KS QH 2D 3H KH
3C AS 7C AH 6H 5C TC QD 6C KD JC 7D AC
5D 9D JH 7H JD 4H 5H AD 4D 2S QS TD 2C
#

1: 8 6 7 4 3 5 4 4 2 5 4
2: 10 6 10 4 1 1 2 5 5 5 3
3: 13 5 7 2 3 1 5 2 3 3 1 2 1 4
4: 13 7 5 6 4 2 2 6 1 2 4
5: 10 4 7 7 5 2 5 4 6 2
6: 8 14 4 5 1 3 2 3 3 1 2 6
7: Overflowed on card no 31
8: 7 3 6 7 4 4 4 4 2 3 3 1 2 2
9: 12 4 5 2 3 5 2 3 2 3 3 2 2 1 3
10: 9 9 2 5 6 4 4 6 2 5
11: 9 9 6 6 3 5 5 2 3 2 2

DataCompBoy
New poster
Posts: 1
Joined: Sat Aug 02, 2003 4:31 pm
Location: Novosibirsk, Russia
Contact:

### Re: Problem 178 - Shuffling Patience

olestorm wrote: my program produces:
1: 8 10 5 1 6 4 6 2 2 4 4
ummm... Yep, my program produces this output too :(
Can you say, what move incorrect?

(card "1" is ace, ":" is ten)

Code: Select all

``````      0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: :S
:     1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: QC
:Q    1 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 8S
:Q8   1 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 8D
:Q88  1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: QH
:Q88  1 1 1 1
Q     1 0 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 2D
:Q88  1 1 1 1
Q2    1 1 0 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 3H
:Q88  1 1 1 1
Q23   1 1 1 0
0 0 0 0
0 0 0 0
Cards to: 2 6 -1
Card: KH
:QK8  1 1 2 1
Q23   1 1 1 0
0 0 0 0
0 0 0 0
Cards to: 6 -1 -1
Card: 9H
:QK8  1 1 2 1
Q29   1 1 2 0
0 0 0 0
0 0 0 0
Cards to: 1 2 4
Card: 2H
:2K8  1 2 2 1
Q29   1 1 2 0
0 0 0 0
0 0 0 0
Cards to: 2 4 -1
Card: :H
:2:8  1 2 3 1
Q29   1 1 2 0
0 0 0 0
0 0 0 0
Cards to: 4 -1 -1
Card: KS
:2:8  1 2 3 1
K29   2 1 2 0
0 0 0 0
0 0 0 0
Cards to: 1 6 -1
Card: KC
:K:8  1 3 3 1
K29   2 1 2 0
0 0 0 0
0 0 0 0
Cards to: 6 -1 -1
Card: 9D
:K:8  1 3 3 1
K29   2 1 3 0
0 0 0 0
0 0 0 0
Cards to: 5 6 -1
Card: JH
:K:8  1 3 3 1
KJ9   2 2 3 0
0 0 0 0
0 0 0 0
Cards to: 6 -1 -1
Card: 7H
:K:8  1 3 3 1
KJ7   2 2 4 0
0 0 0 0
0 0 0 0
Cards to: 1 4 5
Card: JD
:J:8  1 4 3 1
KJ7   2 2 4 0
0 0 0 0
0 0 0 0
Cards to: 4 5 -1
Card: 2S
:J:8  1 4 3 1
2J7   3 2 4 0
0 0 0 0
0 0 0 0
Cards to: 5 -1 -1
Card: QS
:J:8  1 4 3 1
2Q7   3 3 4 0
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: :D
:J:8  1 4 3 1
2Q7:  3 3 4 1
0 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 2C
:J:8  1 4 3 1
2Q7:  3 3 4 1
2     1 0 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 4H
:J:8  1 4 3 1
2Q7:  3 3 4 1
24    1 1 0 0
0 0 0 0
Cards to: 6 9 -1
Card: 5H
:J:8  1 4 3 1
2Q5:  3 3 5 1
24    1 1 0 0
0 0 0 0
Cards to: 9 -1 -1
Card: 1D
:J:8  1 4 3 1
2Q5:  3 3 5 1
21    1 2 0 0
0 0 0 0
Cards to: 0 9 -1
Card: 4D
4J:8  2 4 3 1
2Q5:  3 3 5 1
21    1 2 0 0
0 0 0 0
Cards to: 9 -1 -1
Card: 5D
4J:8  2 4 3 1
2Q5:  3 3 5 1
25    1 3 0 0
0 0 0 0
Cards to: -1 -1 -1
Card: 6D
4J:8  2 4 3 1
2Q5:  3 3 5 1
256   1 3 1 0
0 0 0 0
Cards to: 6 10 -1
Card: 4S
4J:8  2 4 3 1
2Q4:  3 3 6 1
256   1 3 1 0
0 0 0 0
Cards to: 10 -1 -1
Card: 9S
4J:8  2 4 3 1
2Q4:  3 3 6 1
259   1 3 2 0
0 0 0 0
Cards to: 4 10 -1
Card: 5S
4J:8  2 4 3 1
5Q4:  4 3 6 1
259   1 3 2 0
0 0 0 0
Cards to: 10 -1 -1
Card: 7S
4J:8  2 4 3 1
5Q4:  4 3 6 1
257   1 3 3 0
0 0 0 0
Cards to: 0 10 -1
Card: JS
JJ:8  3 4 3 1
5Q4:  4 3 6 1
257   1 3 3 0
0 0 0 0
Cards to: 10 -1 -1
Card: 8H
JJ:8  3 4 3 1
5Q4:  4 3 6 1
258   1 3 4 0
0 0 0 0
Cards to: 0 1 5
Card: 3D
3J:8  4 4 3 1
5Q4:  4 3 6 1
258   1 3 4 0
0 0 0 0
Cards to: 1 5 -1
Card: 8C
38:8  4 5 3 1
5Q4:  4 3 6 1
258   1 3 4 0
0 0 0 0
Cards to: 5 -1 -1
Card: 3S
38:8  4 5 3 1
534:  4 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 0 1 -1
Card: 4C
48:8  5 5 3 1
534:  4 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 1 -1 -1
Card: 6S
46:8  5 6 3 1
534:  4 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 1 4 -1
Card: 9C
49:8  5 7 3 1
534:  4 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 4 -1 -1
Card: 1S
49:8  5 7 3 1
134:  5 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 1 8 -1
Card: 7C
47:8  5 8 3 1
134:  5 4 6 1
258   1 3 4 0
0 0 0 0
Cards to: 8 -1 -1
Card: 1H
47:8  5 8 3 1
134:  5 4 6 1
158   2 3 4 0
0 0 0 0
Cards to: 0 1 -1
Card: 6H
67:8  6 8 3 1
134:  5 4 6 1
158   2 3 4 0
0 0 0 0
Cards to: 1 -1 -1
Card: KD
6K:8  6 9 3 1
134:  5 4 6 1
158   2 3 4 0
0 0 0 0
Cards to: 0 9 -1
Card: JC
JK:8  7 9 3 1
134:  5 4 6 1
158   2 3 4 0
0 0 0 0
Cards to: 9 -1 -1
Card: 7D
JK:8  7 9 3 1
134:  5 4 6 1
178   2 4 4 0
0 0 0 0
Cards to: 2 4 -1
Card: 1C
JK18  7 9 4 1
134:  5 4 6 1
178   2 4 4 0
0 0 0 0
Cards to: 4 -1 -1
Card: 5C
JK18  7 9 4 1
534:  6 4 6 1
178   2 4 4 0
0 0 0 0
Cards to: 2 7 -1
Card: :C
JK:8  7 9 5 1
534:  6 4 6 1
178   2 4 4 0
0 0 0 0
Cards to: 7 -1 -1
Card: QD
JK:8  7 9 5 1
534Q  6 4 6 2
178   2 4 4 0
0 0 0 0
Cards to: 0 1 7
Card: 6C
6K:8  8 9 5 1
534Q  6 4 6 2
178   2 4 4 0
0 0 0 0
Cards to: 1 7 -1
Card: 3C
1:  8 10  5  1  6  4  6  2  2  4  4
``````
suicide proc near\n call death\n suicide endp

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
First of all, it would probably be easier to debug if you printed the number of the top card, instead of size of the pile. But I think I found a problem:

Code: Select all

``````Card: 9H
:QK8  1 1 2 1
Q29   1 1 2 0
0 0 0 0
0 0 0 0
Cards to: 1 2 4``````
Now, after the previous move, the cards should be like so:

Code: Select all

``````T Q K 8
Q 2 9``````
Why does your code think the next sequence should be pile 1, pile 2, and pile 4? (which are currently, Q, K, 9 respectively -- the triple must have a jack, a queen, and a king, and since there are no jacks on the board, there can be no triple) ... The next cards should go onto pile 5 and 6 (the 2 and 9 which add up to 11) ... Hope this helps!

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
[didn't mean to reply here.. woops]

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
my program produces:
1: 8 10 5 1 6 4 6 2 2 4 4
If you get this as the output of the sample input, you probably misunderstood the condition for covering a triple. A triple of cards can be covered if they form the set {jack, queen, king}, in other words, all 3 face cards must be present.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

### sorry i don't know your program..

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

### 178 Shuffling Patience need further explanation

I am confused by the problem description of 7 cards dealt,
should not the 7th card cover the 4th card 8D <- 3H ?
before 3H gets played on a different pile all by itself?
8S + 3H is 11, so a covering should take place right above 8D. NO?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm