178 - Shuffling Patience

paulhryu · Post by **paulhryu** » Sat Feb 16, 2002 3:59 am

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 · Post by **Caesum** » Thu May 16, 2002 8:26 pm

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 · Post by **Mart** » Wed Jun 12, 2002 8:51 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 · Post by **olestorm** » Thu Aug 01, 2002 8:55 pm

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 · Post by **Dominik Michniewski** » Mon Mar 24, 2003 9:05 am

I'm do it in the same way and I got WA too ....
Maybe someone tell us tricky inputs ?

Dominik

olestorm · Post by **olestorm** » Thu Apr 03, 2003 11:03 pm

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 · Post by **Dominik Michniewski** » Fri Apr 04, 2003 8:04 am

Yes, I'm still faced with WA on this problem

Could you tell me something special about it ?

Dominik

olestorm · Post by **olestorm** » Wed Apr 09, 2003 12:12 am

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.

Below are some test-problems with answers, which might help you.

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 · Post by **DataCompBoy** » Sat Aug 02, 2003 4:37 pm

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

UFP2161 · Post by **UFP2161** » Tue Aug 12, 2003 1:08 am

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 · Post by **UFP2161** » Wed Aug 13, 2003 1:42 am

[didn't mean to reply here.. woops]

sclo · Post by **sclo** » Mon Feb 06, 2006 12:25 pm

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 · Post by **sds1100** » Fri Mar 03, 2006 8:43 am

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

mars kaseijin · Post by **mars kaseijin** » Fri Apr 27, 2007 11:27 am

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 · Post by **Jan** » Sat Apr 28, 2007 10:17 pm

Search the board first. Don't open a new thread if there is one already.

OJ Board

178 - Shuffling Patience

178 error in description

178 - Shuffling Patience

Re: Problem 178 - Shuffling Patience

sorry i don't know your program..

178 Shuffling Patience need further explanation